Lineare Logik

Inhaltsverzeichnis:

Lineare Logik
Lineare Logik

Video: Lineare Logik

Video: Lineare Logik
Video: Foundations of Programming Languages: Linear Logic [1/2] - Paul Downen - OPLSS 2018 2024, March
Anonim

Eintragsnavigation

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

Lineare Logik

Erstveröffentlichung Mi 6. September 2006; inhaltliche Überarbeitung Fr 24. Mai 2019

Die lineare Logik ist eine Verfeinerung der klassischen und intuitionistischen Logik. Anstatt die Wahrheit wie in der klassischen Logik oder den Beweis wie in der intuitionistischen Logik zu betonen, betont die lineare Logik die Rolle von Formeln als Ressourcen. Um diesen Fokus zu erreichen, erlaubt die lineare Logik nicht, dass die üblichen strukturellen Regeln für Kontraktion und Schwächung auf alle Formeln angewendet werden, sondern nur auf die Formeln, die mit bestimmten Modalitäten markiert sind. Die lineare Logik enthält eine vollständig involutive Negation unter Beibehaltung einer starken konstruktiven Interpretation. Die lineare Logik bietet auch neue Einblicke in die Natur von Beweisen sowohl in der klassischen als auch in der intuitionistischen Logik. Aufgrund ihres Fokus auf Ressourcen hat die lineare Logik in der Informatik viele Anwendungen gefunden.

  • 1. Einleitung

    • 1.1 Ein bisschen Geschichte
    • 1.2 Lineare Logik und Informatik
  • 2. Beweissysteme

    • 2.1 Sequentielle Berechnung
    • 2.2 Fokussierte Proofsuche
    • 2.3 Beweisnetze
  • 3. Semantik

    • 3.1 Semantik der Beweisbarkeit
    • 3.2 Semantik der Beweise
  • 4. Komplexität
  • 5. Auswirkungen auf die Informatik

    • 5.1 Beweisnormalisierung
    • 5.2 Beweissuche
  • 6. Variationen

    • 6.1 Verschiedene Modalitätsbehandlungen
    • 6.2 Nicht kommutative lineare Logik
    • 6.3 Behandlung von unbegrenztem Verhalten
  • Literaturverzeichnis
  • Akademische Werkzeuge
  • Andere Internetquellen
  • Verwandte Einträge

1. Einleitung

1.1 Ein bisschen Geschichte

Die lineare Logik wurde von Jean-Yves Girard in seiner wegweisenden Arbeit eingeführt (Girard 1987). Während der Ursprung der Entdeckung dieser neuen Logik in einer semantischen Analyse der Modelle des Systems F (oder des polymorphen (lambda) - Kalküls) liegt, kann man das gesamte System der linearen Logik als einen mutigen Versuch betrachten, das zu versöhnen Schönheit und Symmetrie der Systeme für die klassische Logik mit der Suche nach konstruktiven Beweisen, die zu intuitionistischer Logik geführt hatten.

In der Tat könnte man ein Fragment der linearen Logik, bekannt als multiplikative additive lineare Logik (MALL), als Ergebnis zweier einfacher Beobachtungen präsentieren.

  • In der sequentiellen Kalküldarstellung der klassischen Logik können die Regeln für die Konnektive „und“und „oder“sowie die Cut-Regel und die Implikationsregel äquivalent in einer additiven Form dargestellt werden (der Kontext der Prämissen ist der gleiche) oder eine multiplikative Form (der Kontext der Prämissen ist unterschiedlich). Diese beiden Darstellungen sind in der klassischen Logik gleichwertig, da einige sogenannte „strukturelle“Regeln verfügbar sind, nämlich Kontraktion und Schwächung.
  • Die nicht konstruktiven Beweise, die man in der klassischen Logik ausführen kann, verwenden in der sequentiellen Kalküldarstellung tatsächlich die eine oder andere dieser Strukturregeln.

