algorithm - 使用 AND 和 OR 转换逻辑条件

Question

我有一个复杂的条件，带有 AND 和 OR，例如： (c1 OR c2) AND (c3 OR c4 OR c5)

这相当于：

(c1 AND c3) OR (c1 AND c4) OR (c1 AND c5) OR (c2 AND c3) OR (c2 AND c4) OR (c2 AND c5)

然后可以将该条件分解为仅包含 AND 的条件列表：

c1 AND c3
c1 AND c4
c1 AND c5
c2 AND c3
c2 AND c4
c2 AND c5

这种转变总是可能的吗？什么算法可以做到？

条件以树的形式存储在内存中，例如：

    OR
   /  \
  AND c1
 / ! \
c2 c3 c4

我认为我们应该尝试通过使用分布将 OR 向上“移动”：

(a OR b) AND c = (a AND c) OR (b AND c).

这是一个好方法吗？

score 2 · Accepted Answer

看看析取范式（或合取范式）。但他们都不仅使用AND而且OR也使用NOT。

注意：如果我们只受ORs 和ANDs 的限制（并且不能使用任何其他布尔函数），那么由于Post 的功能完备性定理，我们甚至不能表达任何布尔函数（AND并且OR都保真并且不形成基础）。因此，也许有一个公式，无法转换。

score 0 · Accepted Answer

(a or b) and c逻辑上等价于(a and c) or (b and c)。但是，在支持短路布尔表达式的语言中，我可能最终会写成 as c and (a or b)，因为没有必要评估(a or b)if 是否c为假。

如果其中一个a或b都是昂贵的函数调用而不仅仅是变量引用，则尤其如此。

2 回答 2