Utilizzare 2SAT per dimostrare che un grafico di implicazione deve avere un ciclo se non è soddisfacente

Question

Usando grafici 2sat e implicazioni, come potrei provare le seguenti proprietà dei grafici di implicazione:

Supponiamo che vi sia un percorso diretto tra i letterali L1 e L2 in G_φ. Poi c'è anche un percorso diretto tra i loro complementi. Quindi, c'è τ, un incarico di verità che soddisfa φ dove τ (L1) è vero, quindi τ (L2) deve anche essere vero.

Usando questo, mostra che φ è insoddisfacanza <=> c'è un ciclo diretto in g_φ contenente una variabile X e il suo complemento.

Dove G_φ è il grafico di implicazione diretto di 2sat contenente formula φ con N Variabili. Quindi 2N vertici con uno per ogni possibile letterale in φ e bordi (non L1, L2) e (non L2, L1) per ogni clausola (L1 ∨ l2) in φ.

La mia prima intuizione è stata una prova per contraddizione, ma non sono riuscita a costruire un'ipotesi abbastanza generale. Ho quindi cercato di dimostrare che se l'assegnazione della verità significa che L1 e L2 sono true, quindi costruendo un ciclo che collega tutte le variabili, l'assegnazione è valida solo quando esistono tali bordi. Tuttavia questo non sembra abbastanza rigoroso poiché non capisco correttamente perché il ciclo richiede il complemento di x esistere.

Attualmente creo g aggiungendo un vertice per ogni variabile X ed è anche il complemento. Quindi per ogni clausola (A V B) aggiungo un vantaggio tra non A e B e non B e A.

Comunque non riesco a vedere come questo formerà specificamente un ciclo.

Lavorando del libro di testo SIPSER.

Answer 1

Ecco uno schizzo a prova. Mostreremo che la formula data è insoddisfacida se esiste un ciclo contenente sia $ x $ e $ \ lnot x $ < / span>, per qualche variabile $ x $ .

Supponiamo che prima che esista un ciclo contenente sia $ x $ e $ \ lnot x $ . L'esistenza di un percorso $ x \ a ^ * y $ Nel grafico di implicazione significa che in un compito soddisfacente, se $ x $ Tiene quindi così $ y $ (puoi dimostrarlo per induzione sulla lunghezza del percorso). Dal momento che c'è un ciclo contenente sia $ x $ e $ \ lnot x $ , ci sono percorsi $ x \ a ^ * \ lnot x $ e $ \ lnot x \ to ^ * x $ . In qualsiasi assegnazione soddisfacente, o $ x $ o $ \ lnot x $ contiene entrambi i casi contraddizione.

Supponiamo che non ci siano cicli contenenti sia $ x $ e $ \ lnot x $ . Costruiremo un incarico soddisfacente come segue. Scegli alcune variabili $ x $ . Se c'è un percorso $ x \ a ^ * \ lnot x $ , assegna $ x= f $ e per ogni letterale $ \ ell $ tale che $ \ lnot x \ to ^ * \ ell $ , Assegna il valore alla variabile sottostante che rende $ \ ell $ true. Non è possibile assegnare la stessa variabile due valori di verità diversi, poiché se $ \ lnot x \ to ^ * y $ e $ \ lnot x \ to ^ * \ lnot y $ quindi anche $ y ^ a ^ * x $ e così anche $ \ lnot x \ to ^ * x $ , completando un ciclo che coinvolge $ x $ e $ \ lnot x $ .

Se c'è un percorso $ \ lnot x \ to ^ * x $ , assegnare $ x= T $ < / span> e continuare analogamente.

Se non esistono nessuno di questi percorsi, assegnare $ x $ arbitrariamente e continuare come prima. Questo non può portare a una contraddizione, per il seguente motivo. Supponiamo di assegnare $ x= f $ e che ci sono percorsi $ x \ to ^ * y $ e $ x \ a ^ * \ lnot y $ . Poi c'è anche un percorso $ y ^ to ^ * \ lnot x $ e così un percorso $ x \ a ^ * \ lnot x $ , contraddicando il presupposto che nessuno dei due percorsi esiste.

Se dopo questo processo vi è una variabile non assegnata a sinistra, sceglierne uno e ripetere fino a quando l'assegnazione copre tutte le variabili.