Satisfiability

In <a href="/facts/Mathematical_logic/SaI7Y3wN">mathematical logic</a>, a <a href="/facts/Well-formed_formula/YpTVlzuj">formula</a> is satisfiable if it is true under some assignment of values to its <a href="/facts/Variable_(mathematics)/VbQlrvKz">variables</a>. For example, the formula 
 
 
 
 x
 +
 3
 =
 y
 
 
 {\displaystyle x+3=y}
 
 is satisfiable because it is true when 
 
 
 
 x
 =
 3
 
 
 {\displaystyle x=3}
 
 and 
 
 
 
 y
 =
 6
 
 
 {\displaystyle y=6}
 
, while the formula 
 
 
 
 x
 +
 1
 =
 x
 
 
 {\displaystyle x+1=x}
 
 is not satisfiable over the integers. The dual concept to satisfiability is <a href="/facts/Validity_(logic)/oMGkywGC">validity</a>; a formula is valid if every assignment of values to its variables makes the formula true. For example, 
 
 
 
 x
 +
 3
 =
 3
 +
 x
 
 
 {\displaystyle x+3=3+x}
 
 is valid over the integers, but 
 
 
 
 x
 +
 3
 =
 y
 
 
 {\displaystyle x+3=y}
 
 is not.
Formally, satisfiability is studied with respect to a fixed logic defining the <a href="/facts/Syntax_(logic)/WrLeuvgp">syntax</a> of allowed symbols, such as <a href="/facts/First-order_logic/lcISqWIg">first-order logic</a>, <a href="/facts/Second-order_logic/C138cGXQ">second-order logic</a> or <a href="/facts/Propositional_calculus/MNt5v31V">propositional logic</a>. Rather than being syntactic, however, satisfiability is a <a href="/facts/Semantics/1L4WwLAP">semantic</a> property because it relates to the meaning of the symbols, for example, the meaning of 
 
 
 
 +
 
 
 {\displaystyle +}
 
 in a formula such as 
 
 
 
 x
 +
 1
 =
 x
 
 
 {\displaystyle x+1=x}
 
. Formally, we define an <a href="/facts/Interpretation_(logic)/goPmjjQG">interpretation</a> (or <a href="/facts/Model_theory/vLWVV8sQ">model</a>) to be an assignment of values to the variables and an assignment of meaning to all other non-logical symbols, and a formula is said to be satisfiable if there is some interpretation which makes it true. While this allows non-standard interpretations of symbols such as 
 
 
 
 +
 
 
 {\displaystyle +}
 
, one can restrict their meaning by providing additional <a href="/facts/Axiom/mLjP14Mc">axioms</a>. The <a href="/facts/Satisfiability_modulo_theories/10mBFLFB">satisfiability modulo theories</a> problem considers satisfiability of a formula with respect to a <a href="/facts/Theory_(mathematical_logic)/mYe5gQpI">formal theory</a>, which is a (finite or infinite) set of axioms.
Satisfiability and validity are defined for a single formula, but can be generalized to an arbitrary theory or set of formulas: a theory is satisfiable if at least one interpretation makes every formula in the theory true, and valid if every formula is true in every interpretation. For example, theories of arithmetic such as <a href="/facts/Peano_axioms/DhhDnNug">Peano arithmetic</a> are satisfiable because they are true in the natural numbers. This concept is closely related to the <a href="/facts/Consistency/IHkdnA9M">consistency</a> of a theory, and in fact is equivalent to consistency for first-order logic, a result known as <a href="/facts/G%25C3%25B6del%2527s_completeness_theorem/yq02MUyw">Gödel's completeness theorem</a>. The negation of satisfiability is unsatisfiability, and the negation of validity is invalidity. These four concepts are related to each other in a manner exactly analogous to <a href="/facts/Aristotle/U2bDlBFW">Aristotle</a>'s <a href="/facts/Square_of_opposition/z9S71UVr">square of opposition</a>.
The <a href="/facts/Decision_problem/cQNWjbdE">problem</a> of determining whether a formula in <a href="/facts/Propositional_logic/MNt5v31V">propositional logic</a> is satisfiable is <a href="/facts/Decidable_problem/cQNWjbdE">decidable</a>, and is known as the <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">Boolean satisfiability problem</a>, or SAT. In general, the problem of determining whether a sentence of <a href="/facts/First-order_logic/lcISqWIg">first-order logic</a> is satisfiable is not decidable. In <a href="/facts/Universal_algebra/uMJAL6ER">universal algebra</a>, <a href="/facts/Equational_theory/uMJAL6ER">equational theory</a>, and <a href="/facts/Automated_theorem_proving/vKGvuKFI">automated theorem proving</a>, the methods of <a href="/facts/Term_rewriting/9PHlnnnJ">term rewriting</a>, <a href="/facts/Congruence_closure/Ct6r2fJz">congruence closure</a> and <a href="/facts/Unification_(computer_science)/4EPHSB1T">unification</a> are used to attempt to decide satisfiability. Whether a particular <a href="/facts/Theory_(logic)/mYe5gQpI">theory</a> is decidable or not depends whether the theory is <a href="/facts/Variable-free/4Is2zkGg">variable-free</a> and on other conditions.

Satisfiability open-in-new

Satisfiability