Minimální logika - Minimal logic

Minimální logikanebo minimální počet, je symbolická logika systém původně vyvinutý společností Ingebrigt Johansson.^[1] Je to intuitivní a parakonzistentní logika, který odmítá oba zákon vyloučeného středu stejně jako princip exploze (ex falso quodlibet), a proto drží žádný z následujících dvou odvozenin jako platný:

{ displaystyle vdash (A lor neg A)}

{ displaystyle (A land neg A) vdash}

kde ${ displaystyle A}$ je jakýkoli návrh. Většina konstruktivních logik odmítá pouze to první, zákon vyloučeného středu. V klasické logice je ex falso zákony

{ displaystyle (A land neg A) až B,}

{ displaystyle neg (A lor neg A) na B,}

{ displaystyle A to ( neg A až B),}

stejně jako jejich varianty s ${ displaystyle A}$ a ${ displaystyle neg A}$ přepnuty, jsou navzájem rovnocenné a platné. Minimální logika tyto zásady také odmítá.

Axiomatizace

Stejně jako intuitivní logika lze i minimální logiku v jazyce formulovat pomocí znaku implikace ${ displaystyle to}$ ,A spojení ${ displaystyle land}$ ,A disjunkce ${ displaystyle lor}$ ,afalsum nebo absurdita ${ displaystyle bot}$ jako základní spojky. Negace ${ displaystyle neg A}$ se považuje za zkratku pro ${ displaystyle A k bot}$ . Minimální logika je axiomatizována jako pozitivní fragment intuicionistické logiky.

Vztah ke klasické logice

Přidání zákona o dvojí negaci ${ displaystyle neg neg A až A}$ minimální logika vrací kalkul zpět klasická logika:

Vyloučený střed, ${ displaystyle A lor neg A}$ , je pak ekvivalentem odmítnutí ${ displaystyle neg (A lor neg A)}$ a je dosaženo použitím úvod k disjunkci na obou stranách.
Exploze, ${ displaystyle (A land neg A) až B}$ , pak vyplývá z důkazu o rozporu ${ displaystyle (C to (A land neg A)) to neg C}$ použitím ${ displaystyle C = neg B}$ .

Vztah k intuicionistické logice

Výroková forma modus ponens,

{ displaystyle (A land (A až B)) do B,}

je jasně platný i v minimální logice.

Konstruktivně, ${ displaystyle bot}$ představuje návrh, u kterého není důvod věřit tomu. Prokázat návrhy formuláře ${ displaystyle neg A}$ , jeden ukazuje, že za předpokladu ${ displaystyle A}$ vede k rozporu, ${ displaystyle A k bot}$ S principem exploze to bylo uvedeno jako

{ displaystyle (A land (A to bot)) do B,}

princip výbuchu vyjadřuje, že k odvození jakéhokoli tvrzení ${ displaystyle B}$ lze to udělat také odvozením absurdity ${ displaystyle bot}$ . Tento princip je v minimální logice odmítnut. To znamená, že vzorec axiomaticky neplatí pro libovolné ${ displaystyle A}$ a ${ displaystyle B}$ .

Protože minimální logika představuje pouze pozitivní fragment intuicionistické logiky, jedná se o subsystém intuitivní logiky a je přísně slabší.

Prakticky to umožňuje disjunktivní úsudek intuitivní kontext:

{ displaystyle ((A lor B) land (A to bot)) do B.}

Dostal konstruktivní důkaz ${ displaystyle A lor B}$ a konstruktivní odmítnutí ${ displaystyle A}$ , princip exploze bezpodmínečně umožňuje pozitivní volbu případu ${ displaystyle B}$ Je to proto, že pokud ${ displaystyle A lor B}$ bylo prokázáno prokázáním ${ displaystyle B}$ pak ${ displaystyle B}$ je již prokázáno, zatímco pokud ${ displaystyle A lor B}$ bylo prokázáno prokázáním ${ displaystyle A}$ , pak ${ displaystyle B}$ také následuje, pokud systém umožňuje výbuch.

Všimněte si, že s ${ displaystyle bot}$ přijato pro ${ displaystyle B}$ ve výrazu modus ponens zákon neporovnatelnosti

{ displaystyle (A land (A to bot)) to bot,}

tj. ${ displaystyle neg (A land neg A)}$ , lze stále dokázat v minimální logice. Kromě toho jakýkoli vzorec pouze s použitím ${ displaystyle land, lor, to}$ je prokazatelný v minimální logice právě tehdy, je-li prokazatelný v intuitivní logice.

