In der Probetheorie und mathematischen Logik ist folgende Rechnung eine Familie von formellen Systemen, die einen bestimmten Stil der Schlussfolgerung und bestimmte formelle Eigenschaften teilen. Die ersten folgenden Rechnungen, Systeme LK und LJ, wurden von Gerhard Gentzen 1934 als ein Werkzeug eingeführt, um natürlichen Abzug in der Logik der ersten Ordnung (in klassischen und intuitionistic Versionen, beziehungsweise) zu studieren. Der so genannte "Hauptlehrsatz von Gentzen" (Hauptsatz) über LK und LJ war der Kürzungsbeseitigungslehrsatz, ein Ergebnis mit weit reichenden meta-theoretischen Folgen einschließlich der Konsistenz. Gentzen hat weiter die Macht und Flexibilität dieser Technik ein paar Jahre später demonstriert, ein Kürzungsbeseitigungsargument anwendend, um einen (transfiniten) Beweis der Konsistenz der Arithmetik von Peano in der überraschenden Antwort auf die Unvollständigkeitslehrsätze von Gödel zu geben. Seit dieser frühen Arbeit sind folgende Rechnungen (hat auch Systeme von Gentzen genannt), und die Gesamtkonzepte in Zusammenhang mit ihnen in den Feldern der Probetheorie, der mathematischen Logik und des automatisierten Abzugs weit angewandt worden.

Einführung

Eine Weise, verschiedene Stile von Abzug-Systemen zu klassifizieren, soll auf die Form von Urteilen im System schauen, d. h., welche Dinge als der Beschluss (U-Boot) Beweis erscheinen können. Die einfachste Urteil-Form wird in Hilbert-artigen Abzug-Systemen verwendet, wo ein Urteil die Form hat

:

wo jede Formel der ersten Ordnungslogik ist (oder was für die Logik, gilt das Abzug-System für, z.B, Satzrechnung oder eine höherwertige Logik oder eine modale Logik). Die Lehrsätze sind jene Formeln, die als das Endurteil in einem gültigen Beweis erscheinen. Ein Hilbert-artiges System braucht keine Unterscheidung zwischen Formeln und Urteilen; wir machen denjenigen hier allein zum Vergleich mit den Fällen, die folgen.

Der für die einfache Syntax eines Hilbert-artigen Systems bezahlte Preis ist, dass ganze formelle Beweise dazu neigen, äußerst lang zu werden. Konkrete Argumente über Beweise in solch einem System appellieren fast immer an den Abzug-Lehrsatz. Das führt zur Idee, des Abzug-Lehrsatzes als eine formelle Regel im System einzuschließen, das im natürlichen Abzug geschieht. Im natürlichen Abzug haben Urteile die Gestalt

:

wo 's und wieder Formeln sind und. In Wörtern besteht ein Urteil aus einer Liste (vielleicht leer) Formeln auf der linken Seite eines Drehkreuz-Symbols"", mit einer einzelnen Formel auf der rechten Seite. Die Lehrsätze sind jene solche Formeln, der (mit einer leeren linken Seite) der Beschluss eines gültigen Beweises ist.

(In einigen Präsentationen des natürlichen Abzugs werden der s und das Drehkreuz ausführlich nicht niedergeschrieben; stattdessen wird eine zweidimensionale Notation, aus der sie abgeleitet werden können, verwendet).

Die Standardsemantik eines Urteils im natürlichen Abzug ist, dass er behauptet, dass, wann auch immer, alle usw. wahr sind, auch wahr sein wird. Die Urteile

:sind

des starken Gefühls gleichwertig, dass ein Beweis jedes zu einem Beweis vom anderen erweitert werden kann.

Schließlich verallgemeinert folgende Rechnung die Form eines natürlichen Abzug-Urteils zu

:

ein syntaktischer Gegenstand hat eine Folge genannt. Die Formeln auf der linken Seite des Drehkreuzes werden das vorangegangene Ereignis genannt, und die Formeln auf der Rechte werden den succedent genannt; zusammen werden sie cedents genannt. Wieder, und sind Formeln, und und sind natürliche Zahlen, d. h. die linke Seite oder die rechte Seite (oder keiner oder beide) können leer sein. Als im natürlichen Abzug sind Lehrsätze diejenigen, wo der Beschluss eines gültigen Beweises ist. Die leere Folge, beide cedents leer habend, wird definiert, um falsch zu sein.

