Substrukturlogik

2023 Autor: Noah Black | [email protected]. Zuletzt bearbeitet: 2023-11-26 16:05

Eintragsnavigation

• Eintragsinhalt
• Literaturverzeichnis
• Akademische Werkzeuge
• Freunde PDF Vorschau
• Autor und Zitierinfo
• Zurück nach oben

Substrukturlogik

Erstveröffentlichung Di 4. Juli 2000; inhaltliche Überarbeitung Mi 21. Februar 2018

Substrukturlogiken sind nicht-klassische Logiken, die schwächer als die klassische Logik sind, insbesondere aufgrund des Fehlens struktureller Regeln in der klassischen Logik. Diese Logik basiert auf Überlegungen aus den Bereichen Philosophie (relevante Logik), Linguistik (Lambek-Kalkül) und Computer (lineare Logik). Darüber hinaus sind Techniken aus der Substrukturlogik nützlich, um traditionelle Logiken wie die klassische und die intuitionistische Logik zu untersuchen. Dieser Artikel bietet einen kurzen Überblick über das Gebiet der Unterstrukturlogik. Für eine detailliertere Einführung mit Theoremen, Beweisen und Beispielen kann der Leser die Bücher und Artikel in der Bibliographie konsultieren.

• 1. Residuation
• 2. Logik in der Familie
• 3. Beweissysteme
• 4. Semantik
• Literaturverzeichnis
• Akademische Werkzeuge
• Andere Internetquellen
• Verwandte Einträge

1. Residuation

Bei Logik geht es um logische Konsequenzen. Infolgedessen ist die Bedingung aufgrund ihrer engen Verbindung mit logischer Konsequenz ein zentraler Begriff in der Logik. Diese Verbindung wird in der Restbedingung (auch als Abzugssatz bekannt) genau ausgedrückt:

[p, q / vdash r / text {genau dann, wenn} p / vdash q / rightarrow r)

Es heißt, dass (r) aus (p) zusammen mit (q) folgt, wenn (q / rightarrow r) allein aus (p) folgt. Die Gültigkeit des Übergangs von (q) zu (r) (gegeben (p)) wird durch die Bedingung (q / rightarrow r) aufgezeichnet.

Diese Verbindung zwischen Bedingung und Konsequenz wird in Analogie zum mathematischen Fall als Residuation bezeichnet. Betrachten Sie den Zusammenhang zwischen Addition und Subtraktion. (a + b = c) genau dann, wenn (a = c - b). Das resultierende (a) (das ist (c - b)) ist der Rest, der von (c) übrig bleibt, wenn (b) weggenommen wird. Ein anderer Name für diese Verbindung ist der Abzugssatz.

Dort enthält der Zusammenhang zwischen Konsequenz und Bedingung jedoch einen zusätzlichen Faktor. Es gibt nicht nur das Drehkreuz für die logische Konsequenz und die bedingte, codierende Konsequenz innerhalb der Sprache der Sätze, sondern auch das Komma, das die Kombination der Prämissen angibt. Wir haben "(p, q / vdash r)" gelesen, da "(r) zusammen mit (q) aus (p) folgt". Räumlichkeiten zu kombinieren bedeutet, eine Möglichkeit zu haben, sie zusammenzuführen. Aber wie können wir sie zusammen nehmen? Es stellt sich heraus, dass es verschiedene Möglichkeiten gibt, dies zu tun, und somit unterschiedliche Unterstrukturlogiken. Das Verhalten der Prämissenkombination variiert, wenn sich das Verhalten der Bedingung ändert. In dieser Einführung werden wir einige Beispiele dafür betrachten.

1.1 Schwächung

Es ist eine Sache, dass (p) wahr ist. Es ist eine andere Voraussetzung, dass die Bedingung (q / rightarrow p) wahr ist. Wenn jedoch '(rightarrow)' eine materielle Bedingung ist, folgt (q / rightarrow p) aus (p). Aus vielen verschiedenen Gründen möchten wir vielleicht verstehen, wie eine Bedingung ohne diese Schlussfolgerung funktionieren könnte. Dies hängt mit dem Verhalten der Prämissenkombination zusammen, wie diese Demonstration zeigen kann.

) cfrac {p / vdash p} { cfrac {p, q / vdash p} {p / vdash q / rightarrow p}})

Aus dem axiomatischen (p / vdash p) (alles folgt aus sich selbst) schließen wir, dass (p) aus (p) zusammen mit (q) und dann durch Residuation (p / vdash) folgt q / rightarrow p). Wenn wir die Folgerung von (p) nach (q / rightarrow p) ablehnen möchten, lehnen wir entweder die Residuen oder das Identitätsaxiom zu Beginn des Beweises ab oder lehnen den ersten Schritt des Beweises ab. Es ist aufschlussreich zu überlegen, worum es bei dieser letzten Option geht. Hier ist zu leugnen, dass (p) aus (p, q) folgt. Im Allgemeinen müssen wir die Inferenzregel ablehnen, die diese Form hat:

) frac {X / vdash A} {X, Y / vdash A})

Dies nennt man die Regel der Schwächung. Die Regel geht von einer stärkeren Aussage, dass (A) aus (X) folgt, zu einer möglicherweise schwächeren, dass (A) aus (X) zusammen mit (Y) folgt.

