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

Question

• 表达式 1：（A 和 B 或（非 C））

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

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

该变换基于德摩根定律。

这是我的问题：

是否有 C/C++ 库实现此功能？我不太了解 C/C++ 库。我搜索了GMP和http://mathworld.wolfram.com/，但没有找到解决方案。

谢谢！

Answer 1

当您递归地考虑它时，规则很简单：

• not (X and Y)==>(not X) or (not Y)
• not (X or Y)==>(not X) and (not 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); }
};

和操作的negation代码只是应用德摩根定律，从而将否定“推”到树下andor

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++ 中表示表达式树。仅仅拥有一个库来实现 De Morgan 的变换是没有意义的，因为一旦你有了表示，它就绝对是微不足道的。

一个能够使用不同树表示的包装器的实现将是 99% 的样板代码和接口代码来实现一个两行代码（完全是胡说八道）。

只需使用您拥有的任何树表示直接实现它。