2SATを使用して、満足できるものではない場合は、暗黙のグラフがサイクルを持っている必要があることを示しています。

Question

2SATおよび含意グラフを使用すると、その意味グラフの次のプロパティをどのように証明できるか：

は、g_φのリテラルL1とL2の間に向けられた経路があるとします。それから彼らの補完の間に向けられた道もあります。次に、τ（L1）が真の場合、τを満たす真理的割り当て、τ（L2）も真実でなければならない。

これを使用して、φが満足できる<=>変数Xとその補数を含むG_φにいくつかの有向サイクルがあることを示しています。

ここで、G_φは、n変数を有する式φを含む2SATの有向含差グラフである。したがって、φ内のすべての可能なリテラルに対して1つの頂点、およびφ内のすべての節（L1、L2）および（L2、L1）。

私の最初の直感は矛盾することによって証明でしたが、私は一般的な十分な仮定を構築することに失敗しました。その後、Truth AssignmentがL1とL2が真のことを意味する場合は、すべての変数を接続するサイクルを構築することで、割り当てはそれらのエッジが存在する場合にのみ有効です。しかし、このサイクルがXの補数が存在するのを必要とする理由が正しく理解されているので、これは十分に厳しくないようです。

現在、変数xごとに頂点を追加することでgを構築し、それも補完します。次に各句（A V B）では、AとBとの間にエッジを追加してください。

しかし、これがどのようにサイクルをどのように形成するかを確認しません。

Sipser教科書の働き

Answer 1

これは証明スケッチです。与えられた式が不満足なIFFが不満足な場合、 $ x $ 、 $ \ lnot x $ < / span>、ある変数 $ x $ 。

最初に $ x $ 、 $ \ l not x $ の両方を含むサイクルが存在するとします。影響グラフ内のパス $ x \ to ^ * y $ の存在は、 $の場合X $ は、 $ y $ になります（パスの長さの誘導によって証明できます）。 $ x $ と $ \ lnot x $ の両方を含むサイクルがあるので、パスがあります。 class="math-container"> $ x \ to ^ * \ lnot x $ と $ \ lnot x \ to ^ * x $ 。任意の満足のいく割り当てでは、 $ x $ または $ \ lnot x $ のどちらかの場合、矛盾

次に、 $ x $ と $ \ lnot x $ の両方を含むサイクルがないことを仮定します。次のように満足のいく割当を構築します。いくつかの変数 $ x $ を選択してください。パス $ x \ x ^ * x \ $ x $ の場合、 $ x= f $ を割り当てます。 、および各リテラル $ \ eell $ の場合、 $ \ lnot x \ to ^ * \ etell $ $ \ etell $ trueにする基に値を割り当てます。 $ \ lnot x \ to ^ * y $ と $から、同じ変数2つの異なる真理値を割り当てることはできません。 \ lnot x \ ^ * \ lnot y $ また、 $ y \ to ^ * x $ x $ x $ などの $ \ lnot x \ ^ * x $ 、 $ x $ 、 $を含むサイクルを完了します。 \ lnot x $ 。

パス $ \ lnot x \ ^ * x $ の場合、 $ x= t $ < / SPAN>、そして同様に続けます。

これらのパスが存在しない場合は、 $ x $ を任意に割り当て、以前と同じように続行します。これは矛盾につながることはできません。なぜなら、次の理由で矛盾することはできません。 $ x= f $ $ を割り当て、パスがあると仮定し、 $ x \ to ^ * ^ * y $ と $ x \ to ^ * \ lnot y $ 。その後、パス $ y \ to ^ * \ lnot x $ など、パス $ x \ to ^ * \ lnot x $ 、2つのパスのどれも存在しないという仮定に矛盾します。

このプロセスの後に未割り当て変数が残っている場合は、それらの1つを選択し、割り当てがすべての変数をカバーするまで繰り返します。