Definição de fórmula 2-CNF (A.K.A Krom)

Question

Nas notas da minha palestrante, a seguinte definição para um WFF 2-CNF é dada:

.

Uma fórmula 2-CNF, ou a fórmula Krom é uma fórmula CNF F tal que cada cláusula tem no máximo dois literais.

No entanto, não há menção nas notas de como se pode representar cláusulas contendo um único literal L no gráfico de implicação correspondente WFF (embora eu suponho que alguém possa adicionar uma borda de todos os outros literais a l).Olhando para o papel original de Krom, a definição que ele parece usar é:

.

Uma fórmula 2-CNF, ou a fórmula Krom é uma fórmula CNF F tal que cada cláusula tem exatamente dois literais.

Esta definição parece fazer muito mais sentido.Qual definição está correta?Estou perdendo alguma coisa?

Answer 1

uma cláusula unitária do formulário $ P $ é o mesmo que a cláusula $ P $ P $ , e assim corresponde à seta $ \ lnot p \ to p $ .

Como exemplo, considere o insatisfatório CNF $$ p \ land (\ lnot p \ lor q) \ terra \ lnot q.$$ O gráfico de implicação contém as seguintes arestas: $$ \ lnot p \ para p \\ P \ to Q, \ lnot \ para \ lnot p \\ q \ to \ lnot q $$ Estes podem ser organizados em um ciclo: $$ \ lnot p \ to p \ to \ to \ lnot \ to \ lnot p $$ Este ciclo contém ambos $ P $ e $ \ lnot p $ (e também ambos $ q $ e $ \ lnot q $ ), mostrando que a fórmula é insatisfatível.