3.2.1. Sudoku Puzzle Solver

Try these first

1. 1.

   Define the SAT problem in your own words.

   Hint

   Think about truth assignments and propositions.

2. 2.

   What is a conjunctive normal form?

   Hint

   Focus on conjunctions and clauses.

3. 3.

   What does the SAT problem determine?

   • The truth of a singular proposition
   • The satisfiability of a propositional expression
   • The validity of logical deductions

   Hint

   Recall the purpose of the SAT problem.

4. 4.

   True or False: Every compound proposition is satisfiable.

   • True
   • False

   Hint

   Consider definitions of satisfiability.

5. 5.

   Given the proposition (p or (not q and r)), prove whether it's satisfiable or unsatisfiable through truth assignment.

   Hint

   Break down the expression to see how the assignments impact the overall truth.

6. 6.

   Create a CNF for the expression (p → (q and r)) and verify its correctness by showing an equivalent expression.

   Hint

   Use truth tables to show equivalence at every logical step.