是否存在不能放入 3SAT 的布尔代数表达式？
在我看来，这似乎很明显，没有，但我可能会留下一个特殊情况。 在我看来，1SAT（每个子句只有一个文字）和 2SAT 可以轻松转换为 3SAT。 任何超过3升的子句都被证明可以转化为3SAT。 所以也许这个问题应该这样问： 所有布尔代数都可以考SAT吗？或者 我们可以只用这些运算符来定义布尔代数吗？与或与非
This seems to me pretty obvious, There is not but I might be leaving a special case.
As I see it 1SAT (only one literal per clause) and 2SAT can be easily transformed into 3SAT.
An any clause with more than 3 literas has been proven it can be transformed into 3SAT.
So maybe the question should be asked as:
Do all boolean algebra can be put into SAT? or
can we define boolean algebra with ony these operators? AND OR and NOT
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
不，没有。
我不会给出完整的证明，但主要思想是：以正常形式（即析取的合取）编写给定的公式。对表达式中的变量数量使用归纳法。选择具有 n+1 个变量的最长子表达式，为子表达式的某些部分引入一个新变量以留下 n 个变量的表达式，将新变量的约束添加到公式中，根据需要重复该过程多次以获得公式其中最长的子表达式有 n 个变量。
No, there is not.
I will not give the full proof but here is the main idea: Write the given formula in a normal form i.e. conjunction of disjunctions. Use induction on the number of variables on an expression. Pick the longest subexpression with n+1 variables, introduce a new variable for some part of subexpression to leave an expression of n variables, add the constraints for the new variable to the formula, repeat the procedure as many times as needed to have a formula where the longest subexpression has n variables.