Lineární Logika

Obsah:

Lineární Logika
Lineární Logika

Video: Lineární Logika

Video: Lineární Logika
Video: Graf lineární funkce 1 - Jak na to? 2024, Březen
Anonim

Vstupní navigace

  • Obsah příspěvku
  • Bibliografie
  • Akademické nástroje
  • Náhled PDF přátel
  • Informace o autorovi a citaci
  • Zpět na začátek

Lineární logika

První publikováno 6. září 2006; věcná revize pá 24. května 2019

Lineární logika je zdokonalením klasické a intuicionální logiky. Namísto zdůrazňování pravdy, jako v klasické logice nebo důkazu, jako v intuicionistické logice, lineární logika zdůrazňuje roli vzorců jako zdrojů. K dosažení tohoto zaměření neumožňuje lineární logika obvyklá strukturální pravidla kontrakce a oslabení pro všechny vzorce, ale pouze pro ty vzorce, které jsou označeny určitými modály. Lineární logika obsahuje plně nedobrovolnou negaci při zachování silné konstruktivní interpretace. Lineární logika také poskytuje nový pohled na povahu důkazů v klasické i intuicionální logice. Vzhledem ke svému zaměření na zdroje našla lineární logika mnoho aplikací v informatice.

  • 1. Úvod

    • 1.1 Trocha historie
    • 1.2 Lineární logika a informatika
  • 2. Důkazní systémy

    • 2.1 Sekvenční počet
    • 2.2 Cílené vyhledávání důkazů
    • 2.3 Důkazové sítě
  • 3. Sémantika

    • 3.1 Sémantika prokazatelnosti
    • 3.2 Sémantika důkazů
  • 4. Složitost
  • 5. Dopad informatiky

    • 5.1 Důkazní normalizace
    • 5.2 Důkazní vyhledávání
  • 6. Variace

    • 6.1 Různé způsoby modality
    • 6.2 nekomutativní lineární logika
    • 6.3 Léčení neohraničeného chování
  • Bibliografie
  • Akademické nástroje
  • Další internetové zdroje
  • Související záznamy

1. Úvod

1.1 Trocha historie

Lineární logiku představil Jean-Yves Girard ve své klíčové práci (Girard 1987). Zatímco původ objevu této nové logiky pochází ze sémantické analýzy modelů systému F (nebo polymorfního (lambda) - počtu), je možné vidět celý systém lineární logiky jako odvážný pokus o smíření krása a symetrie systémů pro klasickou logiku s hledáním konstruktivních důkazů, které vedly k intuicionální logice.

Opravdu lze představit fragment lineární logiky, známý jako multiplikativní aditivní lineární logika (MALL), jako výsledek dvou jednoduchých pozorování.

  • V sekvenční prezentaci klasické logiky mohou být pravidla pro spojky „a“a „nebo“, jakož i pravidlo Cut a pravidlo pro implikaci prezentovány rovnocenně v aditivní podobě (kontext prostor je stejný)) nebo multiplikativní forma (kontext prostor se liší). Tyto dvě prezentace jsou v klasické logice rovnocenné z důvodu dostupnosti několika tzv. „Strukturálních“pravidel, konkrétně kontrakce a oslabení.
  • Non-konstruktivní důkazy, že jeden může vykonávat v klasické logice vlastně používat, v sekvenčním počítání prezentace, jeden nebo jiný z těchto strukturálních pravidel.

