转换为XOR联合形式

Question

XOR联合形式定义如下：（XOR b）和（c XOR d）......等

SAT-XCF是可以满足的先例（XOR联合）表达式定义的语言。

我想知道SAT-XCF是NP难吗？因此，是否有一个函数能够将任何可满足的布尔表达式转换为可满足的XOR连接形式？

非常感谢您的贡献。

Answer 1

我认为你的上一个问题的答案是“不”，即使对于2个变量也是如此。具体而言，（a OR b）不能表示为任何数量的XOR表达式的AND。在最多2个变量中，很少有不同的XOR表达式：false，true，a，b，！a，！b，（一个XOR b）和（一个XOR！b）。如果你和以下任何一个：假，真，a，b，！a，！b，（一个XOR b），（一个异或！）你将设置为假的一个可能的组合之一（a， b）。这只留下表达式为真，这与（a OR b）不同。

Answer 2

是的，你可以并且有一个有效的算法。你遵循正常的代数规则模2。关于以前的评论：

A|B=A^B^AB

这种形式称为代数正规形式https://en.wikipedia.org/wiki/Algebraic_normal_form