轉換爲XOR合取形式

Question

異或結膜的形式被定義爲如下：（a XOR b）和（C XOR d）...等

和SAT-XCF是由先例定義的語言（XOR連詞）表達式是可以滿足的。

我想知道SAT-XCF是NP很難嗎？因此，是否有一個函數能夠將任何可滿足的布爾表達式轉換爲可滿足的XOR連接形式？

非常感謝您的貢獻。

Answer 1

我認爲即使對於2個變量，您最後一個問題的答案也是「否」。具體而言，（a或b）不能被表示爲任何數量的XOR表達式的AND。在最多2個變量中有很少不同的XOR表達式：假，真，a，b，！a，！b，（a XOR b）和（異或！b）。如果你和以下任何一個：假，真，a，b，！a，！b，（a XOR b），（a XOR！b），你將設置爲false（a， b）。這隻允許表達式爲真，這與（a或b）不同。