Die Standardsemantik einer Folge ist eine Behauptung, dass, wann auch immer jeder wahr ist, mindestens ein auch wahr sein werden. Eine Weise, das auszudrücken, besteht darin, dass von einem Komma links vom Drehkreuz als gedacht werden sollte "und", und von einem Komma rechts vom Drehkreuz als (einschließlich) gedacht werden sollte "oder". Die Folgen

:sind des starken Gefühls gleichwertig, dass ein Beweis jedes zu einem Beweis vom anderen erweitert werden kann.

Auf den ersten Blick kann diese Erweiterung der Urteil-Form scheinen, eine fremde Komplikation zu sein — es wird durch einen offensichtlichen Fehler des natürlichen Abzugs nicht motiviert, und es ist am Anfang verwirrend, dass das Komma scheint, völlig verschiedene Dinge auf den zwei Seiten des Drehkreuzes zu bedeuten. Jedoch, in einem klassischen Zusammenhang die Semantik der folgenden Dose auch (durch die Satztautologie), irgendein als ausgedrückt werden

:

(mindestens ein, Wie, oder einer des Bakkalaureus der Naturwissenschaften falsch ist, ist wahr), oder als

:

(es kann nicht der Fall sein, dass ganzer, Wie wahr sind und der ganze Bakkalaureus der Naturwissenschaften, falsch ist). In diesen Formulierungen ist der einzige Unterschied zwischen Formeln auf beiden Seiten des Drehkreuzes, dass eine Seite verneint wird. So entspricht das Tauschen abgereist direkt in einer Folge zum Verneinen von allen konstituierenden Formeln. Das bedeutet, dass eine Symmetrie wie die Gesetze von De Morgan, der sich als logische Ablehnung auf dem semantischen Niveau äußert, direkt in eine nach links richtige Symmetrie von Folgen — und tatsächlich übersetzt, sind die Interferenzregeln in der folgenden Rechnung, um sich mit Verbindung () zu befassen, Spiegelimages von denjenigen, die sich mit Trennung () befassen.

Viele Logiker finden, dass diese symmetrische Präsentation eine tiefere Scharfsinnigkeit in der Struktur der Logik anbietet als andere Stile des Probesystems, wo die klassische Dualität der Ablehnung nicht als offenbar in den Regeln ist.

Das System LK

Diese Abteilung führt die Regeln der folgenden Rechnung LK ein (der für "logistischer klassischer Kalkül" kurz ist), wie eingeführt, durch Gentzen 1934.

Ein (formeller) Beweis in dieser Rechnung ist eine Folge von Folgen, wo jede der Folgen von Folgen ableitbar ist, die früher in der Folge durch das Verwenden von einer der Regeln unten scheinen.

Interferenzregeln

Die folgende Notation wird verwendet:

• bekannt als das Drehkreuz, trennt die Annahmen links von den Vorschlägen rechts

• und zeigen Sie Formeln der Prädikat-Logik der ersten Ordnung an (man kann auch das auf die Satzlogik einschränken),

• und sind (vielleicht leer) Folgen von Formeln begrenzt (tatsächlich, die Ordnung von Formeln sind nicht von Bedeutung; sieh Paragraph Strukturregeln), genannt Zusammenhänge,
• wenn auf dem verlassenen die Folge von Formeln verbindend (alle angenommen betrachtet wird, zur gleichen Zeit zu halten),
• während rechts von die Folge von Formeln abtrennend betrachtet wird (mindestens eine der Formeln müssen für jede Anweisung von Variablen halten),

• zeigt einen willkürlichen Begriff, an

• und zeigen Sie Variablen, an

• zeigt die Formel an, die durch das Auswechseln gegen den Begriff jedes freie Ereignis der Variable in der Formel, erhalten wird

wie man

• sagt, kommt eine Variable frei innerhalb einer Formel vor, wenn sie außerhalb des Spielraums von quantifiers vorkommt oder.

