The Boolean Satisfiability Problem
The Boolean satisfiability problem (often referred to as SAT or B-SAT) is a fundamental decision problem in computer science and logic. It involves determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it checks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE.
Areas of application
- Computer Science
- Logic
- Artificial Intelligence
- Formal Verification
- Software Engineering
Example
Consider a Boolean formula with variables x and y, and a clause that states ‘if x is true, then y must be false’. If there exists an interpretation where both x and y are either true or false, then the formula is satisfiable. Otherwise, it is unsatisfiable.