3.8. Verification of CNF

Try these first

1. 1.

   Define the satisfiability problem.

   Hint

   Focus on the meaning of 'satisfy'.

2. 2.

   What is CNF?

   Hint

   Recall how clauses are structured.

3. 3.

   What is a satisfiable proposition?

   • Always false
   • Always true
   • True for at least one assignment

   Hint

   Remember the definition of satisfiability.

4. 4.

   In CNF, what does each clause consist of?

   • Conjunctions of literals
   • Disjunctions of literals
   • Tautologies

   Hint

   Recall the structure of CNF.

5. 5.

   Given the expression (p ↔ q) ∧ (¬q ∨ r), convert it to CNF and explain each step.

   Hint

   Sequential transformations are hand in hand with logical identities.

6. 6.

   Create an unsatisfiable proposition and explain why it cannot be satisfied.

   Hint

   Review the properties of contradictions to guide your creation.