Pokud tedy chceme eliminovat nekonstruktivní důkazy bez zničení symetrie sekvenčního počtu, jak se to děje v intuicionální logice, můžeme se místo toho pokusit eliminovat pravidla kontrakce a oslabení. Přitom nám zbývají dvě různé verze každého pojivového: aditivní verze a multiplikativní verze spojení a disjunkce. Tyto různé verze stejného spojení již nejsou rovnocenné. Tyto nové spojky jsou & („s“, aditivní a), (oplus) („plus“, aditivní nebo, (otimes) („tensor“, multiplikativní a) a (lpar) („Par“, multiplikativní nebo).

Tato duplikace spojek ve skutečnosti vede k mnohem jasnějšímu pochopení konfliktu mezi klasickou a intuicionální logikou. Například zákon vyloučeného středu ((A) nebo ne - (A)) je považován za platný v klasickém světě a absurdní v intuicionálním. Ale v lineární logice má tento zákon dvě čtení: aditivní verze ((A / oplus / neg A)) není prokazatelná a odpovídá intuicionálnímu čtení disjunkce; multiplikativní verze ((A / lpar / neg A)) je triviálně prokazatelná a jednoduše odpovídá tautologii ((A) implikuje (A)), což je naprosto přijatelné i v intuicionistické logice.

Také vlastnost disjunkce, nezbytná v konstruktivismu, se pro aditivní disjunkce snadno stanoví.

V této bohatší logice pak najdeme způsob, jak reprezentovat jak potřeby intuicionismu, tak eleganci klasické logiky: negace je bezpředmětná, sekvence jsou symetrické a spoje jsou definovatelné. Kontrastují tyto vlastnosti s vlastnostmi intuicionální logiky, kde negace není nedílná, posloupnosti nejsou symetrické a spojky nejsou definovatelné.

Všimněte si však, že jakmile někdo odstraní pravidlo kontrakce a oslabení, vzorce se už nebudou chovat jako neměnné hodnoty pravdy: skutečně, když máme důkaz o (A / Rightarrow B) a důkaz o (A) v lineární logice, jejich složením je vlastně konzumujeme, abychom získali důkaz o (B), takže (A / Rightarrow B) a (A) již nejsou po složení k dispozici. Lineární logické vzorce se nyní chovají spíše jako zdroje, které lze použít pouze jednou.

Abychom získali plnou expresivní sílu intuicionální a klasické logiky, je nutné do fragmentu MALL přidat dvě duální modality, které se v lineární logické literatuře obvykle nazývají exponenciální. Zejména "samozřejmě" exponenciální (bang) umožňuje, aby se kontrakce a oslabení aplikovaly na vzorec (bang B) v levém sekvenčním kontextu, zatímco "proč-ne" exponenciální (quest) umožňuje, aby se kontrakce a oslabení aplikovaly na vzorec (quest B) v pravém sekvenčním kontextu. To vede k plné výrokové lineární logice a velmi pěknému spojení s informatikou.

Všimněte si, že kromě MALL existují dva další široce používané fragmenty lineární logiky: Multiplikativní lineární logika (MLL), která je MALL bez aditivních spojiv; a multiplikativní exponenciální lineární logika (MELL), což je lineární logika bez aditivních spojiv.

Před zavedením lineární logiky v roce 1987 různí vědci pracovali na různých druzích substrukturální logiky, ve které nejsou přijímána všechna Gentzenova strukturální pravidla (kontrakce, oslabení a výměna). Lambek studoval sekvenční systémy důkazního počtu, ve kterých nebylo povoleno žádné z těchto strukturálních pravidel (Lambek 1958). Dalšími příklady takové logiky jsou relevantní logiky (ve kterých není oslabování akceptováno) (Avron 1988, Read 1988). a afinní logika (ve které není kontrakce akceptována) (Grishin 1981).

1.2 Lineární logika a informatika

Důkazová teorie je zaměřena na formální důkazní systémy a takové formální systémy byly vyvinuty pro intuicionální predikátový počet, klasický predikátový počet, aritmetiku, vyšší řády a další. Intuitionistická a konstruktivní logika začala, když lidé viděli možnost čtení '(A / Rightarrow B)' jako 'když mi dáte (A), dám vám (B)', což je významný odklon od klasického čtení '(A) je nepravdivý nebo (B) je pravdivý'.

Počítačová věda se naopak zaměřuje na výpočetní mechanismy: aplikace funkcí, zpracování výjimek, vyvolávání metod v objektově orientovaných jazycích, přiřazení proměnných a podobné sady pravidel pro vytváření procesů. Kromě toho, že mechanismy těchto procesů musí být explicitně vyjádřeny: funkce typu (A / rightarrow B) poskytuje formální popis toho, jak transformovat (A) na (B).

V daném okamžiku se tyto dva smysly setkaly. HB Curry a W. Howard si uvědomili, že množina intuitivních dedukcí pouze pro implikaci je klíčovým funkčním jazykem, který se nazývá jednoduše zadaný (lambda) - počet: programovací jazyk je logika, logika programovací jazyk. Toto nezapomenutelné setkání bylo nazváno „Curry-Howardův izomorfismus“(Howard 1980).

Lineární logika poskytuje další zvrat v interpretaci implikace '(A / Rightarrow B)': nyní ji lze číst jako 'dejte mi tolik (A)', kolik potřebuji, a dám vám jeden (B) '. Pojem kopie, který je tak zásadní pro myšlenku výpočtu, je nyní zapojen do logiky.

Toto nové hledisko otevírá nové možnosti, včetně:

  • nové vzorce vyjadřující rafinované provozní vlastnosti, jako například „dej mi jednou (A) a dám ti (B)“. Aplikace se pohybují od rafinovaného logického programování, ve kterém je využívána schopnost lineární logiky reprezentovat státy (Hodas & Miller, 1994), až po analýzu jejích klasických logických a výpočetních interpretací (Abramsky 1993), až po specifikaci mechanismů výjimek v programovací jazyky (Miller, 1996), k analýze linearity (Wadler, 1991).
  • nová pravidla vyjadřující omezení používání kopií vedoucí k fragmentu lineární logiky pro výpočty v polytime, aby bylo možné zmínit pouze nejpůsobivější aplikaci (Baillot & Terui, 2004, Baillot 2015).
  • nové způsoby reprezentace důkazů (Abramsky & Jagadeesan, 1994, Girard 1987).

2. Důkazní systémy

Základní výrokové spojky lineární logiky jsou rozděleny na aditivní a multiplikativní spojky. Klasická konjunkce a její identita (wedge) a (top), rozdělená na aditivum (amp) (with) a (top) (top) a multiplikativní (otimes) (tensor) a 1 (one). Podobně klasická disjunkce a její identita, (vee) a (bot), se rozdělí na aditivum (oplus) (oplus) a 0 (nula) a multiplikativní (lpar) (par) a (bot) (dole). Negace se v prezentacích obecně považují za lineární logiku jedním ze dvou způsobů. Negaci lze považovat za primitivní výrokovou konektivitu bez omezení na její výskyt ve vzorcích. Protože De Morganovy duality existují mezi negací a všemi výrokovými spojkami, exponenciály a kvantifikátory,je také možné zacházet s negací jako se zvláštním symbolem, který se vyskytuje pouze u atomových vzorců. Implikace jsou také běžně zavedeny do lineární logiky pomocí definic: lineární implikace (B / limp C) může být definována jako (B ^ { bot} lpar C), zatímco intuicionální implikace (B / Rightarrow C) lze definovat jako (bang B / limp C). Operátory (bang) a (quest) se různě nazývají modály nebo exponenciály. Termín „exponenciální“je zvláště vhodný, protože po obvyklém vztahu mezi exponentací, sčítáním a násobením lineární logika podporuje ekvivalence (bang (B / amp C) equiv (bang B / otimes / bang C)) a (quest (B / oplus C) equiv (quest B / lpar / quest C)), stejně jako 0-ary verze těchto ekvivalencí, konkrétně ((bang / top / equiv) 1)) a ((quest 0 / equiv / bot)). Tady,používáme binární ekvivalenci (B / equiv C), což znamená, že vzorec ((B / limp C) amp (C / limp B)) je odvozitelný v lineární logice.

