12.3. Boolean satisfiability Problem

Try these first

1. 1.

   What is a Boolean variable?

   Hint

   Think about binary options.

2. 2.

   Define a clause in the context of Boolean logic.

   Hint

   Recall that literals can be either a variable or its negation.

3. 3.

   What does a clause consist of?

   • A conjunction of literals
   • A disjunction of literals
   • An assignment of truth values

   Hint

   Think about OR and AND definitions.

4. 4.

   True or False: The Boolean satisfiability problem is a decision problem.

   • True
   • False

   Hint

   Consider the definition of decision problems in computing.

5. 5.

   Consider the Boolean formula (x AND y) OR (NOT x AND z). Given the truth assignments: x=true, y=true, z=false; evaluate whether this is a satisfying assignment.

   Hint

   Break down each clause to assess its truth.

6. 6.

   Propose a method to transform the Boolean satisfiability problem into a checking problem. Discuss how this transformation assists in understanding computational difficulties.

   Hint

   Reflect on limitations of brute-force approaches.