3.2.5. Finding Truth Assignments

Try these first

1. 1.

   Define what it means for a proposition to be satisfiable.

   Hint

   Recall the definition discussed in class.

2. 2.

   What does it signify if a proposition is unsatisfiable?

   Hint

   Think of the meaning behind a tautology.

3. 3.

   What is a satisfiable compound proposition?

   • It is one that cannot be true
   • It is true for at least one truth assignment
   • It is always false

   Hint

   Recall the definition from the lecture.

4. 4.

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

   • True
   • False

   Hint

   Think about the relationship between satisfiability and tautology.

5. 5.

   Create a CNF representation for a logical statement combining multiple conditions, explain each step, and validate it.

   Hint

   Step through each transformation explicitly.

6. 6.

   Analyze a given SAT instance from Sudoku, encode it, and explain how you would determine its satisfiability.

   Hint

   Utilize logical conditions for each row, column, and block.