Lineárna Logika

Obsah:

Lineárna Logika
Lineárna Logika

Video: Lineárna Logika

Video: Lineárna Logika
Video: 1. Доказательство в интуиционистской и классической логиках 2024, Marec
Anonim

Vstupná navigácia

  • Obsah vstupu
  • Bibliografia
  • Akademické nástroje
  • Náhľad priateľov PDF
  • Informácie o autorovi a citácii
  • Späť na začiatok

Lineárna logika

Prvýkrát zverejnené 6. septembra 2006; podstatná revízia piatok 24. mája 2019

Lineárna logika je zdokonalením klasickej a intuitívnej logiky. Namiesto zdôrazňovania pravdy, ako v klasickej logike alebo v dôkazoch, ako v intuicionálnej logike, lineárna logika zdôrazňuje úlohu vzorcov ako zdrojov. Na dosiahnutie tohto zamerania lineárna logika neumožňuje, aby sa obvyklé štrukturálne pravidlá kontrakcie a oslabenia uplatňovali na všetky vzorce, ale iba na tie vzorce, ktoré sú označené určitými druhmi. Lineárna logika obsahuje úplne implicitnú negáciu pri zachovaní silnej konštruktívnej interpretácie. Lineárna logika tiež poskytuje nové pohľady na povahu dôkazov v klasickej aj intuičnej logike. Lineárna logika vzhľadom na svoje zameranie na zdroje našla v počítačovej vede veľa aplikácií.

  • 1. Úvod

    • 1.1 Trocha histórie
    • 1.2 Lineárna logika a informatika
  • 2. Dôkazové systémy

    • 2.1 Sekvenčný počet
    • 2.2 Zamerané vyhľadávanie dôkazov
    • 2.3 Dôkazové siete
  • 3. Sémantika

    • 3.1 Sémantika preukázateľnosti
    • 3.2 Sémantika dôkazov
  • 4. Zložitosť
  • 5. Dopad informatiky

    • 5.1 Dôkazná normalizácia
    • 5.2 Dôkazové vyhľadávanie
  • 6. Variácie

    • 6.1 Rôzne spôsoby zaobchádzania
    • 6.2 nekomutatívna lineárna logika
    • 6.3 Zaobchádzanie s neobmedzeným správaním
  • Bibliografia
  • Akademické nástroje
  • Ďalšie internetové zdroje
  • Súvisiace záznamy

1. Úvod

1.1 Trocha histórie

Lineárnu logiku predstavil Jean-Yves Girard vo svojej kľúčovej práci (Girard 1987). Zatiaľ čo pôvod objavu tejto novej logiky pochádza zo sémantickej analýzy modelov systému F (alebo polymorfného (lambda) - počtu), celý systém lineárnej logiky možno vidieť ako odvážny pokus o zmierenie krása a symetria systémov klasickej logiky s hľadaním konštruktívnych dôkazov, ktoré viedli k intuicionálnej logike.

V skutočnosti by bolo možné uviesť výsledok lineárnej logiky, známej ako multiplikatívna aditívna lineárna logika (MALL), ako výsledok dvoch jednoduchých pozorovaní.

  • V postupnej prezentácii klasickej logiky sa pravidlá pre spojky „a“a „alebo“, ako aj pravidlo Cut a pravidlo pre implikáciu môžu prezentovať rovnocenne v aditívnej forme (kontext priestorov je rovnaký)) alebo multiplikatívna forma (kontext priestorov je odlišný). Tieto dve prezentácie sú v klasickej logike rovnocenné z dôvodu dostupnosti niekoľkých takzvaných „štrukturálnych“pravidiel, konkrétne kontrakcie a oslabenia.
  • Nekonštruktívne dôkazy, ktoré človek môže predviesť v klasickej logike, skutočne používajú pri prezentácii kalkulu jeden alebo druhý z týchto štrukturálnych pravidiel.

