Lineārā Loģika

Satura rādītājs:

Lineārā Loģika
Lineārā Loģika

Video: Lineārā Loģika

Video: Lineārā Loģika
Video: Кобордизмы и коммутативные категориальные грамматики. Сергей Славнов (17.12.2020) 2024, Marts
Anonim

Ieejas navigācija

  • Iestāšanās saturs
  • Bibliogrāfija
  • Akadēmiskie rīki
  • Draugu PDF priekšskatījums
  • Informācija par autoru un atsauce
  • Atpakaļ uz augšu

Lineārā loģika

Pirmoreiz publicēts trešdien, 2006. gada 6. septembrī; būtiska pārskatīšana - piektdien, 2019. gada 24. maijā

Lineārā loģika ir klasiskās un intuitīvās loģikas uzlabojums. Tā vietā, lai uzsvērtu patiesību, piemēram, klasiskajā loģikā vai pierādījumos, tāpat kā intuitionistiskajā loģikā, lineārā loģika uzsver formulu kā resursu lomu. Lai sasniegtu šo fokusu, lineārā loģika neļauj parastos strukturālos kontrakcijas un vājināšanās noteikumus piemērot visām formulām, bet tikai tām formulām, kas apzīmētas ar noteiktiem modeļiem. Lineārā loģika satur pilnīgi negribīgu noliegumu, saglabājot spēcīgu konstruktīvu interpretāciju. Lineārā loģika sniedz arī jaunu ieskatu pierādījumu būtībā gan klasiskajā, gan intuitīvajā loģikā. Ņemot vērā koncentrēšanos uz resursiem, lineārā loģika ir atradusi daudzus lietojumus datorzinātnēs.

  • 1. Ievads

    • 1.1 Nedaudz vēstures
    • 1.2 Lineārā loģika un datorzinātnes
  • 2. Pārbaudes sistēmas

    • 2.1. Secīgais aprēķins
    • 2.2. Koncentrēta pierādījumu meklēšana
    • 2.3 Pārliecinoši tīkli
  • 3. Semantika

    • 3.1. Pārbaudāmības semantika
    • 3.2. Pierādījumu semantika
  • 4. Sarežģītība
  • 5. Datorzinātnes ietekme

    • 5.1. Pierādījums normalizēšanai
    • 5.2 Pārbaude ar pierādījumiem
  • 6. Variācijas

    • 6.1. Dažāda veida modifikācija
    • 6.2 Nekomutējoša lineārā loģika
    • 6.3 Neierobežotas izturēšanās ārstēšana
  • Bibliogrāfija
  • Akadēmiskie rīki
  • Citi interneta resursi
  • Saistītie ieraksti

1. Ievads

1.1 Nedaudz vēstures

Lineāro loģiku ieviesa Žans Īvs Girards savā pamatdarbā (Girard 1987). Kaut arī šīs jaunās loģikas atklāšanas cēlonis ir sistēmas F (vai polimorfā (lambda) - aprēķina) modeļu semantiskā analīze, visu lineārās loģikas sistēmu var redzēt kā drosmīgu mēģinājumu saskaņot klasiskās loģikas sistēmu skaistums un simetrija ar konstruktīvu pierādījumu meklējumiem, kas noveda pie intuitīvās loģikas.

Patiešām, kā divu vienkāršu novērojumu iznākumu varētu parādīt lineārās loģikas fragmentu, kas pazīstams kā multiplikatīvās piedevas lineārā loģika (MALL).

  • Secīgajā klasiskās loģikas noformējumā savienojumu “un” un “vai” noteikumus, kā arī izgriezuma likumu un implicēšanas likumu var noformēt līdzvērtīgi papildinošā formā (telpu konteksts ir vienāds) vai reizinošu formu (telpu konteksts ir atšķirīgs). Šīs divas prezentācijas ir līdzvērtīgas klasiskajā loģikā, jo ir pieejami daži tā sauktie “strukturālie” noteikumi, proti, kontrakcijas un vājināšanās.
  • Nekonstruktīvie pierādījumi, ko var veikt klasiskajā loģikā, secīgajā aprēķina formā faktiski izmanto vienu vai otru no šiem strukturālajiem noteikumiem.