2.1 Sekvenční počet

Na obrázku níže je uveden oboustranný sekvenční počet pro lineární logiku. Všimněte si, že negace je považována za jinou logickou konektivitu: to znamená, že její výskyt ve vzorcích není omezen a v levém a pravém dolním rohu jsou pravidla pro negaci. Levá a pravá strana posloupností je multiset vzorců: na pořadí řádů v těchto kontextech tedy nezáleží, ale na jejich multiplicitě záleží.

Pravidla 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}) Negativní pravidla) 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í pravidla) frac { Delta / vdash / Gamma} { Delta, / one / vdash / Gamma} / one L / qquad / frac {} { vdash / one} / one R)) frac { } { bot / vdash} / bot L / qquad / frac { Delta / vdash / Gamma} { Delta / vdash / bot, / Gamma} / bot R)) frac { Delta, B_1, B_2 / vdash / Gamma} { Delta, B_1 / ot B_2 / vdash / Gamma} / ot L / qquad / frac { Delta_1 / vdash B, / Gamma_1 / qquad / Delta_2 / vdash C, / Gamma_2} { Delta_1, / Delta_2 / vdash B / ot C, / Gamma_ {1}, / Gamma_ {2}} / ot R)) frac { Delta_1, B / vdash / Gamma_1 / qquad / Delta_2, C / vdash / Gamma_2} { Delta_1, / Delta_2, B / lpar C / vdash / Gamma_1, / Gamma_2} / lpar L / qquad / frac { Delta / vdash B, C, / Gamma} { Delta / vdash B / lpar C, / Gamma} / lpar R) Additive 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)) Kvantifikátorová pravidla) 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ální pravidla) 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} { třesk / Delta, / quest B / vdash / quest / Gamma} / quest L)

