Questions and Answers
What is the Boolean satisfiability problem?
The Boolean satisfiability problem is the problem of determining if there exists an interpretation that satisfies a given Boolean formula.
What does it mean for a Boolean formula to be satisfiable?
A Boolean formula is satisfiable if there exists an assignment of TRUE or FALSE values to its variables that makes the formula evaluate to TRUE.
Give an example of a satisfiable Boolean formula.
An example of a satisfiable Boolean formula is 'a AND NOT b', where a = TRUE and b = FALSE.
Give an example of an unsatisfiable Boolean formula.
Signup and view all the answers
What is the complexity class that the Boolean satisfiability problem belongs to?
Signup and view all the answers