Ak teda chceme eliminovať nekonštruktívne dôkazy bez toho, aby sme zničili symetriu postupného počtu, ako sa to robí v intuičnej logike, môžeme sa namiesto toho pokúsiť eliminovať pravidlá kontrakcie a oslabenia. Pritom nám zostávajú dve rôzne verzie každého spojiva: doplnková verzia a multiplikatívna verzia spojenia a disjunkcie. Tieto rôzne verzie toho istého pripojenia už nie sú rovnocenné. Tieto nové spojky sú & („s“, aditívne a), (oplus) („plus“, aditívne alebo, (otimes) („tenzorové“, multiplikatívne a) a (lpar) („Par“, multiplikatívne alebo).

Táto duplikácia spojív v skutočnosti vedie k oveľa jasnejšiemu pochopeniu konfliktu medzi klasickou a intuičnou logikou. Napríklad zákon vylúčeného stredného ((A) alebo nie - (A)) sa považuje za platný v klasickom svete a absurdný v intuicionálnom svete. Ale v lineárnej logike má tento zákon dve čítania: aditívna verzia ((A / oplus / neg A)) nie je preukázateľná a zodpovedá intuitívnemu čítaniu disjunkcie; multiplikatívna verzia ((A / lpar / neg A)) je triviálne preukázateľná a jednoducho zodpovedá tautológii ((A) implikuje (A)), čo je úplne prijateľné aj v intuičnej logike.

Tiež disjunkčná vlastnosť, nevyhnutná v konštruktivizme, sa ľahko stanoví pre aditívne disjunkcia.

V tejto bohatšej logike potom nachádzame spôsob, ako reprezentovať potreby intuicionizmu a elegancie klasickej logiky: negácia je bezprecedentná, sekvencie sú symetrické a spoje sú definované. Kontrastujú tieto vlastnosti s tými, ktoré majú intuicionálnu logiku, kde negácia nie je nevyhnutná, sekvencie nie sú symetrické a spojivá nie sú definované.

Všimnite si však, že akonáhle sme odstránili pravidlo kontrakcie a oslabenia, vzorce sa už nebudú správať ako nemenné hodnoty pravdy: skutočne, keď máme dôkaz o (A / Rightarrow B) a dôkaz o (A) v lineárnej logike, ich zložením ich vlastne konzumujeme, aby sme získali dôkaz o (B), takže (A / Rightarrow B) a (A) už nie sú k dispozícii po zložení. Lineárne logické vzorce sa teraz správajú skôr ako zdroje, ktoré sa dajú použiť iba raz.

Na obnovenie plnej expresívnej sily intuicionálnej a klasickej logiky je potom potrebné do fragmentu MALL pridať dve duálne modality, ktoré sa v lineárnej logickej literatúre obvykle nazývajú exponenciálne. Najmä "samozrejme" exponenciálny (bang) umožňuje kontrakciu a oslabenie, ktoré sa majú aplikovať na vzorec (bang B) v ľavom sekvenčnom kontexte, zatiaľ čo "prečo nie" exponenciálny (quest) povoľuje kontrakciu a oslabenie na vzorec (quest B) v pravom poradí. To vedie k úplnej výrokovej lineárnej logike ak veľmi peknému prepojeniu s počítačovou vedou.

Všimnite si, že okrem MALL existujú ďalšie dva často používané fragmenty lineárnej logiky: Multiplikatívna lineárna logika (MLL), ktorá je MALL bez aditívnych spojív; a multiplikatívna exponenciálna lineárna logika (MELL), čo je lineárna logika bez aditívnych spojív.

Pred zavedením lineárnej logiky v roku 1987 rôzni vedci pracovali na rôznych druhoch subštruktúrnej logiky, v ktorej nie sú akceptované všetky Gentzenove štrukturálne pravidlá (kontrakcia, oslabenie a výmena). Lambek študoval postupné systémy ochrany proti počtu, v ktorých nebolo povolené žiadne z týchto štrukturálnych pravidiel (Lambek 1958). Ďalšími príkladmi takejto logiky sú relevantné logiky (v ktorých oslabenie nie je akceptované) (Avron 1988, Read 1988). a afinná logika (v ktorej kontrakcia nie je akceptovaná) (Grishin 1981).

1.2 Lineárna logika a informatika

Dôkazová teória je zameraná na formálne korektívne systémy a také formálne systémy boli vyvinuté pre intuicionálny predikátový počet, klasický predikátový počet, aritmetiku, kalkulácie vyššieho rádu a mnoho ďalších. Intuitionistická a konštruktívna logika sa začala, keď ľudia videli možnosť čítať '(A / Rightarrow B)' ako 'ak mi dáte (A), dám ti (B)', čo je výrazný odklon od klasického čítania „(A) je nepravdivý alebo (B) je pravdivý“.

Počítačová veda sa naopak zameriava na výpočtové mechanizmy: aplikácia funkcií, spracovanie výnimiek, vyvolávanie metód v objektovo orientovaných jazykoch, priradenie premenných a podobné súbory pravidiel budovania procesov. S výnimkou toho, že mechanizmy týchto procesov je potrebné výslovne uviesť: funkcia typu (A / rightarrow B) formálne vysvetľuje, ako transformovať (A) na (B).

V danom okamihu sa tieto dva zmysly stretli. HB Curry a W. Howard si uvedomili, že množina intuitívnych dedukčných odvodení iba pre implikáciu je základným funkčným jazykom nazývaným jednoducho napísaný (lambda) - počet: programovací jazyk je logika, logika programovací jazyk. Toto nezabudnuteľné stretnutie sa volalo „Curry-Howardov izomorfizmus“(Howard 1980).

Lineárna logika poskytuje ďalšie zvraty vo výklade implikácie '(A / Rightarrow B)': teraz sa dá čítať ako 'daj mi toľko (A)', koľko budem potrebovať, a dám ti jeden (B) '. Pojem kópia, ktorý je tak ústredný pre myšlienku výpočtu, je teraz zapojený do logiky.

Toto nové hľadisko otvára nové možnosti vrátane:

  • nové vzorce vyjadrujúce vylepšené prevádzkové vlastnosti, ako napríklad „daj mi raz (A) a dám ti (B)“. Aplikácie sa pohybujú od rafinovaného logického programovania, v ktorom sa využíva schopnosť lineárnej logiky reprezentovať štáty (Hodas & Miller, 1994), až po analýzu jej klasických logických a výpočtových interpretácií (Abramsky 1993), až po špecifikáciu mechanizmov výnimiek v programovacie jazyky (Miller, 1996), na analýzu linearity (Wadler, 1991).
  • nové pravidlá vyjadrujúce obmedzenia týkajúce sa používania kópií, ktoré vedú k fragmentu lineárnej logiky pre výpočty v polytime, aby bolo možné spomenúť iba najokázalejšiu aplikáciu (Baillot & Terui, 2004, Baillot 2015).
  • nové spôsoby reprezentácie dôkazov (Abramsky & Jagadeesan, 1994, Girard 1987).

2. Dôkazové systémy

Základné výrokové spojky lineárnej logiky sú rozdelené na aditívne a multiplikatívne. Klasická konjunkcia a jej identita (wedge) a (top) sa rozdelia na aditívum (amp) (with) a (top) (top) a multiplikative (otimes) (tensor) a 1 (one). Podobne klasický disjunkcia a jej identita (vee) a (bot) sa rozdelia na aditívum (oplus) (oplus) a 0 (nula) a multiplikatívne (lpar). (par) a (bot) (dole). Negácia sa v prezentáciách spravidla považuje za lineárnu logiku jedným z dvoch spôsobov. Negáciu je možné vnímať ako primitívny výrokový spojovací výraz bez obmedzenia ich výskytu v rámci vzorcov. Keďže De Morganove duality existujú medzi negáciou a všetkými výrokovými spojivami, exponenciálmi a kvantifikátormi,je tiež možné považovať negáciu za špeciálny symbol, ktorý sa vyskytuje iba pri atómových vzorcoch. Implikácie sa tiež bežne zavádzajú do lineárnej logiky pomocou definícií: lineárna implikácia (B / limp C) sa dá definovať ako (B ^ { bot} lpar C), zatiaľ čo intuicionálna implikácia (B / Rightarrow C) možno definovať ako (bang B / limp C). Operátory (bang) a (quest) sa nazývajú rôzne spôsoby alebo exponenciály. Termín „exponenciálny“je obzvlášť vhodný, pretože po obvyklom vzťahu medzi exponentíciou, sčítaním a multiplikáciou lineárna logika podporuje ekvivalencie (bang (B / amp C) equiv (bang B / otimes / bang C)) a (quest (B / oplus C) equiv (quest B / lpar / quest C)), ako aj 0-ročných verzií týchto ekvivalencií, konkrétne ((bang / top / equiv) 1)) a ((quest 0 / equiv / bot)). Tu,binárna ekvivalencia (B / ekviv. C) znamená, že vzorec ((B / limp C) amp (C / limp B)) je odvoditeľný v lineárnej logike.

2.1 Sekvenčný počet

Na nasledujúcom obrázku je uvedený dvojstranný sekvenčný počet pre lineárnu logiku. Všimnite si tu, že negácia sa považuje za inú logickú spojitosť: to znamená, že jej výskyt vo vzorcoch nie je obmedzený a vľavo a vpravo sú stanovené pravidlá pre negáciu. Ľavá a pravá strana sekvencií je multiset vzorcov: preto poradie vzorcov v týchto kontextoch nezáleží, ale na ich multiplicite záleží.

Pravidlá identity (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}) Negatívne pravidlá (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) Multiplikačné pravidlá(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) Pravidlá prísad(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)) Kvantifikačné pravidlá(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 / existuje xB / Gamma} / existuje R / qquad / frac { Delta, B [y / x] vdash / Gamma} { Delta, / existuje xB / vdash / Gamma} / existuje L,) Exponenciálne pravidlá(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} { tresk / Delta, / quest B / vdash / quest / Gamma} / quest L)

Všimnite si, že pravidlá oslabenia a kontrakcie sú dostupné iba pre vzorce označené exponenciálnym (bang) vľavo alebo (quest) napravo od poradca. Pravidlá (quest) R a (bang) L sa často nazývajú pravidlá "develiction". Pravidlá (quest) L a (bang) R sa často nazývajú „propagačné“pravidlá a sú rovnaké ako pravidlá možnosti a nevyhnutnosti, ktoré sa nachádzajú v modálnej logike spoločnosti Kripke S4. Predpokladá sa obvyklá výhrada pre pravidlá zavedenia pravého (forall) pravého a (existujúceho) ľavého: najmä premenná (y) nesmie byť voľná vo vzorcoch nižšej sekvencie týchto inferenčné pravidlá. Predpokladá sa, že kvantifikácia je prvého poriadku: verzie lineárnej logiky vyšších rádov možno písať podľa štandardných riadkov.

Pravidlo strihu je možné vylúčiť a jeho úplnosť je stále zachovaná. Pravidlo init môže byť tiež vylúčené tiež s výnimkou prípadov, keď sa vyskytujú atómy zahŕňajúce atómové vzorce.

2.2 Zamerané dôkazy

Dôležitú normálnu tvarovú vetu pre štruktúru dôkazov bez orezania poskytol Andreoli (1992). Klasifikoval nematický vzorec ako asynchrónny, ak jeho logické spojivo najvyššej úrovne je (top), &, (bot, / lpar), (quest) alebo (forall) alebo synchrónne, ak jeho logické spojivo najvyššej úrovne je (0, / oplus, 1, / otimes), (bang) alebo (existuje).

Pri hľadaní korektného vyhľadávania ako výpočtového modelu vidíme vzorce v poradí ako „agenti“, ktorí môžu vo svojom prostredí konať nezávisle alebo v zhode s ostatnými. Činnosti týchto činiteľov sa tu určujú prečítaním úvodného pravidla pre nich zdola nahor. Ak sa asynchrónny vzorec vyskytuje napravo od postupníka, môže sa vyvíjať bez toho, aby to ovplyvnilo preukázateľnosť a bez interakcie s jeho kontextom, tj príslušné pravidlo zavedenia je nevratné. Napríklad agent ((B / lpar C)) sa (uplatnením pravidla (lpar) - pravého úvodného pravidla) stane dvoma agentmi (B) a (C) (teraz pracujú paralelne)). Podobne agent ((B / amp C)) poskytuje (použitím pravidla pravého úvodu) dva rôzne rovnaké svety (postupnosti) s výnimkou toho, že (B) je v jednom z týchto svetov a (C) je v druhom.

Na druhej strane, ak vidíme synchrónny vzorec ako agenta, ktorého vývoj je určený zodpovedajúcim pravidlom na zavedenie práva, potom je možné, aby sa preukázateľná sekvencia vyvinula na nepreukázateľnú sekvenciu (napríklad použitím (oplus) pravidlo zavedenia práva). Prípady takýchto inferenčných pravidiel tiež závisia od detailov kontextu kontextu. Napríklad úspech pravidla pre pravú introdukciu 1 vyžaduje, aby bol okolitý kontext prázdny a úspech pravého pravidla pre zavedenie (otimes) závisí od toho, ako je okolitý kontext agenta rozdelený do dvoch kontextov. Vývoj takýchto činiteľov teda závisí od „synchronizácie“s inými časťami kontextu.

Teraz zvážte jednostrannú sekvenčnú prezentáciu lineárnej logiky, kde jedinými pravidlami zavádzania sú pravidlá správneho zavádzania. Vzhľadom na uvedenú klasifikáciu spojív je možné preukázať, že vyhľadávanie dôkazov možno rozdeliť do nasledujúcich fáz bez straty úplnosti. Asynchrónna fáza nastane, ak je v sekvencii prítomný asynchrónny vzorec. V tejto fáze sa pravidlá zavádzania práva uplatňujú v akomkoľvek poradí, až kým neexistujú žiadne ďalšie asynchrónne vzorce. V synchrónnej fáze sa vyberie nejaký synchrónny vzorec, ktorý sa stane „zameraním“tejto fázy: to znamená, že na ňu a na všetky synchrónne podformuly, ktoré môže vygenerovať, sa uplatňujú pravidlá na správne zavedenie.

Nasledujúci obrázok ilustruje lineárnu logiku systému korekcie zaostrenia. Všimnite si, že dve fázy sú reprezentované rôznymi šípkami: šípka hore označuje asynchrónnu fázu a šípka dole označuje synchrónnu fázu. Sekvencie sú tiež rozdelené do troch zón (kde sú zóny oddelené bodkočiarkou alebo šípkou nahor alebo nadol). Najmä naľavo od šípky hore a dole sú dve zóny. Zóna napísaná ako (Psi) označuje množinu vzorcov, ktoré je možné v doklade o tomto postupe použiť ľubovoľný počet krát. Zóna napísaná ako (Delta) označuje multiset vzorcov, ktoré sú obmedzené ako v MALL. Zóna napravo od šípky hore je tiež multiset vzorcov, zatiaľ čo zóna napravo od šípky nadol je jednoduchý vzorec. Je možné nariadiť svojvoľné poradie vzorcov napravo od šípky nahor, pretože zavedenie asynchrónnych vzorcov sa môže vykonať v akomkoľvek poradí. Atómy sú dané polaritou a na nasledujúcom obrázku znamená (A) kladné atómy a negácia (A) predstavuje záporné atómy. Dôkazy vyhotovené na základe týchto inferenčných pravidiel sa nazývajú cielené dôkazy. Výsledkom v Andreoli 1992 je, že sústredené dôkazy sú kompletné pre lineárnu logiku.

Asynchrónna fáza (frac { Up { Psi} { Delta} {L}} { Up { Psi} { Delta} { bot, L}} (bot] qquad / frac { Hore { Psi, F} { Delta} {L}} { Hore { Psi} { Delta} { quest F, L}} (quest]) (frac {} { Hore { 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 {za predpokladu, že $ F $ nie je asynchrónny}) Synchrónna fáza(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} { existuje xF}} (existuje]) (frac { Up { Psi} { Delta} {F}} { Down { Psi} { Delta} {F}} [R / Downarrow] / text {za predpokladu, že $ F $ je asynchrónny alebo atóm}) Pravidlá identity a rozhodovania (frac {} { Down { Psi} {A} {A ^ { perp}}} [I_1] qquad / frac {} { Down { Psi, A} { cdot} {A ^ { perp}}} [I_2] / text {where} A / text {je atóm}) (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 {pričom} F / text {je pozitívny vzorec})

Zaostrené kontrolné systémy boli navrhnuté aj pre klasickú a intuitívnu logiku (Danos a kol. 1997; Laurent a kol. 2005; Liang & Miller 2009).

2.3 Dôkazové siete

Dôkazy predložené pomocou sekvenčného počtu obsahujú veľa detailov, ktoré niekedy nie sú zaujímavé: zvážte napríklad, koľko nezaujímavo odlišných spôsobov, ako existuje dôkaz o (vdash / Gamma, (A_1 / lpar A_2), / ldots, (A_ { n-1} lpar A_n)) z derivácie (vdash / Gamma, A_1, A_2, / ldots, A_n). Táto nepríjemná skutočnosť vyplýva zo sekvenčnej povahy dôkazov v sekvenčnom kalkulu: ak chceme aplikovať množinu (S) pravidiel (n) na rôzne časti postupníka, nemôžeme ich uplatniť v jednom kroku, aj keď nezasahujú navzájom! Musíme ich postupne sekvenovať, tj zvoliť lineárne poradie v (S) a aplikovať pravidlá v (n) krokoch, podľa tohto poradia.

Vynára sa prirodzená otázka: „Existuje znázornenie dôkazov, ktoré odoberajú tieto nezaujímavé podrobnosti?“. Podobná otázka je zodpovedaná pozitívne v prípade intuicionálneho sekvenčného počtu pomocou tzv. Prirodzeného odpočtu, ktorý má prostredníctvom Curryho-Howardovej korešpondencie silné spojenie s výpočtovým zariadením známym ako (lambda) - počet,

Pre lineárnu logiku je toto stručné znázornenie dôkazov založené na sieťach, grafických štruktúrach, ktoré majú zvlášť dobré vlastnosti pre MLL fragment logiky. Prvým krokom k tejto reprezentácii je konvertovať celý sekvenčný kalkulárny systém s použitím nepriepustnosti negácie na jednostranný systém, kde sú sekvencie v tvare (vdash / Gamma). V dôsledku toho sa počet pravidiel zníži, pretože nemáme žiadne pravidlá na úvodné zavedenie, ale zachovávame si rovnakú výrazovú moc, pretože preukázateľnosť zostáva rovnaká.

Ku každému následnému počtu dôkazov v MLL je možné indukčne priradiť kontrolnú sieť s tými istými závermi:

  • K dôkazu zredukovanému na pravidlo axiómu spájame axiómové spojenie.

    Axiom net
    Axiom net
  • Pre dôkaz získaný uplatnením pravidla strihu na dva dôkazy najprv najskôr indukčne vytvoríme siete na testovanie spojené s týmito dvoma dôkazmi a potom ich skombinujeme pomocou odkazu na strih.

    Rezaná sieťová konštrukcia
    Rezaná sieťová konštrukcia
  • Pre dôkaz získaný uplatnením tenzorového pravidla na dva dôkazy najskôr najskôr indukčne vytvoríme siete na priradenie k týmto dvom dôkazom a potom ich skombinujeme pomocou tenzorového spojenia.

    Konštrukcia tenzorovej siete
    Konštrukcia tenzorovej siete
  • Pre dôkaz získaný uplatnením pravidla par na dôkaz najskôr najskôr indukčne vytvorte sieť dôkazov spojenú s týmto dôkazom a potom pridáme „par link“.

    Konštrukcia siete
    Konštrukcia siete

To všetko sa dá správne formalizovať pomocou hypergrafov (vzorce sú uzly a „odkazy“sú orientované hyperedgey s hypotézami a závermi) a ako formálnu sieť môžeme formálne definovať hypergraf induktívne zostavený zo sekvenčnej derivácie MLL. Všimnite si, že existuje pomerne veľa hypergrafov, ktoré nie sú dôkazovými sieťami.

Ak sa teraz pozriete na kontrolnú sieť vytvorenú z derivácií (vdash / Gamma, (A_1 / lpar A_2), / ldots, (A_ {n-1} lpar A_n)) získaných z (vdash / Gamma, A_1, A_2, / ldots, A_n), uvidíte, že všetky stopy po poradí uplatňovania pravidiel zmizli. V určitom zmysle sú kontrolné siete rovnocennou triedou postupných derivácií počtu, pokiaľ ide o poradie odvodenia pravidiel, ktorých aplikácia je doložená.

Predpokladajme, že k vám niekto teraz prichádza s obrovským hypergrafom vytvoreným s axiomovými, reznými, par a tenzorovými väzbami, ktorý predstiera, že je to v skutočnosti reprezentácia dôkazu nejakého dlhodobého otvoreného matematického problému. Ako môžete overiť, že v skutočnosti ide o reprezentáciu dôkazu, a nie iba o náhodnú štruktúru?

Vykonanie tejto kontroly správnosti je výzvou, ktorá predstavuje prebudovanie postupnej konštrukčnej histórie vašej štruktúry, ktorá zodpovedá derivácii v postupnom počte, a na prvý pohľad sa javí ako veľmi zložitý problém: prvé kritérium správnosti pre kontrolné siete MLL, nazývané „dlhá cesta“kritérium “a je prítomný v Girardovom pôvodnom dokumente, je exponenciálny, ako aj ACC (Acyklicky spojené) kritérium Danos a Regnier (1989), ktoré sa nachádza neskôr. Napriek tomu existuje oveľa efektívnejšie kritérium, známe ako kontrahabilita, kvôli Danosovi a Regnierovi, ktoré nedávno preformulovali Guerrini, Martini a Masini ako nasledujúce elegantné kritérium analýzy grafov: hypergraf je dôkazovou sieťou iba vtedy, ak redukuje sa na singletonový uzol „net“pomocou nasledujúcich pravidiel na zníženie grafu

Analýza grafov pre čisté rozpoznávanie dôkazov MLL
Analýza grafov pre čisté rozpoznávanie dôkazov MLL

Vykonanie tejto kontroly naivne môže trvať kvadratický čas (každá aplikácia pravidla môže vyžadovať úplné vyhľadanie grafu, aby sa našiel redex, a my musíme vykonať toľko krokov, koľko je hypertextových odkazov v grafe). Algoritmy lineárneho času poskytli Guerrini (2011) a Murawski a Ong (2006).