Tātad, ja mēs vēlamies novērst nekonstruktīvos pierādījumus, neiznīcinot secīgās kalkulatūras simetriju, kā tas tiek darīts intuitionistiskajā loģikā, mēs varam mēģināt tā vietā novērst saraušanās un vājināšanas noteikumus. To darot, mums paliek divas atšķirīgas katra savienojuma versijas: pievienojošā versija un daudzkārtējā savienojuma un disjunkcijas versija. Šīs vienas un tās pašas savienojuma dažādās versijas tagad vairs nav līdzvērtīgas. Šie jaunie savienojumi ir & (“ar”, piedevas un), (oplus) (“plus”, piedevas vai, (otimes) (“tenzors”, reizināšanas un) un (lpar) (“Par”, reizinošs vai).

Šī savienotājelementu dublēšanās faktiski ļauj daudz skaidrāk izprast konfliktu starp klasisko un intuitionistisko loģiku. Piemēram, izslēgtā vidējā likuma ((A) vai nē - (A)) likumi tiek uzskatīti par spēkā esošajiem klasiskajā pasaulē un absurdi - intuitionistiskajā. Bet lineārajā loģikā šim likumam ir divi lasījumi: piedevas versija ((A / oplus / neg A)) nav pierādāma un atbilst disjunkcijas intuitīvai lasīšanai; reizinošā versija ((A / lpar / neg A)) ir triviāli pierādāma un vienkārši atbilst tautoloģijai ((A) nozīmē (A)), kas ir pilnīgi pieņemama arī intuitīvisma loģikā.

Arī konjunktivitātē būtiska disjunction īpašība ir viegli nosakāma piedevas disjunction.

Tad bagātākās loģikas iekšienē mēs atrodam veidu, kā attēlot gan intuitīvisma vajadzības, gan klasiskās loģikas eleganci: noliegums ir neaptverams, sekvences ir simetriskas un savienojošie elementi ir savstarpēji definējami. Pretstatā šīm īpašībām ar intuitīvās loģikas īpašībām, kur noliegums nav neaptverams, sekvences nav simetriskas, un visi savienojumi nav savstarpēji definējami.

Tomēr ievērojiet, ka pēc tam, kad ir novērsta sašaurināšanās un vājinošā norma, formulas vairs neuzvedas kā nemainīgas patiesības vērtības: patiešām, ja mums ir pierādījums (A / Rightarrow B) un (A) pierādījums lineārā loģikā, tos komponējot, mēs tos faktiski patērējam, lai iegūtu (B) pierādījumu, lai (A / Rightarrow B) un (A) pēc kompozīcijas vairs nebūtu pieejami. Lineārās loģikas formulas tagad darbojas vairāk kā resursi, kurus var izmantot tikai vienu reizi.

Lai atgūtu intuitīvās un klasiskās loģikas pilnu izteiksmīgo spēku, MALL fragmentam ir jāpievieno divas dubultās modalitātes, kuras lineārās loģikas literatūrā parasti sauc par eksponentiem. Proti, “protams” eksponenciāls (bang) ļauj sašaurināt un vājināt formulu (bang B) kreisās puses secīgajā kontekstā, bet “kāpēc ne” eksponenciāls (quest) ļauj saīsināt un vājināt formulu (quest B) labās kārtas secīgajā kontekstā. Tas noved pie pilnīgas piedāvājuma lineāras loģikas un ļoti jauka savienojuma ar datorzinātnēm.

Ievērojiet, ka papildus MALL ir vēl divi plaši izmantoti lineārās loģikas fragmenti: multiplikative Linear Logic (MLL), kas ir MALL bez piedevu savienojumiem; un multiplikatīvā eksponenciālā lineārā loģika (MELL), kas ir lineārā loģika bez piedevām.

Pirms lineārās loģikas ieviešanas 1987. gadā dažādi pētnieki strādāja pie dažāda veida substruktūras loģikas, kurā nav pieņemti visi Gentzen strukturālie noteikumi (saraušanās, vājināšanās un apmaiņa). Lambeks pētīja secīgas aprēķina necaurlaidīgas sistēmas, kurās neviens no šiem strukturālajiem noteikumiem nebija atļauts (Lambek 1958). Citi šādas loģikas piemēri ir atbilstoša loģika (kurā vājināšana nav pieņemta) (Avron 1988, Read 1988). un afīniskā loģika (kurā kontrakcijas netiek pieņemtas) (Grišins 1981).

1.2 Lineārā loģika un datorzinātnes

Pierādīšanas teorija ir vērsta uz formālu pierādījumu sistēmām, un šādas formālās sistēmas ir izstrādātas intuitionistic predikāta aprēķinam, klasiskajam predikāta aprēķinam, aritmētikai, augstākas kārtas aprēķiniem, starp daudziem citiem. Intuitionistiska un konstruktīva loģika sākās, kad cilvēki redzēja iespēju lasīt '(A / Rightarrow B)' kā 'ja jūs man piešķirat (A), es jums došu (B)', kas ir ievērojama atkāpe no klasiskā lasījuma “(A) ir nepatiesa vai (B) ir pareiza”.

Savukārt datorzinātnes koncentrējas uz skaitļošanas mehānismiem: funkciju piemērošanu, izņēmumu apstrādi, metožu piesaisti objektorientētās valodās, mainīgo piešķiršanu un līdzīgus procesu veidošanas noteikumu kopumus. Izņemot to, ka šo procesu mehānismiem jābūt skaidri izteiktiem: veida (A / labā bulta) funkcija sniedz oficiālu pārskatu par to, kā pārveidot (A) par (B).

Noteiktā brīdī šīs divas maņas satikās. HB Karijs un W. Hovards saprata, ka tikai implicējošu intuitionistu atskaitījumu kopums ir galvenā funkcionālā valoda, ko sauc par vienkārši rakstītu (lambda) - calculus: programmēšanas valoda bija loģika, loģika - programmēšanas valoda. Šo neaizmirstamo tikšanos sauca par “Karija-Hovarda izomorfismu” (Hovards 1980).

Lineārā loģika nodrošina turpmāku implicācijas '(A / Rightarrow B) interpretāciju: tagad to var lasīt kā' dodiet man tik daudz (A), cik man varētu būt nepieciešams, un es jums to sniegšu. viens (B)”. Kopijas jēdziens, kas ir tik svarīgs skaitļošanas idejai, tagad ir iekļauts loģikā.

Šis jaunais skats paver jaunas iespējas, tostarp:

  • jaunas formulas, kas izsaka izsmalcinātas darbības īpašības, piemēram, “dod man (A) vienreiz, un es tev sniegšu (B)”. Pielietojumi šeit svārstās no rafinētas loģikas programmēšanas, kur tiek izmantota lineārās loģikas spēja reprezentēt stāvokļus (Hodas & Miller, 1994), līdz klasiskās loģikas analīzei un to aprēķināšanas interpretācijai (Abramsky 1993) līdz izņēmumu mehānismu specifikācijai programmēšanas valodas (Miller, 1996), līdz linearitātes analīzei (Wadler, 1991).
  • jaunie noteikumi, kas izsaka ierobežojumus eksemplāru izmantošanai, kā rezultātā polimēra aprēķiniem veidojas lineāras loģikas fragments, lai pieminētu tikai visievērojamāko pielietojumu (Baillot & Terui, 2004, Baillot 2015).
  • jauni pierādījumu attēlošanas veidi (Abramsky & Jagadeesan, 1994, Girard 1987).

2. Pārbaudes sistēmas

Galvenie lineārās loģikas ierosinošie savienojumi ir sadalīti pievienojošos un reizinošos savienojumos. Klasiskais savienojums un tā identitāte, (ķīlis) un (top), sadalās piedevās (amp) (ar) un (top) (augšā) un reizinošajā (otimes) (tensors) un 1 (viens). Tāpat klasiskā disjunkcija un tās identitāte (vee) un (bot) sadalās piedevās (oplus) (oplus) un 0 (nulle) un reizināmajā (lpar). (par) un (bot) (apakšā). Negatīvu attieksmi parasti apstrādā vienā no diviem veidiem, izmantojot lineāru loģiku. Neigāciju var uzskatīt par primitīvu ierosinošu savienojumu, bez ierobežojumiem tā rašanās formulās. Tā kā De morgana divējādības pastāv starp noliegumu un visiem ierosinošajiem savienojumiem, eksponentiem un skaitļiem,ir arī iespējams traktēt noliegumu kā īpašu simbolu, kas rodas tikai atomu formulās. Ietekmi parasti arī ievieš lineārajā loģikā, izmantojot definīcijas: lineāro implikāciju (B / limp C) var definēt kā (B ^ { bot} lpar C), savukārt intuitīvo implicīciju (B / Rightarrow C) var definēt kā (bang B / limp C). Operatorus (bang) un (quest) dažādi sauc par modāliem vai eksponentiem. Termins “eksponenciāls” ir īpaši piemērots, jo pēc parastajām attiecībām starp eksponenciāciju, saskaitīšanu un reizināšanu, lineārā loģika atbalsta ekvivalences (sprādziens (B / amp C) ekvivalents (sprādziens B / otimes / bangs C)) un (quest (B / oplus C) equiv (quest B / lpar / quest C)), kā arī šo ekvivalentu 0-versiju versijas, proti, ((bang / top / equiv 1)) un ((Quest 0 / equiv / bot)). Šeit,mēs izmantojam bināro ekvivalenci (B / equiv C), lai nozīmētu, ka formula ((B / limp C) amp (C / limp B)) ir iegūstama lineārā loģikā.

2.1. Secīgais aprēķins

Divpusējs secīgs aprēķins lineārajai loģikai ir parādīts zemāk redzamajā attēlā. Ievērojiet, ka noliegums tiek traktēts tā, it kā tas būtu jebkurš cits loģisks savienojums: tas ir, tā parādīšanās formulās nav ierobežota, un nolikuma kreisajā un labajā pusē ir ievada noteikumi. Secību kreisajā un labajā pusē ir daudzskaitlī izteiktas formulas: tādējādi formulu secībai šajos kontekstos nav nozīmes, bet gan to daudzkārtībai ir nozīme.

Identitātes noteikumi (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}) Neigācijas noteikumi (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) Reizinošie noteikumi(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) Piedevu noteikumi(frac {} { Delta, / nulle / vdash / Gamma} / nulle 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)) kvantitatīvie noteikumi(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 / eksistē xB / Gamma} / eksistē R / qquad / frac { Delta, B [y / x] vdash / Gamma} { Delta, / eksistē xB / vdash / Gamma} / eksistē L,) eksponenciālie noteikumi(frac { Delta / vdash / Gamma} { Delta, / bang B / vdash / Gamma} / bang W / quad / frac { Delta, / bang B, / bang B / vdash / Gamma} { Delta, / sprādziena B / vdash / gamma} / sprādziena C / quad / frac { Delta, B / vdash / Gamma} { Delta, / sprādziena B / vdash / gamma} / sprādziena D) (frac { Delta / vdash / Gamma} { Delta / vdash / quest B, / Gamma} / quest W / quad / frac { Delta / vdash / quest B, / quest B, / Gamma} { Delta / vdash / meklēt B, / gamma} / meklēt C / quad / frac { Delta / vdash B, / Gamma} { Delta / vdash / meklēt B, / Gamma} / meklēt 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)