Wenn wir also die nicht konstruktiven Beweise eliminieren wollen, ohne die Symmetrie des sequentiellen Kalküls zu zerstören, wie dies in der intuitionistischen Logik der Fall ist, können wir stattdessen versuchen, die Kontraktions- und Schwächungsregeln zu eliminieren. Dabei bleiben uns zwei verschiedene Versionen jedes Konnektivs: eine additive Version und eine multiplikative Version der Konjunktion und der Disjunktion. Diese verschiedenen Versionen derselben Verbindung sind jetzt nicht mehr gleichwertig. Diese neuen Verknüpfungen sind & ("mit", additiv und), (oplus) ("plus", additiv oder, (otimes) ("Tensor", multiplikativ und) und (lpar) ("Par", multiplikativ oder).

Diese Verdoppelung der Konnektiva führt tatsächlich zu einem viel klareren Verständnis des Konflikts zwischen klassischer und intuitionistischer Logik. Zum Beispiel wird das Gesetz der ausgeschlossenen Mitte ((A) oder nicht - (A)) in der klassischen Welt als gültig und in der intuitionistischen als absurd angesehen. In der linearen Logik hat dieses Gesetz jedoch zwei Lesarten: Die additive Version ((A / oplus / neg A)) ist nicht beweisbar und entspricht der intuitionistischen Lesart der Disjunktion; Die multiplikative Version ((A / lpar / neg A)) ist trivial beweisbar und entspricht einfach der Tautologie ((A) impliziert (A)), die auch in der intuitionistischen Logik vollkommen akzeptabel ist.

Auch die für den Konstruktivismus wesentliche Disjunktionseigenschaft lässt sich für die additive Disjunktion leicht feststellen.

Wir finden dann in dieser reichhaltigeren Logik einen Weg, sowohl die Bedürfnisse des Intuitionismus als auch die Eleganz der klassischen Logik darzustellen: Negation ist involutiv, Sequenzen sind symmetrisch und Konnektiva sind definierbar. Vergleichen Sie diese Eigenschaften mit denen der intuitionistischen Logik, bei denen die Negation nicht involutiv ist, die Sequenzen nicht symmetrisch sind und die Konnektiva nicht alle miteinander definierbar sind.

Beachten Sie jedoch, dass sich Formeln nach Beseitigung der Kontraktions- und Schwächungsregel nicht mehr als unveränderliche Wahrheitswerte verhalten: in der Tat, wenn wir einen Beweis für (A / Rightarrow B) und einen Beweis für (A) in der linearen Logik haben Wenn wir sie komponieren, verbrauchen wir sie tatsächlich, um einen Beweis für (B) zu erhalten, so dass (A / Rightarrow B) und (A) nach der Komposition nicht mehr verfügbar sind. Lineare Logikformeln verhalten sich jetzt eher wie Ressourcen, die nur einmal verwendet werden können.

Um die volle Ausdruckskraft der intuitionistischen und klassischen Logik wiederzugewinnen, müssen dem MALL-Fragment zwei duale Modalitäten hinzugefügt werden, die in der Literatur zur linearen Logik üblicherweise als Exponentiale bezeichnet werden. Insbesondere erlaubt das "natürlich" Exponential (bang), dass Kontraktion und Schwächung auf die Formel (bang B) im linken sequentiellen Kontext angewendet werden, während das "Warum-nicht" Exponential (bang). / quest) ermöglicht das Anwenden von Kontraktion und Schwächung auf die Formel (quest B) im rechten sequentiellen Kontext. Dies führt zu einer vollständigen aussagekräftigen linearen Logik und zu einer sehr guten Verbindung mit der Informatik.

Beachten Sie, dass es neben MALL zwei weitere weit verbreitete Fragmente der linearen Logik gibt: Multiplikative lineare Logik (MLL), bei der es sich um MALL ohne die additiven Konnektiva handelt. und Multiplikative Exponentielle Lineare Logik (MELL), die lineare Logik ohne die additiven Konnektiva ist.

Vor der Einführung der linearen Logik im Jahr 1987 hatten verschiedene Forscher an verschiedenen Arten von Substrukturlogik gearbeitet, bei denen nicht alle Gentzen-Strukturregeln (Kontraktion, Schwächung und Austausch) akzeptiert werden. Lambek untersuchte ein sequentielles Kalkülprüfsystem, in dem keine dieser Strukturregeln zulässig war (Lambek 1958). Andere Beispiele für solche Logiken sind relevante Logik (in der eine Schwächung nicht akzeptiert wird) (Avron 1988, Read 1988). und affine Logik (in der Kontraktion nicht akzeptiert wird) (Grishin 1981).

1.2 Lineare Logik und Informatik

Die Beweistheorie konzentriert sich auf formale Beweissysteme, und solche formalen Systeme wurden unter anderem für intuitionistische Prädikatenrechnung, klassische Prädikatenrechnung, Arithmetik und Kalkül höherer Ordnung entwickelt. Intuitionistische und konstruktive Logik begann, als die Leute die Möglichkeit sahen, '(A / Rightarrow B)' zu lesen, als 'wenn du mir ein (A) gibst, gebe ich dir ein (B)', was a ist Eine signifikante Abweichung von der klassischen Lesart "(A) ist falsch oder (B) ist wahr".

Die Informatik hingegen konzentriert sich auf Rechenmechanismen: Funktionsanwendung, Ausnahmebehandlung, Methodenaufruf in objektorientierten Sprachen, Variablenzuweisung und ähnliche Sätze prozessbildender Regeln. Abgesehen davon, dass die Mechanismen dieser Prozesse explizit angegeben werden müssen: Eine Funktion vom Typ (A / rightarrow B) gibt einen formalen Bericht darüber, wie ein (A) in ein (B) umgewandelt werden kann.

Zu einem bestimmten Zeitpunkt trafen sich diese beiden Sinne. HB Curry und W. Howard erkannten, dass die Menge der nur impliziten intuitionistischen Ableitungen eine funktionale Kernsprache war, die einfach typisierte (lambda) - Kalkül genannt wurde: Die Programmiersprache war eine Logik, die Logik eine Programmiersprache. Dieses denkwürdige Treffen wurde als "Curry-Howard-Isomorphismus" bezeichnet (Howard 1980).

Die lineare Logik bietet eine weitere Wendung in der Interpretation der Implikation '(A / Rightarrow B)': Jetzt kann sie als 'gib mir so viele (A)' gelesen werden, wie ich brauche, und ich werde dir geben ein B)'. Der Begriff der Kopie, der für die Idee der Berechnung so zentral ist, ist jetzt in die Logik eingebunden.

