Lineaarne Loogika

2023 Autor: Noah Black | [email protected]. Viimati modifitseeritud: 2023-05-24 11:17

Sisenemise navigeerimine

• Sissesõidu sisu
• Bibliograafia
• Akadeemilised tööriistad
• Sõprade PDF-i eelvaade
• Teave autori ja tsitaadi kohta
• Tagasi üles

Lineaarne loogika

Esmakordselt avaldatud K, 6. september 2006; sisuline redaktsioon reedel 24. mail 2019

Lineaarne loogika on klassikalise ja intuitsioonilise loogika täpsustus. Tõe rõhutamise asemel, nagu klassikalises loogikas või tõestuses, nagu ka intuitionistlikus loogikas, rõhutab lineaarne loogika valemite kui ressursside rolli. Selle fookuse saavutamiseks ei võimalda lineaarne loogika tavapäraseid kokkutõmbumise ja nõrgenemise struktuurireegleid kohaldada kõigile valemitele, vaid ainult teatud modaalidega tähistatud valemitele. Lineaarne loogika sisaldab täielikult tahtmatut eitust, säilitades samal ajal tugeva konstruktiivse tõlgenduse. Lineaarne loogika pakub ka uusi teadmisi tõestuste olemusest nii klassikalises kui ka intuitsioonilises loogikas. Arvestades keskendumist ressurssidele, on lineaarne loogika arvutiteaduses leidnud palju rakendusi.

• 1. Sissejuhatus

  • 1.1 Natuke ajalugu
  • 1.2 Lineaarne loogika ja arvutiteadus

• 2. Tõestussüsteemid

  • 2.1 Järjestikune arvutus
  • 2.2 Keskendunud tõendusotsing
  • 2.3 Tõendusvõrgud

• 3. Semantika

  • 3.1 Tõendatavuse semantika
  • 3.2 Tõendite semantika
• 4. Keerukus

• 5. Arvutiteaduse mõju

  • 5.1 Tõestatud normaliseerimine
  • 5.2 Tõendusotsing

• 6. Variatsioonid

  • 6.1. Modaalsuse erinevad käsitlused
  • 6.2 Mittekommutatiivne lineaarne loogika
  • 6.3 Piiramatu käitumise kohtlemine
• Bibliograafia
• Akadeemilised tööriistad
• Muud Interneti-ressursid
• Seotud kirjed

1. Sissejuhatus

1.1 Natuke ajalugu

Lineaarset loogikat tutvustas Jean-Yves Girard oma lõputöös (Girard 1987). Ehkki selle uue loogika avastus pärineb süsteemi F (või polümorfse ((lambda)) - arvutusliku) mudelite semantilisest analüüsist, võib kogu lineaarse loogika süsteemi näha julge katsega ühitada klassikalise loogika süsteemide ilu ja sümmeetria koos konstruktiivsete tõendite otsinguga, mis oli viinud intuitionistliku loogika juurde.

Tõepoolest, kahe lihtsa vaatluse tulemusena võiks esitada lineaarse loogika fragmendi, mida tuntakse multiplikatiivse lisandina lineaarse loogikana (MALL).

• Klassikalise loogika järjestikuses arvutuslikus esituses võivad liitmike ja „või” reeglid, samuti lõikereegel ja implikatsioonireegel esitada samaväärselt lisandvormis (ruumide kontekst on sama) või korrutavat vormi (ruumide kontekst on erinev). Need kaks esitlust on klassikalises loogikas samaväärsed, kuna on olemas mõned niinimetatud “struktuurilised” reeglid, nimelt kokkutõmbumine ja nõrgenemine.
• Mittekonstruktiivsed tõestused, mida saab klassikalises loogikas täita, kasutavad järjestikuses arvutusmeetodis ühte või teist neist struktuurireeglitest.