Ievērojiet, ka pavājināšanās un saraušanās noteikumi ir pieejami tikai formulām, kuras ir iezīmētas ar eksponenciālu (bang) kreisajā pusē vai (quest) sekvences labajā pusē. (Quest) R un (bang) L noteikumus bieži sauc par “atmešanas” noteikumiem. (Quest) L un (bang) R noteikumus bieži sauc par “paaugstināšanas” noteikumiem, un tie ir tādi paši kā iespēju un nepieciešamības noteikumi, kas atrodami Kripke S4 modālā loģikā. Tiek pieņemts, ka ievada (forall) - labās un (eksistē) - kreisās ievada normas: jo īpaši mainīgais (y) nedrīkst būt brīvs to apakšējā secībā. secinājumu noteikumi. Kvantitatīvā noteikšana šeit tiek pieņemta kā pirmās kārtas: lineāras loģikas augstākas kārtas versijas var rakstīt pa standarta rindiņām.

Griezuma likumu var novērst, un tā pilnība joprojām tiek saglabāta. Divējādos gadījumos var izslēgt arī init likumu, izņemot iniciācijas gadījumus, kuros iesaistītas atomu formulas.

2.2. Koncentrēti pierādījumi

Svarīgu normālas formas teorēmu izgriezumu bez izkārtojuma struktūrai sniedza Andreoli (1992). Viņš atomu formulu klasificēja kā asinhrono, ja tā augstākā līmeņa loģiskais savienojums ir (top), &, (bot, / lpar), (quest) vai (forall). vai sinhronizēts, ja tā augstākā līmeņa loģiskais savienojums ir (0, / oplus, 1, / otimes), (bang) vai (eksistē).