Dieser neue Standpunkt eröffnet neue Möglichkeiten, darunter:

  • neue Formeln, die verfeinerte Betriebseigenschaften wie "gib mir (A) einmal und ich gebe dir (B)" ausdrücken. Die Anwendungen reichen hier von der verfeinerten Logikprogrammierung, bei der die Fähigkeit der linearen Logik zur Darstellung von Zuständen genutzt wird (Hodas & Miller, 1994), über die Analyse der klassischen Logik und deren rechnerische Interpretation (Abramsky 1993) bis hin zur Spezifikation von Ausnahmemechanismen in Programmiersprachen (Miller, 1996) bis zur Linearitätsanalyse (Wadler, 1991).
  • neue Regeln, die Einschränkungen bei der Verwendung von Kopien zum Ausdruck bringen und zu einem Fragment linearer Logik für Polytime-Berechnungen führen, um nur die spektakulärste Anwendung zu erwähnen (Baillot & Terui, 2004, Baillot 2015).
  • neue Arten der Darstellung von Beweisen (Abramsky & Jagadeesan, 1994, Girard 1987).

2. Beweissysteme

Die Kernaussagen der linearen Logik werden in additive und multiplikative Verbindungen unterteilt. Die klassische Konjunktion und ihre Identität (wedge) und (top) teilen sich in das Additiv (amp) (mit) und (top) (oben) und das Multiplikativ () auf otimes) (Tensor) und 1 (eins). In ähnlicher Weise teilen sich die klassische Disjunktion und ihre Identität (vee) und (bot) in das Additiv (oplus) (oplus) und 0 (null) und das Multiplikativ (lpar). (par) und (bot) (unten). Negation wird in Präsentationen einer linearen Logik im Allgemeinen auf zwei Arten behandelt. Negation kann als primitiver Satzkonnektiv ohne Einschränkung seines Auftretens innerhalb von Formeln angesehen werden. Da De Morgan-Dualitäten zwischen Negation und allen Aussagenkonnektiven, Exponentialen und Quantifizierern bestehen,Es ist auch möglich, die Negation als ein spezielles Symbol zu behandeln, das nur bei Atomformeln auftritt. Implikationen werden üblicherweise auch über Definitionen in die lineare Logik eingeführt: Die lineare Implikation (B / limp C) kann als (B ^ { bot} lpar C) definiert werden, während die intuitionistische Implikation (B / Rightarrow C)) kann definiert werden als (bang B / limp C). Die Operatoren (bang) und (quest) werden verschiedentlich als Modal oder Exponential bezeichnet. Der Begriff "exponentiell" ist besonders geeignet, da die lineare Logik gemäß der üblichen Beziehung zwischen Exponentiation, Addition und Multiplikation die Äquivalenzen (bang (B / amp C) equiv (bang B / otimes / bang C) unterstützt) und (quest (B / oplus C) equiv (quest B / lpar / quest C)) sowie die 0-fachen Versionen dieser Äquivalenzen, nämlich ((bang / top / equiv) 1)) und ((quest 0 / equiv / bot)). Hier,Wir verwenden die binäre Äquivalenz (B / equiv C), um zu bedeuten, dass die Formel ((B / limp C) amp (C / limp B)) in linearer Logik ableitbar ist.

2.1 Sequentielle Berechnung

Eine zweiseitige sequentielle Berechnung für die lineare Logik ist in der folgenden Abbildung dargestellt. Beachten Sie hier, dass die Negation so behandelt wird, als wäre sie eine andere logische Verbindung: Das heißt, ihre Vorkommen in Formeln sind nicht eingeschränkt, und links und rechts gibt es Einführungsregeln für die Negation. Die linke und rechte Seite von Sequenzen sind mehrere Formeln: Daher spielt die Reihenfolge der Formeln in diesen Kontexten keine Rolle, aber ihre Vielheit spielt eine Rolle.