Je nach Interpretation der Kombination von Konsequenz und Prämisse haben die Menschen unterschiedliche Gründe für die Ablehnung der Schwächungsregel angegeben. Eines der frühen motivierenden Beispiele ist die Sorge um Relevanz. Wenn die Logik relevant ist (wenn zu sagen ist, dass (p) (q) wahr ist, heißt das zumindest, dass (q) wirklich von (p) abhängt), dann muss das Komma nicht Schwächung nicht befriedigen. Wir können tatsächlich haben, dass (A) von (X) folgt, ohne dass (A) von (X, Y) folgt, denn es muss nicht der Fall sein, dass (A) von (abhängt) X) und (Y) zusammen.

In relevanten Logiken versagt die Schwächungsregel auch auf der anderen Seite, indem wir wünschen, dass dieses Argument auch ungültig ist:

) cfrac {q / vdash q} { cfrac {p, q / vdash q} {p / vdash q / rightarrow q}})

Wiederum kann (q) aus (q) folgen, aber dies bedeutet nicht, dass es aus (p) zusammen mit (q) folgt, vorausgesetzt, dass "zusammen mit" in einer entsprechend starken Bedeutung gemeint ist Sinn. In relevanten Logiken kann der Rückschluss von einer beliebigen Prämisse auf eine logische Wahrheit wie (q / rightarrow q) durchaus fehlschlagen.

1.2 Kommutativität

Wenn der Modus der Prämissenkombination kommutativ ist (wenn etwas, das aus (X, Y) folgt, auch aus (Y, X) folgt), können wir wie folgt argumentieren, indem wir nur das Identitätsaxiom und den Rest verwenden:

) cfrac {p / rightarrow q / vdash p / rightarrow q} { cfrac {p / rightarrow q, p / vdash q} { cfrac {p, p / rightarrow q / vdash q} {p / vdash (p / rightarrow q) rightarrow q}}})

In Ermangelung einer Kommutativität der Prämissenkombination ist dieser Beweis nicht verfügbar. Dies ist ein weiteres einfaches Beispiel für den Zusammenhang zwischen dem Verhalten der Prämissenkombination und dem der Abzüge, an denen die Bedingung beteiligt ist.

Es gibt viele Arten von Bedingungen, für die diese Folgerung fehlschlägt. Wenn "(rightarrow)" modale Kraft hat (wenn es eine Art Konsequenz ausdrückt, in der (p / rightarrow q) wahr ist, wenn unter allen verwandten Umständen, in denen (p) gilt, (q) auch), und wenn "(vdash)" die lokale Konsequenz ausdrückt ((p / vdash q) genau dann, wenn irgendein Modell, unter allen Umständen, unter denen (p) gilt, auch (q)) es schlägt fehl. Es mag wahr sein, dass Greg ein Logiker ist (((p)) und es ist wahr, dass Greg ein Logiker ist, was bedeutet, dass Greg ein Philosoph ist ((p / rightarrow q)) - in verwandten Situationen, in denen Greg ein Logiker ist, er ist ein Philosoph), aber das bedeutet nicht, dass Greg ein Philosoph ist. (Es gibt viele Umstände, unter denen die Folge ((p / rightarrow q)) wahr ist, (q) jedoch nicht.) Wir haben also einen Umstand, in dem (p) wahr ist, ((p / rightarrow q) rightarrow q) jedoch nicht. Das Argument ist ungültig.

Dieses Gegenbeispiel kann auch im Hinblick auf das Verhalten der Prämissenkombination verstanden werden. Wenn wir hier sagen, dass (X, A / vdash B) wahr ist, sagen wir nicht nur, dass (B) unter allen Umständen gilt, unter denen (X) und (A) beide gelten. Wenn wir nach einer echten Folge A (rightarrow) B suchen, wollen wir, dass (B) unter allen (verwandten) Umständen wahr ist, unter denen (A) wahr ist. Also sagt (X, A / vdash B), dass in jeder Möglichkeit, in der (A) wahr ist, (B) auch wahr ist. Diese Möglichkeiten erfüllen möglicherweise nicht alle (X). (In den klassischen Entailment-Theorien sind die Möglichkeiten diejenigen, in denen alles, was in (X) als notwendig erachtet wird, wahr ist.)

Wenn die Prämissenkombination nicht kommutativ ist, kann die Rückhaltung auf zwei Arten erfolgen. Zusätzlich zu der Restbedingungsbedingung, die das Verhalten von (rightarrow) angibt, möchten wir möglicherweise einen neuen Pfeil (leftarrow) wie folgt definieren:

[p, q / vdash r / text {genau dann, wenn} q / vdash r / leftarrow p)

Für den Pfeil von links nach rechts haben wir Modus Ponens in dieser Richtung:

[p / rightarrow q, p / vdash q)

Für den Pfeil von rechts nach links ist modus ponens mit den Prämissen in umgekehrter Reihenfolge nachweisbar:

[p, q / leftarrow p / vdash q)

Dies ist ein Merkmal der Unterstrukturlogik. Wenn wir darauf achten, was passiert, wenn wir nicht alle Strukturregeln vollständig ergänzen, eröffnen sich neue Möglichkeiten. Wir decken zwei Bedingungen unter einer zuvor auf (in intuitionistischer oder klassischer Logik).

Im nächsten Abschnitt sehen wir ein weiteres Beispiel, das eine nicht kommutative Prämissenkombination und diese beiden unterschiedlichen Bedingungen motiviert.

1.3 Assoziativität

Hier ist eine andere Möglichkeit, wie strukturelle Regeln den Beweis beeinflussen. Die Assoziativität der Prämissenkombination liefert den folgenden Beweis:

) cfrac {r / rechter Pfeil p, r / vdash p / \ / p / rechter Pfeil q, p / vdash q} { cfrac {p / rechter Pfeil q, (r / rechter Pfeil p, r) vdash q} { cfrac {(p / rechter Pfeil q, r / rechter Pfeil p), r / vdash q} { cfrac {p / rechter Pfeil q, r / rechter Pfeil p / vdash r / rechter Pfeil q} {p / rechter Pfeil q / vdash (r / rechter Pfeil) p) rightarrow (r / rightarrow q)}}}})