Apskatot pierādījumu meklēšanu kā skaitļošanas modeli, secībā esošās formulas varam redzēt kā “aģentus”, kas var rīkoties neatkarīgi vai saskaņoti ar citiem savā vidē. Šeit šādu aģentu rīcību nosaka, nolasot ievada likumu par tiem no apakšas. Ja sekvences labajā pusē rodas asinhrona formula, tā var attīstīties, neietekmējot provalabitāti un neiejaucoties tās kontekstā, ti, atbilstošais ievadnoteikums ir apgriezts. Piemēram, aģents ((B / lpar C)) kļūst (piemērojot (lpar) - labās ievades noteikumu) par diviem aģentiem (B) un (C) (tagad darbojas paralēli). Līdzīgi aģents ((B / amp C)) iegūst (piemērojot & pareizās ievada noteikumu) divas dažādas identiskas pasaules (secības), izņemot to, ka (B) atrodas vienā no šīm pasaulēm un (C) ir otrā.

No otras puses, ja mēs skatāmies sinhrono formulu kā aģentu, kura evolūciju nosaka atbilstošais labo ievades noteikums, tad ir iespējams, ka pierādāmā secība var pārtapt par nepierādāmu sekvenci (piemēram, piemērojot (oplus) labās ieviešanas noteikums). Arī šādu secinājumu noteikumu gadījumi ir atkarīgi no formulas konteksta detaļām. Piemēram, lai panāktu 1 labās ievades noteikumu, ir nepieciešams, lai apkārtējais konteksts nebūtu tukšs, un (otimes) pareiza ieviešanas noteikuma panākumi ir atkarīgi no tā, kā aģenta apkārtējais konteksts ir sadalīts divos kontekstos. Tādējādi šādu aģentu evolūcija ir atkarīga no “sinhronizācijas” ar citām konteksta daļām.

Tagad apsveriet vienpusēju secīgu lineāras loģikas aprēķinu noformējumu, kurā vienīgie ievadnoteikumi ir labās ievadīšanas noteikumi. Ņemot vērā iepriekš minēto savienojumu klasifikāciju, ir iespējams parādīt, ka pierādījumu meklēšanu var strukturēt šādās fāzēs, nezaudējot pilnīgumu. Asinhronā fāze notiek, ja secībā ir asinhrona formula. Šajā posmā labās ievades noteikumi tiek piemēroti jebkurā secībā, līdz vairs nav asinhronās formulas. Sinhronā fāzē tiek izvēlēta kāda sinhronā formula, un tā kļūst par šīs fāzes “fokusu”: tas ir, uz to un visām sinhronām apakšformulām, kuras tā varētu radīt, tiek piemēroti labās ievada noteikumi.