Niisiis, kui soovime mittekonstruktiivseid tõestusi kaotada järkjärgulise arvutuse sümmeetriat hävitamata, nagu seda tehakse intuitsioonilises loogikas, võime proovida selle asemel kõrvaldada kokkutõmbumis- ja nõrgendamisreeglid. Seejuures on meil iga ühenduse jaoks kaks erinevat versiooni: aditiivne versioon ning liit- ja disjunktsiooni korrutatav versioon. Need sama ühenduse erinevad versioonid pole nüüd enam samaväärsed. Need uued ühendused on & (“koos”, lisandiga ja), (oplus) (“pluss”, lisand või, (otimes) (“tenor”, korrutatav ja) ning (lpar) (“Par”, korrutatav või).

See ühenduste dubleerimine viib tegelikult palju selgema arusaamiseni klassikalise ja intuitionistliku loogika konfliktist. Näiteks peetakse välistatud keskmise seadust ((A) või mitte - (A)) klassikalises maailmas kehtivaks ja intuitsioonistlikus absurdiks. Kuid lineaarses loogikas on sellel seadusel kaks lugemist: aditiivne versioon ((A \ oplus \ neg A)) pole tõestatav ja vastab disjunktsiooni intuitiivsele lugemisele; korrutatav versioon ((A \ lpar \ neg A)) on triviaalselt tõestatav ja vastab lihtsalt tautoloogiale ((A) tähendab (A)), mis on täiesti vastuvõetav ka intuitionistlikus loogikas.

Samuti on konstruktiivsuses hädavajalik disjunktsiooni omadus aditiivse disjunktsiooni jaoks kergesti tuvastatav.

Seejärel leiame selle rikkama loogika sees võimaluse esindada nii intuitionismi vajadusi kui ka klassikalise loogika elegantsi: eitus on tahtmatu, järjestused sümmeetrilised ja ühendused on määratletavad. Need omadused on vastuolus intuitiivse loogikaga, kus eitus ei ole tahtmatu, jadad pole sümmeetrilised ja ühendused pole kõik määratletavad.

Pange tähele, et kui ükskord on kokkutõmbumis- ja nõrgenemisreegel kõrvaldatud, ei käitu valemid enam muutumatute tõeväärtustena: tõepoolest, kui meil on lineaarses loogikas tõend (A \ Rightarrow B) ja (A)., neid komponeerides tarbime neid tõendusmaterjali (B) saamiseks, nii et (A \ Rightarrow B) ja (A) pole pärast kompositsiooni enam saadaval. Lineaarsed loogikavalemid käituvad nüüd rohkem nagu ressursid, mida saab kasutada ainult üks kord.

Intuitsionistliku ja klassikalise loogika täieliku väljendusjõu taastamiseks on vaja MALLi fragmendile lisada kaks kahesugust modaalsust, mida lineaarloogilises kirjanduses nimetatakse tavaliselt eksponentsiaalideks. Eelkõige võimaldab "muidugi" eksponentsiaal (bang) koondada ja nõrgendada valemit (bang B) vasakpoolses järjestikuses kontekstis, samas kui "miks mitte" eksponentsiaalne (quest) võimaldab valemile (quest B) parempoolses järjestikuses kontekstis rakendada kokkutõmbumist ja nõrgendamist. See viib täieliku propositsioonilise lineaarloogikani ja väga kena ühenduseni arvutiteadusega.

Pange tähele, et lisaks MALL-ile on veel kaks lineaarse loogika laialt levinud fragmenti: multiplikatiivne lineaarne loogika (MLL), mis on MALL ilma lisandühendusteta; ja multiplikatiivne eksponentsiaalne lineaarne loogika (MELL), mis on lineaarne loogika ilma lisaühendusteta.

Enne lineaarse loogika juurutamist 1987. aastal olid erinevad teadlased töötanud erinevat tüüpi substrukturaalse loogika kallal, milles kõiki Gentzeni struktuurireegleid (kokkutõmbumine, nõrgenemine ja vahetus) ei aktsepteerita. Lambek uuris järjestikuseid kivikindlaid süsteeme, milles ükski neist ehituseeskirjadest ei olnud lubatud (Lambek 1958). Sellise loogika muud näited on asjakohane loogika (milles nõrgendamist ei aktsepteerita) (Avron 1988, Loe 1988). ja afiinne loogika (milles kontraktsiooni ei aktsepteerita) (Grishin 1981).

1.2 Lineaarne loogika ja arvutiteadus

Tõestusteooria on keskendunud formaalsetele tõestussüsteemidele ja sellised formaalsed süsteemid on välja töötatud intuitionistlike predikaatkalkuluste, klassikalise predikaatkalkulatsiooni, aritmeetika ja kõrgema astme kalkulite jaoks paljude teiste hulgas. Intuitsiooniline ja konstruktiivne loogika sai alguse, kui inimesed nägid võimalust lugeda '(A \ Rightarrow B)' nagu 'kui annate mulle (A), ma annan teile (B)', mis on oluline kõrvalekalle klassikalisest lugemisest "(A) on vale või (B) on tõene".

Arvutiteadus keskendub seevastu arvutusmehhanismidele: funktsioonide rakendamine, erandite käsitlemine, meetodi kutsumine objektorienteeritud keeltes, muutuja määramine ja sarnased protsesside moodustamise reeglite kogumid. Välja arvatud see, et nende protsesside mehhanismid peavad olema selgesõnalised: funktsioon tüüp (A \ paremnool B) annab ametliku ülevaate sellest, kuidas muuta (A) (B) -ks.

Teatud hetkel need kaks meelt kohtusid. HB Curry ja W. Howard mõistsid, et implikatsiooniliste intuitiivsete järelduste kogum oli põhiline funktsionaalne keel, mida nimetatakse lihtsalt kirjutatud (lambda) - calculus: programmeerimiskeel oli loogika, loogika programmeerimiskeel. Seda meeldejäävat kohtumist kutsuti “Curry-Howardi isomorfismiks” (Howard 1980).

Lineaarne loogika annab implikatsiooni '(A \ Rightarrow B) tõlgendamisel veelgi keerdkäigu: nüüd võib seda lugeda järgmiselt:' andke mulle nii palju (A '), kui mul vaja võiks olla, ja ma annan teile üks (B) '. Koopia mõiste, mis on arvutamise idees nii keskne, on nüüd ühendatud loogikaga.

See uus vaade avab uusi võimalusi, sealhulgas:

• uued valemid, mis väljendavad rafineeritud tööomadusi, nagu 'anna mulle (A) üks kord ja ma annan sulle (B)'. Siia kuuluvad rakendused alates rafineeritud loogikaprogrammeerimisest, kus kasutatakse lineaarse loogika võimet esindada olekuid (Hodas & Miller, 1994), kuni klassikalise loogika ja selle arvutuslike tõlgenduste analüüsimiseni (Abramsky 1993) kuni erandite mehhanismide täpsustamiseni programmeerimiskeeli (Miller, 1996), lineaarsuse analüüsi (Wadler, 1991).
• uued reeglid, mis väljendavad koopiate kasutamise piiranguid, mille tulemusel saadakse polümeeride arvutamisel lineaarse loogika fragment, et mainida ainult kõige silmapaistvamat rakendust (Baillot & Terui, 2004, Baillot 2015).
• uued tõendite esindamise viisid (Abramsky & Jagadeesan, 1994, Girard 1987).

2. Tõestussüsteemid

Lineaarse loogika põhilised propositsioonilised ühendühendid jagunevad aditiivseteks ja korrutatavateks ühendusteks. Klassikaline konjunktsioon ja selle identiteet, (kiil) ja (ülemine), jagunevad lisanditeks (amp) (koos) ja (top) (ülaosa) ning korrutatavaks (otimes) (tenor) ja 1 (üks). Samamoodi jagunevad klassikaline disjunktsioon ja selle identiteet (vee) ja (bot) lisandiks (oplus) (oplus) ja 0 (null) ning korrutiseks (lpar). (par) ja (bot) (alt). Negatsiooni käsitletakse esitusviisides lineaarset loogikat kasutades üldiselt kahel viisil. Eitust võib vaadelda kui primitiivset propositsioonilist ühendit, mille valemites piiranguid selle esinemisele pole. Kuna eituse ja kõigi propositsiooniliste ühenduste, eksponentsiaalide ja kvantifikaatorite vahel on De Morgani kahesus,samuti on võimalik eitamist käsitleda spetsiaalse sümbolina, mida kasutatakse ainult aatomivalemite korral. Implikatsioonid tuuakse tavaliselt ka lineaarsesse loogikasse definitsioonide kaudu: lineaarset implikatsiooni (B \ limp C) saab määratleda kui (B ^ { bot} lpar C), intuitiivset implikatsiooni (B \ Rightarrow C) võib määratleda kui (bang B \ limp C). Operaatoreid (bang) ja (quest) nimetatakse erinevalt modaalideks või eksponentsiaalideks. Mõiste “eksponentsiaal” on eriti sobiv, kuna pärast eksponenteerimise, liitmise ja korrutamise tavapärast seost toetab lineaarne loogika ekvivalente (bang (B \ amp C) ekvivalenti (bang B \ otimes \ bang C)) ja (quest (B \ oplus C) equiv (quest B \ lpar \ quest C)), aga ka nende ekvivalentide 0-kujulised versioonid, nimelt ((bang \ top \ equiv 1)) ja ((quest 0 \ equiv \ bot)). Siinkasutame binaarset ekvivalenti (B \ equiv C), et valem ((B \ limp C) amp (C \ limp B)) oleks tuletatav lineaarses loogikas.

2.1 Järjestikune arvutus

Kahepoolne järjestikune lineaarse loogika arvutamine on esitatud alloleval joonisel. Pange tähele, et eitamist käsitletakse nagu mis tahes muud loogikat ühendavat: see tähendab, et selle esinemist valemites ei piirata ja eitamiseks vasakul ja paremal on sissejuhatuseeskirjad. Jadade vasak ja parem külg on valemite mitu osa: seega pole valemite järjekorral nendes kontekstides tähtsust, kuid nende paljususel on tähtsus.

Identiteedi reeglid) 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}) Eituse reeglid) 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) Korrutavad reeglid) 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} \ LPARi R) Lisand Rules) 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)) kvantifikaatori reeglid) 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 \ eksisteerib xB \ Gamma} \ eksisteerib R \ qquad \ frac { Delta, B [y / x] vdash \ Gamma} { Delta, \ eksisteerib xB \ vdash \ Gamma} \ eksisteerib L,) eksponentsiaalsed reeglid) 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)