Všimněte si, že pravidla oslabení a kontrakce jsou dostupná pouze pro vzorce označené exponenciálním (bang) vlevo nebo (quest) napravo od posloupníka. Pravidla (quest) R a (bang) L jsou často označována jako pravidla "dereliction". Pravidla (quest) L a (bang) R jsou často označována jako „propagační“pravidla a jsou stejná jako pravidla pro možnost a nezbytnost, která jsou uvedena v modální logice Kripke S4. Předpokládají se obvyklé podmínky pro pravidla zavedení (forall) - right a (existují) - left: Zejména proměnná (y) nesmí být volná ve vzorcích dolní posloupnosti těch inferenční pravidla. Kvantifikace je zde považována za řád prvního řádu: verze lineární logiky vyšších řádů lze psát podle standardních řádků.

Pravidlo řezu lze odstranit a úplnost je stále zachována. Pravidlo init může být také dvojitě vyloučeno, s výjimkou výskytů init zahrnujících atomové vzorce.

2.2 Zaměřené důkazy

Důležitý normální tvar věty pro strukturu důkazů bez ořezu poskytl Andreoli (1992). Klasifikoval neatomický vzorec jako asynchronní, pokud jeho logické spojivo nejvyšší úrovně je (top), &, (bot, / lpar), (quest) nebo (forall) nebo synchronní, pokud jeho logické konektivum nejvyšší úrovně je (0, / oplus, 1, / otimes), (bang) nebo (existuje).

Při pohledu na hledání důkazů jako na výpočetní model můžeme vidět vzorce v sekvenci jako „agenty“, kteří mohou ve svém prostředí jednat nezávisle nebo ve shodě s ostatními. Akce těchto agentů jsou zde určeny čtením úvodního pravidla pro ně zdola nahoru. Dojde-li k asynchronnímu vzorci napravo od posloupníka, může se vyvíjet bez ovlivnění prokazatelnosti a bez interakce s jeho kontextem, tj. Odpovídající pravidlo zavedení je nevratné. Například agent ((B / lpar C)) se stává (použitím pravidla (lpar) - pravé úvodní pravidlo) dva agenty (B) a (C) (nyní pracující paralelně)). Podobně agent ((B / amp C)) poskytuje (použitím pravidla pravého úvodu) dva různé identické světy (posloupnosti) s výjimkou toho, že (B) je v jednom z těchto světů a (C) je v druhém.

Na druhou stranu, pokud vidíme synchronní vzorec jako agenta, jehož vývoj je určen odpovídajícím pravidlem pro zavedení pravého úvodu, je možné, že se prokazatelná sekvence vyvine na neprokázatelnou sekvenci (například použitím (oplus) pravidlo zavedení práva). Případy takových odvozených pravidel také závisí na detailech kontextu vzorce. Například úspěch pravidla 1-pravého zavedení vyžaduje, aby okolní kontext byl prázdný a úspěch pravého úvodního pravidla (otimes) závisí na tom, jak je okolní kontext agenta rozdělen do dvou kontextů. Evoluce takových činitelů tedy závisí na „synchronizaci“s ostatními částmi kontextu.

