تعريف 2-CNF (A.K.A Krom) الصيغة

Question

في ملاحظات محاضرتي، يتم إعطاء التعريف التالي ل 2 CNF WFF:

صيغة 2-CNF، أو صيغة KROM هي صيغة CNF FS بحيث يحتوي كل جملة على أحدث حرفين.

غير ذلك، ومع ذلك، لا يوجد ذكر في ملاحظات كيف يمكن للمرء أن يمثل البنود التي تحتوي على L حرفي واحد في الرسم البياني للتأييج المقابل ل WFF (على الرغم من أنني أفترض أنه يمكنني إضافة حافة من كل حرفي آخر إلى L).النظر في الورق الأصلي في Krom، التعريف الذي يبدو أنه يستخدمه هو:

صيغة 2-CNF، أو Formula Krom هي صيغة CNF F أن كل جملة يحتوي على حرفين بالضبط.

يبدو أن هذا التعريف أكثر منطقية.أي تعريف صحيح؟هل أنا أفتقد شيئا؟

Answer 1

جملة وحدة من النموذج $ p $ هو نفسه مثل البند $ p \ lor p $ ، وكذلك يتوافق مع السهم $ \ lnot p \ to p $ .

كمثال، فكر في CNF غير مرضية $$ p \ land (\ lnot p \ lor q) \ land \ lnot q.$ يحتوي الرسم البياني التضمين على الحواف التالية: $$ \ lnot p \ إلى p \\ p \ إلى q، \ lnot q \ to \ lnot p \\ س \ إلى \ Lnot q $ يمكن ترتيب هذه في دورة: $$ \ lnot p \ to p \ to q \ to \ lnot q \ to \ lnot p $ تحتوي هذه الدورة على كل من $ p $ و $ \ lnot p $ (وأيضا $ q $ و $ \ lnot q $ )، إظهار أن الصيغة غير مرضية.