Pange tähele, et nõrgenemise ja kokkutõmbumise reeglid on saadaval ainult valemite korral, mille järjestus on vasakul eksponentsiaalne (bang) või paremal (quest). Reegleid (quest) R ja (bang) L nimetatakse sageli “mahajätmise” reegliteks. Reegleid (quest) L ja (bang) R nimetatakse sageli edutamisreegliteks ja need on samad kui Kripke S4 modaalloogikas leiduvad võimaluste ja vajalikkuse reeglid. Eeldatakse, et sissejuhatuse reeglid (forall) - parempoolsed ja (eksisteerib) - vasakpoolsed: eeskätt ei tohi muutuja (y) olla vaba nende alamjärjestuse valemites. järelduse reeglid. Kvantifitseerimine eeldatakse, et see on esimese astme: lineaarse loogika kõrgema astme versioone saab kirjutada standardjoonte järgi.

Lõikamise reeglit saab kaotada ja terviklikkus säilib endiselt. Kahepoolselt saab ka init-reegli elimineerida, välja arvatud initsiatiivid, mis hõlmavad aatomi valemeid.

2.2 Keskendunud tõendid

Tähtsa normaalvormi teoreemi lõikamata tõendite struktuuri kohta esitas Andreoli (1992). Ta klassifitseeris mitteaatomilise valemi asünkroonseks, kui selle tipptasemel loogiline ühend on (top), &, (bot, \ lpar), (quest) või (forall) või sünkroonne, kui selle tipptasemel loogiline ühenduvus on (0, \ oplus, 1, \ otimes), (bang) või (eksisteerib).

