3.9. Conversion to CNF

Try these first

1. 1.

   What does it mean for a proposition to be satisfiable?

   Hint

   Think about truth assignments for variables.

2. 2.

   Define a literal.

   Hint

   What basic elements make up propositional logic?

3. 3.

   What is a satisfiable proposition?

   • Always false for any assignment
   • True for all assignments
   • True for at least one assignment

   Hint

   Consider the definition of satisfiability.

4. 4.

   In CNF, what is the form of a clause?

   • A conjunction of literals
   • A disjunction of literals
   • A sequence of variables

   Hint

   Focus on how CNF is structured.

5. 5.

   Convert the expression (¬A ∧ (B ∨ C)) → D into CNF.

   Hint

   Start with the logical identities.

6. 6.

   Determine whether the expression (A ∨ B) ∧ (¬A ∨ C) is satisfiable. Explain your reasoning.

   Hint

   Test various truth assignments!