3. SAT Problem

Try these first

1. 1.

   Define a satisfiable proposition.

   Hint

   Think about a scenario where it is at least true.

2. 2.

   What does it mean for a proposition to be unsatisfiable?

   Hint

   What if there are no conditions making it true?

3. 3.

   What is a satisfiable proposition?

   • A proposition that is always false
   • A proposition that is true for at least one assignment
   • A proposition that is a contradiction

   Hint

   Consider cases where it can be true.

4. 4.

   True or False: An unsatisfiable proposition can be true for some assignments.

   • True
   • False

   Hint

   Recall the definition of unsatisfiability.

5. 5.

   Create an expression for the compound proposition to show that either A is true or B is true, but not both.

   Hint

   Think about how to combine the two propositions safely.

6. 6.

   Given the expression (p ∧ q) ∨ (¬p ∧ r), express it in CNF.

   Hint

   Use logical identities to help in reformatting.