Nyní zvažte jednostrannou sekvenční kalkulaci lineární logiky, kde jediná úvodní pravidla jsou pravidla správného zavedení. Vzhledem k výše uvedené klasifikaci spojiv je možné prokázat, že hledání důkazů může být strukturováno do následujících fází bez ztráty úplnosti. Asynchronní fáze nastane, pokud je v sekvenci přítomen asynchronní vzorec. V této fázi se pravidla zavádění pravého pravidla používají v libovolném pořadí, dokud neexistují žádné další asynchronní vzorce. V synchronní fázi je vybrán nějaký synchronní vzorec a stává se „ohniskem“této fáze: to znamená, že se na něj a na všechny synchronní podformuláře, které může vygenerovat, použijí pravidla pro správné zavedení.

Následující obrázek ilustruje lineární logiku zaostřovacího systému. Všimněte si, že dvě fáze jsou reprezentovány různými šipkami: šipka nahoru označuje asynchronní fázi a šipka dolů označuje synchronní fázi. Sekvence jsou také rozděleny do tří zón (kde jsou zóny odděleny středníkem nebo šipkou nahoru nebo dolů). Zejména vlevo od šipky nahoru a dolů jsou dvě zóny. Zóna zapsaná jako (Psi) označuje sadu vzorců, které lze v důkazu této sekvence použít libovolně kolikrát. Zóna zapsaná jako (Delta) označuje multiset vzorců, které jsou omezeny jako v MALL. Zóna napravo od šipky nahoru je také multiset vzorců, zatímco zóna napravo od šipky dolů je jednoduchý vzorec. Je možné uložit vzorcům napravo od šipky nahoru libovolný řád, protože zavedení asynchronních vzorců lze provést v libovolném pořadí. Atomy jsou dány polaritou a na obrázku níže, (A) znamená kladné atomy a negace (A) znamená záporné atomy. Důkazy vytvořené na základě těchto inferenčních pravidel se nazývají zaměřené důkazy. Výsledkem v Andreoli 1992 je, že zaměřené důkazy jsou kompletní pro lineární logiku.

Asynchronní fáze) frac { Up { Psi} { Delta} {L}} { Up { Psi} { Delta} { bot, L}}) bot] qquad / frac { Nahoru { 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 {za předpokladu, že $ F $ není asynchronní}) Synchronní 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}} { 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 předpokladu, že $ F $ je asynchronní nebo atom}) Pravidla identity a rozhodování) frac {} { Down { Psi} {A} {A ^ { perp}}} [I_1] qquad / frac {} { Down { Psi, A} { cdot} {A ^ { perp}}} [I_2] / text {kde} A / text {je atom})) 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 {kde} F / text {je pozitivní vzorec})

Zaměřené systémy důkazů byly také navrženy pro klasickou a intuicionální logiku (Danos a kol. 1997; Laurent a kol. 2005; Liang & Miller 2009).

2.3 Důkazové sítě

Důkazy předložené pomocí sekvenčního počtu obsahují mnoho podrobností, které někdy nejsou zajímavé: zvažte například, kolik nezajímavých odlišných způsobů existuje jako důkaz (vdash / Gamma, (A_1 / lpar A_2), / ldots, (A_ { n-1} lpar A_n)) z odvození (vdash / Gamma, A_1, A_2, / ldots, A_n). Tato nepříjemná skutečnost vyplývá ze sekvenční povahy důkazů v sekvenčním počtu: pokud chceme použít sadu (S) pravidel (n) na různé části sekvence, nemůžeme je aplikovat v jednom kroku, i když nezasahují do sebe! Musíme je sekvenovat, tj. Zvolit lineární pořadí na (S) a použít pravidla v (n) krocích, podle tohoto pořadí.

