Teorie strukturního důkazu - Structural proof theory - Wikipedia

v matematická logika, teorie strukturního důkazu je subdisciplína teorie důkazů že studie důkazní kameny které podporují představu analytický důkaz, druh důkazu, jehož sémantické vlastnosti jsou vystaveny. Pokud všechny teorémy logiky formalizované v teorii strukturních důkazů mají analytické důkazy, lze teorii důkazů použít k prokázání takových věcí, jako je konzistence, poskytnutí rozhodovacích postupů a umožnění extrahování matematických nebo výpočetních svědků jako protikladů k teorémám, druh úkolu, který je častěji zadáván teorie modelů.

Analytický důkaz

Pojem analytický důkaz byl do teorie důkazů zaveden Gerhard Gentzen pro následný počet; analytické důkazy jsou ty, které jsou bez řezu. Jeho přirozený dedukční kalkul podporuje rovněž pojem analytického důkazu, jak ukázal Dag Prawitz; definice je o něco složitější - analytické důkazy jsou normální formy, které souvisejí s pojmem normální forma v přepis termínu.

Struktury a spojovací prvky

Termín struktura v teorii strukturního důkazu pochází z technického pojmu zavedeného do sekvenčního počtu: sekvenční počet představuje úsudek učiněný v jakékoli fázi závěru pomocí speciálních, extralogických operátorů nazývaných strukturální operátory: v ${ displaystyle A_ {1}, tečky, A_ {m} vdash B_ {1}, tečky, B_ {n}}$, čárky nalevo od turniket jsou operátoři běžně interpretovaní jako spojky, ti napravo jako disjunkce, zatímco samotný symbol turniketu je interpretován jako implikace. Je však důležité poznamenat, že existuje zásadní rozdíl v chování mezi těmito operátory a logické spojky jsou interpretovány v následném kalkulu: strukturální operátory jsou použity v každém pravidle kalkulu a nejsou brány v úvahu při dotazování, zda platí vlastnost podformule. Logická pravidla navíc fungují pouze jedním způsobem: logická struktura je zavedena logickými pravidly a nelze ji po vytvoření eliminovat, zatímco strukturní operátory lze zavést a eliminovat v průběhu derivace.

Myšlenka nahlížet na syntaktické vlastnosti sekvencí jako na speciální nelogické operátory není stará a byla vynucena inovacemi v teorii důkazů: když jsou strukturní operátory tak jednoduché jako v původním Getzenově sekvenčním počtu, není potřeba je analyzovat , ale důkazní kameny z hluboký závěr jako logika zobrazení (představil Nuel Belnap v roce 1982)^[1] podporovat strukturální operátory tak složité jako logické spojky a vyžadovat sofistikované zacházení.

Eliminace řezu v následném počtu

Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Prosince 2009)

Přirozená dedukce a korespondence vzorců jako typů

Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Prosince 2009)

Logická dualita a harmonie

Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Prosince 2009)

Hypersquenty

Rámec hypersequent rozšiřuje obyčejnost následná struktura do více sad sekvencí pomocí dodatečného strukturního pojiva | (volal hypersquent bar) k oddělení různých sekvencí. Používá se k poskytování analytických výpočtů např. Pro modální, středně pokročilí a substrukturní logika^[2][3][4] A hypersquent je struktura

${ displaystyle Gamma _ {1} vdash Delta _ {1} mid dots mid Gamma _ {n} vdash Delta _ {n}}$

kde každý ${ displaystyle Gamma _ {i} vdash Delta _ {i}}$ je běžný sled, který se nazývá a komponent hypersquenta. Co se týče sekvencí, hypersequenty mohou být založeny na množinách, vícenásobných sadách nebo sekvencích a komponenty mohou být jednoduché nebo vícečetné sekvence. The interpretace vzorce hypersekvencí závisí na uvažované logice, ale téměř vždy jde o nějakou formu disjunkce. Nejběžnější interpretace jsou jako jednoduchá disjunkce

${ displaystyle ( bigwedge Gamma _ {1} rightarrow bigvee Delta _ {1}) lor dots lor ( bigwedge Gamma _ {n} rightarrow bigvee Delta _ {n})}$

pro mezilehlé logiky nebo jako disjunkce krabic

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

pro modální logiku.

V souladu s disjunktivní interpretací hypersquentního pruhu zahrnují v podstatě všechny hypersquentní kameny vnější strukturální pravidla, zejména pravidlo vnějšího oslabení

${ displaystyle { frac { Gamma _ {1} vdash Delta _ {1} mid dots mid Gamma _ {n} vdash Delta _ {n}} { Gamma _ {1} vdash Delta _ {1} mid dots mid Gamma _ {n} vdash Delta _ {n} mid Sigma vdash Pi}}}$

a pravidlo vnější kontrakce

${ displaystyle { frac { Gamma _ {1} vdash Delta _ {1} mid dots mid Gamma _ {n} vdash Delta _ {n} mid Gamma _ {n} vdash Delta _ {n}} { Gamma _ {1} vdash Delta _ {1} mid dots mid Gamma _ {n} vdash Delta _ {n}}}}$

Dodatečná expresivita rámce hypersequent je poskytována pravidly manipulujícími se strukturou hypersequent. Důležitým příkladem je modalizované pravidlo rozdělení^[3]

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

pro modální logiku S5, kde ${ displaystyle Box Sigma}$ znamená, že každý vzorec v ${ displaystyle Box Sigma}$ je ve formě ${ displaystyle Box A}$.

Další příklad uvádí komunikační pravidlo pro střední logiku LC^[3]

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

Všimněte si, že v komunikačním pravidle jsou komponenty sekvencemi s jedním závěrem.

Počet struktur

Tato sekce potřebuje expanzi. Můžete pomoci přidávat k tomu. (Prosince 2009)

Vnořený sekvenční počet

Vnořený sekvenční počet je formalizace, která se podobá dvoustrannému počtu struktur.

Poznámky

Reference

• Sara Negri; Jan Von Plato (2001). Teorie strukturního důkazu. Cambridge University Press. ISBN  978-0-521-79307-0.
• Anne Sjerp Troelstra; Helmut Schwichtenberg (2000). Základní teorie důkazů (2. vyd.). Cambridge University Press. ISBN  978-0-521-77911-1.