7.3. Question 9

Try these first

1. 1.

   Provide a simple compound proposition in CNF and explain if it is satisfiable.

   Hint

   Check if you can find a truth assignment.

2. 2.

   What does it mean for a proposition to be unsatisfiable?

   Hint

   Consider logical contradictions.

3. 3.

   What is satisfiability in propositional logic?

   • A property that makes a statement always true.
   • The ability to find at least one truth assignment that makes the formula true.
   • The counting of propositions in a formula.

   Hint

   Think about the meaning of truth assignments.

4. 4.

   True or False: A tautology is always satisfiable.

   • True
   • False

   Hint

   Consider the definition of tautology.

5. 5.

   Given the expression (p OR ¬q) AND (¬p OR r), determine all possible truth assignments and their impact on satisfiability.

   Hint

   Create a detailed truth table mapping variables.

6. 6.

   Construct a CNF expression that is unsatisfiable and explain why it cannot be satisfied.

   Hint

   Think of contradictions in logical statements.