Definizione di formula 2-cnf (a.k.a krom)

Question

Nelle esigenze dei miei docenti, viene data la seguente definizione per un WFF 2-CNF:

.

Una formula a 2 cnf, o la formula di Krom è una formula CNF in tale che ogni clausola abbia al massimo due letterali.

Tuttavia, non vi è alcuna menzione nelle note di come si potrebbero rappresentare le clausole contenenti una singola l letterale l nel corrispondente grafico di implicazione del WFF (anche se suppongo che si possa aggiungere un bordo da ogni altro letterale a L).Guardando il documento originale di Krom, la definizione che sembra usare è:

.

Una formula a 2 cnf, o la formula KROL è una formula CNF in tale che ogni clausola abbia esattamente due livelli letterali.

Questa definizione sembrerebbe avere molto più senso.Quale definizione è corretta?Mi manca qualcosa?

Answer 1

Una clausola unit del modulo $ p $ è la stessa della clausola $ p \ lor p $ , e quindi corrisponde alla freccia $ \ lnot p \ to p $ .

Ad esempio, considera la CNF insoddisfacente $$ p \ Land (\ lnot p \ lor q) \ Land \ lnot q.$$ Il grafico di implicazione contiene i seguenti bordi: $$ \ lnot p \ to p \\ p \ to q, \ lnot q \ to \ lnot p \\ q \ a \ lnot q $$ Questi possono essere organizzati in un ciclo: $$ \ lnot p \ to p \ to q \ to \ lnot q \ to \ lnot p $$ Questo ciclo contiene sia $ P $ e $ \ lnot p $ (e anche (e anche $ Q $ e $ \ lnot q $ ), mostrando che la formula è insoddisfacida.