Identitätsregeln) frac {} {B / vdash B} / textit {init} qquad / frac { Delta_1 / vdash B, / Gamma_1 / qquad / Delta_2, B / vdash / Gamma_2} { Delta_1, / Delta_2 / vdash / Gamma_1, / Gamma_2} / textit {cut}) Negationsregeln) frac { Delta / vdash B, / Gamma} { Delta, B ^ { perp} vdash / Gamma} (cdot) ^ { perp} L / qquad / frac { Delta, B / vdash / Gamma} { Delta / vdash B ^ { perp}, / Gamma} (cdot) ^ { perp} R) Multiplikative Regeln) frac { Delta / vdash / Gamma} { Delta, / one / vdash / Gamma} / one L / qquad / frac {} { vdash / one} / one R)) frac { } { bot / vdash} / bot L / qquad / frac { Delta / vdash / Gamma} { Delta / vdash / bot, / Gamma} / bot R)) frac { Delta, B_1, B_2 / vdash / Gamma} { Delta, B_1 / ot B_2 / vdash / Gamma} / ot L / qquad / frac { Delta_1 / vdash B, / Gamma_1 / qquad / Delta_2 / vdash C, / Gamma_2} { Delta_1, / Delta_2 / vdash B / ot C, / Gamma_ {1}, / Gamma_ {2}} / ot R)) frac { Delta_1, B / vdash / Gamma_1 / qquad / Delta_2, C / vdash / Gamma_2} { Delta_1, / Delta_2, B / lpar C / vdash / Gamma_1, / Gamma_2} / lpar L / qquad / frac { Delta / vdash B, C, / Gamma} { Delta / vdash B / lpar C., / Gamma} / lpar R) Additive Regeln) frac {} { Delta, / zero / vdash / Gamma} / zero L / qquad / frac {} { Delta / vdash / top, / Gamma} / top R)) frac { Delta, B_i / vdash / Gamma} { Delta, B_1 / amp B_2 / vdash / Gamma} { amp} L (i = 1,2) qquad / frac { Delta / vdash B, / Gamma / qquad / Delta / vdash C, / Gamma} { Delta / vdash B / amp C, / Gamma} { amp} R)) frac { Delta, B / vdash / Gamma / qquad / Delta, C / vdash / Gamma} { Delta, B / oplus C / vdash / Gamma} { oplus} L / qquad / frac { Delta / vdash B_i, / Gamma} { Delta / vdash B_1 / oplus B_2, / Gamma} { oplus} R (i = 1,2)) Quantifiziererregeln) frac { Delta, B [t / x] vdash / Gamma} { Delta, / für alle xB / vdash / Gamma} / für alle L / qquad / frac { Delta / vdash B [y / x], / Gamma} { Delta / vdash / für alle xB, / Gamma} / für alle R)) frac { Delta / vdash B [t / x], / Gamma} { Delta / vdash / existiert xB / Gamma} / existiert R / qquad / frac { Delta, B [y / x] vdash / Gamma} { Delta, / existiert xB / vdash / Gamma} / existiert L,) Exponential Rules) frac { Delta / vdash / Gamma} { Delta, / bang B / vdash / Gamma} / bang W / quad / frac { Delta, / bang B, / bang B / vdash / Gamma} { Delta, / bang B / vdash / Gamma} / bang C / quad / frac { Delta, B / vdash / Gamma} { Delta, / bang B / vdash / Gamma} / bang D)) frac { Delta / vdash / Gamma} { Delta / vdash / Quest B, / Gamma} / Quest W / quad / frac { Delta / vdash / Quest B, / Quest B, / Gamma} { Delta / vdash / Quest B, / Gamma} / Quest C / quad / frac { Delta / vdash B, / Gamma} { Delta / vdash / Quest B, / Gamma} / Quest D)) frac { bang / Delta / vdash B, / quest / Gamma} { bang / Delta / vdash / bang B, / quest / Gamma} / bang R / quad / frac { bang / Delta, B / vdash / quest / Gamma} { Knall / Delta, / Quest B / vdash / Quest / Gamma} / Quest L)

Beachten Sie, dass die Regeln für Schwächung und Kontraktion nur für Formeln verfügbar sind, die links mit dem Exponential (bang) oder rechts von (quest) rechts von der Sequenz gekennzeichnet sind. Die Regeln (quest) R und (bang) L werden oft als "Verfallsregeln" bezeichnet. Die Regeln (quest) L und (bang) R werden oft als "Beförderungsregeln" bezeichnet und entsprechen den Regeln für Möglichkeiten und Notwendigkeiten, die in Kripkes S4-Modallogik enthalten sind. Die übliche Maßgabe für die Einführungsregeln (forall) - rechts und (existiert) - links wird angenommen: Insbesondere darf die Variable (y) in den Formeln der unteren Folge dieser Regeln nicht frei sein Inferenzregeln. Die Quantifizierung wird hier als erste Ordnung angenommen: Versionen höherer Ordnung der linearen Logik können entlang von Standardlinien geschrieben werden.

Die Schnittregel kann beseitigt werden und die Vollständigkeit bleibt erhalten. Doppelt kann die Init-Regel auch eliminiert werden, mit Ausnahme des Auftretens von Init, an dem Atomformeln beteiligt sind.

2.2 Fokussierte Beweise

Ein wichtiger Normalformsatz für die Struktur schnittfreier Beweise wurde von Andreoli (1992) geliefert. Er klassifizierte eine nichtatomare Formel als asynchron, wenn ihre logische Verbindung auf oberster Ebene (top), &, (bot, / lpar), (quest) oder (forall) ist. oder synchron, wenn die logische Verbindung der obersten Ebene (0, / oplus, 1, / otimes), (bang) oder (existiert) ist.

Wenn wir die Proof-Suche als Rechenmodell betrachten, können wir Formeln in einer Folge als „Agenten“betrachten, die unabhängig oder zusammen mit anderen in ihrer Umgebung agieren können. Hier werden die Aktionen solcher Agenten bestimmt, indem die Einführungsregel für sie von unten nach oben gelesen wird. Wenn eine asynchrone Formel rechts von einer Sequenz auftritt, kann sie sich entwickeln, ohne die Beweisbarkeit zu beeinträchtigen und ohne mit ihrem Kontext zu interagieren, dh die entsprechende Einführungsregel ist invertierbar. Zum Beispiel wird der Agent ((B / lpar C)) (durch Anwenden der (lpar) - rechten Einführungsregel) zu den beiden Agenten (B) und (C) (die jetzt parallel arbeiten)). In ähnlicher Weise liefert der Agent ((B / amp C)) (unter Anwendung der & -right-Einführungsregel) zwei verschiedene identische Welten (Sequenzen), außer dass (B) in einer dieser Welten liegt und (C)) ist in der anderen.

Wenn wir andererseits eine Synchronformel als einen Agenten betrachten, dessen Entwicklung durch die entsprechende Rechtseinführungsregel bestimmt wird, kann sich eine nachweisbare Sequenz zu einer nicht nachweisbaren Sequenz entwickeln (z. B. durch Anwenden der (oplus) Rechtseinführungsregel). Die Instanzen solcher Inferenzregeln hängen auch von Einzelheiten des Kontextes der Formel ab. Zum Beispiel erfordert der Erfolg der 1-Rechts-Einführungsregel, dass der umgebende Kontext leer ist und der Erfolg der (otimes) - richtigen Einführungsregel davon abhängt, wie der umgebende Kontext des Agenten in zwei Kontexte unterteilt ist. Daher hängt die Entwicklung solcher Agenten von der „Synchronisation“mit anderen Teilen des Kontexts ab.