Vyvstává přirozená otázka: „Existuje reprezentace důkazů, které abstrahují od takových nezajímavých detailů?“. Podobná otázka je zodpovězena pozitivně v případě intuicionálního sekvenčního počtu pomocí tzv. Přirozené dedukce, která má prostřednictvím Curryho-Howardovy korespondence silné spojení s výpočetním zařízením známým jako (lambda) - počet.

Pro lineární logiku je toto stručné znázornění důkazů dáno zkušebními sítěmi, grafickými strukturami, které mají zvláště dobré vlastnosti pro MLL fragment logiky. Prvním krokem k této reprezentaci je převést celý sekvenční početní systém pomocí nepřímosti negace na jednostranný systém, kde jsou posloupnosti ve tvaru (vdash / Gamma). V důsledku toho se počet pravidel snižuje, protože nemáme žádná pravidla pro úvodní představení, ale zachováváme stejnou expresivní sílu, protože průkaznost zůstává stejná.

Ke každému následnému důkazu počtu v MLL lze induktivně spojit důkazní síť se stejnými závěry, jako je následující:

  • K důkazu zredukovanému na pravidlo axiomu přidružujeme spojení axiom.

    Axiom net
    Axiom net
  • Pro důkaz získaný použitím pravidla oříznutí na dva důkazy nejprve vytvoříme indukční sítě spojené s těmito dvěma důkazy indukčně a poté je zkombinujeme pomocí spojení oříznutí.

    Řezaná síťová konstrukce
    Řezaná síťová konstrukce
  • Pro důkaz získaný použitím tenzorového pravidla na dva důkazy, nejprve indukčně vytvoříme zkušební sítě spojené s těmito dvěma důkazy, a potom je spojíme pomocí tenzorového spojení.

    Konstrukce tenzorové sítě
    Konstrukce tenzorové sítě
  • Pro důkaz získaný použitím pravidla par na důkaz nejprve vytvořte indukční síť spojenou s tímto důkazem a poté přidejte „par link“.

    Par síťová konstrukce
    Par síťová konstrukce

To vše lze řádně formalizovat pomocí hypergrafů (vzorce jsou uzly a „odkazy“jsou orientované hyperedgey s hypotézami a závěry) a můžeme formálně definovat jako důkazní síť hypergraf indukčně vytvořený ze sekvenční derivace derivátu MLL. Všimněte si, že existuje spousta hypergrafů, které nejsou důkazními sítěmi.

