3.4. Practical Implications of the SAT Problem

Try these first

1. 1.

   Define a satisfiable proposition.

   Hint

   Think of a scenario where a statement can be true.

2. 2.

   What is the main goal of the SAT problem?

   Hint

   Consider what you are checking when solving a logical equation.

3. 3.

   What defines a satisfiable proposition?

   • It can be true under no truth assignments.
   • It can be true under at least one truth assignment.
   • It is always false.

   Hint

   Think about the definitions we went through.

4. 4.

   True or False: Every logical expression can be converted to CNF.

   • True
   • False

   Hint

   Recall that CNF is a standard form.

5. 5.

   Given the proposition P ↔ Q, convert it to CNF and explain each transformation step.

   Hint

   Start by recalling the logical identities that define bi-implications.

6. 6.

   Design a simple Sudoku solver algorithm using the SAT approach. Describe the propositional variables and constraints you'll implement.

   Hint

   Think through each Sudoku rule to encode your requirements.