Vaadeldes tõendusotsingut arvutusliku mudelina, näeme järjestuses olevaid vormeleid kui „agente”, kes võivad tegutseda iseseisvalt või kooskõlastatult oma keskkonnaga. Siin määratakse selliste esindajate tegevused nende jaoks alt-üles sissejuhatuse reegli lugemisega. Kui asünkroonne valem leiab aset jada paremal, võib see areneda ilma tõestatavust mõjutamata ja selle konteksti mõjutamata, st vastav sissejuhatuse reegel on pöördumatu. Näiteks agent ((B \ lpar C)) saab (rakendades (lpar) - parema sissejuhatuse reeglit) kaheks agendiks (B) ja (C) (töötavad nüüd paralleelselt)). Samamoodi annab agent ((B \ amp C)) (kasutades & parempoolse sissejuhatuse reeglit) kahte erinevat identset maailma (jada), välja arvatud see, et (B) on ühes neist maailmadest ja (C) on teises.

Teisest küljest, kui vaadata sünkroonset valemit agendina, mille arengu määrab vastav parempoolse sissejuhatuse reegel, siis on tõestatav jada võimeline arenema tõestamatuks jadaks (näiteks rakendades (oplus) parema sissejuhatuse reegel). Samuti sõltuvad selliste järeldusreeglite esinemisjuhud valemi konteksti üksikasjadest. Näiteks eeldab ühe parempoolse sissejuhatuse reegli edukus, et ümbritsev kontekst on tühi ja (otimes) - õige sissejuhatuse reegli edukus sõltub sellest, kuidas agendi ümbritsev kontekst jaguneb kaheks kontekstiks. Seega sõltub selliste agensite areng sünkroonimisest konteksti teiste osadega.

