Hypersquent - Hypersequent

v matematická logika, hypersquent framework je rozšířením důkazně-teoretického rámce následující kalkul použito v teorie strukturního důkazu poskytnout analytické výpočty pro logiky, které nejsou zachyceny v následném rámci. Hypersekven se obvykle považuje za konečný multiset obyčejný sekvence, psaný

{ displaystyle Gamma _ {1} Rightarrow Delta _ {1} mid cdots mid Gamma _ {n} Rightarrow Delta _ {n}}

Sekvence tvořící hypersequenta se nazývají komponenty. Přidaná expresivita rámce hypersequent je poskytována pravidly manipulujícími s různými komponentami, jako je komunikační pravidlo pro střední logika LC (dole vlevo) nebo pravidlo modálního rozdělení pro modální logika S5 (vpravo dole):^[1]

{ displaystyle { frac { Gamma _ {1} Rightarrow Delta _ {1} mid dots mid Gamma _ {n} Rightarrow Delta _ {n} mid Sigma Rightarrow A qquad Omega _ {1} Rightarrow Theta _ {1} mid dots mid Omega _ {m} Rightarrow Theta _ {m} mid Pi Rightarrow B} { Gamma _ {1} Rightarrow Delta _ {1} mid dots mid Gamma _ {n} Rightarrow Delta _ {n} mid Omega _ {1} Rightarrow Theta _ {1} mid dots mid Omega _ {m} Rightarrow Theta _ {m} mid Sigma Rightarrow B mid Pi Rightarrow A}}}

{ displaystyle { frac { Gamma _ {1} Rightarrow Delta _ {1} mid dots mid Gamma _ {n} Rightarrow Delta _ {n} mid Box Sigma, Theta Rightarrow Box Pi, Omega} { Gamma _ {1} Rightarrow Delta _ {1} mid dots mid Gamma _ {n} Rightarrow Delta _ {n} mid Box Sigma Rightarrow Box Pi mid Theta Rightarrow Omega}}}

K léčbě byly použity hypersekentní kameny modální logika, mezilehlé logiky, a substrukturální logika. Hypersequents obvykle mají interpretaci vzorce, tj. Jsou interpretovány vzorcem v jazyce objektu, téměř vždy jako nějaký druh disjunkce. Přesná interpretace vzorce závisí na uvažované logice.

Formální definice a výroková pravidla

Formálně se hypersequent obvykle považuje za konečný multiset obyčejný sekvence, psaný

{ displaystyle Gamma _ {1} Rightarrow Delta _ {1} mid dots mid Gamma _ {n} Rightarrow Delta _ {n}}

Sekvence tvořící hypersquent se skládají z n-tic multisetů vzorců a nazývají se komponentami hypersquentu. Varianty, které definují hypersquenty a sekvence z hlediska množin nebo seznamů namísto multisetů, jsou také zvažovány a v závislosti na uvažované logice mohou být sekvence klasické nebo intuitivní. Pravidly pro výroková spojka jsou obvykle úpravy odpovídajících standardních následných pravidel s dodatečným postranním hypersquentem, nazývaným také hypersequentový kontext. Například společná sada pravidel pro funkčně kompletní sada spojek ${ displaystyle { bot, to }}$ pro klasická výroková logika je dána následujícími čtyřmi pravidly:

{ displaystyle { frac {} {{ mathcal {G}} střední Gamma, p Rightarrow p, Delta}}}

{ displaystyle { frac {} {{ mathcal {G}} střední Gamma, bot Rightarrow Delta}}}

{ displaystyle { frac {{ mathcal {G}} střední Gamma, B Rightarrow Delta qquad { mathcal {G}} střední Gamma Rightarrow A, Delta} {{ mathcal {G }} mid Gamma, A to B Rightarrow Delta}}}

${ displaystyle { frac {{ mathcal {G}} střední Gamma, A Rightarrow B, Delta} {{ mathcal {G}} střední Gamma Rightarrow A na B, Delta}} }$

Vzhledem k další struktuře v nastavení hypersquentu strukturální pravidla jsou zvažovány v jejich vnitřní a vnější variantě. Pravidla vnitřního oslabení a vnitřní kontrakce jsou adaptací odpovídajících následných pravidel s přidaným hypersekvenčním kontextem:

{ displaystyle { frac {{ mathcal {G}} střední Gamma Rightarrow Delta} {{ mathcal {G}} střední Gamma, Sigma Rightarrow Delta, Pi}}}

${ displaystyle { frac {{ mathcal {G}} mid Gamma, A, A Rightarrow Delta} {{ mathcal {G}} mid Gamma, A Rightarrow Delta}}}$

