Deduction theorem

The term deduction theorem two closely related theorems are known that are of importance in mathematical logic. A variant of the theorem, also known as Folgerungstheorem, is geared to the concept of logical conclusion. The other variant, which applies within calculi, makes instead of ( semantic ) logical consequence, the ( syntactic ) derivation of the starting point. In both cases, a relationship is established for the material implication.

The deduction theorem for logical inferences ()

The semantic version of the deduction theorem is as follows:

A formula is then just a logical consequence of the set of formulas with, formally, if the implication

Universal, that is, is a tautology ( in classical logic that is exactly the case when the implication for each possible interpretation is true).

Generally, in classical logic a formula B if a logical consequence of the set of formulas T, ie If for every interpretation I, for all formulas of the formula set T are true, the formula B is true. The deduction theorem is this general definition of a logical conclusion in relation to the implication. It thus forms one of the essential mechanisms to make the semantic notion of logical consequence in computer systems handled by purely formal manipulations. It is therefore closely related to the Widerlegungstheorem.

The key for the above statement terms of the formula and the interpretation are explained in detail in the article about knowledge representation with logic.

The deduction theorem for derivatives of ()

In the area of ​​calculi a different definition of the deduction theorem is used that moves purely on the syntactic level. This version of the deduction theorem has already been found and proved in 1930 by Jacques Herbrand and ( independent of this and almost simultaneously ) by Alfred Tarski. The focus of this definition is in contrast to the ( semantic ) logical consequence, the ( syntactic ) derivation. This is as set in the above deduction theorem in a relationship with the implication:

If

Then

Hilbert and Bernays formulate this as follows: " If for a formula A is a formula B is derivable in such a way [ ... ], then the formula is A → B without using the formula A derivable "

In many calculi, the converse also holds. That is, from a lot of the formula A → B be derived, so the formula B, so this circuit direction is trivial with the help of the additional hypothesis A. Applies in a calculus of modus ponens.