Vaatleme nüüd lineaarse loogika ühekülgset järjestikust arvutuslikku esitust, kus ainsad sissejuhatuseeskirjad on parempoolse sissejuhatuse reeglid. Arvestades ülaltoodud ühenduste klassifikatsiooni, on võimalik näidata, et tõendusotsingu saab struktureerida järgmistesse etappidesse ilma täielikkust kaotamata. Asünkroonne faas toimub siis, kui jadas on asünkroonne valem. Selles etapis rakendatakse parempoolse sissejuhatuse reegleid suvalises järjekorras, kuni enam pole asünkroonseid valemeid. Sünkroonses faasis valitakse mõni sünkroonne valem ja see muutub selle faasi fookuseks: see tähendab, et sellele ja kõigile võimalikele sünkroonsetele alamvormidele rakendatakse parema sissejuhatuse reegleid.

Järgmine joonis illustreerib teravustamiskindel süsteemi lineaarset loogikat. Pange tähele, et kahte faasi tähistavad erinevad nooled: üles-nool tähistab asünkroonset faasi ja allanool tähistab sünkroonset faasi. Samuti jaotatakse järjestused kolmeks tsooniks (kus tsoonid eraldatakse semikooloniga või üles või alla suunatud noolega). Eelkõige on kaks tsooni üles- ja allanoolist vasakul. Tsoon, mis on kirjutatud kui (Psi), tähistab valemit, mida saab selle järjestuse tõestuseks kasutada mitu korda. Tsoon, mis on kirjutatud kui (Delta), tähistab valemeid, mis on piiratud nagu MALL. Üles-noolt paremal asuv tsoon on ka valemitest mitu, samas kui alla-noolt paremal asuv tsoon on üks valem. Üles noolest paremal asuvatele valemitele on võimalik suvalist järjekorda seada, kuna asünkroonsete valemite sisseviimist saab teha suvalises järjekorras. Aatomitele antakse polaarsus ja alloleval joonisel tähistab (A) positiivseid aatomeid ja (A) eitus tähistab negatiivseid aatomeid. Nende järelduse reeglite järgi loodud tõestusi nimetatakse fokuseeritud tõenditeks. Andreoli 1992 tulemus on see, et fokuseeritud tõestused on lineaarse loogika jaoks täielikud.

Asünkroonne faas) frac { Üles { Psi} { Delta} {L}} { Üles { Psi} { Delta} { bot, L}}) bot] qquad \ frac { Üles { Psi, F} { Delta} {L}} { Üles { 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}} { üles { Psi} { delta} {F_1 \ amp F_2, L}}) amp])) frac { üles { Psi} { delta, F} {L}} { Üles { Psi} { Delta} {F, L}} [R \ Uparrow] \ text {tingimusel, et $ F $ ei ole asünkroonne}) sünkroonne faas) 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} { on olemas xF}}) on olemas])) frac { Üles { Psi} { Delta} {F}} { Down { Psi} { Delta} {F}} [R \ Downarrow] \ text {tingimusel, et $ F $ on kas asünkroonne või aatomiline}) Identiteedi ja otsustamise reeglid) frac {} { Down { Psi} {A} {A ^ { perp}}} [I_1] qquad \ frac {} { Down { Psi, A} { cdot} {A ^ { perp}}} [I_2] \ tekst {kus} A-tekst {on aatom})) 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] \ tekst {kus} F \ tekst {on positiivne valem})

Fokuseeritud tõestussüsteemid on loodud ka klassikalise ja intuitiivse loogika jaoks (Danos jt 1997; Laurent jt 2005; Liang & Miller 2009).

2.3 Tõendusvõrgud

Järjestikuse arvutamise abil esitatud tõestused sisaldavad palju detaile, mis mõnikord on ebahuvitavad: kaaluge näiteks, kui palju ebahuvitavalt erinevaid võimalusi on (vdash \ Gamma, (A_1 \ lpar A_2), \ ldots, (A_ {) tõestuseks. n-1} lpar A_n)) tuletisest (vdash \ Gamma, A_1, A_2, \ ldots, A_n). See ebameeldiv fakt tuleneb tõendite järjestikusest olemuses järjestikuses arvutamises: kui tahame rakendada (n) reeglite kogumit jada erinevatele osadele, ei saa me neid rakendada ühes etapis, isegi kui nad ei sega üksteist! Peame need järjestama, st valima (S) -s lineaarse järjekorra ja rakendama reegleid (n) sammudes vastavalt sellele järjekorrale.

