2-CNF（A.K.A KROM）の定義

Question

私の講師の注意事項では、2 CNF WFFの次の定義が与えられます。

2 - CNF式、またはKROM式はCNF式Fであるため、各項は最大2つのリテラルを持っています。

しかし、WFFの対応する含意グラフ内の単一のリテラルLを含む節をどのように表すかもしれないかについての言及はありません（ただし、LigutalからL個のリテラルのすべてのリテラルのエッジを追加できると思います）。KROMのオリジナルの紙を見て、彼が使うように思われる定義は次のとおりです。

2-CNF式、またはKROM式は、すべての条項が正確に2つのリテラルを持っているようなCNF式Fです。

この定義はもっと意味があるようです。どの定義が正しいですか？私は何かがありませんか？

Answer 1

フォームのUNIT句 $ p $ は、 $ p \ lor p $ 、そして矢印 $ \ lnot p \ to p $ に対応します。

例として、不満足なCNFを考えてみましょう $$ p \ land（\ lnot p \ lor q）\ land \ lnot q。$$ 含意グラフには次のエッジが含まれています。 $$ \ lnot p \ to p \\ P \ Q、 \ lnot q \ to \ lnot p \\ q \ to \ lnot Q. $$ これらはサイクルで配置できます。 $$ \ to \ to \ to to \ to to \ lnot pへ $$ このサイクルには、 $ p $ と $ \ lnot p $ （そしてまた両方の $ Q $ と $ \ lnot q $ ）、式が不満足のあることを示す。