c++ - 使用 C/C++ 实现德摩根定律

Question

• 表达式 1:(A 和 B 或(非 C))

• 表达式 2:not((not A) or (not B) and C)

我想将表达式 2 更改为表达式 1。所以表达式可以表示为一棵树，如下图所示。这意味着“非”操作只能存在于叶节点中。

变换基于De Morgan's Law .

这是我的问题:

有没有C/C++库实现这个功能？我对 C/C++ 库了解不多。我搜索了GMP和 http://mathworld.wolfram.com/但没有找到解决办法。

谢谢!

Answer 1

当你递归地思考它时，规则很简单:

• 不是(X 和 Y) ==> (不是 X)或(不是 Y)
• 不是(X 或 Y) ==> (不是 X)和(不是 Y)

所以在 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); }
};

and 和 or 运算的否定代码简单地应用了德摩根定律，从而将否定“推”到了树上

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

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

否定的否定代替了省略简化

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

只有叶节点实际上包含在否定操作中

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

正如你所见，摩根定律只有两行，其他的都是如何在 C++ 中表示表达式树。拥有一个库来实现德摩根变换是没有意义的，因为一旦有了表示，它就绝对微不足道了。

一个能够使用不同树表示的包装器的实现将是 99% 的样板文件和接口(interface)代码来实现两行代码(完全是废话)。

只需使用您拥有的任何树表示形式直接实现即可。