• und treten Sie für Schwächung Link/richtig, und für die Zusammenziehung, und und für die Versetzung ein.

</td>

\cfrac {\\Gamma \vdash \Delta, ein \qquad A, \Sigma \vdash \Pi} {\\Gamma, \Sigma \vdash \Delta, \Pi} \quad (\mathit {Kürzung})

</Mathematik></td>

</tr>

</Mathematik></td> </Mathematik></td></tr> </Mathematik></td> </Mathematik></td></tr> </Mathematik></td> </Mathematik></td></tr>

\cfrac {\\Gamma \vdash A, \Delta \qquad \Sigma, B \vdash \Pi} {\\Gamma, \Sigma, A\rightarrow B \vdash \Delta, \Pi} \quad ({\\rightarrow} L)

</Mathematik></td>

\cfrac {\\Gamma, ein \vdash B, \Delta} {\\Gamma \vdash ein \rightarrow B, \Delta} \quad ({\\rightarrow} R)

</Mathematik></td></tr>

\cfrac {\\Gamma \vdash A, \Delta} {\\Gamma, \lnot ein \vdash \Delta} \quad ({\\lnot} L)

</Mathematik></td>

\cfrac {\\Gamma, ein \vdash \Delta} {\\Gamma \vdash \lnot A, \Delta} \quad ({\\lnot} R)

</Mathematik></td></tr>

\cfrac {\\Gamma, [t/x] \vdash \Delta} {\\Gamma, \forall x Ein \vdash \Delta} \quad ({\\forall} L)

</Mathematik></td>

\cfrac {\\Gamma \vdash [y/x], \Delta} {\\Gamma \vdash \forall x A, \Delta} \quad ({\\forall} R)

</Mathematik></td></tr>

\cfrac {\\Gamma, [y/x] \vdash \Delta} {\\Gamma, \exist x Ein \vdash \Delta} \quad (bestehen {\\} L)

</Mathematik></td>

\cfrac {\\Gamma \vdash [t/x], \Delta} {\\Gamma \vdash \exist x A, \Delta} \quad (bestehen {\\} R)

</Mathematik></td></tr>

\cfrac {\\Gamma \vdash \Delta} {\\Gamma, Ein \vdash \Delta} \quad (\mathit {WL})

</Mathematik></td>

\cfrac {\\Gamma \vdash \Delta} {\\Gamma \vdash A, \Delta} \quad (\mathit {WR})

</Mathematik></td></tr>

\cfrac {\\Gamma, A, ein \vdash \Delta} {\\Gamma, ein \vdash \Delta} \quad (\mathit {KL.})

</Mathematik></td>

\cfrac {\\Gamma \vdash A, A, \Delta} {\\Gamma \vdash A, \Delta} \quad (\mathit {CR})

</Mathematik></td></tr>

\cfrac {\\Gamma_1, A, B, \Gamma_2 \vdash \Delta} {\\Gamma_1, B, A, \Gamma_2 \vdash \Delta} \quad (\mathit {PL})

</Mathematik></td>

\cfrac {\\Gamma \vdash \Delta_1, A, B, \Delta_2} {\\Gamma \vdash \Delta_1, B, A, \Delta_2} \quad (\mathit {PR})

</Mathematik></td></tr></Tisch>

Beschränkungen: In den Regeln und muss die Variable nicht frei innerhalb vorkommen und. Wechselweise muss die Variable nirgends in den jeweiligen niedrigeren Folgen erscheinen.

Eine intuitive Erklärung

Die obengenannten Regeln können in zwei Hauptgruppen geteilt werden: logische und strukturelle. Jede der logischen Regeln führt eine neue logische Formel entweder links oder rechts vom Drehkreuz ein. Im Gegensatz funktionieren die Strukturregeln auf der Struktur der Folgen, die genaue Gestalt der Formeln ignorierend. Die zwei Ausnahmen zu diesem allgemeinen Schema sind das Axiom der Identität (I) und die Regel (der Kürzung).