Tekib loomulik küsimus: “Kas on olemas tõendusmaterjali esitus, mis võtab kokku sellised ebahuvitavad üksikasjad?”. Sarnasele küsimusele antakse positiivse vastuse abil intuitiivse järjestikuse arvutuse korral nn loodusliku deduktiivsuse abil, millel on Curry-Howardi kirjavahetuse kaudu tugev seos arvutusseadmega, mida tuntakse kui (lambda) - calculus.

Lineaarse loogika jaoks annavad selle tõestusmaterjali lühikese esituse tõendusvõrgud, graafikujulised struktuurid, millel on loogika MLL fragmendi jaoks eriti head omadused. Esimene samm selle esituse suunas on kogu järjestikune arvutusmeetod, kasutades eituse involutiivsust, teisendada ühepoolseks süsteemiks, kus järjestused on kujul (vdash \ Gamma). Selle tagajärjel väheneb reeglite arv, kuna meil pole vasakpoolseid sissejuhatusreegleid, kuid meil on sama väljendusjõud, kuna tõestatavus jääb samaks.

Iga MLL-s oleva arvutusliku tõestuse korral saab induktiivselt siduda tõendvõrgu samade järeldustega järgmiselt:

• Tõenduseni, mis on taandatud aksioomireeglile, seostame aksioomi lüli.

  

• Lõigete reegli kahe tõestuse abil saadud tõendusmaterjali jaoks ehitame esmalt induktiivselt nende kahe tõendiga seotud proovivõrgud ja ühendame need lõigatud lingi abil.

  

• Tõendite saamiseks, mis on saadud tensoreegli kohaldamisega kahele tõendile, ehitame esmalt induktiivselt nende kahe tõendiga seotud tõendusvõrgud ja ühendame need siis tensorlingi abil.

  

• Par-reegli kohaldamisel saadud tõendi jaoks ehitage esmalt induktiivselt selle tõendiga seotud tõendusvõrk ja lisage seejärel par-link.

  

Kõike seda saab hüpergraafide abil korralikult vormistada (valemid on sõlmed ja „lingid” on orienteeritud hüperediidid koos hüpoteeside ja järeldustega) ning tõendusvõrguna saame ametlikult määratleda hüpergraafi, mis on induktiivselt üles ehitatud MLL järjestikust arvutustuletusest. Pange tähele, et hüpergraafiaid, mis pole tõestusvõrgud, on üsna palju.

