Sequent calculus
In the proof theory and mathematical logic is denoted by sequent calculus a family of formal systems (or calculi ) that share a certain style of derivation and some properties. The first sequences calculi LK for classical and intuitionistic logic LJ for, have been introduced by Gerhard Gentzen in 1934 as a formal framework for the study of systems of natural deduction in predicate logic first order.
The Gentzensche main theorem on LK and LJ states that the cut rule is valid in these systems, a set of far-reaching consequences in the metalogic. The flexibility of the sequent calculus turned out later, in 1936, when the technique of Gentzen cut elimination used to prove the consistency of Peano arithmetic.
The going back to Gentzen calculi sequences and the general concepts behind them, are used by default in many areas of proof theory, mathematical logic and machine-assisted proving.
- 4.1 Basic rules 4.1.1 Antezedensregel
- 4.1.2 acceptance rule
- 4.2.1 Case distinction
- 4.2.2 Contradiction
- 4.2.3 Adjunktionseinführung in the antecedent
- 4.2.4 Adjunktionseinführung the consequent
- 4.3.1 Introduction existence in the consequent
- 4.3.2 Introduction existence in the antecedent
- 4.4.1 reflexivity
- 4.4.2 substitution rule
- 5.1 law of excluded middle
- 5.2 triviality
- 5.3 Chain -circuit
- 5.4 contraposition
- 5.5 disjunctive syllogism
- 6.1 correctness 6.1.1 definitions 6.1.1.1 model
- 6.1.1.2 Variable assignment
- 6.1.1.3 Logical truth / result
- 6.1.2.1 Correctness of ( Ant)
- 6.1.2.2 Correctness of ( Ann )
- 6.1.2.3 Correctness of ( FU)
- 6.1.2.4 Correctness of ( KD)
- 7.1 Example 1
- 7.2 Example 2
Notations and conventions
In this article, the following symbols are used:
- ... ( Sets of formulas )
- ... ( Formulas of predicate logic )
- ... ( Sign of Herleitungsbeziehung )
- ... ( Sign of the relation of logical truth / order)
- ... ( Negation sign )
- ... ( Adjunktionszeichen )
- ... ( Existential )
- ... ( Brackets as auxiliary character for more clarity)
- ... (Designation for the extension of a set of formulas )
- ... ( Sign of model)
- ... ( Characters for variable assignment function)
The following conventions are introduced:
- By means of various rules can transform the other connectives in formulas, which then included only and. The following transformation rules:
Of these transformations, use is made in the examples.
Introduction
The sequent calculus serves to represent the procedure for mathematical theorem proving as accurately as possible. Part of this method of proof is that at any point of the proof Additional requirements may be introduced, which then come to the conclusion either or but can be eliminated again.
The basic unit of the sequent calculus is a string ( a sequence ) from variables that are each expressions of the considered logical system; eg for expressions of a first-order language. Such a sequence is denoted by
Or shorter with
Wherein represents the sequence of expressions. The idea here is that the conditions are in and the last term refers to the implication of these conditions. The conditions are also called antecedent and the conclusion as consequent. While the version shown here, the calculus of the succedent formula consists of only one, to let other variants, including Gentzen's LK, any number of formulas in the succedent.
The sequent calculus is concerned with the derivation of sequences. Is there a derivation in the calculus sequence, then we also write
Definition: The term is called derivable from ( short ), if there is with.
The sequences of rules: General shape
The following are the rules for the sequent calculus of classical first-order logic are listed. Sequences have rules while the general shape
Above the stroke already are derived sequences and below the sequence derived therefrom.
Other notation
Sequences rules can be found in the literature in the form
Or as
Noted.
Rules of the sequent calculus of first-order predicate logic with identity
The rules of the sequent calculus of first-order predicate logic with identity can be divided into the following groups:
Principles Junktorenregeln, quantifier and identity rules.
Basic rules
The basic rules are the Antezedensregel and acceptance rule.
Antezedensregel
Wherein:
In words: One can easily add assumptions.
Acceptance rule
Wherein:
In words: One can conclude from the same assumptions.
Junktorenregeln
The Junktorenregeln include the case distinction, the contradiction, the Adjunktionseinführung in the antecedent and the consequent in Adjunktionseinführung.
Case distinction
In words: If one can derive the one hand, assuming the other hand, assuming, one may, without any assumption about or having to do close to.
Contradiction
In words: when leads to a contradiction, then it may be concluded on.
Adjunktionseinführung in the antecedent
In words: the form of disjunctions in the antecedent can be used in two ways - on the one hand in the case and on the other hand in the case.
Adjunktionseinführung the consequent
In words: One must always weaken the consequent by a Adjunktionseinführung.
Quantifier
The quantifier rules are introduced in the existence and the existence consequent introduction in the antecedent.
Existence launch in consequent
In words: If you can not derive from the fact that t has expressed a property, then one may also suggest that something exists which has a property that is expressed by.
Existence launch in antecedent
When y is not found free in the sequence.
Identity rules
The identity rules are reflexivity and the substitution rule.
Reflexivity
In words, the equivalence relation on the object domain D is reflexive.
Substitution rule
In words: the establishment of identicals in Identical.
Useful derivations
With the above stated rules of the sequent calculus some more useful rules are now derived in finitely many steps. To distinguish between the above ground rules they also mean derived rules. (Recall that the derivation is equivalent to manipulation sequences by applying the rules. ) This once derived rules can then be used without any problems, that is, it is enough to show their derivation here once. Here, the following rules are proved: the law of excluded middle, the triviality of the chain end, the contrapositive and the disjunctive syllogism. For notation: Each derivation is divided into three columns. In the left column is the numbering of the individual modifications. They are useful for an unequivocal reference by other modifications. The middle column contains the new modification with a sequence of sequences as a result. The right column contains the information such as the sequence has been reached in the middle column. The rule is written in brackets, and possibly initiated by a colon ( to be read as " used up") that are relevant for the result line numbers are listed. Example: " ( Ant): 1st, 2nd " is read as " Antezedensregel applied to line one and two ."
Law of excluded middle
Derivation:
Triviality
Derivation:
Chain end
Derivation:
Note: In this derivation the rule ( Triv ) was used. From this example you can see that a rule needs to be merely derived once error-free; as a result they can be used as an abbreviation. By using the rule ( Triv ) five Herleitungsschritte were omitted (namely exactly the five steps that you needed to ( Triv ) derive ).
Contraposition
Derivation of ( KP1 ) (( KP2 ) - ( KP4 ) Analog):
Disjunctive syllogism
Derivation:
Properties of the sequent calculus
Correctness
The correctness theorem is as follows:
For all sets of formulas and formulas applies: If, then.
The correctness of the sequent calculus is thus shown to be shown for each rule of the sequent calculus that it is correct, that is, each model and variable assignment s that make the premises generally true, their consequence make it true. All proofs can be taken together then give the proof of the correctness theorem.
Definitions
In order to show the correctness theorem, previously still need to " model ", " variable assignments " and " make true " (logical truth ) can be defined.
Model
A model is an ordered pair, so that:
Variable assignment
A variable assignment s about a model is a function.
Logical truth / result
For all formulas and all sets of formulas: follows logically from ( short ) iff for all models and all variable assignments s over the following applies: If, then. ( In other words: If there which make it true, is made true by the same. )
Correctness of the rules of the sequent calculus
The correctness of the rules of the sequent calculus, one can show by showing the logical truth of the rules. It is based on the definition of logical truth / order. Now it is shown that each rule of the sequent calculus is logically true. ( These do not show all the evidence. It is enough merely to outline a few. The remaining proofs are similar in structure. )
Correctness of ( Ant)
Assuming that is correct, that is. Let be a set of formulas, so that:. Be chosen arbitrarily, so that:. Then, also, and, according to condition also. It follows. So is correct.
Correctness of ( Ann )
If, then applies. Thus is correct.
Correctness of ( FU)
Suppose and are correct, that is, and. Be chosen arbitrarily, so that:.
Case 1:. Then and therefore, by assumption.
Case 2:. Then. Then and therefore, by assumption.
In both cases. Thus is correct.
Correctness of ( KD)
Suppose and. Then for all with:
And. There will be no, so that:. Then for all with. Thus applies and thus is correct.
If one has additionally proven the remaining rules, so its correctness shown, the correctness theorem is proved and it may be said: If a formula derivable in the sequent calculus, this formula is logically true.
Completeness
The calculus is also still fully. That is, it applies:
For all sets of formulas and formulas applies: If, then.
Intuitively, this means that all true sequences using the above-mentioned rules can be derived.
Examples
Finally, two examples are still to be demonstrated with the sequent calculus.
Example 1
Derivation:
Example 2
Derivation: