3.2. Application of SAT Problem

Try these first

1. 1.

   What is the definition of a satisfiable proposition?

   Hint

   Think about what it means for an expression to be true.

2. 2.

   What does CNF stand for?

   Hint

   Recall how logical statements are structured in CNF.

3. 3.

   What is the definition of SAT?

   • Check if a statement can be satisfied
   • Only validate truths
   • Make any statement true

   Hint

   Think about the main function of SAT.

4. 4.

   True or False: The SAT problem is easy to solve for all logical expressions.

   • True
   • False

   Hint

   Consider the challenges discussed in the SAT problem.

5. 5.

   Given the expression (p AND (q OR r)) → (s AND t), rewrite it in CNF form.

   Hint

   Start by rewriting implications and then apply distribution.

6. 6.

   Prove that the expression (p AND ¬q) OR (¬p AND q) is unsatisfiable if p = true and q = false.

   Hint

   Analyze how truth values interact within the clauses.