Problem of determining if a Boolean formula could be made true
Also known as propositional satisfiability problem · SATISFIABILITY · SAT
13 statements · 23% with external sources · numbers in brackets are citations
5 identifiers linking boolean satisfiability problem across the web's reference databases
From Wikipedia, the free encyclopedia · Read full article · Text CC BY-SA 4.0
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) asks whether there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the formula's variables can be consistently replaced by the values TRUE or FALSE to make the formula evaluate to TRUE. If this is the case, the formula is called satisfiable, else unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, "a AND NOT a" is unsatisfiable.