Dieser Beweis verwendet die Schnittregel im obersten Schritt. Die Idee ist, dass Schlussfolgerungen kombiniert werden können. Wenn (X / vdash A) und (Y (A) vdash B) (wobei (Y (A)) eine Struktur von Räumlichkeiten ist, die möglicherweise (A) einmal oder mehrmals enthält), dann (Y (X) vdash B) auch (wobei (Y (X)) die Struktur von Prämissen ist, wobei die Instanzen von (A) durch (X) ersetzt werden). In diesem Beweis ersetzen wir das (p) in (p / rightarrow q, p / vdash q) durch (r / rightarrow p, r) auf der Grundlage der Gültigkeit von (r / rightarrow p, r / vdash p).

1.4 Kontraktion

Ein letztes wichtiges Beispiel ist die Kontraktionsregel, die vorschreibt, wie Räumlichkeiten wiederverwendet werden dürfen. Die Kontraktion ist entscheidend für die Schlussfolgerung von (p / rightarrow q) aus (p / rightarrow (p / rightarrow q)).

) cfrac { matrix { cfrac {p / rightarrow (p / rightarrow q) vdash p / rightarrow (p / rightarrow q)} {p / rightarrow (p / rightarrow q), p / vdash p / rightarrow q } & / cfrac {p / rightarrow q / vdash p / rightarrow q} {p / rightarrow q, p / vdash q}} { cfrac {(p / rightarrow (p / rightarrow q), p), p / vdash q} { cfrac {p / rechter Pfeil (p / rechter Pfeil q), p / vdash q} {p / rechter Pfeil (p / rechter Pfeil q) vdash p / rechter Pfeil q}}})

Diese verschiedenen Beispiele geben Ihnen einen Vorgeschmack darauf, was strukturelle Regeln bewirken können. Strukturelle Regeln beeinflussen nicht nur die Bedingung, sondern wirken sich auch auf andere Konnektiva aus, wie z. B. Konjunktion und Disjunktion (wie wir weiter unten sehen werden) und Negation (Dunn 1993; Restall 2000).

1.5 Struktur rechts vom Drehkreuz

Seit der Einführung von Gentzens sequentiellem Kalkül (Gentzen 1935) wissen wir, dass der Unterschied zwischen klassischer Logik und intuitionistischer Logik auch als Unterschied struktureller Regeln verstanden werden kann. Anstatt Sequenzen der Form (X / vdash A) zu betrachten, in denen wir eine Sammlung von Antezedenzien und eine einzige Konsequenz haben, ist es für die klassische Logik fruchtbar, Sequenzen der Form zu betrachten

[X / vdash Y)

Dabei sind sowohl (X) als auch (Y) Sammlungen von Anweisungen. Die beabsichtigte Interpretation ist, dass aus allen (X) folgt, dass einige der (Y). Mit anderen Worten, wir können nicht alle (X) und keine der (Y) erhalten.

Wenn wir Sequenzen mit mehreren Konsequenzen zulassen und die Regeln in diesen erweiterten Kontext übersetzen, können wir klassische Tautologien ableiten. Zum Beispiel die Ableitung

) cfrac {p / vdash p} { cfrac {p / vdash q, p} { vdash p / rightarrow q, p}})

zeigt, dass entweder (p / rightarrow q) oder (p) gelten muss. Dies ist klassisch gültig (wenn (p) fehlschlägt, (p) falsch ist und Bedingungen mit falschen Antezedenzen wahr sind), aber in der intuitionistischen Logik ungültig. Der Unterschied zwischen klassischer und intuitionistischer Logik kann formal als Unterschied zwischen den Arten der zulässigen Strukturregeln und den Arten von Strukturen verstanden werden, die für die Analyse der logischen Konsequenzen geeignet sind.

2. Logik in der Familie

Es gibt viele verschiedene formale Systeme in der Familie der Unterstrukturlogiken. Diese Logik kann auf unterschiedliche Weise motiviert werden.

2.1 Relevante Logik

Viele Menschen wollten einen Bericht über die logische Gültigkeit geben, in dem die relevanten Bedingungen berücksichtigt werden. Wenn (X, A / vdash B) gilt, muss (X) für (A) irgendwie relevant sein. Die Prämissenkombination wird auf folgende Weise eingeschränkt. Wir können (X / vdash A) haben, ohne auch (X, Y / vdash A) zu haben. Das neue Material (Y) ist möglicherweise für den Abzug nicht relevant. In den 1950er Jahren berichteten Moh (1950), Church (1951) und Ackermann (1956), was eine "relevante" Logik sein könnte. Die Ideen wurden von einer Gruppe von Arbeitern entwickelt, die sich um Anderson und Belnap, ihre Schüler Dunn und Meyer und viele andere drehten. Die kanonischen Referenzen für das Gebiet sind Anderson, Belnap und Dunns zweibändiges Entailment (1975 und 1992). Weitere Einführungen finden sich in Reads Relevant Logic, Dunn and Restalls Relevance Logic (2002),und Mares 'relevante Logik: eine philosophische Interpretation (2004).

2.2 Ressourcenbewusstsein

Dies ist nicht die einzige Möglichkeit, die Prämissenkombination einzuschränken. Girard (1987) führte die lineare Logik als Modell für Prozesse und Ressourcennutzung ein. Die Idee in diesem Abzugskonto ist, dass Ressourcen verwendet werden müssen (damit die Prämissenkombination das Relevanzkriterium erfüllt) und sich nicht auf unbestimmte Zeit erstrecken. Räumlichkeiten können nicht (re) - verwendet werden. Ich könnte also (X, X / vdash A) haben, was besagt, dass ich (X) zweimal verwenden kann, um (A) zu erhalten. Ich habe möglicherweise nicht (X / vdash A), was besagt, dass ich (X) einmal alleine verwenden kann, um (A) zu erhalten. Eine hilfreiche Einführung in die lineare Logik finden Sie in Troelstras Lectures on Linear Logic (1992). Es gibt andere formale Logiken, in denen die Kontraktionsregel (von (X, X / vdash A) bis (X / vdash A)) fehlt. Am bekanntesten unter ihnen sind die vielen geschätzten Logiken von Łukasiewicz. Aufgrund des Curry-Paradoxons besteht ein anhaltendes Interesse an Logik ohne diese Regel (Curry 1977, Geach 1995; siehe auch Restall 1994 in Other Internet Resources).

3. Bestellen

Unabhängig von einer dieser Traditionen betrachtete Joachim Lambek mathematische Modelle von Sprache und Syntax (Lambek 1958, 1961). Die Idee hier ist, dass die Prämissenkombination der Zusammensetzung von Strings oder anderen sprachlichen Einheiten entspricht. Hier unterscheidet sich (X, X) im Inhalt von (X), aber zusätzlich unterscheidet sich (X, Y) von Y, X. Es zählt nicht nur die Anzahl der genutzten Räumlichkeiten, sondern auch deren Reihenfolge. Gute Einführungen in die Lambek-Rechnung (auch kategoriale Grammatik genannt) finden sich in Büchern von Moortgat (1988) und Morrill (1994).

3. Beweissysteme

Wir haben bereits ein Fragment einer Möglichkeit gesehen, die Substrukturlogik in Form von Beweisen darzustellen. Wir haben die Rückstandsbedingung verwendet, die zwei Regeln für die Bedingung enthält, eine zur Einführung einer Bedingung

) cfrac {X, A / vdash B} {X / vdash A / rightarrow B})

und eine andere, um es zu beseitigen.

) cfrac {X / vdash A / rightarrow B / \ / Y / vdash A} {X, Y / vdash B})

Regeln wie diese bilden den Eckpfeiler eines natürlichen Abzugssystems, und diese Systeme stehen für die breite Palette von Substrukturlogiken zur Verfügung. Die Beweistheorie kann jedoch auch auf andere Weise durchgeführt werden. Gentzen-Systeme arbeiten nicht durch Einführen und Entfernen von Konnektiven, sondern durch Einführen sowohl links als auch rechts vom Drehkreuz mit logischer Konsequenz. Wir behalten die Einführungsregel oben bei und ersetzen die Eliminierungsregel durch eine Einführungsregel auf der linken Seite:

) cfrac {X / vdash A / \ / Y (B) vdash C} {Y (A / rechter Pfeil B, X) vdash C})

Diese Regel ist komplexer, hat jedoch den gleichen Effekt wie die Pfeileliminierungsregel: Sie besagt, dass wenn (X) für (A) ausreicht und wenn Sie (B) verwenden (in einem bestimmten Kontext () Y)) um (C) zu beweisen, dann hätten Sie genauso gut (A / rightarrow B) zusammen mit (X) (in demselben Kontext (Y)) verwenden können, um (C) zu beweisen), da (A / rightarrow B) zusammen mit (X) (B) ergibt.

Gentzen-Systeme mit ihren Einführungsregeln links und rechts haben ganz besondere Eigenschaften, die beim Studium der Logik nützlich sind. Da Konnektiva immer in einem Proof eingeführt werden (von oben nach unten gelesen), verlieren Proofs nie an Struktur. Wenn ein Konnektiv nicht im Abschluss eines Beweises erscheint, erscheint er überhaupt nicht im Beweis, da Konnektiva nicht beseitigt werden können.

In bestimmten Unterstrukturlogiken wie der linearen Logik und der Lambek-Rechnung und im Fragment der relevanten Logik (mathbf {R}) ohne Disjunktion kann ein Gentzen-System verwendet werden, um zu zeigen, dass die Logik darin entscheidbar ist Es kann ein Algorithmus gefunden werden, um zu bestimmen, ob ein Argument (X / vdash A) gültig ist oder nicht. Dies erfolgt durch Suchen nach Beweisen für (X / vdash A) in einem Gentzen-System. Da Prämissen dieser Schlussfolgerung keine Sprache enthalten dürfen, die nicht in dieser Schlussfolgerung enthalten ist, und sie keine größere Komplexität aufweisen (in diesen Systemen), gibt es nur eine begrenzte Anzahl möglicher Prämissen. Ein Algorithmus kann prüfen, ob diese den Regeln des Systems entsprechen, und nach Prämissen für diese suchen oder beenden, wenn wir ein Axiom treffen. Auf diese Weise wird die Entscheidbarkeit einiger Unterstrukturlogiken sichergestellt.

In diesem Sinne sind jedoch nicht alle Unterstrukturlogiken entscheidbar. Am bekanntesten ist, dass die relevante Logik (mathbf {R}) nicht entscheidbar ist. Dies liegt zum Teil daran, dass seine Beweistheorie komplexer ist als die anderer substruktureller Logiken. (mathbf {R}) unterscheidet sich von der linearen Logik und dem Lambek-Kalkül durch eine einfache Behandlung von Konjunktion und Disjunktion. Konjunktion und Disjunktion erfüllen insbesondere die Verteilungsregel:

[p / amp (q / vee r) vdash (p / amp q) vee (p / amp r))

Der natürliche Verteilungsnachweis in jedem Beweissystem verwendet sowohl Schwächung als auch Kontraktion, sodass er in der relevanten Logik (mathbf {R}) nicht verfügbar ist, die keine Schwächung enthält. Infolgedessen enthalten Beweistheorien für (mathbf {R}) entweder die Verteilung als primitive Regel oder eine zweite Form der Prämissenkombination (sogenannte Erweiterungskombination im Gegensatz zu der von uns gesehenen intensiven Prämissenkombination), die befriedigt Schwächung und Kontraktion.

In den letzten Jahren wurde viel an der Beweistheorie der klassischen Logik gearbeitet, die von der Erforschung der Substrukturlogik inspiriert und beeinflusst wurde. Die klassische Logik enthält alle Strukturregeln und ist historisch gesehen den neueren Systemen der Substrukturlogik voraus. Wenn es jedoch darum geht, die tiefe Struktur klassischer Beweissysteme zu verstehen (und insbesondere, wenn zwei Ableitungen, die sich auf oberflächliche syntaktische Weise unterscheiden, wirklich unterschiedliche Arten der Darstellung des zugrunde liegenden „Beweises“sind), ist es aufschlussreich, darüber nachzudenken klassische Logik, wie sie durch eine grundlegende Unterstrukturlogik gebildet wird, in der zusätzliche Strukturregeln als Ergänzungen auferlegt werden. Bestimmtes,Es ist klar geworden, dass das, was den klassischen Beweis von seinen Geschwistern unterscheidet, das Vorhandensein der strukturellen Regeln der Kontraktion und Schwächung in ihrer vollständigen Allgemeinheit ist (siehe zum Beispiel Bellin et al. 2006 und die darin zitierte Literatur).

4. Modelltheorie

Während die relevante Logik (mathbf {R}) ein Beweissystem hat, das komplexer ist als die substrukturellen Logiken wie die lineare Logik, bei denen die (Extensions-) Konjunktion über die Disjunktion verteilt ist, ist ihre Modelltheorie insgesamt einfacher. Ein Routley-Meyer-Modell für die relevante Logik (mathbf {R}) besteht aus einer Menge von Punkten (P) mit einer Drei-Stellen-Beziehung (R) auf (P). Eine Bedingung (A / rightarrow B) wird in einer Welt wie folgt bewertet:

(A / rightarrow B) ist genau dann bei (x) wahr, wenn für jedes (y) und (z) wobei (Rxyz), wenn (A) bei / wahr ist (y, B) ist wahr bei (z).

Ein Argument ist in einem Modell nur dann gültig, wenn an einem Punkt, an dem die Prämissen wahr sind, auch die Schlussfolgerung. Das Argument (A / vdash B / rightarrow B) ist ungültig, weil wir möglicherweise einen Punkt (x) haben, an dem (A) wahr ist, an dem (B / rightarrow B) jedoch nicht. Wir können haben, dass (B / rightarrow B) bei (x) nicht wahr ist, indem wir einfach (Rxyz) haben, wobei (B) bei (y) wahr ist, aber nicht bei (z)).

Die Drei-Stellen-Beziehung (R) folgt genau dem Verhalten der Prämissenkombinationsart in der Beweistheorie für eine Substrukturlogik. Für unterschiedliche Logiken können unterschiedliche Bedingungen für (R) gestellt werden. Wenn beispielsweise die Prämissenkombination kommutativ ist, setzen wir eine Symmetriebedingung auf (R) wie folgt: (Rxyz) genau dann, wenn (Ryxz). Die ternäre relationale Semantik bietet uns eine großartige Möglichkeit, das Verhalten von Substrukturlogiken zu modellieren. (Das Ausmaß der Entsprechung zwischen der Beweistheorie und der Algebra der Substrukturlogik und der Semantik ist in Dunns Arbeit zur Gaggle-Theorie (1991) dargestellt und in Restalls Einführung in die Substrukturlogik (2000) zusammengefasst.)

Wenn Konjunktion und Disjunktion das im vorherigen Abschnitt erwähnte Verteilungsaxiom erfüllen, können sie auch direkt modelliert werden: Eine Konjunktion ist an einem Punkt wahr, an dem beide Konjunktionen an diesem Punkt wahr sind, und eine Disjunktion ist an einem Punkt wahr, an dem genau dort ist mindestens eine Disjunktion wahr. Für Logiken wie die lineare Logik ohne das Verteilungsaxiom muss die Semantik komplexer sein, wobei eine andere Klausel für die Disjunktion erforderlich ist, um die Inferenz der Verteilung ungültig zu machen.

Es ist eine Sache, eine Semantik als formales Mittel zur Modellierung einer Logik zu verwenden. Es ist eine andere Möglichkeit, eine Semantik als Interpretationsinstrument zum Anwenden einer Logik zu verwenden. Die Literatur zur Substrukturlogik bietet uns eine Reihe verschiedener Möglichkeiten, wie die ternäre relationale Semantik angewendet werden kann, um die logische Struktur einiger Phänomene zu beschreiben, bei denen die traditionellen Strukturregeln nicht gelten.

Für Logiken wie den Lambek-Kalkül ist die Interpretation der Semantik einfach. Wir können die Punkte als sprachliche Elemente betrachten, und die ternäre Beziehung ist die Verkettungsbeziehung ((Rxyz) genau dann, wenn (x) mit (y) verkettet zu (z) führt.). In diesen Modellen versagen alle strukturellen Regeln für Kontraktion, Schwächung und Permutation, aber die Prämissenkombination ist assoziativ.

Die zeitgenössische Literatur zur sprachlichen Klassifikation erweitert die Lambek-Grundrechnung um reichhaltigere Kombinationsformen, in denen syntaktischere Merkmale modelliert werden können (siehe Moortgat 1995).

Eine weitere Anwendung dieser Modelle ist die Behandlung der Semantik der Funktionsanwendung. Wir können uns die Punkte in einer Modellstruktur sowohl als Funktionen als auch als Daten vorstellen und halten, dass (Rxyz) genau dann gilt, wenn (x) (als Funktion betrachtet) auf (y) (als Daten betrachtet) angewendet wird) ist (z). Herkömmliche Funktionsberichte fördern diese doppelte Verwendung nicht, da Funktionen als "höher" als ihre Ein- oder Ausgänge angesehen werden (beim traditionellen satztheoretischen Funktionsmodell ist eine Funktion (ist) die Menge ihrer Eingabe -ausgabepaare, und so kann es sich niemals als Eingabe nehmen, da Mengen sich nicht als Mitglieder enthalten können). Funktionssysteme, die beispielsweise durch den untypisierten (lambda) - Kalkül modelliert werden, ermöglichen jedoch eine Selbstanwendung. Angesichts dieser Lesart von Punkten in einem Modell,Ein Punkt ist vom Typ (A / rightarrow B), nur wenn immer dann, wenn Eingaben vom Typ (A) verwendet werden, Ausgaben vom Typ (B) verwendet werden. Die Inferenzregeln dieses Systems sind dann Prinzipien, die Arten von Funktionen regeln: die Sequenz

[(A / rechter Pfeil B) amp (A / rechter Pfeil C) vdash A / rechter Pfeil (B / amp C))

sagt uns, dass wenn eine Funktion (A) s zu (B) s und (A) s zu (C) s nimmt, dann (A) s zu Dingen führt, die beide / sind (B) und (C).

Dieses Beispiel gibt uns ein Modell, in dem die entsprechende Unterstrukturlogik extrem schwach ist. Keine der üblichen Strukturregeln (nicht einmal Assoziativität) ist in diesem Modell erfüllt. Dieses Beispiel eines ternären relationalen Modells wird in (Restall 2000, Kapitel 11) erörtert.

Für die relevante Logik (mathbf {R}) und ihre Interpretation von Bedingungen der natürlichen Sprache muss mehr Arbeit geleistet werden, um zu identifizieren, welche Merkmale der Realität die formalen Semantikmodelle sind. Dies war Gegenstand einiger Kontroversen, da nicht nur die ternäre Beziehung denjenigen unbekannt ist, deren Exposition in erster Linie der Modallogik mit einer einfacheren binären Zugänglichkeitsbeziehung zwischen möglichen Welten entspricht, sondern auch der Neuheit der Behandlung der Negation in Modellen für relevante Logik. Es ist nicht unsere Aufgabe, diese Debatte hier ausführlich zu diskutieren. Einige dieser Arbeiten werden in dem Artikel über relevante Logik in dieser Enzyklopädie beschrieben, und eine buchlange Behandlung relevanter Logik in diesem Licht ist Mares 'relevante Logik: eine philosophische Interpretation (2004).

5. Quantifizierer

Die Behandlung von Quantifizierern in Modellen für die Substrukturlogik hat sich als recht schwierig erwiesen, aber Anfang der 2000er Jahre wurden Fortschritte erzielt. Die Schwierigkeit bestand darin, dass die Beweistheorie und die Modelltheorie für Quantifizierer nicht übereinstimmten. Geeignete Axiome oder Regeln für die Quantifizierer sind relativ einfach. Das universelle Quantifizierer-Eliminierungsaxiom) forall xA / rightarrow A [t / x]) besagt, dass eine Instanz (im relevanten Sinne) aus ihrer universellen Verallgemeinerung folgt. Die Einführungsregel) cfrac { vdash A / rightarrow B} { vdash A / rightarrow / forall xB}) (wobei die Maßgabe, dass (x) in (A) nicht frei ist, besagt) dass, wenn wir eine Instanz der Verallgemeinerung (forall xB) logisch aus einer Annahme beweisen können, die keinen besonderen Anspruch auf diese Instanz erhebt,wir können auch die Verallgemeinerung aus dieser Annahme beweisen. Dieses Axiom und diese Regel scheinen gut zu jeder Interpretation der Quantifizierer erster Ordnung in einer Reihe von Substrukturlogiken zu passen, von den schwächsten Systemen bis zu starken Systemen wie (mathbf {R}).

