boolean-logic - 3SATに入れられないブール代数式はありますか?

Question

これは私には明らかなように思えますが、そうではありませんが、特別なケースを残している可能性があります。私が見ているように、1SAT (節ごとに 1 つのリテラルのみ) と 2SAT は簡単に 3SAT に変換できます。3 リテラルを超える any 句は、3SAT に変換できることが証明されています。したがって、次のような質問をする必要があります: すべてのブール代数を SAT に入れることができますか? それとも、これらの演算子だけでブール代数を定義できますか? AND OR および NOT

Answer 1

いいえ、ありません。

完全な証明はしませんが、主な考え方は次のとおりです。与えられた式を通常の形式、つまり論理和の論理積で書きます。式の変数の数に帰納法を使用します。n+1 個の変数を持つ最長の部分式を選択し、部分式の一部に新しい変数を導入して n 個の変数の式を残し、新しい変数の制約を式に追加し、式を得るために必要な回数だけ手順を繰り返しますここで、最長の部分式には n 個の変数があります。