3.2. Definition of Satisfiability

Try these first

1. 1.

   Define satisfiability in your own words.

   Hint

   Think about conditions needed for a proposition to be true.

2. 2.

   What is the meaning of a tautology?

   Hint

   Consider an expression that never fails.

3. 3.

   What does it mean for a proposition to be satisfiable?

   • It is always false
   • It can be true under certain variable assignments
   • It is always true

   Hint

   Think of when a statement holds true.

4. 4.

   True or False: A tautology is a proposition that can never be true.

   Hint

   Consider the definition of a tautology.

5. 5.

   Given the following proposition, determine if it's satisfiable: (p ∨ q) ∧ (¬p ∧ r).

   Hint

   Try different combinations of truth assignments.

6. 6.

   Explain how you would convert the compound proposition ¬(p ∧ q) into CNF.

   Hint

   Look for simplifications through negations.