Šis attēls parāda fokusēšanas pierādīšanas sistēmas lineāro loģiku. Ievērojiet, ka abas fāzes ir attēlotas ar dažādām bultiņām: augšupvērstā bultiņa apzīmē asinhrono fāzi, bet bultas uz leju - sinhronās fāzes. Arī sekvences tiek sadalītas trīs zonās (kur zonas atdala ar semikolu vai bultiņu augšup vai lejup). Jo īpaši pa kreisi no augšupvērstās bultiņas un bultiņas uz leju ir divas zonas. Zona, kas uzrakstīta kā (Psi), apzīmē formulu kopu, kuru var izmantot neierobežotu reižu skaitu šī sekvences pierādīšanā. Zona, kas rakstīta kā (Delta), apzīmē daudzkārtīgu formulu, kas ir ierobežotas tāpat kā MALL. Zona pa labi no augšupvērstās bultiņas ir arī vairāku formulu virkne, savukārt zona pa labi no lejupvērstās bultiņas ir viena formula. Formulām pa labi no augšupvērstās bultiņas ir iespējams uzlikt patvaļīgu secību, jo asinhrono formulu ieviešanu var veikt jebkurā secībā. Atomiem ir piešķirta polaritāte, un zemāk redzamajā attēlā (A) apzīmē pozitīvos atomus, un (A) negatīvs apzīmē negatīvos atomus. Pierādījumus, kas izveidoti pēc šiem secinājumu noteikumiem, sauc par fokusētiem pierādījumiem. Andreoli 1992 rezultāts ir tāds, ka fokusēti pierādījumi ir pilnīgi lineārajai loģikai.

Asinhronā fāze (frac { Up { Psi} { Delta} {L}} { Up { Psi} { Delta} { bot, L}} (bot] qquad / frac { Augšup { Psi, F} { Delta} {L}} { Up { Psi} { Delta} { quest F, L}} [quest]) (frac {} { Up { Psi} { Delta} { top, L}} (top] qquad / frac { Up { Psi} { Delta} {F [y / x], L}} { Up { Psi} { Delta} { forall xF, L}} (forall]) (frac { Up { Psi} { Delta} {F_1, F_2, L}} { Up { Psi} { Delta} {F_1 / lpar F_2, L}} (lpar] qquad / frac { Up { Psi} { Delta} {F_1, L} quad / Up { Psi} { Delta} {F_2, L}} { Up { Psi} { Delta} {F_1 / amp F_2, L}} (amp]) (frac { Up { Psi} { Delta, F} {L}} { Up { Psi} { Delta} {F, L}} [R / Uparrow] / text {ar nosacījumu, ka $ F $ nav asinhrona}) Sinhronā fāze(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}} { Lejā { Psi} { Delta} {F_1 / oplus F_2}} (oplus_i] qquad / frac { Down { Psi} { Delta} {F [t / x]}}} { Down { Psi} { Delta} { eksistē xF}} (eksistē]) (frac { Up { Psi} { Delta} {F}} { Down { Psi} { Delta} {F}} [R / Downarrow] / text {ar nosacījumu, ka $ F $ ir asinhrons vai atoms}) Identitātes un lēmuma noteikumi (frac {} { Down { Psi} {A} {A ^ { perp}}} [I_1] qquad / frac {} { Down { Psi, A} { cdot} {A ^ { perp}}} [I_2] / text {kur} A teksts ir {atoms}) (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 {kur} F / text {ir pozitīva formula})

Koncentrētas pierādīšanas sistēmas ir izstrādātas arī klasiskajai un intuitīvai loģikai (Danos et al. 1997; Laurent et al. 2005; Liang & Miller 2009).

2.3 Pārliecinoši tīkli

Pierādījumos, kas iesniegti, izmantojot secīgus aprēķinus, ir daudz detaļu, kas dažreiz ir neinteresanti: piemēram, apsveriet, cik daudz neinteresanti dažādu paņēmienu ir, lai izveidotu (vdash / Gamma, (A_1 / lpar A_2), / ldots, (A_ {) pierādījumu. n-1} lpar A_n)) no (vdash / Gamma, A_1, A_2, / ldots, A_n) atvasinājuma. Šis nepatīkamais fakts izriet no secīgu aprēķinu pierādījumu secības: ja mēs vēlamies (n) noteikumu kopumu piemērot dažādām secības daļām, mēs tos nevaram piemērot vienā solī, pat ja viņi netraucē viens otram! Mums tie ir jāsecina, ti, jāizvēlas lineārā secība (S) un jāpiemēro kārtulas (n) soļos atbilstoši šai secībai.

