2-CNF 정의 (A.K.A KROM) 공식

Question

내 강사의 메모에서는 2-CNF WFF에 대한 다음 정의가 주어집니다 :

A 2-CNF 공식 또는 KROM 공식은 모든 조항이 가장 두 리터럴에 있도록 CNF 수식 F입니다.

그러나 WFF의 해당 암사 그래프에서 단일 리터럴 L이 포함 된 절을 나타내는 방법에 대한 메모에는 언급이 없습니다 (나는 다른 모든 리터럴에서 L까지의 가장자리를 추가 할 수 있다고 가정 할 수 있지만).KROM의 원래 종이를보고, 그가 사용하는 정의는 다음과 같습니다 :

A 2-CNF 공식 또는 KROM 공식은 모든 조항이 정확히 두 개의 리터럴을 갖도록 CNF 수식 F입니다.

이 정의는 더 많은 의미를 갖는 것처럼 보입니다.어떤 정의가 맞습니까?나는 뭔가를 놓치고 있니?

Answer 1

$ P $ 은 $ p \ lor p $ 이므로 화살표 $ \ lnot p \ p $ 에 해당합니다.

예를 들어, 불만족 할 수없는 CNF를 고려하십시오. $$ P \ LAND (\ lnot p \ lor q) \ land \ lnot q.$$ 암시 그래프에는 다음 가장자리가 포함됩니다. $$ \ lnot p \ p \\ p \ ~ q, \ lnot q \ to \ lnot p \\ q \ \ lnot Q. $$ 이들은 주기로 배열 될 수 있습니다. $$ \ lnot p \ p \ to q \ lnot q \ lnot p \ lnot p $$ 이 사이클에는 $ P $ 및 $ \ lnot p $ (그리고 $ Q $ 및 $ \ lnot Q $ ). 수식이 만족하지 않음을 보여줍니다.