Obwohl festgesetzt, auf eine formelle Weise berücksichtigen die obengenannten Regeln, dass ein sehr intuitiver in Bezug auf die klassische Logik liest., Denken Sie zum Beispiel, die Regel (L). Es sagt, dass, wann auch immer man beweisen kann, dass Δ aus einer Folge von Formeln geschlossen werden kann, die A dann enthalten, man auch Δ aus der (stärkeren) Annahme schließen kann, die AB hält. Ebenfalls stellt die Regel (¬ R) fest, dass, wenn Γ und A genügen, um Δ zu schließen, dann vom Γ allein kann entweder noch aufhören, Δ oder A falsch sein müssen, d. h. ¬ A hält. Alle Regeln können auf diese Weise interpretiert werden.

Für eine Intuition über die Quantifier-Regeln, denken Sie die Regel (R). Natürlich ist das Beschließen, dass x A gerade von der Tatsache hält, dass [y/x] wahr ist, nicht im Allgemeinen möglich. Wenn, jedoch, die Variable y anderswohin nicht erwähnt wird (d. h. sie noch frei gewählt werden kann, ohne die anderen Formeln zu beeinflussen), dann kann man annehmen, der [y/x] für jeden Wert von y hält. Die anderen Regeln sollten dann ziemlich aufrichtig sein.

Anstatt die Regeln als Beschreibungen für gesetzliche Abstammungen in der Prädikat-Logik anzusehen, kann man sie auch als Instruktionen für den Aufbau eines Beweises für eine gegebene Behauptung betrachten. In diesem Fall können die Regeln von unten nach oben gelesen werden; zum Beispiel sagt (R), dass, um zu beweisen, dass AB aus den Annahmen Γ und Σ folgt, es genügt, um zu beweisen, dass A aus Γ geschlossen werden kann und B aus Σ beziehungsweise geschlossen werden kann. Bemerken Sie, dass, in Anbetracht eines vorangegangenen Ereignisses, es nicht klar ist, wie das in Γ und Σ gespalten werden soll. Jedoch gibt es nur begrenzt viele Möglichkeiten, überprüft zu werden, da das vorangegangene Ereignis durch die Annahme begrenzt ist. Das illustriert auch, wie Probetheorie als das Funktionieren auf Beweisen auf eine kombinatorische Mode angesehen werden kann: Gegebene Beweise sowohl für A als auch für B, man kann einen Beweis für AB bauen.

Wenn

sie nach einem Beweis suchen, bieten die meisten Regeln mehr oder weniger direkte Rezepte dessen an, wie man das tut. Die Regel der Kürzung ist verschieden: Es stellt fest, dass, wenn eine Formel A geschlossen werden kann und diese Formel auch als eine Proposition dienen kann, um andere Behauptungen zu schließen, dann kann die Formel A "ausgeschnitten" werden, und die jeweiligen Abstammungen werden angeschlossen. Wenn es einen Beweis von unten nach oben baut, schafft das das Problem, zu schätzen (da es überhaupt unten nicht erscheint). Der Kürzungsbeseitigungslehrsatz ist so für die Anwendungen der folgenden Rechnung im automatisierten Abzug entscheidend: Es stellt fest, dass der ganze Gebrauch der Kürzungsregel von einem Beweis beseitigt werden kann, andeutend, dass jede nachweisbare Folge ein Beweis ohne Kürzung gegeben werden kann.

Die zweite Regel, die etwas speziell ist, ist das Axiom der Identität (I). Das intuitive Lesen davon ist offensichtlich: Jede Formel bewährt sich. Wie die Kürzungsregel ist das Axiom der Identität etwas überflüssig: Die Vollständigkeit von anfänglichen Atomfolgen stellt fest, dass die Regel auf Atomformeln ohne jeden Verlust von provability eingeschränkt werden kann.

Bemerken Sie, dass alle Regeln Spiegelbegleiter haben, außer denjenigen für die Implikation. Das widerspiegelt die Tatsache, dass die übliche Sprache der Logik der ersten Ordnung nicht einschließt, "wird durch das" Bindewort nicht einbezogen, das der der Implikation Doppel-De Morgan sein würde. Das Hinzufügen solch eines Bindewortes mit seinen natürlichen Regeln würde die Rechnung völlig nach links richtig symmetrisch machen.

