Lineaire Logica

2023 Auteur: Noah Black | [email protected]. Laatst gewijzigd: 2023-11-26 16:11

Toegang navigatie

• Inhoud van het item
• Bibliografie
• Academische hulpmiddelen
• Vrienden PDF-voorbeeld
• Info over auteur en citaat
• Terug naar boven

Lineaire logica

Voor het eerst gepubliceerd op 6 september 2006; inhoudelijke herziening vr 24 mei 2019

Lineaire logica is een verfijning van klassieke en intuïtionistische logica. In plaats van waarheid te benadrukken, zoals in klassieke logica of bewijs, zoals in intuïtionistische logica, benadrukt lineaire logica de rol van formules als bronnen. Om deze focus te bereiken, staat lineaire logica niet toe dat de gebruikelijke structurele regels van contractie en verzwakking van toepassing zijn op alle formules, maar alleen op die formules die zijn gemarkeerd met bepaalde modalen. Lineaire logica bevat een volledig involutieve ontkenning met behoud van een sterke constructieve interpretatie. Lineaire logica biedt ook nieuwe inzichten in de aard van bewijzen in zowel klassieke als intuïtionistische logica. Gezien de focus op bronnen, heeft lineaire logica veel toepassingen gevonden in de informatica.

• 1. Inleiding

  • 1.1 Een beetje geschiedenis
  • 1.2 Lineaire logica en informatica

• 2. Proofsystemen

  • 2.1 Opeenvolgende calculus
  • 2.2 Gericht zoeken op proef
  • 2.3 Proefnetten

• 3. Semantiek

  • 3.1 Semantiek van bewijsbaarheid
  • 3.2 Semantiek van bewijzen
• 4. Complexiteit

• 5. Impact van informatica

  • 5.1 Proefnormalisatie
  • 5.2 Proefonderzoek

• 6. Variaties

  • 6.1 Verschillende modaliteitsbehandelingen
  • 6.2 Niet-commutatieve lineaire logica
  • 6.3 Behandeling van onbegrensd gedrag
• Bibliografie
• Academische hulpmiddelen
• Andere internetbronnen
• Gerelateerde vermeldingen

1. Inleiding

1.1 Een beetje geschiedenis

Jean-Yves Girard introduceerde lineaire logica in zijn baanbrekende werk (Girard 1987). Hoewel de oorsprong van de ontdekking van deze nieuwe logica voortkomt uit een semantische analyse van de modellen van Systeem F (of polymorfe (lambda) - calculus), kan men het hele systeem van lineaire logica zien als een gedurfde poging om de schoonheid en symmetrie van de systemen voor klassieke logica met de zoektocht naar constructieve bewijzen die tot intuïtionistische logica hadden geleid.

Je zou inderdaad een fragment van lineaire logica, bekend als multiplicatieve additieve lineaire logica (MALL), kunnen presenteren als het resultaat van twee eenvoudige waarnemingen.

• In de opeenvolgende calculuspresentatie van klassieke logica kunnen de regels voor de connectieven "en" en "of", evenals de Cut-regel en de implicatieregel equivalent worden gepresenteerd in een additieve vorm (de context van de premissen is hetzelfde) of een multiplicatieve vorm (de context van de premissen is anders). Deze twee presentaties zijn in klassieke logica gelijkwaardig vanwege de beschikbaarheid van een paar zogenaamde "structurele" regels, namelijk samentrekking en verzwakking.
• De niet-constructieve bewijzen die men in de klassieke logica kan uitvoeren, gebruiken in de opeenvolgende calculuspresentatie eigenlijk de een of de ander van deze structurele regels.

Dus als we de niet-constructieve bewijzen willen elimineren zonder de symmetrie van de opeenvolgende calculus te vernietigen, zoals wordt gedaan in de intuïtionistische logica, kunnen we in plaats daarvan proberen de regels voor contractie en verzwakking te elimineren. Daarbij blijven we achter met twee verschillende versies van elke connectieve: een additieve versie en een multiplicatieve versie van conjunctie en disjunctie. Deze verschillende versies van dezelfde verbinding zijn nu niet langer equivalent. Deze nieuwe connectieven zijn & ("met", additief en), (oplus) ("plus", additief of, (otimes) ("tensor", multiplicatief en) en (lpar) ("Par", vermenigvuldigend of).

Deze duplicatie van de connectieven leidt in feite tot een veel duidelijker begrip van het conflict tussen klassieke en intuïtionistische logica. De wet van uitgesloten midden ((A) of niet - (A)) wordt bijvoorbeeld als geldig beschouwd in de klassieke wereld en absurd in de intuïtionistische. Maar in lineaire logica heeft deze wet twee lezingen: de additieve versie ((A / oplus / neg A)) is niet aantoonbaar en komt overeen met de intuïtionistische lezing van disjunctie; de multiplicatieve versie ((A / lpar / neg A)) is triviaal bewijsbaar en komt eenvoudig overeen met de tautologie ((A) impliceert (A)) die ook volkomen acceptabel is in de intuïtionistische logica.

Ook is de disjunctie-eigenschap, essentieel in constructivisme, gemakkelijk vast te stellen voor de additieve disjunctie.

We vinden dan in deze rijkere logica een manier om zowel de behoeften van intuïtionisme als de elegantie van klassieke logica weer te geven: negatie is involutief, sequenties zijn symmetrisch en connectieven zijn onderling te definiëren. Vergelijk deze eigenschappen met die van de intuïtionistische logica, waar negatie niet involutief is, sequenties niet symmetrisch zijn en connectieven niet allemaal onderling te definiëren zijn.

Merk echter op dat zodra men de regel van samentrekking en verzwakking heeft geëlimineerd, formules zich niet langer gedragen als onveranderlijke waarheidswaarden: inderdaad, als we een bewijs hebben van (A / Rightarrow B) en een bewijs van (A) in lineaire logica, door ze te componeren, consumeren we ze eigenlijk om een bewijs van (B) te krijgen, zodat (A / Rightarrow B) en (A) niet langer beschikbaar zijn na de compositie. Lineaire logische formules gedragen zich nu meer als bronnen die maar één keer kunnen worden gebruikt.

Om de volledige expressieve kracht van intuïtionistische en klassieke logica terug te winnen, is het dan nodig om aan het MALL-fragment twee dubbele modaliteiten toe te voegen, die in de lineaire logicaliteratuur gewoonlijk exponentieel worden genoemd. In het bijzonder staat de "natuurlijk" exponentiële (bang) toe dat samentrekking en verzwakking worden toegepast op de formule (bang B) in de opeenvolgende linkercontext terwijl de "waarom-niet" exponentiële (quest) staat toe dat contractie en verzwakking worden toegepast op de formule (quest B) in de context van de rechter sequentie. Dit leidt tot de volledige propositionele lineaire logica en tot een zeer mooie connectie met informatica.

Merk op dat er naast MALL nog twee andere veelgebruikte fragmenten van lineaire logica zijn: Multiplicative Linear Logic (MLL), dat is MALL zonder de additieve connectieven; en Multiplicative Exponential Linear Logic (MELL), wat lineaire logica is zonder de additieve connectieven.

Voorafgaand aan de introductie van lineaire logica in 1987 werkten verschillende onderzoekers aan verschillende soorten substructurele logica waarin niet alle Gentzen's structurele regels (contractie, verzwakking en uitwisseling) worden geaccepteerd. Lambek bestudeerde opeenvolgende calculusbestendige systemen waarin geen van deze structurele regels was toegestaan (Lambek 1958). Andere voorbeelden van dergelijke logica zijn relevante logica (waarin verzwakking niet wordt geaccepteerd) (Avron 1988, Read 1988). en affiene logica (waarin contractie niet wordt geaccepteerd) (Grishin 1981).

1.2 Lineaire logica en informatica

Proof-theorie is gericht op formele bewijssystemen en dergelijke formele systemen zijn ontwikkeld voor intuïtionistische predikaatrekening, klassieke predikaatrekening, rekenen, hogere orde calculi, en vele andere. Intuïtionistische en constructieve logica begon toen mensen de mogelijkheid zagen om '(A / Rightarrow B)' te lezen als 'als je me een (A) geeft, dan geef ik je een (B)', wat een significante afwijking van de klassieke lezing '(A) is onwaar of (B) is waar'.

Informatica richt zich daarentegen op computationele mechanismen: functietoepassing, uitzonderingsbehandeling, methode-aanroep in objectgeoriënteerde talen, variabele toewijzing en soortgelijke sets van procesopbouwende regels. Behalve dat de mechanismen van deze processen expliciet moeten worden gemaakt: een functie van type (A / rightarrow B) geeft een formeel verslag van hoe een (A) in een (B) kan worden getransformeerd.

Op een gegeven moment ontmoetten deze twee zintuigen elkaar. HB Curry en W. Howard realiseerden zich dat het geheel van intuïtionistische deducties die uitsluitend implicaties bevatten, een functionele kerntaal was die eenvoudig-typed (lambda) - calculus werd genoemd: de programmeertaal was een logica, de logica een programmeertaal. Deze gedenkwaardige bijeenkomst heette het 'Curry-Howard-isomorfisme' (Howard 1980).

Lineaire logica zorgt voor een verdere draai in de interpretatie van de implicatie '(A / Rightarrow B)': nu kan het worden gelezen als 'geef me zoveel (A)' s als ik nodig zou kunnen hebben en ik zal je geven een (B) '. Het begrip kopiëren, dat zo centraal staat in het idee van berekening, is nu verbonden met de logica.

Dit nieuwe gezichtspunt biedt nieuwe mogelijkheden, waaronder:

• nieuwe formules die verfijnde operationele eigenschappen uitdrukken, zoals 'geef me (A) een keer en ik geef je (B)'. Toepassingen hier variëren van verfijnde logische programmering waarbij gebruik wordt gemaakt van het vermogen van lineaire logica om toestanden weer te geven (Hodas & Miller, 1994), tot de analyse van klassieke logica en computationele interpretaties daarvan (Abramsky 1993) tot de specificatie van uitzonderingsmechanismen in programmeertalen (Miller, 1996), naar lineariteitsanalyse (Wadler, 1991).
• nieuwe regels die beperkingen opleggen aan het gebruik van kopieën, resulterend in een fragment van lineaire logica voor polytime-berekeningen om alleen de meest spectaculaire toepassing te noemen (Baillot & Terui, 2004, Baillot 2015).
• nieuwe manieren om bewijzen weer te geven (Abramsky & Jagadeesan, 1994, Girard 1987).

2. Proofsystemen

De belangrijkste propositionele connectieven van lineaire logica zijn onderverdeeld in additieve en multiplicatieve connectieven. De klassieke conjunctie en zijn identiteit, (wedge) en (top), opgesplitst in het additief (amp) (met) en (top) (top) en het multiplicatieve (otimes) (tensor) en 1 (één). Evenzo splitsen de klassieke disjunctie en zijn identiteit, (vee) en (bot), zich op in het additief (oplus) (oplus) en 0 (nul) en het multiplicatieve (lpar) (par) en (bot) (onder). Negatie wordt over het algemeen op twee manieren behandeld in presentaties, een lineaire logica. Negatie kan worden gezien als een primitieve propositionele connectiviteit zonder beperkingen op het voorkomen ervan binnen formules. Aangezien De Morgan dualiteiten bestaan tussen negatie en alle propositionele connectieven, exponentiële factoren en kwantoren,het is ook mogelijk om negatie te behandelen als een speciaal symbool dat alleen voorkomt bij atoomformules. Implicaties worden ook vaak geïntroduceerd in lineaire logica via definities: de lineaire implicatie (B / limp C) kan worden gedefinieerd als (B ^ { bot} lpar C), terwijl de intuïtionistische implicatie (B / Rightarrow C) kan worden gedefinieerd als (bang B / limp C). De operators (bang) en (quest) worden ook wel modals of exponentials genoemd. De term "exponentieel" is bijzonder geschikt omdat, volgens de gebruikelijke relatie tussen machtsverheffen, optellen en vermenigvuldigen, lineaire logica de equivalenten ondersteunt (bang (B / amp C) equiv (bang B / otimes / bang C)) en (quest (B / oplus C) equiv (quest B / lpar / quest C)), evenals de 0-ary-versies van deze equivalenties, namelijk ((bang / top / equiv 1)) en ((quest 0 / equiv / bot)). Hier,we gebruiken de binaire equivalentie (B / equiv C) om aan te geven dat de formule ((B / limp C) amp (C / limp B)) afleidbaar is in lineaire logica.

2.1 Opeenvolgende calculus

Een tweezijdige sequentieberekening voor lineaire logica wordt weergegeven in de onderstaande afbeelding. Merk hier op dat negatie wordt behandeld alsof het een andere logische connectiviteit is: dat wil zeggen, het voorkomen ervan in formules is niet beperkt en er zijn links en rechts introductie regels voor negatie. De linker- en rechterkant van sequenties zijn multiset van formules: dus de volgorde van formules in deze contexten doet er niet toe, maar hun veelvoud doet er toe.

Identiteitsregels (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}) Negation Rules (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) Multiplicatieve regels(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) Aanvullende regels(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)) Quantifier Rules(frac { Delta, B [t / x] vdash / Gamma} { Delta, / forall xB / vdash / Gamma} / forall L / qquad / frac { Delta / vdash B [y / x], / Gamma} { Delta / vdash / forall xB, / Gamma} / forall R) (frac { Delta / vdash B [t / x], / Gamma} { Delta / vdash / bestaat xB / Gamma} / bestaat R / qquad / frac { Delta, B [y / x] vdash / Gamma} { Delta, / bestaat xB / vdash / Gamma} / bestaat L,) Exponentiële regels(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} { bang / Delta, / quest B / vdash / quest / Gamma} / quest L)

Merk op dat de regels voor verzwakking en contractie alleen beschikbaar zijn voor formules gemarkeerd met de exponentiële (bang) aan de linkerkant of (quest) aan de rechterkant van de sequent. De (quest) R- en (bang) L-regels worden vaak 'dereliction'-regels genoemd. De (quest) L- en (bang) R-regels worden vaak 'promotieregels' genoemd en zijn dezelfde als de mogelijkheid- en noodzaakregels in Kripke's S4 modale logica. De gebruikelijke voorwaarde voor de (forall) - rechts en (bestaat) - links introductie regels worden aangenomen: in het bijzonder mag de variabele (y) niet vrij zijn in de formules van de lagere sequentie van die gevolgtrekkingsregels. Kwantificering wordt hier als eerste orde beschouwd: hogere-orde versies van lineaire logica kunnen langs standaardlijnen worden geschreven.

De snijlijn kan worden geëlimineerd en de volledigheid blijft behouden. Tweevoudig kan de init-regel ook worden geëlimineerd, behalve voor het optreden van init met atoomformules.

2.2 Gerichte proeven

Andreoli (1992) leverde een belangrijke stelling van de normale vorm voor de structuur van snijvrije proeven. Hij classificeerde een niet-atomaire formule als asynchroon als de logische connectiviteit op het hoogste niveau (top), &, (bot, / lpar), (quest) of (forall) is. of synchroon als de logische connectiviteit op het hoogste niveau (0, / oplus, 1, / otimes), (bang) of (bestaat) is.

Wanneer we proof search als een computermodel beschouwen, kunnen we formules in een sequentie zien als 'agenten' die onafhankelijk of samen met anderen in hun omgeving kunnen optreden. Hier worden de acties van dergelijke agenten bepaald door de introductieregel voor hen van onderaf te lezen. Als een asynchrone formule rechts van een sequentie voorkomt, kan deze evolueren zonder de bewijsbaarheid te beïnvloeden en zonder interactie met de context, dat wil zeggen dat de bijbehorende introductieregel omkeerbaar is. De agent ((B / lpar C)) wordt bijvoorbeeld (door toepassing van de (lpar) - juiste introductieregel) de twee agents (B) en (C) (die nu parallel werken)). Evenzo levert de agent ((B / amp C)) (door toepassing van de & -right introductieregel) twee verschillende identieke werelden (sequenties) op, behalve dat (B) zich in een van deze werelden bevindt en (C) zit in de andere.

Aan de andere kant, als we een synchrone formule zien als een agent waarvan de evolutie wordt bepaald door de overeenkomstige rechtsintroductieregel, dan is het mogelijk dat een bewijsbare sequent evolueert naar een niet-bewijsbare sequent (bijvoorbeeld door het toepassen van de (oplus) rechts-introductie regel). Ook zijn de gevallen van dergelijke inferentieregels afhankelijk van details van de context van de formule. Het succes van de 1-rechtse introductieregel vereist bijvoorbeeld dat de omringende context leeg is en het succes van de (otimes) - juiste introductieregel hangt af van hoe de omringende context van de agent is verdeeld in twee contexten. De evolutie van dergelijke agents hangt dus af van "synchronisatie" met andere delen van de context.

Overweeg nu een eenzijdige opeenvolgende calculuspresentatie van lineaire logica waarbij de enige introductieregels de juiste introductieregels zijn. Gezien de bovenstaande classificatie van connectieven, is het mogelijk om aan te tonen dat proof search kan worden gestructureerd in de volgende fasen zonder verlies van volledigheid. De asynchrone fase treedt op als er een asynchrone formule in de sequentie aanwezig is. In deze fase worden regels voor rechtsintroductie in willekeurige volgorde toegepast totdat er geen asynchrone formules meer zijn. In de synchrone fase wordt een synchrone formule geselecteerd en wordt de "focus" van deze fase: dat wil zeggen dat de regels voor de juiste introductie erop worden toegepast en op alle synchrone subformules die het zou kunnen genereren.

De volgende afbeelding illustreert de lineaire logica van het focusseringsbestendige systeem. Merk op dat de twee fasen worden weergegeven door verschillende pijlen: de pijl-omhoog geeft de asynchrone fase aan en de pijl-omlaag geeft de synchrone fase aan. Ook zijn sequenties verdeeld in drie zones (waarbij de zones zijn gescheiden door een puntkomma of een pijl omhoog of omlaag). Met name links van de pijl-omhoog en pijl-omlaag bevinden zich de twee zones. De zone geschreven als (Psi) duidt een set formules aan die een onbeperkt aantal keren kunnen worden gebruikt in het bewijs van die sequentie. De zone geschreven als (Delta) duidt een multiset van formules aan die beperkt zijn zoals in MALL. De zone rechts van een pijl-omhoog is ook een multiset van formules, terwijl de zone rechts van een pijl-omlaag een enkele formule is. Het is mogelijk om een willekeurige volgorde op te leggen op de formules rechts van de pijl-omhoog, aangezien de introductie van asynchrone formules in elke volgorde kan worden gedaan. Atomen krijgen polariteit en in onderstaande figuur staat (A) voor positieve atomen en de negatie van (A) voor negatieve atomen. Bewijzen die door deze inferentieregels zijn opgebouwd, worden gerichte bewijzen genoemd. Het resultaat in Andreoli 1992 is dat gerichte proeven volledig zijn voor lineaire logica.

Asynchrone fase (frac { Up { Psi} { Delta} {L}} { Up { Psi} { Delta} { bot, L}} (bot] qquad / frac { Omhoog { Psi, F} { Delta} {L}} { Omhoog { 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 {op voorwaarde dat $ F $ niet asynchroon is}) Synchrone fase(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} { bestaat xF}} (bestaat]) (frac { Up { Psi} { Delta} {F}} { Down { Psi} { Delta} {F}} [R / Downarrow] / text {op voorwaarde dat $ F $ asynchroon is of een atoom}) Identiteits- en beslisregels (frac {} { Down { Psi} {A} {A ^ { perp}}} [I_1] qquad / frac {} { Down { Psi, A} { cdot} {A ^ { perp}}} [I_2] / text {where} A / text {is een atoom}) (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 {where} F / text {is een positieve formule})

Er zijn ook gerichte proofsystemen ontworpen voor klassieke en intuïtionistische logica (Danos et al. 1997; Laurent et al. 2005; Liang & Miller 2009).

2.3 Proefnetten

Bewijzen die met opeenvolgende berekeningen worden gepresenteerd, bevatten veel details die soms oninteressant zijn: overweeg bijvoorbeeld hoeveel oninteressant verschillende manieren er zijn om een bewijs te vormen van (vdash / Gamma, (A_1 / lpar A_2), / ldots, (A_ { n-1} lpar A_n)) uit een afleiding van (vdash / Gamma, A_1, A_2, / ldots, A_n). Dit onaangename feit komt voort uit het sequentiële karakter van bewijzen in sequent calculus: als we een set (S) van (n) regels willen toepassen op verschillende delen van een sequent, kunnen we ze niet in één stap toepassen, zelfs als ze interfereren niet met elkaar! We moeten ze opeenvolgen, dwz een lineaire volgorde kiezen op (S) en de regels toepassen in (n) stappen, volgens deze volgorde.

Een natuurlijke vraag rijst: "Is er een representatie van bewijzen die abstraheren van zulke oninteressante details?". Een soortgelijke vraag wordt positief beantwoord in het geval van intuïtionistische sequentiële calculus door middel van wat bekend staat als natuurlijke deductie, die via de Curry-Howard-correspondentie een sterke verbinding heeft met het computationele apparaat dat bekend staat als (lambda) - calculus.

Voor lineaire logica wordt deze beknopte weergave van bewijzen gegeven door proefnetten, grafiekachtige structuren die bijzonder goede eigenschappen hebben voor het MLL-fragment van de logica. De eerste stap in de richting van deze representatie is om het hele sequente calculussysteem, gebruikmakend van de involutiviteit van negatie, om te zetten in een eenzijdig systeem, waarin sequenties de vorm (vdash / Gamma) hebben. Als gevolg hiervan wordt het aantal regels verminderd omdat we geen regels voor linksinleiding hebben, maar we behouden dezelfde expressieve kracht, omdat de bewijsbaarheid hetzelfde blijft.

Aan elke opeenvolgende calculusproef in MLL kan men inductief een proefnet associëren met dezelfde conclusies als volgt:

• Om een bewijs terug te brengen tot de axioma-regel, associëren we een axioma-link.

  

• Voor een proef die is verkregen door de snijlijn toe te passen op twee proefdrukken, bouwen we eerst inductief de proefnetten die bij die twee proefdrukken horen, en combineren we ze vervolgens met behulp van een afgesneden schakel.

  

• Voor een bewijs dat is verkregen door de tensorregel op twee proeven toe te passen, bouwen we eerst inductief de proefnetten die bij die twee proeven horen, en combineren we ze vervolgens met behulp van een tensorverbinding.

  

• Voor een bewijs dat is verkregen door de par-regel toe te passen op een bewijs, bouwt u eerst inductief het proefnet dat bij dat bewijs hoort, en dan voegen we een "par-link" toe.

  

Dit alles kan op de juiste manier worden geformaliseerd met behulp van hypergrafen (formules zijn knooppunten en 'links' zijn georiënteerde hypergrenzen met hypothesen en conclusies), en we kunnen formeel een hypergraaf definiëren dat inductief is opgebouwd uit een sequentiële calculusafleiding van MLL. Merk op dat er nogal wat hypergrafen zijn die geen proefnetten zijn.

Als je nu kijkt naar het bewijsnet dat is opgebouwd uit de afleidingen van (vdash / Gamma, (A_1 / lpar A_2), / ldots, (A_ {n-1} lpar A_n)) verkregen uit (vdash / Gamma, A_1, A_2, / ldots, A_n), je zult zien dat alle sporen van de volgorde van toepassing van de regels zijn verdwenen. In zekere zin zijn de bewijsnetten een equivalentieklasse van opeenvolgende calculusafleidingen met betrekking tot de afleidingsvolgorde van regels waarvan de toepassing pendelt.

Stel dat iemand nu naar je toe komt met een enorme hypergraaf gebouwd met axioma-, cut-, par- en tensor-links, alsof hij eigenlijk een weergave is van het bewijs van een al lang bestaand open wiskundig probleem. Hoe kun je verifiëren dat het eigenlijk een weergave van een bewijs is, en niet alleen een willekeurige structuur?

Het uitvoeren van deze correctheidscontrole is een uitdaging die neerkomt op het opnieuw opbouwen van een sequentiële constructiehistorie voor uw constructie, overeenkomend met een afleiding in sequentiële calculus, en lijkt in eerste instantie een zeer complex probleem: het eerste correctheidscriterium voor MLL-proof netten, de "lange reis" genoemd criterium”, en aanwezig in het originele artikel van Girard, is exponentieel, evenals het ACC (Acyclisch verbonden) criterium van Danos en Regnier (1989) dat later werd gevonden. Desalniettemin bestaat er een veel efficiënter criterium, bekend als contractibiliteit, vanwege Danos en Regnier, dat recentelijk door Guerrini, Martini en Masini is geherformuleerd als het volgende elegante ontledingscriterium voor grafieken: een hypergraaf is een proefnet als en alleen als het wordt gereduceerd tot het singleton-knooppunt "net" via de volgende regels voor grafiekreductie

Het naïef uitvoeren van deze controle kan kwadratisch duren (elke toepassing van een regel vereist mogelijk een volledige opzoeking van de grafiek om de redex te vinden, en we moeten zoveel stappen uitvoeren als er hyperlinks in de grafiek zijn). Er zijn lineaire tijdalgoritmen gegeven door Guerrini (2011) en door Murawski en Ong (2006).

Een andere stijl van correctheidscriterium voor MLL-proofnetten wordt gegeven door Retoré (2003) waarin een kwadratisch algoritme wordt gegeven voor MLL.

Op proefnetten kan men op een bijzonder schone manier de uitsnijding van sneden uitvoeren: vanwege hun parallelle karakter kunnen sneden lokaal worden geëlimineerd via twee vereenvoudigingsregels:

• Axioma-beweging:

  

• Multiplicatieve zet:

  

Dit zijn eigenlijk rekenregels over proefnetten, en met de juistheidscriteria kan gemakkelijk worden geverifieerd dat een dergelijke regel de juistheid behoudt, en als gevolg daarvan komt de verkleining van een proefnet nog steeds voort uit een opeenvolgend calculusbewijs van dezelfde reeks.

Daarom kan de eliminatie van snijwonden in MLL-proof netten in lineaire tijd worden uitgevoerd en geeft het een eenvoudig, elegant snij-eliminatieresultaat voor heel MLL.

De proefnettenbenadering kan worden uitgebreid tot grotere subsets van lineaire logica, maar dan is het minder duidelijk hoe dezelfde elegante resultaten kunnen worden verkregen als voor MLL: het oorspronkelijke systeem dat in Girard 1987 wordt voorgesteld, werkt voor MELL, bijvoorbeeld door te associëren met de vier exponentieel regeert de volgende hypergraafconstructies:

• Contractie

  

• Verzwakking

  

• Verval

  

• Promotie, die het begrip "box" introduceert, een volgordemarkering rond een stuk van een proefnet dat in de afbeeldingen van de grafieken is gematerialiseerd door de rechthoek die is getekend rond het proefnet van conclusies (A) en (quest / Gamma).

  

Hoewel deze constructies en de bijbehorende grafiekreducties opvallende gelijkenis vertonen met (lambda) - calculus met expliciete substituties, zoals voor het eerst opgemerkt door Di Cosmo & Kesner (1997), lijken ze te veel op de corresponderende opeenvolgende rekenregels: het parallellisatie-effect zo elegant voor MLL gaat hier niet goed door, en de regels voor grafiekreductie hebben betrekking op vakken en zijn niet lokaal.

Om een bevredigend systeem te herstellen, zijn er veel voorstellen gedaan, te beginnen met die van Danos & Regnier (1995), maar we willen hier de zeer elegante benadering van Guerrini, Martini en Masini (Guerrini et al. 2003) noemen, die netjes laat zien de verbinding tussen twee niveau-proof systemen voor modale logica, goede proof-netten voor MELL, en een optimale reductie van de (lambda) - calculus.

Een recent artikel van Heijltjes en Houston (2016) heeft aangetoond dat er geen bevredigend idee bestaat van proefnetten voor MLL als eenheden ook zijn toegestaan.

Het is mogelijk om zelfs met eerste-orde kwantificering een canonieke behandeling van additieve connectieven te bieden (Heijltjes et al.2018). Proefnetten voor formules die zowel multiplicatieve als additieve connectieven bevatten, hebben verschillende technische presentaties, die geen van allen canoniek en bevredigend lijken. Hun behandeling in proof-net-achtige proofsystemen is momenteel onderwerp van actief onderzoek. Zie met name (Hughes en van Glabbeek 2005) en (Hughes en Heijltjes 2016).

3. Semantiek

Het benaderen van de semantiek van lineaire logica gebeurt meestal langs twee verschillende paden. Ten eerste zijn er verschillende semantische structuren beschikbaar die kunnen worden gebruikt om formules toe te wijzen aan aanduidingen in dergelijke structuren. Die benadering kan worden gebruikt om deugdelijkheid en volledigheid vast te stellen voor verschillende fragmenten van lineaire logica. Een meer nieuwe semantische benadering van lineaire logica houdt in dat semantiek direct aan bewijzen wordt gegeven. We beschrijven deze twee benaderingen kort en geven enkele links naar de literatuur.

3.1 Semantiek van bewijsbaarheid

Eén benadering om een degelijke en volledige semantiek te proberen voor fragmenten van lineaire logische associaties met een formule, de verzameling van alle contexten die kunnen worden gebruikt om die formule te bewijzen. Het kan natuurlijk nodig zijn dat een dergelijke collectie abstracter moet zijn en verschillende sluitingseigenschappen moet krijgen. De fase-semantiek van Girard (1987) biedt zo'n semantiek: sommige toepassingen van dergelijke semantiek zijn in de informatica gebruikt om tegenvoorbeelden te geven en als een hulpmiddel dat kan helpen vaststellen dat een bepaald gelijktijdig systeem niet kan evolueren naar een ander met bepaalde eigenschappen (Fages et al. 2001). Evenzo zijn semantiek in Kripke-stijl verschaft in Allwein & Dunn 1993 en Hodas & Miller 1994. Quantales, een bepaald soort gedeeltelijk geordende algebraïsche structuren, zijn ook gebruikt om vroege semantische modellen te verschaffen voor delen van lineaire logica (Yetter 1990).

3.2 Semantiek van bewijzen

In de formules-als-typen-analogie die zo populair en vruchtbaar is in de theoretische informatica, wordt een logisch systeem in overeenstemming gebracht met een getypt computerapparaat (zoals getypt (lambda) - calculus), door te associëren met elk bewijs van die formule een programma met die formule als een type. Een bewijs van de tautologie (A / Rightarrow A) komt bijvoorbeeld overeen met het programma fun ((x: A).x: A / rightarrow A), de identiteitsfunctie op objecten van type (A). Daarom wordt in constructieve logische systemen (zoals intuïtionistische logica en rekenkunde) en in lineaire logica zoveel belang gehecht aan bewijzen, dat het bouwen en bestuderen van proefmodellen zoveel meer aandacht krijgt dan het bouwen en bestuderen van modellen van bewijsbaarheid: we zijn niet tevreden om te weten dat een formule bewijsbaar is,we willen echt de computationele inhoud van het bewijs weten.

Er zijn veel modellen van lineaire logische bewijzen voorgesteld; we zijn van mening dat tot nu toe de eenvoudigste en meest intuïtieve constructie die is die is gebaseerd op de zogenaamde "relationele semantiek" of "Kripke-achtige semantiek", waarbij formules worden geïnterpreteerd als multisets, eenzijdige sequenties worden geïnterpreteerd als tuples van multisets en bewijzen worden geïnterpreteerd als relaties boven de interpretatie van sequenties. Als men een puur set-theoretische semantiek wil geven, zonder zijn toevlucht te nemen tot multisets, is het mogelijk om dit te doen door middel van coherentieruimten, sets uitgerust met een speciale coherentierelatie, zoals oorspronkelijk aangetoond door Girard 1987. Er zijn interessante categorietheoretische modellen van lineaire logica, zoals de * -autonome categorieën (Barr 1991) en hypercoherenties (Ehrhard 1993).

Een andere benadering van de semantiek van bewijzen wordt gegeven door Girard's Geometry of Interaction, waarmee we een volledig algebraïsche karakterisering van bewijzen kunnen verkrijgen. Aan elk proefnet kan men een gedeeltelijke permutatiematrix (sigma) koppelen die overeenkomt met de geknipte links, en een eigen matrix (M) corresponderende uitdrukkingen die zijn opgebouwd uit een bepaalde dynamische algebra, die de mogelijke paden binnen de bewijsnet. Het is dan mogelijk om het proofnet volledig te beschrijven via de uitvoeringsformule

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

wat in het geval van MLL een invariant is van het normalisatieproces. Een mooie connectie met resultaten afkomstig van alt = "sep man icon" /> Hoe deze vermelding te citeren.

Bekijk een voorbeeld van de PDF-versie van dit item bij de Vrienden van de SEP Society.

Zoek dit itemonderwerp op bij het Internet Philosophy Ontology Project (InPhO).

Verbeterde bibliografie voor dit item op PhilPapers, met links naar de database.

Andere internetbronnen

• De lineaire logische bibliografie (tot 1998).
• Vincent Danos en Roberto Di Cosmo. De lineaire logische primer. Cursusnotities. (1992).