Nyní se podíváte na zkušební síť vytvořenou z derivací (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šechny stopy po pořadí aplikace pravidel zmizely. V jistém smyslu jsou sítě důkazů ekvivalenční třídou sekvenčních derivací počtu, pokud jde o pořadí odvození pravidel, jejichž aplikace dojíždí.

Předpokládejme, že k vám nyní někdo přichází s obrovským hypergrafem vytvořeným s axiomovými, řezanými, par a tenzorovými vazbami, který předstírá, že se jedná o reprezentaci důkazu nějakého dlouhodobého otevřeného matematického problému. Jak můžete ověřit, že se jedná o reprezentaci důkazu, a nikoli pouze náhodnou strukturu?

Provedení této kontroly správnosti je výzvou, která se rovná obnově sekvenční historie konstrukce vaší struktury, která odpovídá derivaci v sekvenčním počtu, a na první pohled se zdá být velmi složitým problémem: první kritérium správnosti pro sítě důkazů MLL, nazývané „dlouhý výlet“kritérium “, a přítomný v Girardově původním článku, je exponenciální, stejně jako kritérium ACC (Acyclic linked) podle Danos a Regnier (1989), které bylo nalezeno později. Přesto existuje mnohem účinnější kritérium, známé jako kontrahabilita, způsobené Danosem a Regnierem, které bylo nedávno nově Guerrini, Martinim a Masinim přeformulováno na následující elegantní kritérium pro analýzu grafů: hypergraf je důkazní síť pouze tehdy, pokud redukuje se na singletonový uzel „net“pomocí následujících pravidel redukce grafu

Analýza grafů pro čisté rozpoznávání důkazů MLL
Analýza grafů pro čisté rozpoznávání důkazů MLL

Provedení této kontroly naivně může trvat kvadratický čas (každá aplikace pravidla může vyžadovat úplné vyhledávání grafu, aby se našel redex, a my musíme provést tolik kroků, kolik je v grafu hypertextových odkazů). Algoritmy lineárního času poskytly Guerrini (2011) a Murawski a Ong (2006).

Další styl kritéria správnosti pro sítě důkazů MLL je uveden v Retoré (2003), ve kterém je pro MLL uveden kvadratický algoritmus.

Na zkušebních sítích lze eliminovat řezy zvláště čistým způsobem: díky paralelní povaze lze řezy odstranit místně pomocí dvou pravidel pro zjednodušení:

  • Pohyb axiomu:

    Axiom pohyb
    Axiom pohyb
  • Multiplikativní tah:

    Multiplikativní tah
    Multiplikativní tah

Toto jsou ve skutečnosti pravidla pro výpočet na zkušebních sítích a kritéria správnosti umožňují snadno ověřit, že jakékoli takové pravidlo zachovává správnost, a v důsledku toho snížení důkazní sítě stále pochází ze sekvenčního důkazu stejného sledu.

Odstranění řezu v sítích odolných vůči MLL lze tedy provádět v lineárním čase a poskytuje jednoduchý a elegantní výsledek eliminace řezu pro všechny MLL.

Přístup pomocí kontrolních sítí lze rozšířit na větší podmnožiny lineární logiky, ale pak je méně jasné, jak získat stejné elegantní výsledky jako pro MLL: původní systém navržený v Girardu 1987 funguje pro MELL, například přidružením ke čtyřem exponenciální pravidla následující hypergrafické konstrukce:

  • Kontrakce

    Konstrukce kontrakce
    Konstrukce kontrakce
  • Oslabení

    Oslabující konstrukce
    Oslabující konstrukce
  • Opuštění

    Konstrukce opuštění
    Konstrukce opuštění
  • Propagace, která zavádí pojem „box“, sekvenční značka kolem kusu zkušební sítě zhmotněná na obrázcích grafů pomocí obdélníku nakresleného kolem zkušební sítě závěrů (A) a (quest / Gamma).

    Propagační konstrukce
    Propagační konstrukce

I když tyto konstrukce a související redukce grafů nesou výraznou podobnost s (lambda) - počet s explicitními substitucemi, jak poprvé poznamenal Di Cosmo & Kesner (1997), jsou příliš podobné odpovídajícím pravidlům pro postupný počet: účinek paralelizace tak elegantní pro MLL zde nefunguje správně a pravidla pro snížení grafu zahrnují pole a nejsou místní.

Pro obnovení uspokojivého systému bylo předloženo mnoho návrhů, počínaje tím, který předložil Danos & Regnier (1995), ale chceme zde zmínit velmi elegantní přístup Guerriniho, Martiniho a Masiniho (Guerrini et al. 2003), který přehledně ukazuje spojení mezi dvěma úrovněmi důkazních systémů pro modální logiku, správnými korekčními sítěmi pro MELL a optimální redukcí počtu (lambda) -.

Nedávný příspěvek Heijltjes a Houston (2016) ukázal, že pokud jsou jednotky povoleny, nemůže existovat uspokojivá představa sítí důkazů pro MLL.

Je možné provést kanonické zpracování aditivních spojiv, dokonce i při kvantifikaci prvního řádu (Heijltjes et al. 2018). Důkazové sítě pro receptury obsahující multiplikativní i aditivní spojovací prostředky mají různé technické prezentace, z nichž žádná se nezdá být kanonická a uspokojivá. Jejich léčba v důkazních sítích podobných důkazům je v současné době předmětem aktivního výzkumu. Viz zejména (Hughes a van Glabbeek 2005) a (Hughes a Heijltjes 2016).

3. Sémantika

Blíží se sémantika lineární logiky obvykle dvěma různými cestami. Nejprve jsou k dispozici různé sémantické struktury, které lze použít k mapování vzorců na označení v takových strukturách. Tento přístup lze použít ke stanovení spolehlivosti a úplnosti různých fragmentů lineární logiky. Novější sémantický přístup k lineární logice zahrnuje přímé sémantiku důkazů. Popíšeme stručně tyto dva přístupy a poskytneme několik odkazů na literaturu.

3.1 Sémantika prokazatelnosti

Jeden přístup k pokusu o zvukovou a úplnou sémantiku pro fragmenty lineární logické asociace do vzorce, soubor všech kontextů, které lze použít k prokázání tohoto vzorce. Taková kolekce může samozřejmě být abstraktnější a musí mít různé uzavírací vlastnosti. Fázová sémantika Girarda (1987) poskytuje jednu takovou sémantiku: některá použití této sémantiky byla v počítačové vědě provedena, aby poskytla protiklady a jako nástroj, který může pomoci prokázat, že daný souběžný systém se nemůže vyvinout v jiný s určitými vlastnostmi (Fages et al. 2001). Podobně, sémantika Kripkeho stylu byla poskytnuta v Allwein & Dunn 1993 a Hodas & Miller 1994. Quantales, určitý druh částečně uspořádaných algebraických struktur, byly také použity k poskytnutí časných sémantických modelů pro části lineární logiky (Yetter 1990).

3.2 Sémantika důkazů

V analogii vzorců typu, která je tak populární a plodná v teoretické informatice, je logický systém uváděn do souladu s typovým výpočtovým zařízením (jako je typed (lambda) - počet), přiřazením ke každému důkazu o tento vzorec program, který má tento vzorec jako typ. Například důkaz o tautologii (A / Rightarrow A) odpovídá programu fun ((x: A).x: A / rightarrow A), funkci identity na objektech typu (A). To je důvod, proč se v konstruktivních logických systémech (jako je intuicionální logika a aritmetika) a v lineární logice přikládá tolik důležitosti důkazům, a to do té míry, že budování a studium modelů důkazů získává tolik pozornosti než vytváření a studování modelů prokazatelnosti: nejsme spokojeni, když víme, že vzorec je prokazatelný,opravdu chceme znát výpočetní obsah jeho důkazu.

Bylo navrženo mnoho modelů lineárních logických důkazů; domníváme se, že nejjednodušší a nejintuitivnější konstrukce je dosud ta, která je založena na takzvané „relační sémantice“nebo „sémantice Kripkeho stylu“, kde jsou vzorce interpretovány jako multisety, jednostranné sekvence jsou interpretovány jako n-tice multiset a důkazy jsou interpretovány jako vztahy nad interpretací sekvencí. Pokud chceme dát čistě teoretickou sémantiku, aniž by se uchýlili k multisetům, je možné to udělat pomocí koherenčních prostorů, setů vybavených speciální koherenční relací, jak původně ukazoval Girard 1987. Existuje zajímavá kategorie teoretická modely lineární logiky, jako jsou * -autonomní kategorie (Barr 1991) a hypercoherence (Ehrhard 1993).

Další přístup k sémantice důkazů je dán Girardovou geometrií interakce, která nám umožňuje získat plně algebraickou charakterizaci důkazů. Ke každé zkušební síti lze přiřadit částečnou permutační matici (sigma) odpovídající řezaným odkazům a správnou matici (M) odpovídající výrazy vytvořené z určité dynamické algebry, které popisují možné cesty uvnitř síť důkazů. Potom je možné podrobně popsat zkušební síť pomocí vzorce provádění

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

což je v případě MLL invariantní proces normalizace. Něco pěkného spojení s výsledky pocházejícími z alt="sep man icon" /> Jak citovat tento záznam.

ikona sep muž
ikona sep muž

Náhled na PDF verzi tohoto příspěvku v Friends of the SEP Society.

ikona inpho
ikona inpho

Vyhledejte toto vstupní téma v projektu Internet Philosophy Ontology Project (InPhO).

ikona papíry phil
ikona papíry phil

Vylepšená bibliografie tohoto záznamu ve PhilPapers s odkazy na jeho databázi.

Další internetové zdroje

  • Lineární logická bibliografie (do roku 1998).
  • Vincent Danos a Roberto Di Cosmo. Lineární logický primer. Poznámky k kurzu. (1992).

Doporučená: