Définition de formule 2-CNF (A.K.A KROM)

Question

Dans les notes de mon conférencier, la définition suivante pour un WFF 2-CNF est donnée:

Une formule 2-CNF ou une formule KROM est une formule CNF F telle que chaque clause a au maximum deux littéraux.

Cependant, les notes de la manière dont on peut représenter des clauses contenant un seul littéral l littéral dans le graphe d'implication correspondant de WFF (bien que je suppose que l'on puisse ajouter un bord de chaque littéral à l).En regardant le papier original de Krom, la définition qu'il semble utiliser est la suivante:

une formule 2-CNF ou une formule KROM est une formule CNF F telle que chaque clause a exactement deux littéraux.

Cette définition semblerait avoir beaucoup plus de sens.Quelle définition est correcte?Est-ce que je manque quelque chose?

Answer 1

Une clause unitaire de la forme $ p $ est la même que la clause $ p \ lor p $ , et donc correspond à la flèche $ \ lnot p \ to p $ .

.

À titre d'exemple, considérons le CNF insatisfait $$ p \ terres (\ lnot p \ lor q) \ terres \ lnot q.$$ Le graphique d'implication contient les bords suivants: $$ \ lnot p \ to p \\ p \ to q, \ lnot q \ to \ lnot p \\ Q \ to \ lnot q $$ Ceux-ci peuvent être organisés dans un cycle: $$ \ lnot p \ to p \ to q \ to \ lnot q \ to \ lnot p $$ Ce cycle contient à la fois $ p $ et $ \ lnot p $ (ainsi que $ q $ et $ \ lnot q $ ), montrant que la formule n'est pas satisfaite.