Betrachten Sie nun eine einseitige sequentielle Kalküldarstellung der linearen Logik, bei der die einzigen Einführungsregeln die Regeln für die richtige Einführung sind. In Anbetracht der obigen Klassifizierung von Konnektiven kann gezeigt werden, dass die Proof-Suche ohne Vollständigkeitsverlust in die folgenden Phasen unterteilt werden kann. Die asynchrone Phase tritt auf, wenn in der Sequenz eine asynchrone Formel vorhanden ist. In dieser Phase werden die Regeln für die Einführung von Rechten in beliebiger Reihenfolge angewendet, bis keine weiteren asynchronen Formeln mehr vorhanden sind. In der synchronen Phase wird eine synchrone Formel ausgewählt, die zum „Fokus“dieser Phase wird. Das heißt, es werden Regeln für die richtige Einführung auf sie und alle möglicherweise erzeugten synchronen Unterformeln angewendet.

Die folgende Abbildung zeigt die lineare Logik des fokussierungssicheren Systems. Beachten Sie, dass die beiden Phasen durch unterschiedliche Pfeile dargestellt werden: Der Aufwärtspfeil kennzeichnet die asynchrone Phase und der Abwärtspfeil kennzeichnet die synchrone Phase. Außerdem werden Sequenzen in drei Zonen unterteilt (wobei die Zonen entweder durch ein Semikolon oder einen Aufwärts- oder Abwärtspfeil getrennt sind). Insbesondere links vom Aufwärts- und Abwärtspfeil befinden sich die beiden Zonen. Die als (Psi) geschriebene Zone bezeichnet eine Reihe von Formeln, die beliebig oft für den Beweis dieser Sequenz verwendet werden können. Die als (Delta) geschriebene Zone bezeichnet eine Vielzahl von Formeln, die wie in MALL eingeschränkt sind. Die Zone rechts von einem Aufwärtspfeil ist ebenfalls eine Vielzahl von Formeln, während die Zone rechts von einem Abwärtspfeil eine einzelne Formel ist. Es ist möglich, den Formeln rechts vom Aufwärtspfeil eine beliebige Reihenfolge aufzuerlegen, da die Einführung asynchroner Formeln in beliebiger Reihenfolge erfolgen kann. Atome erhalten eine Polarität und in der folgenden Abbildung steht (A) für positive Atome und die Negation von (A) für negative Atome. Nach diesen Inferenzregeln erstellte Beweise werden fokussierte Beweise genannt. Das Ergebnis in Andreoli 1992 ist, dass fokussierte Beweise für die lineare Logik vollständig sind.

Asynchrone Phase) frac { Up { Psi} { Delta} {L}} { Up { Psi} { Delta} { bot, L}}) bot] qquad / frac { Up { Psi, F} { Delta} {L}} { Up { Psi} { Delta} { Quest F, L}}) quest])) frac {} { Up { Psi} { Delta} { top, L}}) top] qquad / frac { Up { Psi} { Delta} {F [y / x], L}} { Up { Psi} { Delta} { forall xF, L}}) forall])) frac { Up { Psi} { Delta} {F_1, F_2, L}} { Up { Psi} { Delta} {F_1 / lpar F_2, L}}) lpar] qquad / frac { Up { Psi} { Delta} {F_1, L} quad / Up { Psi} { Delta} {F_2, L}} { Up { Psi} { Delta} {F_1 / amp F_2, L}}) amp])) frac { Up { Psi} { Delta, F} {L}} { Up { Psi} { Delta} {F, L}} [R / Uparrow] / text {vorausgesetzt, $ F $ ist nicht asynchron}) Synchrone Phase) frac {} { Down { Psi} { cdot} { one}}) one] qquad / frac { Down { Psi} { Delta_1} {F_1} quad / Down { Psi} { Delta_2} {F_2}} { Down { Psi} { Delta_1, / Delta_2} {F_1 / ot F_2}}) ot] qquad / frac { Up { Psi} { cdot} {F}} { Down { Psi} { cdot} { bang F}}) bang])) frac { Down { Psi} { Delta} {F_i}} { Down { Psi} { Delta} {F_1 / oplus F_2}}) oplus_i] qquad / frac { Down { Psi} { Delta} {F [t / x]}} { Down { Psi} { Delta} { existiert xF}}) existiert])) frac { Up { Psi} { Delta} {F}} { Down { Psi} { Delta} {F}} [R / Downarrow] / text {vorausgesetzt, $ F $ ist entweder asynchron oder ein Atom}) Identitäts- und Entscheidungsregeln) frac {} { Down { Psi} {A} {A ^ { perp}}} [I_1] qquad / frac {} { Down { Psi, A} { cdot} {A. ^ { perp}}} [I_2] / text {wobei} A / text {ein Atom ist})) frac { Down { Psi} { Delta} {F}} { Up { Psi} { Delta, F} { cdot}} [D_1] qquad / frac { Down { Psi} { Delta} {F}} { Up { Psi, F} { Delta} { cdot}} [D_2] / text {wobei} F / text {eine positive Formel ist})

Fokussierte Beweissysteme wurden auch für die klassische und intuitionistische Logik entwickelt (Danos et al. 1997; Laurent et al. 2005; Liang & Miller 2009).

