Definición de fórmula 2-CNF (A.K.A KROM)

Question

En las notas de mi profesor, se da la siguiente definición para un WFF de 2 CNF:

Una fórmula 2-CNF, o la fórmula KROM es una fórmula CNF F tal que cada cláusula tiene como máximo dos literales.

Sin embargo, no se menciona en las notas de cómo uno podría representar cláusulas que contienen un solo literal L en el gráfico de implicación correspondiente de la WFF (aunque supongo que uno podría agregar un borde de todos los demás literales a L).Mirando el papel original de Krom, la definición que parece usar es:

Una fórmula 2-CNF, o la fórmula KROM es una fórmula CNF F tal que cada cláusula tiene exactamente dos literales.

Esta definición parece tener mucho más sentido.¿Qué definición es correcta?¿Me estoy perdiendo algo?

Answer 1

Una cláusula de unidad del formulario $ P $ es el mismo que la cláusula $ P \ lor P $ , y así se corresponde a la flecha $ \ lnot p \ a p $ .

Como ejemplo, considere el CNF insatisfecho $$ P \ Land (\ lNOT P \ lor Q) \ Land \ LNOT Q.$$ El gráfico de implicación contiene los siguientes bordes: $$ \ lnot p \ a p \\ p \ a q, \ lnot q \ to \ lnot p \\ q \ a \ lnot q $$ Estos se pueden organizar en un ciclo: $$ \ lnot p \ a p \ a q \ to \ lnot q \ to \ lnot p $$ Este ciclo contiene tanto $ p $ y $ \ lnot p $ (y también $ q $ y $ \ lnot q $ ), que muestra que la fórmula es insatisfactoria.