Rodas dabisks jautājums: “Vai ir kāds pierādījumu attēlojums, kas apkopo šādas neinteresantas detaļas?”. Uz līdzīgu jautājumu tiek atbildēts pozitīvi intuitīvo secīgo aprēķinu gadījumā, izmantojot tā saukto dabisko dedukciju, kurai ar Karija-Hovarda sarakstes palīdzību ir cieša saikne ar skaitļošanas ierīci, kas pazīstama kā (lambda) - calculus.

Lineārajai loģikai šo kodolīgo pierādījumu attēlojumu nodrošina korektūras tīkli, grafiem līdzīgas struktūras, kurām ir īpaši labas loģikas MLL fragmenta īpašības. Pirmais solis ceļā uz šo attēlojumu ir pārveidot visu secīgo aprēķinu sistēmu, izmantojot negācijas impulsivitāti, vienpusējā sistēmā, kur sekvences ir formā (vdash / Gamma). Rezultātā tiek samazināts noteikumu skaits, jo mums nav ievešanas no kreisās puses, bet mēs saglabājam to pašu izteiksmīgo spēku, jo izredzes paliek nemainīgas.

Katram secīgajam kalkulāra pierādījumam MLL var induktīvi saistīt pierādīšanas tīklu ar šādiem pašiem secinājumiem:

  • Lai pierādījumu samazinātu līdz aksiomu likumam, mēs saistām aksiomu saiti.

    Aksiomu tīkls
    Aksiomu tīkls
  • Lai iegūtu pierādījumu, kas iegūts, piemērojot griezuma likumu diviem pierādījumiem, vispirms induktīvi izveidojam pierādīšanas tīklus, kas saistīti ar šiem diviem pierādījumiem, un pēc tam tos apvienojam, izmantojot grieztu saiti.

    Griezta tīkla konstrukcija
    Griezta tīkla konstrukcija
  • Lai iegūtu pierādījumu, kas iegūts, piemērojot tenzora likumu diviem pierādījumiem, vispirms induktīvi izveidojam pierādīšanas tīklus, kas saistīti ar šiem diviem pierādījumiem, un pēc tam tos apvienojam, izmantojot tenzora saiti.

    Tensoru tīkla konstrukcija
    Tensoru tīkla konstrukcija
  • Lai iegūtu pierādījumu, kas iegūts, piemērojot nominālvērtību, vispirms induktīvi izveidojiet ar šo pierādījumu saistīto pierādījumu tīklu un pēc tam pievienojam “nominālo saiti”.

    Par neto būvniecība
    Par neto būvniecība

To visu var pienācīgi noformēt, izmantojot hipergrāfijas (formulas ir mezgli un “saites” ir orientētas hiperedzes ar hipotēzēm un secinājumiem), un mēs kā oficiālu pierādījumu varam definēt hipergrāfu, kas induktīvi veidots no secīgas MLL aprēķina. Ievērojiet, ka ir diezgan daudz hipergrāfu, kas nav pierādījumu tīkli.

Ja skatāties uz pierādījumu tīklu, kas izveidots no (vdash / Gamma, (A_1 / lpar A_2), / ldots, (A_ {n-1} lpar A_n) atvasinājumiem, kas iegūti no (vdash / Gamma, A_1, A_2, / ldots, A_n), jūs redzēsit, ka ir pazudusi visu noteikumu piemērošanas secība. Savā ziņā pierādīšanas tīkli ir secīgu aprēķinu atvasinājumu ekvivalences klase attiecībā uz noteikumu atvasināšanas secību, kuru piemērošana mainās.

Pieņemsim, ka kāds tagad pie jums ierodas ar milzīgu hipergrāfu, kas izveidots ar aksiomu, sagrieztu, nominālu un tenzoru saitēm, izliekoties, ka tas patiesībā ir kādas ilgstošas atklātas matemātiskas problēmas pierādījums. Kā jūs varat pārliecināties, ka tas faktiski ir pierādījums, nevis tikai izlases struktūra?

Šīs pareizības pārbaudes veikšana ir izaicinājums, kas nozīmē secīgas konstrukcijas vēstures atjaunošanu jūsu struktūrai, kas atbilst atvasinājumam secīgā aprēķinā, un tā sākotnēji šķiet ļoti sarežģīta problēma: pirmais pareizības kritērijs MLL pierādījuma tīkliem, ko sauc par “garu ceļojumu kritērijs”, kas atrodas Girarda oriģināldarbā, ir eksponenciāls, kā arī vēlāk atklātais Danos un Regnier (1989) ACC (Acikliski savienotais) kritērijs. Neskatoties uz to, Danos un Regnier dēļ pastāv daudz efektīvāks kritērijs, kas pazīstams kā kontraktilizējamība un kuru nesen Guerrini, Martini un Masini pārveidoja par šādu elegantu grafika parsēšanas kritēriju: hipergrāfs ir pierādījums tīklam, ja un tikai tad, ja tas tiek samazināts līdz singletona mezglam “tīkls”, izmantojot šādus grafika samazināšanas noteikumus

Grafika parsēšana MLL neto atpazīšanai
Grafika parsēšana MLL neto atpazīšanai

Šīs pārbaudes veikšana naivi var aizņemt kvadrātveida laiku (katrai kārtulu piemērošanai var būt nepieciešams viss diagrammas uzmeklējums, lai atrastu redeksu, un mums jāveic tik daudz darbību, cik diagrammā ir hipersaites). Lineārā laika algoritmus sniedza Guerrini (2011) un Murawski and Ong (2006).

Citu pareizības kritēriju MLL pierādījuma tīkliem sniedz Retoré (2003), kurā MLL ir norādīts kvadrātiskais algoritms.

Pārliecinātos tīklos griezumu novēršanu var veikt īpaši tīrā veidā: to paralēlā rakstura dēļ griezumus var likvidēt uz vietas, izmantojot divus vienkāršošanas noteikumus:

  • Aksioma gājiens:

    Aksioma gājiens
    Aksioma gājiens
  • Reizinošs gājiens:

    Reizinošs gājiens
    Reizinošs gājiens

Faktiski tie ir aprēķināšanas noteikumi attiecībā uz pierādījumu tīkliem, un pareizības kritēriji ļauj viegli pārbaudīt, vai jebkurš šāds noteikums saglabā pareizību, un tā rezultātā pierādīšanas tīkla samazināšana joprojām rodas no secīga aprēķina pierādījuma par to pašu secīgo.

Tādējādi griezumu novēršanu MLL necaurlaidīgos tīklos var veikt lineārā laikā un tas dod vienkāršu, elegantu griezuma novēršanas rezultātu visai MLL.

Pierādīšanas tīklu pieeju var paplašināt līdz lielākām lineāras loģikas apakškopām, bet tad nav tik skaidrs, kā iegūt tādus pašus elegantus rezultātus kā MLL: sākotnējā sistēma, kas ierosināta Girard 1987, darbojas MELL, piemēram, saistot ar četrām eksponenciāli regulē šādas hipergrāfa konstrukcijas:

  • Kontrakcija

    Kontrakciju konstrukcija
    Kontrakciju konstrukcija
  • Pavājināšanās

    Vājinoša konstrukcija
    Vājinoša konstrukcija
  • Nolaidība

    Nolaidības būve
    Nolaidības būve
  • Paaugstinājums, kas ievieš jēdzienu “rūtiņa”, secības simbolu ap koriģējoša tīkla gabala, kas grafiku attēlos materializēts ar taisnstūri, kas apvilkts ap secinājumu (A) un (quest / Gamma pierādījumu tīklu)).

    Veicināšanas būvniecība
    Veicināšanas būvniecība

Kaut arī šīs konstrukcijas un ar tām saistītie grafika samazinājumi ir pārsteidzoši līdzīgi ar (lambda) - calculus ar izteiktām aizstāšanām, kā to pirmo reizi atzīmēja Di Cosmo & Kesner (1997), tie ir pārāk līdzīgi attiecīgajiem secīgajiem aprēķinu noteikumiem: paralēles efekts tik elegants, lai nodrošinātu MLL, šeit netiek pareizi veikts, un grafika samazināšanas noteikumi attiecas uz lodziņiem un nav lokāli.

Lai atgūtu apmierinošu sistēmu, ir iesniegti daudzi priekšlikumi, sākot ar Danos & Regnier (1995), bet mēs šeit vēlamies pieminēt ļoti eleganto Guerrini, Martini un Masini pieeju (Guerrini et al. 2003), kas glīti parāda savienojums starp divu līmeņu pierādīšanas sistēmām modālajai loģikai, pareiziem MELL koriģēšanas tīkliem un optimālu samazinājumu (lambda) - aprēķinos.

Nesenais Heijltjes un Hjūstonas (2016) dokuments parādīja, ka nevar būt apmierinoša priekšstata par MLL pierādīšanas tīkliem, ja ir atļautas arī vienības.

Ir iespējams nodrošināt piedevu savienojumu kanonisku apstrādi, pat veicot pirmās kārtas kvantitatīvu noteikšanu (Heijltjes et al. 2018). Pārliecinošiem tīkliem receptēm, kas satur gan reizinošos, gan papildinošos savienojumus, ir dažādas tehniskās izpausmes, neviena no tām nav kanoniska un apmierinoša. Viņu attieksme pret neto līdzīgām pierādīšanas sistēmām pašlaik ir aktīvas izpētes tēma. Īpaši skat. (Hughes and van Glabbeek 2005) un (Hughes and Heijltjes 2016).

3. Semantika

Tuvošanās lineārās loģikas semantikai parasti tiek veikta pa diviem dažādiem ceļiem. Pirmkārt, ir pieejamas dažādas semantiskās struktūras, kuras var izmantot, lai formulas kartētu līdz apzīmējumiem šādās struktūrās. Šo pieeju var izmantot, lai noteiktu pareizību un pilnīgumu dažādiem lineārās loģikas fragmentiem. Jaunāka semantiskā pieeja lineārajai loģikai nozīmē semantikas piešķiršanu pierādījumiem tieši. Īsumā aprakstīsim šīs divas pieejas un sniegsim dažas saites uz literatūru.

