Satisfiability

In logic and mathematics, satisfiability is a metalinguistic predicate for the property of logical statements and statement forms . A statement can be fulfilled if there is an assignment (interpretation, evaluation ) of the variables for which the truth value of the entire expression is true .

mathematics

In mathematics, the satisfiability of (in) equations and systems of (in) equations is particularly interesting. The general definition can then be rephrased to: "There is (at least) one solution."

Examples: In the theory of real numbers (i.e. the usual number system) the equation can be solved, i.e. this statement can be fulfilled. ${\displaystyle 2x+1=3x}$

The system of equations , however, is not solvable, because the only solution would be , but this solution does not satisfy . So this statement cannot be fulfilled. ${\displaystyle x<0,x^{2}\leq 0}$ ${\displaystyle x^{2}\leq 0}$ ${\displaystyle x=0}$ ${\displaystyle x<0}$

logic

Propositional logic

In propositional logic , statements can be classified on the basis of their satisfiability, whereby the occurring variables assume truth values ​​as statements. One form of statement is called ...

• can be fulfilled if at least one assignment of the variable produces a true statement.
• a tautology , if every (!) assignment of the variables produces a true statement.
• a contradiction if it cannot be fulfilled. The negation of a contradiction is always a tautology. However, the opposite of the term "contradiction" is not "tautology", but "satisfiability".
• a contingency or neutrality if it is neither a tautology nor a contradiction.
• falsifiable if at least one assignment does not represent a model , i.e. generates a false statement.

The problem of deciding whether a propositional formula is satisfiable is called the satisfiability problem of propositional logic . This problem is important in complexity theory , among other things .

Examples

A proposition variable (which does not occur otherwise) can be fulfilled by itself, even a contingency. It is the property of a propositional variable that its truth value is either true or false. ${\displaystyle A}$

The statement (read: or not ) is a tautology, so it can also be fulfilled, because every assignment of true or false provides a true statement. Consequently, the statement (the negation of the previous example) is a contradiction, i.e. it cannot be fulfilled. ${\displaystyle A\vee \neg A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle \neg (A\vee \neg A)}$

Predicate logic

Analogous to propositional logic, the term satisfiability is also used in predicate logic : A predicate logic formula can be fulfilled if there is an interpretation of the predicates and an assignment of the variables for which the formula assumes the truth value to be true ( satisfiability equivalence ).

Examples

• ${\displaystyle \forall x(x=x)}$ "for every x: x is x" is a tautology, since x is always identical to itself.
• ${\displaystyle \forall x\exists y(x\neq y)}$ "for every x there is a y, for which the following applies: x is not equal to y" is a contingency, since it can only be fulfilled if there is more than one object in the set of objects from which x and y are chosen.
• ${\displaystyle \exists x(x\neq x)}$ "The following applies to every x: x is not equal to x" is a contradiction, the statement is false for every object.

See also

• Predictability
• Model theory
• resolution
• intolerance