${ displaystyle { frac {{ mathcal {G}} mid Gamma Rightarrow A, A, Delta} {{ mathcal {G}} mid Gamma Rightarrow A, Delta}}}$

Pravidla vnějšího oslabení a vnější kontrakce jsou odpovídajícími pravidly na úrovni hypersekvenčních složek namísto vzorců:

${ displaystyle { frac { mathcal {G}} {{ mathcal {G}} střední Gamma Rightarrow Delta}}}$

${ displaystyle { frac {{ mathcal {G}} střední Gamma Rightarrow Delta střední Gamma Rightarrow Delta} {{ mathcal {G}} střední Gamma Rightarrow Delta}}}$

Zdravost těchto pravidel úzce souvisí s formulovým výkladem struktury hypersequent, téměř vždy jako nějaká forma disjunkce. Přesná interpretace vzorce závisí na uvažované logice, některé příklady viz níže.

Hlavní příklady

Modální logika

K získání analytických kalkulů pro modální logika, pro které analytické následující kalkul se ukázalo nepolapitelné. V kontextu modální logiky standardní interpretace vzorce hypersequenta

{ displaystyle Gamma _ {1} Rightarrow Delta _ {1} mid dots mid Gamma _ {n} Rightarrow Delta _ {n}}

je vzorec

{ displaystyle Box ( bigwedge Gamma _ {1} to bigvee Delta _ {1}) lor dots lor Box ( bigwedge Gamma _ {n} to bigvee Delta _ { n})}

Tady pokud ${ displaystyle Gamma}$ je multiset ${ displaystyle A_ {1}, tečky, A_ {n}}$ píšeme ${ displaystyle Box Gamma}$ pro výsledek prefixování každého vzorce v ${ displaystyle Gamma}$ s ${ displaystyle Box}$ , tj. multiset ${ displaystyle Box A_ {1}, tečky, Box A_ {n}}$ . Jednotlivé komponenty jsou interpretovány pomocí standardní interpretace vzorců sekvencí a pruhu hypersquent ${ displaystyle mid}$ se interpretuje jako disjunkce boxů. Ukázkovým příkladem modální logiky, pro kterou hypersequenty poskytují analytický počet, je logika S5. Ve standardním hypersekvenčním počtu pro tuto logiku^[1] interpretace vzorce je jak je uvedeno výše a výroková a strukturální pravidla jsou ta z předchozí části. Kromě toho počet obsahuje modální pravidla

{ displaystyle { frac {{ mathcal {G}} mid Box Gamma Rightarrow A} {{ mathcal {G}} mid Box Gamma Rightarrow Box A}}}

${ displaystyle { frac {{ mathcal {G}} mid Gamma, A Rightarrow Delta} {{ mathcal {G}} mid Gamma, Box A Rightarrow Delta}}}$

${ displaystyle { frac {{ mathcal {G}} mid Box Gamma, Sigma Rightarrow Box Delta, Pi} {{ mathcal {G}} mid Box Gamma Rightarrow Box Delta mid Sigma Rightarrow Pi}}}$

Přípustnost vhodně formulované verze snížit pravidlo lze ukázat syntaktickým argumentem o struktuře derivací nebo zobrazením úplnost počtu bez pravidla oříznutí přímo pomocí sémantiky S5. V souladu s významem modální logiky S5 byla formulována řada alternativních kalkulů.^[2]^[3]^[1]^[4]^[5]^[6]^[7] Hypersequent calculi byly také navrženy pro mnoho dalších modálních logik.^[6]^[7]^[8]^[9]

Mezilehlé logiky

Hypersequent kalkul založený na intuitionistic nebo jedno po sobě jdoucí sekvence byly úspěšně použity k zachycení velké třídy mezilehlé logiky, tj. rozšíření intuicionistická výroková logika. Vzhledem k tomu, že hypersequenty v tomto nastavení jsou založeny na jednoduchých následných sekvencích, mají následující podobu:

{ displaystyle Gamma _ {1} Rightarrow A_ {1} mid dots mid Gamma _ {n} Rightarrow A_ {n}}

Standardní interpretace vzorce pro takového hypersekenta je

{ displaystyle ( bigwedge Gamma _ {1} na A_ {1}) lor dots lor ( bigwedge Gamma _ {n} na A_ {n})}

Většina hypersekvenčních kalkulů pro střední logiku zahrnuje jednoduché verze výše uvedených výrokových pravidel, výběr strukturálních pravidel. Vlastnosti konkrétní mezilehlé logiky jsou většinou zachyceny pomocí řady dalších strukturální pravidla. Například standardní počet pro střední logiku LC, někdy nazývaná také Gödel – Dummettova logika, obsahuje navíc tzv. komunikační pravidlo:^[1]