2.3 Beweisnetze

Mit sequentieller Berechnung vorgelegte Beweise enthalten viele Details, die manchmal uninteressant sind: Überlegen Sie beispielsweise, wie viele uninteressant unterschiedliche Möglichkeiten es gibt, einen Beweis für (vdash / Gamma, (A_1 / lpar A_2), / ldots, (A_ { n-1} lpar A_n)) aus einer Ableitung von (vdash / Gamma, A_1, A_2, / ldots, A_n). Diese unangenehme Tatsache ergibt sich aus der sequentiellen Natur von Beweisen in der sequentiellen Berechnung: Wenn wir einen Satz (S) von (n) Regeln auf verschiedene Teile einer Sequenz anwenden wollen, können wir sie nicht in einem Schritt anwenden, selbst wenn sie stören sich nicht! Wir müssen sie sequentiellisieren, dh eine lineare Reihenfolge für (S) wählen und die Regeln in (n) Schritten gemäß dieser Reihenfolge anwenden.

Es stellt sich natürlich die Frage: „Gibt es eine Darstellung von Beweisen, die von solchen uninteressanten Details abstrahieren?“. Eine ähnliche Frage wird im Fall der intuitionistischen sequentiellen Berechnung durch einen sogenannten natürlichen Abzug positiv beantwortet, der über die Curry-Howard-Korrespondenz eine starke Verbindung mit dem als (lambda) - Kalkül bekannten Rechengerät aufweist.

Für die lineare Logik wird diese prägnante Darstellung von Beweisen durch Beweisnetze gegeben, graphische Strukturen, die besonders gute Eigenschaften für das MLL-Fragment der Logik aufweisen. Der erste Schritt in Richtung dieser Darstellung besteht darin, das gesamte sequentielle Kalkülsystem unter Verwendung der Involvivität der Negation in ein einseitiges System umzuwandeln, in dem die Sequenzen die Form (vdash / Gamma) haben. Infolgedessen wird die Anzahl der Regeln reduziert, da wir keine Regeln für die Einführung von Links haben, aber wir behalten die gleiche Ausdruckskraft, da die Beweisbarkeit gleich bleibt.

Jedem sequentiellen Kalkülbeweis in MLL kann man ein Beweisnetz induktiv mit den gleichen Schlussfolgerungen wie folgt verknüpfen:

  • Zu einem auf die Axiomregel reduzierten Beweis ordnen wir eine Axiomverknüpfung zu.

    Axiom net
    Axiom net
  • Für einen Beweis, der durch Anwenden der Schnittregel auf zwei Beweise erhalten wird, bauen wir zuerst die diesen beiden Beweisen zugeordneten Beweisnetze induktiv auf und kombinieren sie dann unter Verwendung einer Schnittverbindung.

    Netzkonstruktion abschneiden
    Netzkonstruktion abschneiden
  • Für einen Beweis, der durch Anwenden der Tensorregel auf zwei Beweise erhalten wird, bauen wir zuerst induktiv die diesen beiden Beweisen zugeordneten Beweisnetze auf und kombinieren sie dann unter Verwendung einer Tensorverbindung.

    Tensornetzkonstruktion
    Tensornetzkonstruktion
  • Für einen Beweis, der durch Anwenden der Par-Regel auf einen Beweis erhalten wird, bauen Sie zuerst induktiv das diesem Beweis zugeordnete Beweisnetz auf und fügen dann einen „Par-Link“hinzu.

    Par net Aufbau
    Par net Aufbau

All dies kann mithilfe von Hypergraphen richtig formalisiert werden (Formeln sind Knoten und „Links“sind orientierte Hyperedges mit Hypothesen und Schlussfolgerungen), und wir können einen Hypergraphen, der induktiv aus einer sequentiellen Kalkülableitung von MLL aufgebaut ist, formal als Beweisnetz definieren. Beachten Sie, dass es ziemlich viele Hypergraphen gibt, die keine Beweisnetze sind.

Betrachten Sie nun das Beweisnetz, das aus den Ableitungen von (vdash / Gamma, (A_1 / lpar A_2), / ldots, (A_ {n-1} lpar A_n)) erstellt wurde, die aus (vdash) erhalten wurden Gamma, A_1, A_2, / ldots, A_n), Sie werden sehen, dass alle Spuren der Reihenfolge der Anwendung der Regeln verschwunden sind. In gewissem Sinne sind die Beweisnetze eine Äquivalenzklasse von sequentiellen Kalkülableitungen in Bezug auf die Ableitungsreihenfolge von Regeln, deren Anwendung pendelt.

Angenommen, jemand kommt jetzt mit einem riesigen Hypergraphen zu Ihnen, der aus Axiom-, Cut-, Par- und Tensor-Links besteht und so tut, als wäre er tatsächlich eine Darstellung des Beweises eines langjährigen offenen mathematischen Problems. Wie können Sie überprüfen, ob es sich tatsächlich um eine Darstellung eines Beweises handelt und nicht nur um eine zufällige Struktur?

Die Durchführung dieser Korrektheitsprüfung ist eine Herausforderung, die darin besteht, eine sequentielle Konstruktionshistorie für Ihre Struktur wiederherzustellen, die einer Ableitung in der sequentiellen Berechnung entspricht, und scheint zunächst ein sehr komplexes Problem zu sein: das erste Korrektheitskriterium für MLL-Proof-Netze, das als „lange Reise“bezeichnet wird Kriterium “, das in Girards Originalarbeit enthalten ist, ist exponentiell, ebenso wie das später gefundene ACC-Kriterium (Acyclic Connected) von Danos und Regnier (1989). Dennoch gibt es ein viel effizienteres Kriterium, das aufgrund von Danos und Regnier als Kontraktibilität bekannt ist und in jüngerer Zeit von Guerrini, Martini und Masini als das folgende elegante Kriterium für die Analyse von Graphen umformuliert wurde: Ein Hypergraph ist genau dann ein Beweisnetz, wenn Es wird über die folgenden Regeln zur Grafikreduzierung auf den Singleton-Knoten "net" reduziert

Graph Parsing für MLL-sichere Netzerkennung
Graph Parsing für MLL-sichere Netzerkennung

Das naive Durchführen dieser Prüfung kann quadratische Zeit in Anspruch nehmen (jede Anwendung einer Regel erfordert möglicherweise eine vollständige Suche im Diagramm, um den Redex zu finden, und wir müssen so viele Schritte ausführen, wie Hyperlinks im Diagramm vorhanden sind). Lineare Zeitalgorithmen wurden von Guerrini (2011) sowie von Murawski und Ong (2006) angegeben.

Ein anderes Korrektheitskriterium für MLL-Proof-Netze wird von Retoré (2003) angegeben, in dem ein quadratischer Algorithmus für MLL angegeben wird.

Bei Proof-Netzen kann die Schnittbeseitigung besonders sauber durchgeführt werden: Aufgrund ihrer Parallelität können Schnitte lokal über zwei Vereinfachungsregeln beseitigt werden:

  • Axiom bewegen:

    Axiom bewegen
    Axiom bewegen
  • Multiplikativer Zug:

    Multiplikativer Zug
    Multiplikativer Zug

Dies sind tatsächlich Berechnungsregeln für Beweisnetze, und die Korrektheitskriterien ermöglichen es, leicht zu überprüfen, ob eine solche Regel die Korrektheit bewahrt, und infolgedessen kommt die Reduzierung eines Beweisnetzes immer noch aus einem sequentiellen Kalkülbeweis derselben Sequenz.

Daher kann die Schnitteliminierung in MLL-Proof-Netzen in linearer Zeit durchgeführt werden und ergibt ein einfaches, elegantes Schnitteliminierungsergebnis für alle MLL.

Der Proof-Nets-Ansatz kann auf größere Teilmengen der linearen Logik ausgedehnt werden, aber dann ist es weniger klar, wie die gleichen eleganten Ergebnisse wie für MLL erzielt werden können: Das in Girard 1987 vorgeschlagene ursprüngliche System funktioniert für MELL beispielsweise durch Zuordnung zu den vier Exponentialregeln die folgenden Hypergraphkonstruktionen:

  • Kontraktion

    Kontraktionskonstruktion
    Kontraktionskonstruktion
  • Schwächung

    Schwächungskonstruktion
    Schwächungskonstruktion
  • Verfall

    Verfallskonstruktion
    Verfallskonstruktion
  • Promotion, die den Begriff „Box“einführt, eine Sequentialisierungsmarke um ein Stück eines Beweisnetzes, die in den Bildern der Grafiken durch das Rechteck materialisiert ist, das um das Beweisnetz der Schlussfolgerungen (A) und (quest / Gamma) gezeichnet ist).

    Promotionsbau
    Promotionsbau

Während diese Konstruktionen und die damit verbundenen Graphenreduktionen eine bemerkenswerte Ähnlichkeit mit (lambda) - Kalkül mit expliziten Substitutionen aufweisen, wie zuerst von Di Cosmo & Kesner (1997) bemerkt, sind sie den entsprechenden Regeln für sequentielle Kalkül zu ähnlich: dem Parallelisierungseffekt So elegant für MLL wird hier nicht richtig weitergemacht, und die Regeln zur Grafikreduzierung beinhalten Kästchen und sind nicht lokal.

Um ein zufriedenstellendes System wiederherzustellen, wurden viele Vorschläge gemacht, ausgehend von dem von Danos & Regnier (1995), aber wir möchten hier den sehr eleganten Ansatz von Guerrini, Martini und Masini (Guerrini et al. 2003) erwähnen, der genau zeigt die Verbindung zwischen zwei Level-Proof-Systemen für die Modallogik, geeigneten Proof-Netzen für MELL und einer optimalen Reduzierung des (lambda) - Kalküls.

Ein kürzlich veröffentlichtes Papier von Heijltjes und Houston (2016) hat gezeigt, dass es keine zufriedenstellende Vorstellung von Beweisnetzen für MLL geben kann, wenn Einheiten ebenfalls erlaubt sind.

Eine kanonische Behandlung von additiven Konnektiven ist auch bei Quantifizierung erster Ordnung möglich (Heijltjes et al. 2018). Beweisnetze für Formeln, die sowohl multiplikative als auch additive Konnektive enthalten, weisen verschiedene technische Darstellungen auf, von denen keine kanonisch und zufriedenstellend erscheint. Ihre Behandlung in Proof-Net-ähnlichen Proof-Systemen ist derzeit Gegenstand aktiver Forschung. Siehe insbesondere (Hughes und van Glabbeek 2005) und (Hughes und Heijltjes 2016).

3. Semantik

