algorithm - 合取/析取范式可以用二叉树表示吗？

Question

我能找到这个相关问题 Distributing AND over OR in a binary tree (Conjunctive Normal Form)

我不太确定 this 表达式的 CNF 二叉树表示的结果是什么。A&B&C

AND
|- A
|- AND
   |-B
   |-C

这样对吗？我的基本问题是 CNF 二进制表示是否可以在树中有多个 AND 节点，而不是只有一个 AND 节点作为根节点。我的理解是，只要其父节点是 AND 节点，我们就可以拥有非根 AND 节点。

相关问题是？这种表示是最优的吗？或者用只有一个根 AND 节点的 n-nary 树表示它们是有益的？我在这里看到的最优性是树的构建和遍历。

//根据评论进行编辑。为了简单起见，假设 not (~) 运算符是叶节点 A、B 或 C 的一部分。这意味着您需要担心 ~ 运算符是非叶节点的一部分根据 Demorgan 定律扩展时可能会改变树结构。

Answer 1

最小 BDD对于你的结合:

BDD是使用这个 online tool 创建的.

对于具有三个输入的简单 AND，没有什么需要优化的。 BDD节点构建链。