Ďalší štýl kritéria správnosti sietí na dôkaz MLL je uvedený v Retoré (2003), v ktorom je pre MLL daný kvadratický algoritmus.

Na skúšobných sieťach je možné odstraňovanie strihov vykonávať zvlášť čistým spôsobom: vďaka svojej paralelnej povahe je možné rezy odstrániť lokálne pomocou dvoch pravidiel zjednodušenia:

  • Pohyb axiom:

    Axiom sa pohol
    Axiom sa pohol
  • Násobný ťah:

    Multiplikatívny ťah
    Multiplikatívny ťah

V skutočnosti ide o pravidlá výpočtu overovacích sietí a kritériá správnosti umožňujú ľahko overiť, či také pravidlo zachováva správnosť, a v dôsledku toho zníženie dôkaznej siete stále pochádza z následného dôkazu toho istého poradia.

Odstránenie rezu v sieťach odolných voči MLL sa preto môže vykonávať v lineárnom čase a poskytuje jednoduchý a elegantný výsledok odstránenia rezov pre všetky MLL.

Prístup pomocou kontrolných sietí možno rozšíriť na väčšie podmnožiny lineárnej logiky, ale potom je menej jasné, ako dosiahnuť rovnaké elegantné výsledky ako pre MLL: pôvodný systém navrhnutý v Girarde 1987 pracuje pre MELL, napríklad priradením k štyrom exponenciálne pravidlá nasledujúce hypergrafické konštrukcie:

  • Kontrakcie

    Konštrukcia stavby
    Konštrukcia stavby
  • oslabenie

    Oslabená konštrukcia
    Oslabená konštrukcia
  • opustenosť

    Konštrukcia opúšťania
    Konštrukcia opúšťania
  • Propagácia, ktorou sa zavádza pojem „box“, sekvenčná značka okolo kusu skúšobnej siete zhmotnená na obrázkoch grafov pomocou obdĺžnika nakresleného okolo skúšobnej siete záverov (A) a (quest / Gamma).

    Propagačná výstavba
    Propagačná výstavba

Aj keď tieto konštrukcie a súvisiace redukcie grafov vykazujú výraznú podobnosť s (lambda) - kalkul s explicitnými substitúciami, ako to prvýkrát poznamenal Di Cosmo & Kesner (1997), sú príliš podobné zodpovedajúcim pravidlám postupného počtu: paralelný efekt tak elegantný pre MLL tu nefunguje správne a pravidlá na zníženie grafu zahŕňajú políčka a nie sú miestne.

Aby sa dosiahol uspokojivý systém, bolo predložených veľa návrhov, počnúc tým, ktorý predložil Danos & Regnier (1995), ale tu by sme chceli spomenúť veľmi elegantný prístup Guerriniho, Martiniho a Masiniho (Guerrini et al. 2003), ktorý prehľadne ukazuje spojenie medzi dvomi úrovňami korektných systémov pre modálnu logiku, správnymi korekčnými sieťami pre MELL a optimálnym znížením počtu (lambda).

Nedávny príspevok spoločnosti Heijltjes a Houston (2016) ukázal, že pokiaľ sú povolené aj jednotky, nemôže existovať uspokojivá predstava sietí dôkazov pre MLL.

Je možné poskytnúť kanonické spracovanie aditívnych spojív, dokonca aj pri kvantifikácii prvého poriadku (Heijltjes et al. 2018). Dôkazové siete pre recepty obsahujúce multiplikatívne aj aditívne spojivá majú rôzne technické úpravy, z ktorých žiadna nie je kanonická a uspokojivá. Ich spracovanie v dôkazových sieťach podobných systémom je v súčasnosti predmetom aktívneho výskumu. Pozri najmä (Hughes a van Glabbeek 2005) a (Hughes a Heijltjes 2016).

3. Sémantika

Sémantika lineárnej logiky sa obvykle približuje dvoma rôznymi cestami. Po prvé, sú k dispozícii rôzne sémantické štruktúry, ktoré sa môžu použiť na mapovanie vzorcov na označenia v týchto štruktúrach. Tento prístup sa môže použiť na stanovenie spoľahlivosti a úplnosti rôznych fragmentov lineárnej logiky. Novší sémantický prístup k lineárnej logike zahŕňa priame sémantiku. Stručne opíšeme tieto dva prístupy a poskytneme niekoľko odkazov na literatúru.

3.1 Sémantika preukázateľnosti

