logic - 转换为 XOR 合取形式

Question

XOR 合取形式定义如下：(a XOR b) and (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、(a XOR b) 和 (a XOR !b)。如果你与其中任何一个：false、true、a、b、!a、!b、(a XOR b)、(a XOR !b)，你将设置为 false 的 4 种可能组合之一 (a,乙）。这仅留下表达式为真，这与 (a OR b) 不同。

Answer 2

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

A|B=A^B^AB

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