Semantic inference

The concept of semantic inference is a form of implication in model theory . From every semantic , that is, a space of possible interpretations of the sentences of a formal, logical language, a concept of semantic inference arises. This is defined in such a way that a sentence follows from a set of sentences if and only if in every interpretation in which the sentences apply (are true), the sentence also applies (is true). The opposite term to semantic inference is deduction , which results from the application of the inference rules of a proof calculus ${\displaystyle B}$ ${\displaystyle A_{1},A_{2},\ldots }$ ${\displaystyle A_{1},A_{2},\ldots }$ ${\displaystyle B}$results, i.e. - typically calculable - defined syntactic transformations on sentences without reference to interpretations . The symbol for the semantic and the syntactic inference relation (deduction) is used to distinguish. By comparison with a semantic inference relation to draw conclusions about the conditions and characteristics can be gained of evidence calculi thereby: So the derivative relations are and depending on the choice of semantics on the one hand and the calculus on the other side is generally not equally powerful. They are equivalent only in special, but also particularly important cases, such as in the first-level classical propositional and predicate logic with Tarski semantics on the one hand and the usual calculi on the other. In the case that every syntactic inference is also a semantic inference, one speaks of correctness , in the opposite case, that there is also a syntactic derivation for every semantic inference, of completeness . ${\displaystyle \models }$ ${\displaystyle \vdash }$ ${\displaystyle \models }$ ${\displaystyle \vdash }$

definition

The relation ${\displaystyle \models }$

Be and sets of statements. If every model of is a model of , then the semantic inference relation is fulfilled and one writes . ${\displaystyle \Phi }$ ${\displaystyle \Psi }$ ${\displaystyle \Phi }$ ${\displaystyle \Psi }$ ${\displaystyle \Phi \models \Psi }$

In the literature it is common to use a structure instead of a set of statements on the left side of . In this case, it reads: “ is a model of ” or “ is fulfilled in”. Strictly speaking, this is not an inference relation in the sense just mentioned, but a satisfiability relation. But since the semantic inference is defined by the satisfiability of sets of statements in structures, the ambiguity is not a problem. ${\displaystyle \Phi }$ ${\displaystyle \Phi \models \Psi }$ ${\displaystyle \Phi }$ ${\displaystyle \Psi }$ ${\displaystyle \Psi }$ ${\displaystyle \Phi }$

In theoretical computer science , the set is always finite and only finite models are considered. Therefore it is customary there to define the set as the finite set of states that satisfy the statements from . Strictly speaking, this is not a corollary, but a satisfiability relation. But here too this usage is compatible with the mathematical definition. ${\displaystyle \Phi }$ ${\displaystyle \Phi }$ ${\displaystyle \Psi }$

tautology

If a formula is fulfilled under all assignments, i.e. always true, then it is a tautology :

${\displaystyle \models \psi }$

This is the semantic counterpart to the theorem. If a formula is never fulfilled, then it is a contradiction ( contradiction ).

Alternative names

The semantic inference is also called "mathematical reasoning" (especially in predicate logic) or " model-theoretical inference ". The satisfiability relation is also called “model relation” or “Tarski's satisfiability relation”. ${\displaystyle \models }$ ${\displaystyle \models }$

Relation to syntactic inference

Given a calculus with derivative relation. Be and formulas in the calculation. The calculus is called ${\displaystyle \vdash }$ ${\displaystyle \phi }$ ${\displaystyle \psi }$

• semantically complete , if itfollowsfrom, ${\displaystyle \phi \models \psi }$ ${\displaystyle \phi \vdash \psi }$
• semantically consistent or correct , if follows from . ${\displaystyle \phi \vdash \psi }$ ${\displaystyle \phi \models \psi }$

If the calculus is semantically complete and free of contradictions, it is called adequate . Important examples of this are first-order predicate logic and propositional logic .

Syntactic and semantic inference in propositional logic

The syntactic derivation looks like this:

${\displaystyle {\begin{alignedat}{3}{\text{1. Ableitungsschritt:}}\quad &p\wedge q&\quad &(Ann)\\{\text{2. Ableitungsschritt:}}\quad &p&\quad &(\wedge -Elimination)\end{alignedat}}}$

So the expression is valid. ${\displaystyle p\wedge q\vdash p}$

In propositional logic, the semantic inference can be checked using a truth table. In order to apply this, one checks whether the conclusion is true for all assignments in which the premises are true.

${\displaystyle p}$	${\displaystyle q}$	${\displaystyle p\wedge q}$
true	true	true
true	not correct	not correct
not correct	true	not correct
not correct	not correct	not correct

Whenever is fulfilled, it is . So it follows . ${\displaystyle p\wedge q}$ ${\displaystyle p}$ ${\displaystyle p\wedge q\models p}$

In mathematics, the semantic inference is the model for logic calculi .

Further examples

formula	valid?	Reason
${\displaystyle p\vee q\models p}$	invalid	Possibility: ${\displaystyle p=f,\ q=t,\ p\vee q=t}$
${\displaystyle \neg q,\ p\vee q\models p}$	valid	always: ${\displaystyle q=f\Longrightarrow \ p\vee q=t\longrightarrow p=t}$
${\displaystyle p\models q\vee \neg q}$	valid	right no dependence on left

See also

• Model theory
• Correctness (logic)
• Completeness (logic)

literature

• Michael Schenke: Logic calculations in computer science . Springer Vieweg, Wiesbaden 2013.
• Michael Huth, Mark Ryan: Logic in Computer Science - Modeling and Reasoning about Systems , 2nd ed., Cambridge University Press, 2005, ISBN 0-521-54310-X website
• Uwe Schöning: Logic for computer scientists , 5th edition, Spectrum Academic Publishing House, 2000. Chapters 1.1 and 2.1. (Propositional logic and predicate logic only).

credentials

1. ↑ Dirk W. Hoffmann: The limits of mathematics . 3. Edition. Springer Spectrum, Berlin, Heidelberg 2018, p. 76 .