Jeden prístup k pokusu o zvukovú a úplnú sémantiku pre fragmenty lineárnej logiky spája vzorec so súborom všetkých kontextov, ktoré sa môžu použiť na preukázanie tohto vzorca. Takáto zbierka bude samozrejme musieť byť abstraktnejšia a musí mať rôzne uzatváracie vlastnosti. Fázová sémantika Girarda (1987) poskytuje jednu takúto sémantiku: niektoré použitia tejto sémantiky sa v oblasti počítačovej vedy uskutočnili s cieľom poskytnúť protiklady a ako nástroj, ktorý môže pomôcť preukázať, že daný súbežný systém sa nemôže vyvinúť do iného s určitými vlastnosťami (Fages et al. 2001). Podobne, sémantika Kripkeho štýlu bola poskytnutá v Allwein & Dunn 1993 a Hodas & Miller 1994. Quantales, istý druh čiastočne usporiadaných algebraických štruktúr, sa tiež použili na poskytnutie skorých sémantických modelov pre časti lineárnej logiky (Yetter 1990).

3.2 Sémantika dôkazov

V analógii vzorcov podľa typu, ktorá je taká populárna a plodná v teoretickej informatike, sa logický systém uvádza do súladu s typickým výpočtovým zariadením (ako je napísaný (lambda) - počet) tým, že priraďuje ku každému dôkazu tento vzorec program, ktorý má tento vzorec ako typ. Napríklad dôkaz tautológie (A / Rightarrow A) zodpovedá programu fun ((x: A).x: A / rightarrow A), funkcii identity objektov typu (A), To je dôvod, prečo v konštruktívnych logických systémoch (ako je intuicionálna logika a aritmetika) a v lineárnej logike sa prikladá toľko dôležitosti dôkazom, a to do tej miery, že budovaniu a štúdiu modelov dôkazov sa venuje oveľa viac pozornosti ako pri zostavovaní a študovaní modelov. preukázateľnosti: nie sme spokojní, keď vieme, že vzorec je preukázateľný,naozaj chceme poznať výpočtový obsah jeho dôkazu.

Bolo navrhnutých veľa modelov lineárnych logických dôkazov; Domnievame sa, že najjednoduchšia a najintuitívnejšia konštrukcia je doteraz taká, ktorá je založená na tzv. „relačnej sémantike“alebo „sémantike podľa Kripkeho štýlu“, kde sa vzorce interpretujú ako multiset, jednostranné sekvencie sa interpretujú ako n-tice multisetov a dôkazy sa interpretujú ako vzťahy týkajúce sa interpretácie sekvencií. Ak chceme dať čisto teoretickú sémantiku, bez toho, aby sme sa uchýlili k multisetom, je možné to urobiť pomocou koherentných priestorov, súborov vybavených špeciálnym koherenčným vzťahom, ako to pôvodne ukázal Girard 1987. Existuje zaujímavá kategória teoretická. modely lineárnej logiky, ako sú * - autonómne kategórie (Barr 1991) a hyperkoferencie (Ehrhard 1993).

Ďalší prístup k sémantike dôkazov predstavuje Girardova geometria interakcie, ktorá nám umožňuje získať úplnú algebraickú charakterizáciu dôkazov. Ku každej skúšobnej sieti je možné priradiť čiastočnú permutačnú maticu (sigma) zodpovedajúcu strihaným spojom a správnu maticu (M) zodpovedajúce výrazy zostavené z určitej dynamickej algebry, ktoré opisujú možné cesty vo vnútri sieť na dôkaz. Potom je možné podrobne opísať kontrolnú sieť prostredníctvom vzorcu vykonania

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

čo je v prípade MLL invariantný proces normalizácie. Pekné spojenie s výsledkami pochádzajúcimi z alt="sep man icon" /> Ako citovať tento záznam.

ikona sep muž
ikona sep muž

Ukážku verzie tohto príspevku vo formáte PDF si môžete pozrieť na stránke Friends of the SEP Society.

ikona
ikona

Vyhľadajte túto vstupnú tému v projekte Internet Philosophy Ontology Project (InPhO).

ikona phil papiere
ikona phil papiere

Vylepšená bibliografia tohto záznamu vo PhilPapers s odkazmi na jeho databázu.

Ďalšie internetové zdroje

  • Lineárna logická bibliografia (do roku 1998).
  • Vincent Danos a Roberto Di Cosmo. Lineárny logický základný náter. Poznámky k kurzu. (1992).

Odporúčaná: