de morgan's law implemention using C/C++

Question

• expression 1: (A and B or (not C))

• expression 2: not((not A) or (not B) and C)

I want to change the expression 2 to expression1. So the expression can be expressed as a tree like the picture below. That means "not" operation can only exist in leaf node.

The transform is based on De Morgan's Law.

And here is my question:

Is there a C/C++ library implement this function? I don't know much about C/C++ library. I searched GMP and http://mathworld.wolfram.com/ but didn't find the solution.

Thank you!

Answer 1

The rule is simple when you think about it recursively:

• not (X and Y) ==> (not X) or (not Y)
• not (X or Y) ==> (not X) and (not Y)

so in C++:

struct Node {
    virtual ~Node() {};
    virtual Node *copy() = 0;
    virtual Node *negation() = 0;

private:
    // Taboo
    Node(const Node&);
    Node& operator=(const Node&);
};

struct AndNode : Node {
    Node *left, *right;
    AndNode(Node *left, Node *right) : left(left), right(right) {}
    ~AndNode() { delete left; delete right; }
    Node *copy() { return new AndNode(left->copy(), right->copy()); }
    Node *negation();
};

struct OrNode : Node {
    Node *left, *right;
    OrNode(Node *left, Node *right) : left(left), right(right) {}
    ~OrNode() { delete left; delete right; }
    Node *copy() { return new OrNode(left->copy(), right->copy()); }
    Node *negation();
};

struct NotNode : Node {
    Node *x;
    NotNode(Node *x) : x(x) {}
    ~NotNode() { delete x; }
    Node *copy() { return new NotNode(x->copy()); }
    Node *negation();
};

struct VarNode : Node {
    std::string var;
    VarNode(const std::string& var) : var(var) {}
    Node *copy() { return new VarNode(var); }
};

The negation code for and and or operations simply applies De Morgan's law thus "pushing" the negation down the tree

Node *AndNode::negation() {
    return new OrNode(left->negation(), right->negation());
}

Node *OrNode::negation() {
    return new AndNode(left->negation(), right->negation());
}

The negation of a negation instead does the elision simplification

Node *NotNode::negation() {
    return x->copy();
}

Only a leaf node gets actually wrapped in a negation operation

Node *VarNode::negation() {
    return new NotNode(this->copy());
}

As you see the Morgan's law is just two lines, everything else is how to represent an expression tree in C++. It doesn't make sense to have a library to implement De Morgan's transform only because once you have the representation it's absolutely trivial.

An implementation with wrappers to be able to work with different tree representations would be 99% boilerplate and interface code to implement a two-liner (a total nonsense).

Just implement it directly with whatever tree representation you have.