Während sich die Beweistheorie für Quantifizierer gut zu verhalten scheint, hat sich die Verallgemeinerung auf die Modelltheorie für die Substrukturlogik als schwierig erwiesen. Richard Routley (1980) zeigte, dass das Hinzufügen der Regeln für die Quantifizierer zu einem sehr schwachen System der Substrukturlogik (mathbf {B}) angemessen zur ternären relationalen Semantik passt, bei der Quantifizierer so interpretiert werden, dass sie sich über einen Bereich von Objekten erstrecken. Konstante über alle Punkte im Modell. Diese Tatsache gilt nicht für stärkere Logiken, insbesondere die relevante Logik (mathbf {R}). Kit Fine (1989) zeigte, dass es eine komplexe Formel gibt, die in allen konstanten Domänenrahmenmodellen für (mathbf {R}) gilt, aber nicht aus den Axiomen ableitbar ist. Die Details der Argumentation von Fine sind für unsere Zwecke nicht wichtig. Die zugrunde liegende Ursache für die Nichtübereinstimmung ist jedoch relativ einfach zu erklären. In der konstanten Domänensemantik hat die universelle Generalisierung (forall x Fx) an jedem Punkt im Modell genau die gleichen Wahrheitsbedingungen wie die Instanzfamilie (Fx_1), (Fx_2), (Fx_3, / ldots), (Fx_ / lambda, / ldots), wobei die Objekte der Domänen durch die Werte der Begriffe (x_i) aufgelistet werden. Der quantifizierte Ausdruck (forall x Fx) ist also semantisch nicht von der (möglicherweise unendlichen) Konjunktion (Fx_1 / land Fx_2 / land Fx_3 / land / cdots) zu unterscheiden. Es kann jedoch keine Konjunktion von Instanzen (auch keine unendliche) der universell quantifizierten Behauptung (forall x Fx) entsprechen.weil die Instanzen unter bestimmten Umständen wahr sein könnten (oder durch einen Umstand wahr gemacht werden könnten), ohne auch die Verallgemeinerung wahr zu machen - wenn es mehr Dinge als diese gegeben hätte. Konstante Domänenmodelle scheinen daher für das Projekt einer relevanten Quantifizierungstheorie ungeeignet zu sein.

Neuere Arbeiten von Goldblatt und Mares (2006) haben gezeigt, dass es eine Alternative gibt, und sie erweist sich als elegant und relativ unkompliziert. Die entscheidende Idee ist, die ternäre relationale Semantik nur ein wenig zu modifizieren, so dass nicht jeder Satz von Punkten als "Satz" gezählt werden muss. Das heißt, nicht jede Menge von Punkten ist der mögliche semantische Wert für einen Satz. Während es also eine Menge von Welten gibt, die durch die unendliche Verbindung von Instanzen von (forall xFx) bestimmt werden: (Fx_1 / land Fx_2 / land Fx_3 / land / cdots), kann diese genaue Menge von Welten möglicherweise nicht als zählen Ein Vorschlag. (Vielleicht gibt es keine Möglichkeit, diese bestimmten Objekte so herauszustellen, dass sie in einem Urteil zusammengefasst werden.) Was wir sagen können, ist die Generalisierung (forall xFx) und das ist ein Satz, der jede der Instanzen beinhaltet (das ist das universelle Quantifizierer-Eliminierungsaxiom), und wenn ein Satz jede Instanz beinhaltet, beinhaltet er die Generalisierung (das ist die Einführungsregel), daher ist der durch (forall xFx) ausgedrückte Satz der semantisch schwächste Satz, der jede Instanz Fa beinhaltet. Dies ist genau die Modellierungsbedingung für den universellen Quantifizierer in den Modellen von Goldblatt & Mares und entspricht genau den Axiomen. Dies ist genau die Modellierungsbedingung für den universellen Quantifizierer in den Modellen von Goldblatt & Mares und entspricht genau den Axiomen. Dies ist genau die Modellierungsbedingung für den universellen Quantifizierer in den Modellen von Goldblatt & Mares und entspricht genau den Axiomen.

Literaturverzeichnis

Eine umfassende Bibliographie zur relevanten Logik wurde von Robert Wolff zusammengestellt und ist in Anderson, Belnap und Dunn 1992 zu finden. Die Bibliographie in Restall 2000 (siehe Andere Internetquellen) ist nicht so umfassend wie die von Wolff, enthält jedoch Material bis zum heutige Tag.

Bücher über substrukturelle Logik und Einführungen in das Feld

• Anderson, AR, und Belnap, ND, 1975, Entailment: Die Logik der Relevanz und Notwendigkeit, Princeton, Princeton University Press, Band I.

• Anderson, AR, Belnap, ND Jr. und Dunn, JM, 1992, Entailment, Band II, Princeton, Princeton University Press

  [Dieses und das vorherige Buch fassen die Arbeit in relevanter Logik in der Anderson-Belnap-Tradition zusammen. Einige Kapitel in diesen Büchern haben andere Autoren, wie Robert K. Meyer und Alasdair Urquhart.]

• Dunn, JM und Restall, G., 2000, "Relevance Logic" in F. Guenthner und D. Gabbay (Hrsg.), Handbook of Philosophical Logic, zweite Auflage; Band 6, Kluwer, S. 1–136.

  [Eine Zusammenfassung der Arbeit in relevanter Logik in der Anderson-Belnap-Tradition.]

• Galatos, N., P. Jipsen, T. Kowalski und H. Ono, 2007, Residuierte Gitter: Ein algebraischer Einblick in die Substrukturlogik (Studies in Logic: Band 151), Amsterdam: Elsevier, 2007.

• Mares, Edwin D., 2004, Relevante Logik: eine philosophische Interpretation Cambridge University Press.

  [Eine Einführung in die relevante Logik, die ein informationstheoretisches Verständnis der ternären relationalen Semantik vorschlägt.]

• Moortgat, Michael, 1988, Kategoriale Untersuchungen: Logische Aspekte des Lambek Calculus Foris, Dordrecht.

  [Eine weitere Einführung in den Lambek-Kalkül.]

• Morrill, Glyn, 1994, Typ Logische Grammatik: Kategoriale Logik der Zeichen Kluwer, Dordrecht

  [Eine Einführung in die Lambek-Rechnung.]

• Paoli, Francesco, 2002, Substructural Logics: A Primer Kluwer, Dordrecht

  [Eine allgemeine Einführung in die Substrukturlogik.]

• Read, S., 1988, Relevant Logic, Oxford: Blackwell.

  [Eine Einführung in die relevante Logik, motiviert durch Überlegungen in der Bedeutungstheorie. Entwickelt eine Beweistheorie im Lemmon-Stil für die relevante Logik (mathbf {R}).]