Beispiel-Abstammungen

Hier ist die Abstammung"", bekannt als

das Gesetz der ausgeschlossenen Mitte (tertium nicht datur in Latein).

(Ich)

</Mathematik> </td>

</tr>

Ein \vdash ein

</Mathematik> </td> </tr>

(\lnot R)

</Mathematik> </td> </tr>

\vdash \lnot A, ein

</Mathematik> </td> </tr>

(\or R_2)

</Mathematik> </td> </tr>

\vdash ein \or \lnot A, ein

</Mathematik> </td> </tr>

(PR)

</Mathematik> </td> </tr>

\vdash A, ein \or \lnot ein

</Mathematik> </td> </tr>

(\or R_1)

</Mathematik> </td> </tr>

\vdash ein \or \lnot A, ein \or \lnot ein

</Mathematik> </td> </tr>

(CR)

</Mathematik> </td> </tr>

\vdash ein \or \lnot ein

</Mathematik> </td> </tr> </tr></Tisch>

Als nächstes ist der Beweis einer einfachen Tatsache, die quantifiers einschließt. Bemerken Sie, dass das gegenteilige nicht wahr ist, und seine Unehrlichkeit gesehen werden kann, wenn man versucht, es von unten nach oben abzuleiten, weil eine vorhandene freie Variable im Ersatz in den Regeln nicht verwendet werden kann und.

(Ich) </Mathematik> </td> </tr>

p (x, y) \vdash p (x, y)

</Mathematik> </td> </tr>

(\forall L)

</Mathematik> </td> </tr>

\forall x \left (p (x, y) \right) \vdash p (x, y)

</Mathematik> </td> </tr>

(\exists R)

</Mathematik> </td> </tr>

\forall x \left (p (x, y) \right) \vdash \exists y \left (p (x, y) \right)

</Mathematik> </td> </tr>

(\exists L)

</Mathematik> </td> </tr>

\exists y \left (\forall x \left (p (x, y) \right) \right) \vdash \exists y \left (p (x, y) \right)

</Mathematik> </td> </tr>

(\forall R)

</Mathematik> </td> </tr>

\exists y \left (\forall x \left (p (x, y) \right) \right) \vdash \forall x \left (\exists y \left (p (x, y) \right) \right)

</Mathematik> </td> </tr> </tr></Tisch>

</klein>

Für etwas Interessanteres werden wir uns erweisen. Es ist aufrichtig, um die Abstammung zu finden, die die Nützlichkeit von LK im automatisierten Beweis veranschaulicht.

(Ich) </Mathematik> </td> </tr> Ein \vdash ein

</Mathematik> </td>

</tr> (\lnot R) </Mathematik> </td> </tr> \vdash \lnot A, ein </Mathematik> </td> </tr> (PR) </Mathematik> </td> </tr>

\vdash A, \lnot ein

</Mathematik> </td> </tr> </tr></Tisch>

</td>

(Ich) </Mathematik> </td> </tr>

B \vdash B

</Mathematik> </td> </tr> </tr></Tisch> (Ich) </Mathematik> </td> </tr>

C \vdash C

</Mathematik> </td> </tr> </tr></Tisch> </td>

</tr>

</Tisch>

</td>

(\or L)

</Mathematik> </td> </tr>

B \or C \vdash B, C

</Mathematik> </td> </tr> (PR) </Mathematik> </td> </tr>

B \or C \vdash C, B

</Mathematik> </td> </tr>

(\lnot L)

</Mathematik> </td> </tr>

B \or C, \lnot C \vdash B

</Mathematik> </td> </tr> </tr></Tisch> </td> (Ich) </Mathematik> </td> </tr>

\lnot ein \vdash \lnot ein

</Mathematik> </td> </tr> </tr></Tisch> </td> </tr> </Tisch> </td>

(\rightarrow L)

</Mathematik> </td> </tr>

\left (B \or C \right), \lnot C, \left (B \rightarrow \lnot ein \right) \vdash \lnot ein

</Mathematik> </td> </tr>

(\and L_1)

</Mathematik> </td> </tr>