{ displaystyle { frac { Gamma _ {1} Rightarrow Delta _ {1} mid dots mid Gamma _ {n} Rightarrow Delta _ {n} mid Sigma Rightarrow A qquad Omega _ {1} Rightarrow Theta _ {1} mid dots mid Omega _ {m} Rightarrow Theta _ {m} mid Pi Rightarrow B} { Gamma _ {1} Rightarrow Delta _ {1} mid dots mid Gamma _ {n} Rightarrow Delta _ {n} mid Omega _ {1} Rightarrow Theta _ {1} mid dots mid Omega _ {m} Rightarrow Theta _ {m} mid Sigma Rightarrow B mid Pi Rightarrow A}}}

Byly zavedeny hypersquentní kameny pro mnoho dalších přechodných logik,^[1]^[10]^[11]^[12] a jsou zde velmi obecné výsledky eliminace řezu v takovém počtu.^[13]

Substrukturální logika

Pokud jde o střední logiku, pro získání analytických kalkulů se pro mnoho lidí používaly hypersquenty substrukturální logika a fuzzy logiky.^[1]^[13]^[14]

Dějiny

Zdá se, že struktura hypersekven se objevila jako první^[2] pod názvem průvod k získání počtu pro modální logiku S5. Zdá se, že byly vyvinuty nezávisle na,^[3] také k léčbě modální logiky a ve vlivných,^[1] kde jsou uvažovány kameny pro modální, střední a substrukturální logiku a je zaveden pojem hypersquent.

Reference

^ ^A ^b ^C ^d ^E ^F ^G Avron, Arnon (1996). Metoda hypersekvencí v teorii důkazů výrokových neklasických logik. Logika: Od základů po aplikace. s. 1–32. ISBN 978-0-19-853862-2.
^ ^A ^b Mincovny, Grigori (1971). "Na některých výpočtech modální logiky". Proc. Steklov Inst. Matematiky. 98: 97–122.
^ ^A ^b Pottinger, Garrell (1983). "Jednotné formulace T, S4 a S5 bez řezu (abstrakt)". J. Symb. Log. 48 (3): 900.
^ Poggiolesi, Francesca (2008). „Jednoduchý sekvenční počet bez řezu pro modální logiku S5“ (PDF). Symb. Log. 1: 3–15. doi:10.1017 / S1755020308080040.
^ Restall, Greg (2007). Dimitracopoulos, Costas; Newelski, Ludomir; Normann, Dag; Steel, John R. (eds.). Msgstr "Proofnety pro S5: Sekvence a obvody pro modální logiku". Logické kolokvium 2005. Logické poznámky k přednášce. 28: 151–172. doi:10.1017 / CBO9780511546464.012. hdl:11343/31712. ISBN 9780511546464.
^ ^A ^b Kurokawa, Hidenori (2014). "Hypersequent Calculi pro modální logiku rozšiřující S4". Nové hranice v umělé inteligenci. Přednášky z informatiky. 8417. str. 51–68. doi:10.1007/978-3-319-10061-6_4. ISBN 978-3-319-10060-9.
^ ^A ^b Lahav, Ori (2013). Msgstr "Od vlastností rámu k hypersquentním pravidlům v modálních logikách". 28. výroční sympozium ACM / IEEE o logice v informatice v roce 2013. 408–417. doi:10.1109 / LICS.2013.47. ISBN 978-1-4799-0413-6. S2CID 221813.
^ Indrzejczak, Andrzej (2015). "Eliminovatelnost řezu v hypersekvenčním počtu pro některé modální logiky lineárních rámců". Dopisy o zpracování informací. 115 (2): 75–81. doi:10.1016 / j.ipl.2014.07.002.
^ Lellmann, Björn (2016). "Hypersequent pravidla s omezeným kontextem pro výrokové modální logiky". Teor. Comput. Sci. 656: 76–105. doi:10.1016 / j.tcs.2016.10.004.
^ Ciabattoni, Agata; Ferrari, Mauro (2001). "Hypersequent kalkul pro některé mezilehlé logiky s ohraničenými Kripkeho modely". J. Log. Comput. 11 (2): 283–294. doi:10.1093 / logcom / 11.2.283.
^ Ciabattoni, Agata; Maffezioli, Paolo; Spendier, Lara (2013). Galmiche, Didier; Larchey-Wendling, Dominique (eds.). "Hypersequent a označené kameny pro mezilehlé logiky". Tableaux 2013: 81–96.
^ Baaz, Matthias; Ciabattoni, Agata; Fermüller, Christian G. (2003). "Hypersequent Calculi pro Gödel Logics - průzkum". J. Log. Comput. 13 (6): 835–861. doi:10.1093 / logcom / 13.6.835.
^ ^A ^b Ciabattoni, Agata; Galatos, Nikolaos; Terui, Kazushige (2008). "Od axiomů k analytickým pravidlům v neklasické logice". 2008 23. výroční sympozium IEEE o logice v informatice. 229–240. CiteSeerX 10.1.1.405.8176. doi:10.1109 / LICS.2008.39. ISBN 978-0-7695-3183-0. S2CID 7456109.
^ Metcalfe, George; Olivetti, Nicola; Gabbay, Dov (2008). Teorie důkazů pro fuzzy logiku. Springer, Berlín.

