L'equivalenza delle formule di KROM è tracciabile?

Question

Assumi che ho due formule Krom $ \ psi_1, \PSI_2 $ .Le formule KROM sono formule proposizionali in CNF che hanno 2 letterali in ogni clausola.Ogni letterale può essere annullato o non andato.In altre parole, $ \ psi_1, \ psi_2 $ sono formule 2-cnf.Ad esempio:

$ (x_1 \ vee \ neg x_2) \ Land (\ neg x_2 \ vee x_3) \ Land (x_3 \ vee x_4) $

Voglio decidere se $ \ psi_1, \ psi_2 $ sono logicamente equivalenti, cioè $ \ psi_1 \ leftrigrow\ psi_2 $ .Equivalentemente, voglio verificare se $ f= (\ psi_1 \ vee \ neg \ psi_2) \ wedge (\ neg \ psi_1 \ vee \ psi_2) $ è vero perTutte le assegnazioni di $ X_1, \ Dots, X_N $ .

Questo problema è trattato?

Answer 1

Sì, l'equivalenza può essere controllata in tempo polinomiale (infatti, in termini quadratici).

Descriverò come verificare se $ \ psi_1 \ lor \ neg \ psi_2 $ è vero per tutte le assegnazioni. Puoi fare lo stesso per $ \ neg \ psi_1 \ lor \ psi_2 $ e usa questo per verificare se $ f $ è una tautologia, cioè, sia che $ \ psi_1, \ psi_2 $ sono logicamente equivalenti.

Lo farò controllando se $ \ psi_1 \ lor \ neg \ psi_2 $ è falso per qualsiasi assegnazione, o in altre parole, sia < "Math-Container"> $ \ neg (\ psi_1 \ lor \ neg \ psi_2) $ è soddisfacente. Si noti che

$$ \ neg (\ psi_1 \ lor \ neg \ psi_2)=neg \ psi_1 \ Land \ psi_2, $$

Quindi è sufficiente per testare la soddisfabilità di $ \ neg \ psi_1 \ Land \ psi_2 $ dove $ \ psi_1, \ PSI_2 $ Formule Krom (2-CNF).

Supponiamo che $ \ PSI_1= c_1 \ Land \ cdots \ Land c_k $ dove $ c_i $ è la $ i $ Clausola in $ \ psi_1 $ . Quindi

$$ \ neg \ psi_1= (\ neg c_1) \ lor \ cdots \ lor (\ neg c_k). $$

quindi

$$ \ Begin {allinea *} \ Neg \ psi_1 \ Land \ psi_2 &= (\ neg c_1) \ lor \ cdots \ lor (\ neg c_k)) \ Land \ psi_2 \\ &= (\ neg c_1 \ Land \ psi_2) \ lor \ cdots \ lor (\ neg c_k \ Land \ psi_2). \ end {allinea *} $$

ora, $ \ neg \ psi_1 \ Land \ psi_2 $ è soddisfavole IFF $ \ neg c_i \ Land \ psi_2 $ è soddisfacente per alcuni $ i $ . Quindi, possiamo isolare su $ I $ e prova la soddisfattiva di ogni $ \ neg c_i \ Land \ psi_2 $ ; Se uno di essi è soddisfavole, allora $ \ neg \ psi_1 \ lor \ psi_2 $ è soddisfavole e $ f $ non è una tautologia e $ \ psi_1, \ psi_2 $ non sono logicamente equivalenti.

Come testare la soddisfazione della $ \ neg c_i \ Land \ psi_2 $ ? Bene, $ c_i $ ha il modulo $ (\ ell_1 \ lor \ ell_2) $ dove $ \ ell_1, \ ell_2 $ sono due letterali, quindi $ \ neg c_i \ Land \ psi_2 $ ha il modulo < Span Class="Math-Container"> $ \ Neg \ ell_1 \ Land \ neg \ ell_2 \ Land \ psi_2 $ . Questa è anche una formula KROM (2-CNF), quindi puoi testare la sua soddisfazione utilizzando l'algoritmo standard polinomiale. Si esegue un numero lineare di tali test, quindi il tempo di esecuzione totale è polinomiale. Infatti, è quadratico, poiché il test di prova può essere fatto in tempo lineare.

Answer 2