Kui vaatate tõendusvõrku, mis on ehitatud (vdash \ Gamma, (A_1 \ lpar A_2), \ ldots, (A_ {n-1} lpar A_n) tuletistest, saadud saidist (vdash \ Gamma, A_1, A_2, \ ldots, A_n), näete, et kõik reeglite kohaldamise järjekorra jäljed on kadunud. Mõnes mõttes on tõendusvõrgud järjestikuste arvutustuletuste ekvivalentsusklass nende reeglite tuletamisjärjestuse suhtes, mille rakendamine pendeldab.

Oletame, et keegi tuleb nüüd teie juurde hiiglasliku hüpergraafiga, mis on ehitatud aksioomi, lõigatud, par- ja tensoühendustega, teeseldes, et see on tegelikult mingi pikaajalise avatud matemaatilise probleemi tõestuse esitus. Kuidas saate kontrollida, kas see on tõendi kujutis, mitte ainult juhuslik struktuur?

Selle õigsuse kontrolli teostamine on väljakutse, mis seisneb teie struktuuri järjestikuse ehitusajaloo taastamises, mis vastab tuletisele järkjärgulises arvutamises, ja tundub alguses väga keeruline probleem: MLL-tõenditega võrkude esimene õigsuse kriteerium, mida nimetatakse „pikaks reisiks“kriteerium”ja eksisteerib Girardi algdokumendis, samuti hiljem leitud Danose ja Regnieri (1989) ACC (atsükliliselt ühendatud) kriteerium. Sellegipoolest on olemas Danosist ja Regnierist tulenev palju tõhusam kriteerium, mida nimetatakse kontraktiilsuseks ja mida on hiljuti ümber sõnastatud järgmise elegantse graafi parsimiskriteeriumina Guerrini, Martini ja Masini poolt: hüpergraaf on tõestatav võrk siis ja ainult siis, kui see taandub järgmiste graafi redutseerimise reeglite kaudu singleton-sõlmeks “net”

Selle kontrolli naiivne täitmine võib võtta ruutkeskmiselt aega (reegli iga rakendamine võib vajada kogu indeksi otsimist uuesti leidmiseks ja me peame tegema nii palju toiminguid, kui graafikus on hüperlinke). Lineaarsed algoritmid on andnud Guerrini (2011) ning Murawski ja Ong (2006).

MLL-võrkude õigsuse kriteeriumi teise stiili annab Retoré (2003), milles MLL-le antakse ruutmeetriline algoritm.

Proovivõrkudega saab lõiked elimineerida eriti puhtal viisil: nende paralleelsuse tõttu saab jaotustükid kohapeal kõrvaldada kahe lihtsustamisreegli abil:

• Aksiomi käik:

  

• Korrutav käik:

  

Need on tegelikult tõendusvõrkude arvutamise reeglid ja õigsuskriteeriumid võimaldavad hõlpsalt kontrollida, kas selline reegel säilitab õigsuse, ja järelikult tuleneb tõendusvõrgu vähendamine ikkagi sama jada järjestikust arvutuslikust tõestusest.

Seega saab MLL-korrosiooniga võrkudes lõigatud elimineerimise teostada lineaarselt ja see annab kogu MLL-i jaoks lihtsa, elegantse lõikamise kõrvaldamise tulemuse.

Tõendusvõrkude lähenemist saab laiendada lineaarse loogika suurematele alamhulkadele, kuid siis pole nii selge, kuidas saada sama elegantseid tulemusi kui MLL-i puhul: Girardis 1987 välja pakutud algsüsteem töötab MELL-i jaoks, seostades seda näiteks neljaga eksponentsiaalne reeglid järgmisi hüpergraafi konstruktsioonid:

• Kokkutõmbumine

  

• Nõrgenemine

  

• Hülgamine

  

• Edendamine, mis tutvustab mõistet „kasti”, järjestusmärgist korrektuurivõrgu tüki ümber, mis on graafikute piltides realiseeritud ristküliku abil, mis on tõmmatud tõendusvõrgu ümber järelduste (A) ja (quest \ Gamma).

  

Ehkki need konstruktsioonid ja nendega seotud graafi redutseerimised on silmatorkavalt sarnased otseste asendustega (lambda) - kalkuleerimisega, nagu Di Cosmo ja Kesner (1997) esmakordselt märkisid, on need liiga sarnased vastavate järjestikuste kalkuleerimisreeglitega: paralleeliefekt nii elegantne MLL-i jaoks ei tööta siin korralikult ning graafi vähenduseeskirjad hõlmavad kaste ja pole kohalikud.

Rahuldava süsteemi taastamiseks on tehtud palju ettepanekuid, alustades Danos & Regnier'ist (1995), kuid tahame siinkohal mainida Guerrini, Martini ja Masini väga elegantset lähenemist (Guerrini jt 2003), mis ilmekalt näitab ühendus modaalloogika kahetasandilise tõestussüsteemi vahel, MELL-i korralikud tõendusvõrgud ja (lambda) -kalkulatsiooni optimaalne vähendamine.

Hiljutine Heijltjesi ja Houstoni (2016) artikkel on näidanud, et MLL-i tõendusvõrkude olemasolu ei saa olla rahuldav, kui ka üksused on lubatud.

Lisandühendite kanoonilist töötlemist on võimalik pakkuda isegi esimese astme kvantifitseerimisega (Heijltjes jt 2018). Nii korrutavaid kui ka lisaaineid sisaldavate piimasegude tõestusvõrkudel on mitmesuguseid tehnilisi esitusi, millest ükski ei tundu kanooniline ega rahuldav. Nende käsitlemine võrgutaolistes tõendussüsteemides on praegu aktiivse uurimistöö teema. Eriti vt (Hughes ja van Glabbeek 2005) ja (Hughes ja Heijltjes 2016).

3. Semantika

Lineaarse loogika semantikale lähenemine toimub tavaliselt kahel erineval viisil. Esiteks on saadaval mitmesuguseid semantilisi struktuure, mida saab kasutada valemite kaardistamiseks deotatsioonidega sellistes struktuurides. Seda lähenemisviisi saab kasutada lineaarse loogika erinevate fragmentide õigsuse ja täielikkuse kindlakstegemiseks. Uudsem semantiline lähenemine lineaarsele loogikale hõlmab semantika andmist tõenditele otse. Kirjeldame lühidalt neid kahte lähenemisviisi ja pakume linke kirjandusele.

3.1 Tõendatavuse semantika

Üks lähenemisviis lineaarse loogika fragmentide usaldusväärse ja tervikliku semantika proovimiseks seostub valemiga kõigi kontekstide kogumiga, mida saab selle valemi tõestamiseks kasutada. Muidugi peab selline kollektsioon olema abstraktsem ja andma mitmesuguseid sulgemisomadusi. Girardi (1987) faasisemantika pakub ühte sellist semantikat: arvutiteaduses on sellist semantikat kasutatud ka vastunäidete pakkumiseks ja abivahendina, mis aitab kindlaks teha, et antud samaaegne süsteem ei saa areneda teatud omadustega teiseks (Fages et al. 2001). Samamoodi on Kripke-tüüpi semantikat pakutud Allwein & Dunn 1993 ja Hodas & Miller 1994. Quantales, teatud tüüpi osaliselt järjestatud algebralisi struktuure, on kasutatud ka lineaarse loogika osade varasemate semantiliste mudelite pakkumiseks (Yetter 1990).

3.2 Tõendite semantika

Teoreetilises arvutiteaduses nii populaarse ja viljaka valemite tüübianaloogias pannakse loogiline süsteem vastavusse trükitud arvutusseadmega (nagu trükitud (lambda) - calculus), seostades selle iga tõendiga see valem moodustab programmi, mille tüüp on see valem. Näiteks tautoloogia (A \ parempoolne nool A) tõend vastab programmi fun ((x: A).x: A \ rightarrow A), identiteedifunktsioon tüüpi (A) objektidele. Seetõttu omistatakse konstruktiivsetes loogilistes süsteemides (nagu intuitsiooniline loogika ja aritmeetika) ja lineaarses loogikas tõestustele nii palju tähtsust, et tõestusmudelite ehitamisele ja uurimisele pööratakse nii palju rohkem tähelepanu kui mudelite ehitamisele ja uurimisele tõestatavuse osas: meil pole rahul teadmisega, et valem on tõestatav,me tõesti tahame teada selle tõestuse arvutuslikku sisu.

Pakutud on palju lineaarsete loogiliste tõendite mudeleid; arvame, et praeguseks on kõige lihtsam ja intuitiivsem konstruktsioon nn relatsioonilise semantika või Kripke-stiilis semantika aluseks olevatest konstruktsioonidest, kus valemeid tõlgendatakse multisetsidena, ühekülgseid jada tõlgendatakse multisetside pakettidena ja tõestusi tõlgendatakse suhetena jadade tõlgendamise suhtes. Kui tahetakse anda puhtalt setteoreetilist semantikat, ilma multiseete kasutamata, on seda võimalik teha koherentsusruumide abil, komplektides, mis on varustatud spetsiaalse sidususe suhtega, nagu algselt näitas Girard 1987. On huvitavaid kategooriateooriaid. lineaarse loogika mudeleid, näiteks * -autonoomsed kategooriad (Barr 1991) ja hüperkoherentsid (Ehrhard 1993).

Veel ühe lähenemisviisi tõendite semantikale pakub Girardi interaktsiooni geomeetria, mis võimaldab meil saada tõendite täielikult algebralist kirjeldust. Iga tõendusvõrguga saab seostada lõigatud linkidele vastava osalise permutatsioonimaatriksi (sigma) ja teatud dünaamilisest algebrast välja ehitatud korraliku maatriksi (M) vastavad avaldised, mis kirjeldavad võimalikke radu tõestusvõrk. Seejärel on täitmisvalemi abil võimalik tõestusvõrku täielikult kirjeldada

) mathrm {EX} (sigma, M) = (1- \ sigma ^ 2) vasakul (sum_i M (sigma M) paremal) (1- \ sigma ^ 2))

mis MLL juhul on normaliseerimisprotsessi invariant. Mõni tore seos alt saadud tulemustega = "sep mehe ikoon" /> Kuidas seda kirjet tsiteerida.

Vaadake selle sissekande PDF-versiooni SEP-i sõprade veebisaidil.

Otsige seda sisenemisteema Interneti-filosoofia ontoloogiaprojekti (InPhO) alt.

Selle kande täiustatud bibliograafia PhilPapersis koos linkidega selle andmebaasi.

Muud Interneti-ressursid

• Lineaarloogiline bibliograafia (kuni 1998).
• Vincent Danos ja Roberto Di Cosmo. Lineaarse loogika praimer. Kursuse märkused. (1992).