Boolean satisfiability problem
![The 3-SAT instance (x∨x∨y) ∧ (¬x∨¬y∨¬y) ∧ (¬x∨y∨y) reduced to a clique problem. The green vertices form a 3-clique and correspond to the satisfying assignment x=FALSE, y=TRUE.](/Images/godic/202502/09/Sat_reduced_to_Clique_from_Sipser.svg0832.png")
![Left: Schaefer's reduction of a 3-SAT clause x∨y∨z. The result of R is TRUE (1) if exactly one of its arguments is TRUE, and FALSE (0) otherwise. All 8 combinations of values for x,y,z are examined, one per line. The fresh variables a,...,f can be chosen to satisfy all clauses (exactly one green argument for each R) in all lines except the first, where x∨y∨z is FALSE. Right: A simpler reduction with the same properties.](/Images/godic/202502/09/Schaefer's_3-SAT_to_1-in-3-SAT_reduction0832.gif")
![A formula with 2 clauses may be unsatisfied (red), 3-satisfied (green), xor-3-satisfied (blue), or/and 1-in-3-satisfied (yellow), depending on the TRUE-literal count in the 1st (hor) and 2nd (vert) clause.](/Images/godic/202502/09/Boolean_satisfiability_vs_true_literal_counts0833.png")
In computer science, the Boolean Satisfiability Problem (sometimes called Propositional Satisfiability Problem and abbreviated as SATISFIABILITY or SAT) is 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 identically FALSE for all possible variable assignments and the formula is 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.