The Boolean satisfiability problem is the problem of determining whether there is an assignment of true or false values to variables that makes a Boolean formula evaluate to true. It is also known as SAT and is a foundational problem in logic, constraint solving, and computational complexity.
(Also propositional satisfiability problem; abbreviated SATISFIABILITY or SAT.) The problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks 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. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, th