3.1. Pārbaudāmības semantika

Viena pieeja pareizas un pilnīgas semantikas mēģinājumiem attiecībā uz lineārās loģikas fragmentiem asociējas ar formulu visu kontekstu kopumu, ko var izmantot šīs formulas pierādīšanai. Protams, šādai kolekcijai var būt jābūt abstraktākai un jāpiešķir dažādas slēgšanas īpašības. Žirarda (1987) fāzes semantika nodrošina vienu no šādām semantikām: datorzinātnē ir izmantoti daži šādas semantikas elementi, lai nodrošinātu pretparaugus, un kā rīks, kas var palīdzēt noteikt, ka dotā vienlaicīgā sistēma nevar izvērsties citā ar noteiktām īpašībām (Fages et al. 2001). Līdzīgi Kripke stila semantika tika sniegta Allwein & Dunn 1993 un Hodas & Miller 1994. Quantales, noteikta veida daļēji sakārtotas algebriskās struktūras, tika izmantotas arī, lai nodrošinātu agrīnos semantiskos modeļus lineārās loģikas daļās (Yetter 1990).

3.2. Pierādījumu semantika

Teorētiskajā datorzinātnē tik populārā un auglīgajā formulu tipu analīzē loģiskā sistēma tiek sakārtota ar drukātu skaitļošanas ierīci (piemēram, drukāta (lambda) - aprēķins), saistot ar katru pierādījumu par kas formulē programmu, kurai ir šī formula kā tips. Piemēram, tautoloģijas pierādījums (A / Rightarrow A) atbilst programmai fun ((x: A).x: A / rightarrow A), identitātes funkcija objektiem, kuru tips ir (A).. Tāpēc konstruktīvajās loģiskajās sistēmās (piemēram, intuitīvā loģikā un aritmētikā) un lineārajā loģikā pierādījumiem tiek piešķirta tik liela nozīme, ka pierādījumu paraugu veidošanai un studēšanai tiek pievērsta daudz lielāka uzmanība nekā modeļu veidošanai un studēšanai pierādāmība: mums nav prieks zināt, ka formula ir pierādāma,mēs patiešām vēlamies uzzināt tā pierādījumu aprēķina saturu.

Ir ierosināti daudzi lineāro loģisko pierādījumu modeļi; mēs uzskatām, ka līdz šim visvienkāršākā un intuitīvākā konstrukcija ir balstīta uz tā saukto “relāciju semantiku” vai “Kripkes stila semantiku”, kur formulas tiek interpretētas kā multiseti, vienpusējie secības tiek interpretētas kā multisektu kopas, un pierādījumi tiek interpretēti kā attiecības pār secību interpretāciju. Ja vēlas sniegt tīri teorētisku semantiku, neizmantojot multisektus, to var izdarīt, izmantojot koherences telpas, komplektus, kas aprīkoti ar īpašu koherences sakarību, kā sākotnēji parādīja Girard 1987. Ir interesantas kategorijas teorētiskās. lineārās loģikas modeļi, piemēram, * -autonomās kategorijas (Barr 1991) un hiperkoherences (Ehrhard 1993).

Vēl viena pieeja pierādījumu semantikai ir Girarda mijiedarbības ģeometrija, kas ļauj mums iegūt pilnībā algebrisku pierādījumu raksturojumu. Katram pierādījuma tīklam var piesaistīt daļēju permutācijas matricu (sigma), kas atbilst izgrieztām saitēm, un pareizu matricu (M), kas atbilst izteiksmēm, kas veidotas no noteiktas dinamiskās algebras, un kas apraksta iespējamos ceļus pierādījuma tīkls. Izmantojot izpildes formulu, ir iespējams pilnībā aprakstīt pierādījumu tīklu

(mathrm {EX} (sigma, M) = (1- / sigma ^ 2) pa kreisi (sum_i M (sigma M) labi) (1- / sigma ^ 2))

kas MLL gadījumā ir normalizācijas procesa invariants. Kāds jauks savienojums ar rezultātiem, kas iegūti no alt="sep man icon" /> Kā citēt šo ierakstu.

sep cilvēks ikona
sep cilvēks ikona

Priekšskatiet šī ieraksta PDF versiju vietnē SEP Friends.

inpho ikona
inpho ikona

Uzmeklējiet šo ierakstu tēmu interneta filozofijas ontoloģijas projektā (InPhO).

phil papīru ikona
phil papīru ikona

Uzlabota šī ieraksta bibliogrāfija vietnē PhilPapers ar saitēm uz tā datu bāzi.

Citi interneta resursi

  • Lineārās loģikas bibliogrāfija (līdz 1998. gadam).
  • Vinsents Danoss un Roberto Di Kosmo. Lineārās loģikas gruntējums. Kursa piezīmes. (1992).

Ieteicams: