3.6. Definition of CNF

Try these first

1. 1.

   Define 'satisfiable' in your own words.

   Hint

   Think about what it means for a statement to be true or false.

2. 2.

   What is the opposite of a satisfiable proposition?

   Hint

   Consider what it means for something never to be true.

3. 3.

   What does it mean for a proposition to be 'satisfiable'?

   • It is always true
   • It is false for all assignments
   • It is true for at least one assignment

   Hint

   Consider the conditions of truth for the proposition.

4. 4.

   True or False: An unsatisfiable proposition has no truth assignments that make it true.

   • True
   • False

   Hint

   Think about what 'unsatisfiable' means in context.

5. 5.

   Given the expression (p AND (q OR r)), convert it to CNF and explain your steps.

   Hint

   Assess if any rules apply that may change the expression's format significantly.

6. 6.

   How would you encode a Sudoku puzzle as a CNF? Explain the logical structure and possible variables.

   Hint

   Think about how each condition narrows down your options and must be captured logically.