3.2.6. Conclusion

Try these first

1. 1.

   Define the SAT problem.

   Hint

   Think about the 'satisfiability' you learned about.

2. 2.

   What is Conjunctive Normal Form?

   Hint

   Consider how conjunctions and disjunctions interact.

3. 3.

   What is the main goal of the SAT problem?

   • To find every possible truth assignment
   • To determine if a logical formula has at least one satisfiable assignment
   • To prove that a logical formula is always true

   Hint

   Think about what 'satisfiable' means.

4. 4.

   True or False: A proposition is unsatisfiable if its negation is a tautology.

   • True
   • False

   Hint

   Recall how contradictions relate to tautologies.

5. 5.

   Given the expression ¬(p ∧ q) ∨ (r ∧ ¬s), transform it into CNF.

   Hint

   Use logical identities and double-check each transformation for correctness.

6. 6.

   Construct a logical formula that represents a Sudoku puzzle's row condition.

   Hint

   Think about how to express uniqueness and presence.