boolean-logic - 是否有任何布尔代数表达式不能放入 3SAT 中？

Question

这在我看来很明显，没有，但我可能会留下一个特殊情况。正如我所看到的，1SAT（每个子句只有一个文字）和 2SAT 可以很容易地转换为 3SAT。超过 3 literas 的 any 子句已被证明可以转化为 3SAT。所以也许应该问这个问题：所有布尔代数都可以放入SAT吗？或者我们可以用这些运算符定义布尔代数吗？AND OR 和 NOT

Answer 1

不，那里没有。

我不会给出完整的证明，但这里是主要思想：以正常形式写给定的公式，即析取的合取。对表达式的变量数使用归纳法。选择具有 n+1 个变量的最长子表达式，为子表达式的某些部分引入一个新变量以留下 n 个变量的表达式，将新变量的约束添加到公式中，根据需要重复该过程多次以获得公式其中最长的子表达式有 n 个变量。