Определение формулы 2-CNF (A.K.A KROM)

Question

В заметках моего лектора дано следующее определение для 2-CNF WFF:

Формула 2-CNF или формула KROM - это формула CNF F, что у каждого предложений у каждого предложений у большинства двух литералов.

Однако в заметках нет упоминания о том, как можно представлять положения, содержащие один буквальный L в соответствующем диапазоне WFF (хотя я полагаю, что можно добавить к краю от любого другого буквального к л).Глядя на оригинальную бумагу KROM, определение, которое он, кажется, используется:

Формула 2-CNF, или формула KROM - это формула CNF, такая, что у каждого предложений есть ровно две литералы.

Это определение казалось бы, намного больше смысла.Какое определение правильно?Я что-то упускаю?

Answer 1

Пункт единиц формы $ p $ такой же, как пункт $ P \ lor p $ , и поэтому соответствует стрелке $ \ lnot p \ to p $ .

в качестве примера, рассмотрите неудовлетворный CNF $$ p \ land (\ lnot p \ lor q) \ load \ lnot q.$$ График подразумевания содержит следующие края: $$ \ lnot p \ to p \\ р \ к Q, \ lnot q \ \ lnot p \\ Q \ to \ lnot q $$ Они могут быть организованы в цикле: $$ \ lnot p \ to p \ to q \ to \ lnot q \ to \ lnot p $$ Этот цикл содержит как $ p $ и $ \ lnot p $ (а также оба $ q $ и $ \ lnot q $ ), показывающий, что формула неудовлетана.