Vztah k teorii typů

Použití negace

Nesmyslnost ${ displaystyle bot}$ je nutné v přirozený odpočet, jakož i typové teoretické formulace v rámci Curry – Howardova korespondence. V typových systémech, ${ displaystyle bot}$ je často také představován jako prázdný typ. V mnoha kontextech ${ displaystyle bot}$ nemusí být samostatnou konstantou v logice, ale její roli lze nahradit jakoukoli odmítnutou větou. Například jej lze definovat jako ${ displaystyle a = b}$ kde ${ displaystyle a, b}$ by měl být odlišný, jako je ${ displaystyle 0 = 1}$ v teorii zahrnující přirozená čísla.

Například s výše uvedenou charakteristikou ${ displaystyle bot}$ , dokazování ${ displaystyle 3 ^ {4} = 8}$ být nepravdivý, tj. ${ displaystyle 3 ^ {4} neq 8}$ , což znamená dokazování ${ displaystyle neg (3 ^ {4} = 8)}$ , znamená jen dokázat ${ displaystyle (3 ^ {4} = 8) až (0 = 1)}$ . A skutečně pomocí aritmetiky ${ displaystyle { tfrac {3 ^ {4} -8} {73}} = 1}$ drží, ale ${ displaystyle (3 ^ {4} = 8)}$ také naznačuje ${ displaystyle { tfrac {3 ^ {4} -8} {73}} = 0}$ . To by tedy znamenalo ${ displaystyle 1 = 0}$ a proto získáváme ${ displaystyle neg (3 ^ {4} = 8)}$ . QED.

Jednoduché typy

Funkční programovací kalkul závisí hlavně na implikaci spojovací, viz např. the Počet konstrukcí pro predikátový logický rámec.

V této části zmiňujeme systém získaný omezením minimální logiky pouze na implikaci. Lze jej definovat následujícím způsobem následující pravidla:

{ displaystyle { dfrac {} { Gamma pohár {A } vdash A}} { mbox {axiom}}}

{ displaystyle { dfrac { Gamma cup {A } vdash B} { Gamma vdash A to B}} { mbox {úvod}}}

{ displaystyle { dfrac { Gamma vdash A až B ~~~~~~~~~~~ Delta vdash A} { Gamma cup Delta vdash B}} { mbox {elim.} }}

^[2]^[3]

Každý vzorec této omezené minimální logiky odpovídá typu v jednoduše zadaný lambda kalkul viz Curry – Howardova korespondence.

Sémantika

Existuje sémantika minimální logiky, která zrcadlí sémantiku rámce intuicionistická logika, viz diskuze o sémantice v parakonzistentní logika. Zde mohou být oceňovací funkce přiřazující pravdivost a nepravdu propozicím méně omezeny.

Viz také

Reference

^ Ingebrigt Johansson (1937). „Der Minimalkalkül, ein reduzierter intuitionistischer formalismus“. Compositio Mathematica (v němčině). 4: 119–136.
^ M. Weber a M. Simons a C. Lafontaine (1993). Obecný vývojový jazyk DEVA: Prezentace a případové studie. LNCS. 738. Springer. p. 246. Zde: str. 36-40.
^ Gérard Huet (květen 1986). Formální struktury pro výpočet a odpočet. Mezinárodní letní škola logiky programování a výpočtů diskrétního designu. Marktoberdorf. Archivovány od originál dne 2014-07-14. Zde: str.125, str.132

TAK JAKO. Troelstra a H. Schwichtenberg, 2000, Základní teorie důkazů, Cambridge University Press, ISBN 0521779111

[1] Ingebrigt Johansson (1937). „Der Minimalkalkül, ein reduzierter intuitionistischer formalismus“. Compositio Mathematica (v němčině). 4: 119–136.

[2] M. Weber a M. Simons a C. Lafontaine (1993). Obecný vývojový jazyk DEVA: Prezentace a případové studie. LNCS. 738. Springer. p. 246. Zde: str. 36-40.

[3] Gérard Huet (květen 1986). Formální struktury pro výpočet a odpočet. Mezinárodní letní škola logiky programování a výpočtů diskrétního designu. Marktoberdorf. Archivovány od originál dne 2014-07-14. Zde: str.125, str.132

[1]

[2]

[3]