[:0-1] A ^b ^C ^d ^E ^F ^G Avron, Arnon (1996). Metoda hypersekvencí v teorii důkazů výrokových neklasických logik. Logika: Od základů po aplikace. s. 1–32. ISBN 978-0-19-853862-2.

[:4-2] A ^b Mincovny, Grigori (1971). "Na některých výpočtech modální logiky". Proc. Steklov Inst. Matematiky. 98: 97–122.

[:5-3] A ^b Pottinger, Garrell (1983). "Jednotné formulace T, S4 a S5 bez řezu (abstrakt)". J. Symb. Log. 48 (3): 900.

[4] Poggiolesi, Francesca (2008). „Jednoduchý sekvenční počet bez řezu pro modální logiku S5“ (PDF). Symb. Log. 1: 3–15. doi:10.1017 / S1755020308080040.

[5] Restall, Greg (2007). Dimitracopoulos, Costas; Newelski, Ludomir; Normann, Dag; Steel, John R. (eds.). Msgstr "Proofnety pro S5: Sekvence a obvody pro modální logiku". Logické kolokvium 2005. Logické poznámky k přednášce. 28: 151–172. doi:10.1017 / CBO9780511546464.012. hdl:11343/31712. ISBN 9780511546464.

[:1-6] A ^b Kurokawa, Hidenori (2014). "Hypersequent Calculi pro modální logiku rozšiřující S4". Nové hranice v umělé inteligenci. Přednášky z informatiky. 8417. str. 51–68. doi:10.1007/978-3-319-10061-6_4. ISBN 978-3-319-10060-9.

[:2-7] A ^b Lahav, Ori (2013). Msgstr "Od vlastností rámu k hypersquentním pravidlům v modálních logikách". 28. výroční sympozium ACM / IEEE o logice v informatice v roce 2013. 408–417. doi:10.1109 / LICS.2013.47. ISBN 978-1-4799-0413-6. S2CID 221813.

[8] Indrzejczak, Andrzej (2015). "Eliminovatelnost řezu v hypersekvenčním počtu pro některé modální logiky lineárních rámců". Dopisy o zpracování informací. 115 (2): 75–81. doi:10.1016 / j.ipl.2014.07.002.

[9] Lellmann, Björn (2016). "Hypersequent pravidla s omezeným kontextem pro výrokové modální logiky". Teor. Comput. Sci. 656: 76–105. doi:10.1016 / j.tcs.2016.10.004.

[10] Ciabattoni, Agata; Ferrari, Mauro (2001). "Hypersequent kalkul pro některé mezilehlé logiky s ohraničenými Kripkeho modely". J. Log. Comput. 11 (2): 283–294. doi:10.1093 / logcom / 11.2.283.

[11] Ciabattoni, Agata; Maffezioli, Paolo; Spendier, Lara (2013). Galmiche, Didier; Larchey-Wendling, Dominique (eds.). "Hypersequent a označené kameny pro mezilehlé logiky". Tableaux 2013: 81–96.

[12] Baaz, Matthias; Ciabattoni, Agata; Fermüller, Christian G. (2003). "Hypersequent Calculi pro Gödel Logics - průzkum". J. Log. Comput. 13 (6): 835–861. doi:10.1093 / logcom / 13.6.835.

[:3-13] A ^b Ciabattoni, Agata; Galatos, Nikolaos; Terui, Kazushige (2008). "Od axiomů k analytickým pravidlům v neklasické logice". 2008 23. výroční sympozium IEEE o logice v informatice. 229–240. CiteSeerX 10.1.1.405.8176. doi:10.1109 / LICS.2008.39. ISBN 978-0-7695-3183-0. S2CID 7456109.

[14] Metcalfe, George; Olivetti, Nicola; Gabbay, Dov (2008). Teorie důkazů pro fuzzy logiku. Springer, Berlín.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]