\left (B \or C \right), \lnot C, \left (\left (B \rightarrow \lnot ein \right) \and \lnot C \right) \vdash \lnot ein

</Mathematik> </td> </tr>

(PL)

</Mathematik> </td> </tr>

\left (B \or C \right), \left (\left (B \rightarrow \lnot ein \right) \and \lnot C \right), \lnot C \vdash \lnot ein

</Mathematik> </td> </tr>

(\and L_2)

</Mathematik> </td> </tr>

\left (B \or C \right), \left (\left (B \rightarrow \lnot ein \right) \and \lnot C \right), \left (\left (B \rightarrow \lnot ein \right) \and \lnot C \right) \vdash \lnot ein

</Mathematik> </td> </tr>

(KL.)

</Mathematik> </td> </tr>

\left (B \or C \right), \left (\left (B \rightarrow \lnot ein \right) \and \lnot C \right) \vdash \lnot ein

</Mathematik> </td> </tr> (PL) </Mathematik> </td> </tr>

\left (\left (B \rightarrow \lnot ein \right) \and \lnot C \right), \left (B \or C \right) \vdash \lnot ein

</Mathematik> </td> </tr> </tr></Tisch> </td> </tr> </Tisch> </td> (\rightarrow L) </Mathematik> </td> </tr>

\left (\left (B \rightarrow \lnot ein \right) \and \lnot C \right), \left (ein \rightarrow \left (B \or C \right) \right) \vdash \lnot A, \lnot ein

</Mathematik> </td> </tr> (CR) </Mathematik> </td> </tr>

\left (\left (B \rightarrow \lnot ein \right) \and \lnot C \right), \left (ein \rightarrow \left (B \or C \right) \right) \vdash \lnot ein

</Mathematik> </td> </tr> (PL) </Mathematik> </td> </tr>

\left (ein \rightarrow \left (B \or C \right) \right), \left (\left (B \rightarrow \lnot ein \right) \and \lnot C \right) \vdash \lnot ein

</Mathematik> </td> </tr>

(\rightarrow R)

</Mathematik> </td> </tr>

\left (ein \rightarrow \left (B \or C \right) \right) \vdash \left (\left (\left (B \rightarrow \lnot ein \right) \and \lnot C \right) \rightarrow \lnot ein \right)

</Mathematik> </td> </tr> (\rightarrow R) </Mathematik> </td> </tr>

\vdash \left (\left (ein \rightarrow \left (B \or C \right) \right) \rightarrow \left (\left (\left (B \rightarrow \lnot ein \right) \and \lnot C \right) \rightarrow \lnot ein \right) \right)

</Mathematik> </td> </tr> </tr></Tisch>

Diese Abstammungen betonen auch die ausschließlich formelle Struktur der folgenden Rechnung. Zum Beispiel folgen die logischen Regeln, wie definiert, oben immer einer Formel sofort neben dem Drehkreuz, solch, dass die Versetzungsregeln notwendig sind. Bemerken Sie jedoch, dass das teilweise ein Kunsterzeugnis der Präsentation im ursprünglichen Stil von Gentzen ist. Eine allgemeine Vereinfachung ist mit dem Gebrauch von Mehrsätzen von Formeln in der Interpretation der Folge, aber nicht den Folgen verbunden, das Bedürfnis nach einer ausführlichen Versetzungsregel beseitigend. Das entspricht Verschiebung commutativity Annahmen und Abstammungen außerhalb der folgenden Rechnung, wohingegen LK es innerhalb des Systems selbst einbettet.

Strukturregeln

Die Strukturregeln verdienen etwas zusätzliche Diskussion.

Schwächung (W) erlaubt die Hinzufügung willkürlicher Elemente zu einer Folge. Intuitiv wird dem im vorangegangenen Ereignis erlaubt, weil wir immer Annahmen zu unserem Beweis, und im succedent hinzufügen können, weil wir immer alternative Beschlüsse berücksichtigen können.

Zusammenziehung (C) und Versetzung (P) versichert dass weder der Auftrag (P) noch die Vielfältigkeit von Ereignissen (C) von Elementen der Folge-Sachen. So hat man statt Folgen gekonnt, auch Sätze denken.

