Satisfiability

Satisfiability is in logic and mathematics, a metalinguistic predicate for the property of logical statements and statement forms. A proposition is satisfiable 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 mainly of (in) equations and (in) equations is interesting. The general definition can then be reformulated as: " There are ( at least) one solution."

Examples: In theory, the real numbers (ie, the conventional numbering system ) thus this statement is the equation solved, satisfiable.

The system of equations, however, is not solvable, because the only solution would be, but this solution is not met. This statement is therefore not met.

Logic

In SL, you can classify statements as a result of their satisfiability, where the variables occurring accept statements as truth values ​​. A statement form is called ...

• Satisfiable if it (ie, a variable assignment a true statement generated ) is satisfiable.

• A tautology, if any (!) assignment of variables produces a true statement.

• A contradiction if it is not satisfiable. Then the negation of the statement form is a tautology.

• A contingency or neutrality when it is neither a tautology nor a contradiction.
• " ' Falsifiable ' " if at least one assignment is not a model.

Examples: A ( not otherwise occurring ) propositional variable is satisfiable for themselves, even a contingency ( because that is the property of a propositional variable that is either true or false).

The statement is a tautology, ie satisfiable, for every assignment of true or false delivers a true statement. Consequently, the statement is a contradiction, so do not satisfiable.

The problem to decide whether a propositional formula is satisfiable is called the satisfiability problem of propositional logic. This problem is important, inter alia, in complexity theory.

Analogous to the notion of satisfiability of propositional logic is also used in the predicate logic: a predicate logic formula is satisfiable if there is an interpretation of the predicates and an assignment of the variables for which the formula takes the truth value true ( Erfüllbarkeitsäquivalenz ).

Examples: The statement is a tautology, the statement is a contingency (only achievable if there is more than one object ), the statement is a contradiction.