3.5. Conjunctive Normal Form (CNF) Introduction

Try these first

1. 1.

   What does it mean for a proposition to be satisfiable?

   Hint

   Think of truth assignments.

2. 2.

   Define Conjunctive Normal Form.

   Hint

   Focus on ANDs and ORs in the definition.

3. 3.

   What does a satisfiable proposition indicate?

   • It is always false
   • It can be true for some assignment
   • It is true regardless of assignment

   Hint

   Consider truth assignments.

4. 4.

   In which form does CNF express logical propositions?

   • True
   • False

   Hint

   Remember the structure of CNF.

5. 5.

   Demonstrate your understanding of the transformation process by converting the expression P ↔ (Q AND R) into CNF.

   Hint

   Ensure you apply logical identities correctly.

6. 6.

   Consider a complex expression. Propose a step-by-step method to verify its CNF status.

   Hint

   Focus on the structure and definitions we discussed.