• Restall, Greg, 2000, Eine Einführung in die Substrukturlogik, Routledge. (online précis)

  [Eine allgemeine Einführung in das Gebiet der Substrukturlogik.]

• Routley, R., Meyer, RK, Plumwood, V. und Brady, R., 1983, Relevante Logik und ihre Rivalen, Band I, Atascardero, CA: Ridgeview.

  [Eine weitere unverwechselbare Darstellung der relevanten Logik, diesmal aus australischer philosophischer Sicht.]

• Schroeder-Heister, Peter und Došen, Kosta, (Hrsg.), 1993, Substructural Logics, Oxford University Press.

  [Eine bearbeitete Sammlung von Aufsätzen zu verschiedenen Themen der Substrukturlogik aus verschiedenen Traditionen auf diesem Gebiet.]

• Troestra, Anne, 1992, Lectures on Linear Logic, CSLI Publications

  [Eine schnelle, leicht zu lesende Einführung in Girards lineare Logik.]

Andere zitierte Werke

• Ackermann, Wilhelm, 1956, „Begründung Einer Strengen Implikation“, Journal of Symbolic Logic, 21: 113–128.
• Avron, Arnon, 1988, „Die Semantik und Beweistheorie der linearen Logik“, Theoretical Computer Science, 57 (2–3): 161–184.
• Gianluigi Bellin, Martin Hyland, Edmund Robinson und Christian Urban, 2006, „Categorical Proof Theory of Classical Propositional Calculus“, Theoretical Computer Science, 364: 146–165.
• Church, Alonzo, 1951, „Die schwache Implikationstheorie“, in Kontrolliertes Denken: Untersuchungen zum Logikkalkül und zur Logik der Einzelwissenschaften, A. Menne, A. Wilhelmy und H. Angsil (Hrsg.), Kommissions-Verlag Karl Alber, 22 –37.
• Curry, Haskell B., 1977, Grundlagen der mathematischen Logik, New York: Dover (ursprünglich 1963 veröffentlicht).
• Dunn, JM, 1991, "Gaggle-Theorie: Eine Abstraktion von Galois-Verbindungen und Residuationen mit Anwendungen auf Negation und verschiedene logische Operationen", in Logics in AI, Proceedings European Workshop JELIA 1990 (Lecture Notes in Computer Science, Band 476), Berlin: Springer-Verlag.
• Dunn, JM, 1993, „Star and Perp“, Philosophical Perspectives, 7: 331–357.
• Fine, K., 1989, „Unvollständigkeit für quantifizierte Relevanzlogik“, in J. Norman und R. Sylvan (Hrsg.), Directions in Relevant Logic, Dordrecht: Kluwer, S. 205–225.
• Geach, PT, 1955, „On Insolubilia“, Analysis, 15: 71–72.
• Gentzen, Gerhard, 1935, „Untersuchungen über das logische Verletzungen“, Mathematische Zeitschrift, 39: 176–210 und 405–431. [Eine englische Übersetzung findet sich in Gentzen 1969.]
• Gentzen, Gerhard, 1969, Die gesammelten Papiere von Gerhard Gentzen, ME Szabo (Hrsg.), Amsterdam: Nordholland, 1969.
• Goldblatt, R. und E. Mares, 2006, „Eine alternative Semantik für quantifizierte relevante Logik“, Journal of Symbolic Logic, 71 (1): 163–187.
• Girard, Jean-Yves, 1987, "Linear Logic", Theoretical Computer Science, 50: 1–101.
• Lambek, Joachim, 1958, „Die Mathematik der Satzstruktur“, American Mathematical Monthly, 65: 154–170.
• Lambek, Joachim, 1961, "Über die Berechnung syntaktischer Typen" in der Struktur der Sprache und ihren mathematischen Aspekten (Proceedings of Symposia in Applied Mathematics, XII), R. Jakobson (Hrsg.), Providence, RI: American Mathematical Society.
• Moh Shaw-Kwei, 1950, „Die Deduktionssätze und zwei neue logische Systeme“, Methodos, 2: 56–75.
• Moortgat, Michael, 1995, „Multimodal Linguistic Inference“, Logic Journal der IGPL, 3: 371–401.
• Ono, Hiroakira, 2003, „Substrukturlogik und Residuierte Gitter - eine Einführung“, in V. Hendricks und J. Malinowski (Hrsg.), Trends in Logic: 50 Jahre Studia Logica, Dordrecht: Kluwer, 2003, S. 193– 228.
• Routley, R., 1980. "Probleme und Lösungen in der Semantik in quantifizierter relevanter Logik", in A. Arruda, R. Chuaqui und NCA Da Costa (Hrsg.), Mathematische Logik in Lateinamerika, Amsterdam: Nordholland, 1980, S. 305–340.

Akademische Werkzeuge

	Wie man diesen Eintrag zitiert.
	Vorschau der PDF-Version dieses Eintrags bei den Freunden der SEP-Gesellschaft.
	Schlagen Sie dieses Eintragsthema im Internet Philosophy Ontology Project (InPhO) nach.
	Erweiterte Bibliographie für diesen Eintrag bei PhilPapers mit Links zu seiner Datenbank.

Andere Internetquellen

• Restall, Greg, 1994, Über Logik ohne Kontraktion, Doktorarbeit, University of Queensland.
• Slaney, John, 1995, MaGIC: Matrixgenerator für Implikationsverbindungen, ein Softwarepaket zur Erzeugung endlicher Modelle für die Substrukturlogik.