Die Extraanstrengung, Folgen zu verwenden, wird jedoch gerechtfertigt, da Teil oder alle Strukturregeln weggelassen werden können. So tuend, erhält man die so genannte Substrukturlogik.

Eigenschaften des Systems LK

Wie man

zeigen kann, ist dieses System von Regeln sowohl Ton als auch abgeschlossen in Bezug auf die Logik der ersten Ordnung, d. h. eine Behauptung folgt semantisch von einer Reihe von Propositionen iff die Folge kann durch die obengenannten Regeln abgeleitet werden.

In der folgenden Rechnung ist die Regel der Kürzung zulässig. Dieses Ergebnis wird auch den Hauptsatz von Gentzen ("Hauptlehrsatz") genannt.

Varianten

Die obengenannten Regeln können auf verschiedene Weisen modifiziert werden:

Geringe Strukturalternativen

Es gibt etwas Freiheit der Wahl bezüglich der technischen Details dessen, wie Folgen und Strukturregeln formalisiert werden. So lange jede Abstammung in LK in eine Abstammung mit den neuen Regeln und umgekehrt effektiv umgestaltet werden kann, können die modifizierten Regeln noch LK genannt werden.

Zuallererst, wie oben erwähnt, können die Folgen angesehen werden, um aus Sätzen oder Mehrsätzen zu bestehen. In diesem Fall sind die Regeln für das Permutieren und (wenn sie Sätze verwenden) das Zusammenziehen von Formeln, veraltet.

Die Regel der Schwächung wird zulässig werden, wenn das Axiom (I) geändert, solch wird, dass jede Folge der Form geschlossen werden kann. Das bedeutet, dass sich das in jedem Zusammenhang erweist. Jede Schwächung, die in einer Abstammung erscheint, kann dann direkt am Anfang durchgeführt werden. Das kann eine günstige Änderung sein, wenn es Beweise von unten nach oben baut.

Unabhängig von diesen kann man auch den Weg ändern, auf den Zusammenhänge innerhalb der Regeln gespalten werden: In den Fällen (R) (L) und (L) wird der linke Zusammenhang irgendwie in Γ und Σ gespalten, wenn man aufwärts geht. Da Zusammenziehung die Verdoppelung von diesen berücksichtigt, kann man annehmen, dass der volle Zusammenhang in beiden Zweigen der Abstammung verwendet wird. Auf diese Weise versichert man, dass keine wichtigen Propositionen im falschen Zweig verloren werden. Mit der Schwächung können die irrelevanten Teile des Zusammenhangs später beseitigt werden.

Substrukturlogik

Wechselweise kann man einschränken oder den Gebrauch von einigen der Strukturregeln verbieten. Das gibt eine Vielfalt von Substrukturlogiksystemen nach. Sie sind allgemein schwächer als LK (d. h. sie haben weniger Lehrsätze), und so nicht abgeschlossen in Bezug auf die Standardsemantik der Logik der ersten Ordnung. Jedoch haben sie andere interessante Eigenschaften, die zu Anwendungen in der theoretischen Informatik und künstlichen Intelligenz geführt haben.

Intuitionistic folgende Rechnung: System LJ

Überraschend genügen einige kleine Änderungen in den Regeln von LK, um es in ein Probesystem für die intuitionistic Logik zu verwandeln. Zu diesem Zweck muss man auf Folgen mit genau einer Formel auf der rechten Seite einschränken, und die Regeln modifizieren, diesen invariant aufrechtzuerhalten. Zum Beispiel wird (L) wie folgt wiederformuliert (wo C eine willkürliche Formel ist):

:

\cfrac {\\Gamma, ein \vdash C \qquad \Sigma, B \vdash C\{\\Gamma, \Sigma, ein \or B \vdash C\\quad ({\\oder} L)

</Mathematik>

Das resultierende System wird LJ genannt. Es ist gesund und in Bezug auf die intuitionistic Logik abgeschlossen und lässt einen ähnlichen Kürzungsbeseitigungsbeweis zu.

Siehe auch

• Entschlossenheit (Logik)

Referenzen

Links

• Eine kurze Ablenkung: Folgende Rechnung