3.1. Introduction to Satisfiability Problem

Try these first

1. 1.

   Define a satisfiable proposition.

   Hint

   Think about truth assignments possible.

2. 2.

   What does it mean for a proposition to be unsatisfiable?

   Hint

   Remember the tautology's role.

3. 3.

   What is a satisfiable proposition?

   • It is always false
   • It can be true for some assignments
   • It cannot be true for any assignments

   Hint

   Think about when a proposition can be true.

4. 4.

   True or False: Every unsatisfiable proposition has a negation that is a tautology.

   • True
   • False

   Hint

   Consider definitions of unsatisfiability.

5. 5.

   Given the proposition (p → q) ∧ (¬q ∨ r), convert it into conjunctive normal form.

   Hint

   Remember rules for negations and implications.

6. 6.

   Explain how a Sudoku puzzle can be encoded as a SAT problem and the implication of each rule.

   Hint

   Think of how you’ll frame each number’s placement in SAT terms.