Richiamo Soluzione a 2 satelliti che utilizza componenti fortemente collegati: Costruiamo un grafico con i vertici $ x_1, \ Ldots, x_n, \ lnot x_1, \ ldots, \ lnot x_n $ < / span>, e sostituiamo ogni clausola $ x_i \ lor x_j $ con bordi $ \ lnot x_i \ to x_j $ < / span> e $ \ lnot x_j \ a x_i $ . Un esempio da qui :

Per soddisfare la formula, è necessario e sufficiente assegnare i vertici in modo che non ci siano contraddizioni nel grafico (senza bordo $ true \ to false $ ). Utilizzeremo questi grafici per il controllo dell'equivalenza.

.
1. Costruiamo questi grafici $ G_1 $ e $ G_2 $ per entrambe le formule $ f_1 $ e $ f_2 $ .
2. Se c'è un ciclo $ x_i \ leadsto \ lnot x_i \ leadsto x_i $ in un grafico, quindi la sua formula non ha soluzioni. Controlliamo che entrambe le formule siano solvibili / irravidabili.
3. Se esiste un percorso di forma $ x_i \ leadsto \ lnot x_i $ (analogamente per il caso $ \ lnot x_i \ leadsto x_i $ ), sappiamo che per soddisfare la formula dobbiamo selezionare $ x_i $ per essere falso (altrimenti abbiamo una contraddizione). Ricordiamo questa scelta. Usando il grafico, possiamo assegnare valori a tutti i vertici raggiungibili da $ \ lnot x_i $ (devono essere veritieri). Di nuovo, verificare che entrambe le formule fecero esattamente le stesse decisioni alla fine.
4. Rimuovere tutti i bordi da / da tutti i vertici noti dai grafici.
5. ora, $ f_1 $ e $ f_2 $ sono equivalenti $ \ IFF $ I grafici rimanenti sono equivalenti nel senso seguente: per qualsiasi classe $ V_1, V_2 $ percorso $ v_1 \ leadsto v_2 $ esiste in $ G_1 $ IFFS esiste in $ G_2 $ . Questo può essere controllato alla maggior parte dei $ o (| v | \ clot | e |) $ tempo (basta eseguire DFS da ciascun vertice e verificare che abbia visitato lo stesso vertici per entrambi i grafici). Forse può essere fatto più velocemente.

Proof :

$ \ Levingarrow $ : evidente, poiché dopo la chiusura transitiva dei grafici avremo le stesse implicazioni in entrambe le formule.

$ \ raggi $ : per contraddizione. Wlog supponiamo che esista un percorso $ v_1 \ leadsto v_2 $ in $ g_1 $ che no Esistono in $ G_2 $ . Significa che l'assegnazione $ V_1:= Vero $ , $ v_2:= false $ è fattibile in $ f_2 $ (dal momento che non c'è percorso $ v_1 \ leadsto v_2 $ ) ma è infastibile in $ f_1 $ .

Vale a dire, il seguente assegno soddisfa $ f_2 $ :

.
• $ TRUE $ Per tutti i vertici raggiungibili da $ v_1 $ .
• $ false $ da tutti i vertici che possono raggiungere $ v_2 $ .
• Rimuovere tutti i vertici noti (menzionati sopra e i loro complementi) dal grafico. Tutti i vertici rimanenti creano componenti collegati. Colouriamo componenti collegati in $ Vero $ e componenti collegati corrispondenti ai loro complementi - in $ false $ ( Vedi Nota sotto).

Questo incarico non ha contraddizione, poiché non può esserci alcuna classe $ u \ a V $ del modulo $ true a false $ :

.
• Se $ U $ appartiene a un componente che è stato pieno colore $ TRUE $ , quindi < Span Class="Math-Container"> $ V $ deve anche essere vero.
• Altrimenti, significa che $ U $ è raggiungibile da $ v_1 $ , e quindi $ V $ è anche raggiungibile da $ v_1 $ e deve essere vero. $ \ Blacksquare $

Nota tecnica : per ogni variabile $ x_i $ Ci sono due vertici:

una classe="container di matematica"> $ v_i $ e $ \ lnot v_i $ - e uno potrebbe chiedersi se porterà ad alcuni problemi conCompiti.La risposta è che dopo il passo 4), $ v_i $ e $ \ lnot v_i $ si troverà in dueComponenti diversi (inoltre, sono simmetrici: $ U \ a V $ in un componente significa $ \ lnot u \ to \lnot v $ in un altro).Pertanto, qualsiasi decisione che facciamo per $ U $ In un componente, possiamo fare la decisione opposta per $ \ lnot U $ in un altro.