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

Question

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

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

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

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

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

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

Answer 1

合相的最低BDD：

BDD是使用此在线工具创建的。

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