Die Annäherung an die Semantik der linearen Logik erfolgt normalerweise auf zwei verschiedenen Wegen. Erstens stehen verschiedene semantische Strukturen zur Verfügung, mit denen Formeln Bezeichnungen in solchen Strukturen zugeordnet werden können. Dieser Ansatz kann verwendet werden, um die Solidität und Vollständigkeit für verschiedene Fragmente der linearen Logik festzustellen. Ein neuerer semantischer Ansatz für die lineare Logik besteht darin, Beweisen direkt Semantik zu verleihen. Wir beschreiben diese beiden Ansätze kurz und geben einige Links zur Literatur.

3.1 Semantik der Beweisbarkeit

Ein Ansatz zum Versuch einer soliden und vollständigen Semantik für Fragmente linearer Logik ordnet einer Formel die Menge aller Kontexte zu, die zum Beweis dieser Formel verwendet werden können. Natürlich muss eine solche Sammlung möglicherweise abstrakter sein und verschiedene Verschlusseigenschaften erhalten. Die Phasensemantik von Girard (1987) liefert eine solche Semantik: Einige Verwendungen dieser Semantik wurden in der Informatik verwendet, um Gegenbeispiele bereitzustellen, und als Werkzeug, mit dessen Hilfe festgestellt werden kann, dass sich ein gegebenes gleichzeitiges System mit bestimmten Eigenschaften nicht zu einem anderen entwickeln kann (Fages et al. 2001). In ähnlicher Weise wurde in Allwein & Dunn 1993 und Hodas & Miller 1994 eine Semantik im Kripke-Stil bereitgestellt. Quantales, bestimmte Arten von teilweise geordneten algebraischen Strukturen, wurden auch verwendet, um frühe semantische Modelle für Teile der linearen Logik bereitzustellen (Yetter 1990).

3.2 Semantik der Beweise

In der in der theoretischen Informatik so populären und fruchtbaren Formel-als-Typ-Analogie wird ein logisches System mit einem typisierten Rechengerät (wie typisiertem (lambda) - Kalkül) korrespondiert, indem jedem Beweis von zugeordnet wird diese Formel ein Programm mit dieser Formel als Typ. Zum Beispiel entspricht ein Beweis der Tautologie (A / Rightarrow A) dem Programmspaß ((x: A).x: A / rightarrow A), der Identitätsfunktion für Objekte vom Typ (A). Aus diesem Grund wird in konstruktiven logischen Systemen (wie intuitionistischer Logik und Arithmetik) und in der linearen Logik den Beweisen so viel Bedeutung beigemessen, dass das Erstellen und Studieren von Beweismodellen so viel mehr Aufmerksamkeit erhält als das Erstellen und Studieren von Modellen der Beweisbarkeit: Wir sind nicht zufrieden zu wissen, dass eine Formel nachweisbar ist,Wir wollen wirklich den rechnerischen Inhalt seines Beweises wissen.

Viele Modelle linearer Logikbeweise wurden vorgeschlagen; Wir sind der Ansicht, dass die einfachste und intuitivste Konstruktion bislang diejenige ist, die auf der sogenannten „relationalen Semantik“oder der „Kripke-Semantik“basiert, wobei Formeln als Multisets interpretiert werden, einseitige Sequenzen als Tupel von Multisets interpretiert werden und Beweise werden als Beziehungen über die Interpretation von Sequenzen interpretiert. Wenn man eine rein satztheoretische Semantik geben will, ohne auf Multisets zurückzugreifen, ist es möglich, dies mittels Kohärenzräumen zu tun, Mengen, die mit einer speziellen Kohärenzbeziehung ausgestattet sind, wie ursprünglich in Girard 1987 gezeigt. Es gibt interessante kategorietheoretische Modelle der linearen Logik wie die * -autonomen Kategorien (Barr 1991) und Hyperkohärenzen (Ehrhard 1993).

Ein anderer Ansatz zur Semantik von Beweisen ist Girards Geometrie der Interaktion, die es uns ermöglicht, eine vollständig algebraische Charakterisierung von Beweisen zu erhalten. Jedem Beweisnetz kann man eine Teilpermutationsmatrix (sigma) zuordnen, die den geschnittenen Verknüpfungen entspricht, und eine geeignete Matrix (M), die aus einer bestimmten dynamischen Algebra aufgebaut ist und die möglichen Pfade innerhalb der beschreibt Beweisnetz. Es ist dann möglich, das Beweisnetz über die Ausführungsformel vollständig zu beschreiben

) mathrm {EX} (sigma, M) = (1- / sigma ^ 2) left (sum_i M (sigma M) right) (1- / sigma ^ 2))

Dies ist im MLL-Fall eine Invariante des Normalisierungsprozesses. Eine nette Verbindung zu Ergebnissen von alt="sep man icon" /> Wie man diesen Eintrag zitiert.

Sep Mann Symbol
Sep Mann Symbol

Vorschau der PDF-Version dieses Eintrags bei den Freunden der SEP-Gesellschaft.

Inpho-Symbol
Inpho-Symbol

Schlagen Sie dieses Eintragsthema im Internet Philosophy Ontology Project (InPhO) nach.

Phil Papers Ikone
Phil Papers Ikone

Erweiterte Bibliographie für diesen Eintrag bei PhilPapers mit Links zu seiner Datenbank.

Andere Internetquellen

  • Die lineare Logikbibliographie (bis 1998).
  • Vincent Danos und Roberto Di Cosmo. Der Linear Logic Primer. Kursnotizen. (1992).

Empfohlen: