Logika intuice

Intuitionistic logika je logika , která se liší od klasické logiky , že pojem pravdy je nahrazen pojmem konstruktivního důkazu . Tvrzení jako „ konstanta Euler-Mascheroni je racionální nebo konstanta Euler-Mascheroni není racionální“ není v rámci našich současných matematických znalostí konstruktivně (intuitivně) demonstrováno; protože klasická tautologie „P nebo ne P“ ( vyloučená třetí strana ) nepatří k intuitivní logice. Intuitionistická logika mimo jiné zavádí rozdíl mezi „být pravdivý“ a „nebýt falešný“ (slabší formulace), protože ¬¬ → P není v intuitivní logice ani prokazatelný.

Dějiny

Intuicionismus byl první pozice filozofický tváří v tvář matematiky navržené matematik holandský L. E. J. Brouwer jako možnost odlišný od přístupu známé klasické ; to ho vedlo k tomu, že nezahrnul určité formy tradičního matematického uvažování, které považoval za neintuitivní:

Vyloučena třetí , která spočívá v tom, že, daný problém , jedna má jeden , nebo ne ; $P$ $P$ $P$
Nekonstruktivní existenciální . Brouwer chce, že když matematik potvrzuje, že existuje taková, že $X$ $P (x)$ se také dává prostředky na výstavbu , které vyhovuje . $X$ $P (x)$

Brouwer obhajoval matematiku, která by odmítla vyloučenou třetí stranu a akceptovala pouze konstruktivní existenciál . Tento přístup byl ostře kritizován matematiky jako David Hilbert, zatímco jiní jako Hermann Weyl se k němu přihlásili.

Poté jej formalizovali pod názvem intuiční logiky jeho žáci V. Glivenko a Arend Heyting , stejně jako Kurt Gödel a Andrej Kolmogorov . Brouwer-Heyting-Kolmogorov výklad nebo prostě výklad BHK je v podstatě zvýraznění konstruktivního charakteru intuitionist implikace : Je-li intuitionist matematik tvrdí , že znamená, že poskytuje způsob „konstrukci“ předpisu intuitionist implikace. Demonstraci od ukázka . Jinými slovy, důkaz je funkce, která transformuje důkaz na na důkaz . $a \ Rightarrow b$ $b$ $na$ $a \ Rightarrow b$ $na$ $b$

Tato výpočetní interpretace vyvrcholí jedním z nejdůležitějších výsledků teoretické informatiky: Curryho-Howardovou korespondencí, jejíž leitmotivem je „dokázat, je programovat“. Mezi pravidly dedukce intuitivní logiky a pravidly psaní lambda-kalkulu existuje izomorfismus. V důsledku toho je důkaz tvrzení asimilován na (lambda-) výraz typu . $P$ $P$

V důsledku toho intuitivní logika (spojená s teorií typů ) získává převládající status v logice a v teoretické informatice, což z ní činí historicky první z konstruktivních logik . Tento zakládající výsledek vygeneruje mnoho odvozených děl ; zejména jeho rozšíření na logiku vyššího řádu, které vyžaduje použití závislých typů ( výpočet konstrukcí je například teoretickým základem softwaru Coq, který je tedy současně asistentem (konstruktivních) důkazů , a nástroj pro vytváření certifikovaných programů).

Syntaxe jazyka intuitivní logiky

Syntax intuiční výrokové logiky je stejná jako u klasické výrokové logiky . Syntax intuitivní logiky prvního řádu je stejná jako syntax klasické logiky prvního řádu .

Syntax výrokové intuicionistické logiky

Konstrukce	Intuitivní čtení v klasické logice	Intuitivní čtení v intuitivní logice
$NA$	$NA$ je pravda	$NA$ je prokazatelné
${\ displaystyle (A \ lor B)}$	$NA$ je pravda nebo je pravda $B$	$NA$ je prokazatelné nebo je prokazatelné $B$
${\ displaystyle (A \ land B)}$	$NA$ je pravda a je pravda $B$	$NA$ je prokazatelný a je prokazatelný $B$
$\ bot$	Nepravdivé	Nepravdivé
${\ displaystyle (A \ Rightarrow B)}$	Pokud je pravda, pak je pravda $NA$ $B$	Pokud je prokazatelné, pak je prokazatelné $NA$ $B$
$\ lnote A$ (zkratka ) ${\ displaystyle A \ Rightarrow \ bot}$	$NA$ je nepravdivé	$NA$ je rozporuplný

Intuicionistická logika prvního řádu syntaxe

Konstrukce	Intuitivní čtení v klasické logice	Intuitivní čtení v intuitivní logice
$\ existuje xA (x)$	existuje prvek , který je pravdivý $X$ $A (x)$	můžeme zkonstruovat prvek , který je prokazatelný $X$ $A (x)$
$\ všech xA (x)$	u součásti , platí $X$ $A (x)$	tím, že vezme jakýkoli prvek , je prokazatelné $X$ $A (x)$

Nedefinovatelnost operátorů

Negaci lze definovat z implikace: je definována jako . V klasické výrokové logice můžeme definovat disjunkci („nebo“) z „a“ a negaci díky Morganovým zákonům . Například lze definovat jako zkratku pro psaní pro . V intuicionistické výrokové logice to již neplatí a každý operátor má jinou interpretaci (viz tabulka výše). Stejně tak nelze definovat jako . $\ lnote A$ ${\ displaystyle A \ Rightarrow \ bot}$ ${\ displaystyle (A \ lor B)}$ $\ lnot (\ lnot A \ land \ lnot B)$ $\ existuje xA (x)$ ${\ Displaystyle \ lnot \ forall x \ lnot A (x)}$

Pravidla přirozeného odpočtu

V intuitivní logice nejsou konektory vzájemně definovatelné. Z tohoto důvodu dáme pravidla pro každý binární konektor, pro unární konektor, který je negací, a pro symbol symbol představující falešný nebo absurdní. Pro každý konektor uvádíme jedno (nebo více) eliminační pravidlo a jedno (nebo více) úvodní pravidlo , typické pro klasickou přirozenou dedukci . Při přirozené dedukci zní „ze sady výroků odvodíme výrok “ . ${\ displaystyle (E)}$ $(Já)$ $\ Gamma \ vdash \ varphi$ $\, \ Gama$ $\ varphi$

Implikativní logika

Pouze konektor ze implicative minimálním logika je implikace . V přirozené dedukci , její pravidla, kromě pravidla axiomu: $\ Pravá šipka$

{\ displaystyle {\ frac {} {\ Gamma, \ varphi \ vdash \ varphi}} \ quad ({\ text {axiom}})}

jsou:

{\ frac {\ Gamma \ vdash \ varphi \ Rightarrow \ psi \ quad \ Gamma \ vdash \ varphi} {\ Gamma \ vdash \ psi}} \ quad (\ Rightarrow E) \ qquad \ qquad \ qquad {\ frac {\ Gamma, \ varphi \ vdash \ psi} {\ Gamma \ vdash \ varphi \ Rightarrow \ psi}} \ quad (\ Rightarrow I)

kde písmeno označuje konečnou sadu vzorců a notace označuje , kde může nebo nemusí být v . $\ Gama$ ${\ displaystyle \ gama, \ varphi}$ ${\ displaystyle \ gama \ pohár \ {\ varphi \}}$ $\ varphi$ $\ Gama$

Pravidlo se nazývá pravidlo eliminace implikace . Zní takto: pokud ze souboru hypotéz odvodíme, a pokud navíc ze souboru hypotéz odvodíme, pak ze souboru hypotéz odvodíme . Odstranění zapojení se také nazývá modus ponens . ${\ displaystyle (\ Rightarrow E)}$ $\ Gama$ $\ varphi \ Rightarrow \ psi$ $\ Gama$ $\ varphi$ $\ Gama$ $\ psi$

Pravidlo se nazývá pravidlo zavedení implikace . Zní to takto: pokud ze souboru hypotéz a z hypotézy lze odvodit, pak ze sady hypotéz se odvodí ( může nebo nemusí patřit ). ${\ displaystyle (\ Rightarrow I)}$ $\ Gama$ $\ varphi$ $\ psi$ $\ Gama$ $\ varphi \ Rightarrow \ psi$ $\ varphi$ $\ Gama$

Zákon Peirce nebo návrh , které jsou tautologie o klasické logiky , nejsou prokazatelné v tomto odpočtu. Přidáním do něj, například Peirceova zákona, získáme deduktivně úplný systém ve smyslu klasické logiky pro čistě implikační vzorce (viz Implikační výrokový počet ( fr ) ). ${\ displaystyle ((\ varphi \ Rightarrow \ psi) \ Rightarrow \ varphi) \ Rightarrow \ varphi}$ ${\ displaystyle ((\ varphi \ Rightarrow \ psi) \ Rightarrow \ rho) \ Rightarrow ((\ psi \ Rightarrow \ varphi) \ Rightarrow \ rho) \ Rightarrow \ rho}$

Intuicionistická výroková logika

Logika intuice má pravidla implikace, minimální logiku a pravidla níže, kterými se řídí ostatní konektory.

Absurdní

Falešný nebo absurdní, ⊥, je nulový konektor, to znamená, že nemá žádný argument v argumentu, řídí se pravidlem:

{\ frac {\ Gamma \ vdash \ bot} {\ Gamma \ vdash \ varphi}} \ qquad (\ bot E).

Toto pravidlo se nazývá princip exploze nebo latinsky ex falso quodlibet . Princip exploze znamená, že pokud soubor výroků $Γ$ vede k absurditě ⊥, pak z $Γ$ , můžeme odvodit jakýkoli výrok . $\ varphi$

Vyjednávání

Tradičně považujeme negaci za zkratku, a proto obvykle nedáváme pravidla odpovídající této negaci. Mohli bychom však některé dát, abychom zjednodušili demonstrace a byly by to: $\ neg \ varphi$ $\ varphi \ Rightarrow \ bot$

{\ displaystyle {\ frac {\ Gamma \ vdash \ neg \ varphi \ quad \ Gamma \ vdash \ varphi} {\ Gamma \ vdash \ bot}} ~ (\ neg E) \ qquad \ qquad {\ frac {\ Gamma, \ varphi \ vdash \ bot} {\ Gamma \ vdash \ neg \ varphi}} ~ (\ neg I)}

Je třeba poznamenat, že tato pravidla pro intuiční intuici jsou slabší než pravidla pro klasickou negaci, protože odtud například nelze odvodit . $\ varphi$ ${\ displaystyle \ neg \ neg \ varphi}$

Spojení

S konektorem (spojkou) spojujeme dvě pravidla eliminace, a , a úvodní pravidlo. $\ přistát$ $\ přistát E_ {1}$ $\ přistát E_ {2}$

{\ frac {\ Gamma \ vdash A_ {1} \ land A_ {2}} {\ Gamma \ vdash A_ {i}}} \ quad (\ land E_ {i}) \ qquad \ qquad \ qquad {\ frac { \ Gamma \ vdash A \ quad \ Gamma \ vdash B} {\ Gamma \ vdash A \ land B}} \ quad (\ land I)

kde se čte „A a B“.

A \ land B

Disjunkce

S konektorem (disjunkce) spojujeme eliminační pravidlo a dvě úvodní pravidla: $\ vee$

{\ frac {\ Gamma \ vdash A \ vee B \ quad \ Gamma, A \ vdash C \ quad \ Gamma, B \ vdash C} {\ Gamma \ vdash C}} \ quad (\ vee E) \ qquad \ qquad \ qquad {\ frac {\ Gamma \ vdash A_ {i}} {\ Gamma \ vdash A_ {1} \ vee A_ {2}}} \ quad (\ vee I_ {i})

Všimněte si, že pravidlo vyloučení disjunkce je triadické pravidlo: má tři premisy.

Výpočet intuicionistických predikátů

Kromě pravidel intuicionistického výrokového kalkulu obsahuje intuitivistický predikátový počet nová pravidla pro zavedení a eliminaci kvantifikátorů „cokoli“ a „existuje“.

Poznámka : Připomínáme, že A [t / x] znamená nahrazení všech volně nahraditelných výskytů proměnné x výrazem t; viz výpočet predikátů pro pojmy „proměnná“, „výraz“, „substituce“ a „volně zaměnitelná“.

Univerzální kvantifikátor

${\ displaystyle {\ frac {\ Gamma, A [t / x] \ vdash B} {\ Gamma, \ forall xA \ vdash B}} (\ forall E)}$ ${\ displaystyle {\ frac {\ Gamma \ vdash A} {\ Gamma \ vdash \ forall xA}} (\ forall I)}$

Existenční kvantifikátor

${\ displaystyle {\ frac {\ Gamma \ vdash A [t / x]} {\ Gamma \ vdash \ existuje xA}} (\ existuje E)}$ ${\ displaystyle {\ frac {\ Gamma, A \ vdash B} {\ Gamma, \ existuje xA \ vdash B}} (\ existuje I)}$

Sémantika intuitivní logiky

Modely Kripke

Můžeme dát sémantiku intuitivní logice, která je Kripkeho sémantikou . Kripke modelu je graf, kde: ${\ mathcal {M}}$

uzly jsou možné světy . Podle Kripkeho tyto světy představují informační obsah založený na důkazech ( důkazní situace ). Každý svět je vybaven klasickým oceněním: intuitivně pro každou výrokovou proměnnou p platí ve světě p, pokud máme dostatek informací k prokázání, že p je jinak nepravdivé;
vztah přístupnosti předobjednávky na světech: reflexivní a přechodný vztah hierarchizuje světy. Pro Kripkeho oblouk m → m 'znamená, že m' je v „budoucnosti“ m;
ocenění je takové, že pokud výroková proměnná p platí v m a m 'je v „budoucnosti“ m, pak p platí i v m' (neztrácíme informace, a proto můžeme vždy dokázat p).

Říkáme-li, že svět splňuje vzorec , říkáme také, že svět si vynucuje vzorec . Vztah vynucení (nebo proveditelnosti ) je definován strukturální indukcí pomocí: $m$ $\ varphi$ $m$ $\ varphi$

svět nutí výrokovou proměnnou si platí ve světě m; $m$ $p$ $p$
světové síly tolik síly a síly ; $m$ ${\ displaystyle (\ varphi \ land \ psi)}$ $m$ $\ varphi$ $m$ $\ psi$
světové síly, ať už síla, nebo síla ; $m$ ${\ displaystyle (\ varphi \ lor \ psi)}$ $m$ $\ varphi$ $m$ $\ psi$
světové síly, pokud pro jakýkoli svět přístupný z , pokud síla pak síla (někteří autoři nazývají soubor světů přístupných ze světa kuželem ). $m$ ${\ displaystyle (\ varphi \ Rightarrow \ psi)}$ ${\ displaystyle m '}$ $m$ $mě$ $\ varphi$ ${\ displaystyle m '}$ $\ psi$

Vzorec je platný , jestliže pro každou světě jakéhokoliv modelu , síla . $\ varphi$ $m$ ${\ mathcal {M}}$ $m$ $\ varphi$

Příklad

Zvažte model Kripke vpravo. Nespokojuje vyloučenou třetí stranu . Opravdu, na jedné straně počáteční svět nenutí (intuitivně, není prokázán, protože je falešný, takže to znamená, že ještě nemáme dostatek informací). Na druhou stranu počáteční svět, který není vynucen, není rozporuplný, protože poskytnutím trochu většího úsilí lze „získat více informací“ a přijít do správného světa a dokázat . Vyloučená třetí strana není platná. Také : $(p \ lor \ lnot p)$ $p$ $p$ $p$ $\ lnot str$ $p$ $(p \ lor \ lnot p)$

$((p \ Rightarrow q) \ Rightarrow p) \ Rightarrow p$ ( Peirceův zákon ) není platný: levý svět Kripkeho modelu vpravo nenutí ; $((p \ Rightarrow q) \ Rightarrow p) \ Rightarrow p$
$((p \ Rightarrow q) \ Rightarrow r) \ Rightarrow ((q \ Rightarrow p) \ Rightarrow r) \ Rightarrow r$ není platný.

Oprava intuitivní logiky

Logika intuice je správná s ohledem na Kripkeho modely, tj. Platí jakýkoli prokazatelný vzorec (například s pravidly přirozené dedukce z předchozí části). Tento výsledek můžeme použít k ukázce, že vzorec není v intuitivní logice prokazatelný. Například protože vyloučená třetí strana nebo Peirceův zákon nejsou platné, nejsou prokazatelné. $(p \ lor \ lnot p)$ $((p \ Rightarrow q) \ Rightarrow p) \ Rightarrow p$

Úplnost intuitivní logiky

Jakýkoli platný vzorec je prokazatelný . Demonstrace se provádí následujícím způsobem: pokud to není prokazatelné, můžeme postavit (nekonečný) protimodel , tj. Model obsahující svět, který nenutí . $\ varphi$ $\ varphi$ ${\ mathcal {M}}$ $\ varphi$

Vztahy s klasickou logikou

Příklady rozdílů od klasické logiky

Operace nejsou navzájem definovány (viz níže) a jsou definovány pouze samy. Jsou definovány interpretací, která z nich musí být provedena. Z tohoto důvodu jsou kromě pravidel výpočtu uvedeny i interpretace výrazů každého operátoru, které je třeba provést.

Některé validity

Následující tabulka uvádí některé validity intuitivní logiky.

Validita v logice intuice	Vysvětlení pro $\ Pravá šipka$	Vysvětlení pro $\ Šipka vlevo$
$A \ Rightarrow \ lnot \ lnot A$	✔ Pokud je A prokazatelné, pak je dokázáno, že A není v rozporu.	✗ Například je prokázáno, že „prší“ není rozporuplné (rozpor se nezíská za předpokladu, že „prší“). „Prší“ však není prokazatelné, pokud nevyjdete ven a nezmoknete.
$\ lnot A \ Leftrightarrow \ lnot \ lnot \ lnot A$	✔ Je-li A rozporuplné, pak rozpor dává důkaz, který není rozporuplný. $NA$	✔ Pokud máme důkaz, který si není protichůdný, dává rozpor, pak A je rozporuplný. $NA$
$(\ lnot A) \ lor (\ lnot B) \ Rightarrow \ lnot (A \ land B)$	✔ Pokud je A rozporuplné nebo B je rozporuplné, pak „A a B“ jsou rozporuplné.	✗ Například být vysoký a nízký je rozporuplný. Být vysoký však není v rozporu a malý není v rozporu.
$\ lnot (A \ lor B) \ Leftarrow (\ lnot A) \ land (\ lnot B)$	✔ Pokud získáme rozpor z důkazu A nebo důkazu B, pak A je rozporuplné a B je rozporuplné.	✔ Pokud je A rozporuplné a B je rozporuplné, pak z důkazu A nebo důkazu B dostaneme rozpor.
$((\ lnot A) \ lor B) \ Rightarrow (A \ Rightarrow B)$	✔ Pokud je A rozporuplné nebo pak B je prokazatelné, pak pokud mám důkaz A (který neexistuje!), Mám důkaz B.	✗ Například konstruuji důkaz „x> 0“, který používá důkaz „x> 1“. „X> 1“ však není rozporuplné a „x> 0“ není prokazatelné.
$\ lnot (\ existuje xA (x)) \ Leftrightarrow \ pro všechny x (\ lnot A (x))$	✔ Pokud „existuje x takové, že A (x)“ je rozporuplné, pak pro všechna x je A (x) rozporuplné.	✔ Pokud je pro všechna x A (x) rozporuplné, pak „existuje x takové, že A (x)“ je rozporuplné.
$\ existuje x (\ lnot A (x)) \ Rightarrow \ lnot (\ pro všechny xA (x))$	✔ Pokud mohu sestrojit x tak, aby A (x) bylo v rozporu, pak „pro všechna x je A (x)“ rozporuplné.	✗ Například „pro všechny x je x chudé“ je rozporuplné (protože vidím, že existuje bohatství). Nemohu však najít jednotlivce x (bohatého) takového, že x je špatné, aby si odporovalo.

V klasické logice jsou vzorce získané nahrazením implikací ekvivalencemi validity (tabulka by obsahovala pouze ✔).

Negace

Lze jej vykládat jako: „Je prokázáno, že je to rozporuplné“. $\ lnote A$ $NA$

V intuiční logice máme následující větu:

$\ lnot A \ Leftrightarrow \ lnot \ lnot \ lnot A$

Z toho však nelze vyvodit závěr , protože tuto ekvivalenci nelze v intuiční logice dokázat. $A \ Leftrightarrow \ lnot \ lnot A$

Dvojitá negace

Lze jej vykládat jako: „Ukázalo se, že je rozporuplné tvrdit, že je to rozporuplné“, to znamená „Je prokázáno, že to není rozporuplné“. Nelze však odvodit, že „ je prokazatelné“. $\ lnot \ lnot A$ $NA$ $NA$ $NA$

Věta:

$A \ Rightarrow \ lnot \ lnot A$

lze demonstrovat v intuitivní logice. Ale konverzace nemůže být. Nemáme . Výraz lze interpretovat jako „z demonstrace , můžeme sestrojit demonstraci “. Skutečnost, která si není protichůdná, však nestačí k prokázání „ “. $\ lnot \ lnot A \ Rightarrow A$ $A \ Rightarrow \ lnot \ lnot A$ $NA$ ${\ displaystyle \ neg \ neg A}$ $NA$ $NA$

Například nechť x je reálné číslo a věta x je racionální. Dokázat znamená dát dvě celá čísla a a b tak, že x = a / b . Pokud je rozporuplné (a tedy pokud máme ), pak x je neracionální nebo iracionální. Říct, co máme, znamená říci, že předpokládat, že x bude iracionální, vede k rozporu, a tedy k závěru, že x není iracionální. Ale to není dostatečné k efektivnímu existenci dvou celých čísel a b tak, že x = / b . V intuicionistické logice tedy není být iracionální jinou a slabší vlastností než být racionální. $NA$ $NA$ $NA$ $\ lnote A$ $\ lnot \ lnot A$

Spojení

Výklad je: máme důkaz a důkaz (srovnatelný s tím, co je v klasické logice). $A \ land B$ $NA$ $B$

V intuicionistické logice je následující věta teorémem:

$(\ lnot A) \ lor (\ lnot B) \ Rightarrow \ lnot (A \ land B)$

Ale na rozdíl od toho, co by to bylo v klasické logice, je to jen důsledek toho , že konverzace je falešná. Předpokládejme, že je to rozporuplné, v intuitivní logice nestačí k tomu, abychom dospěli k závěru, zda je to sám, nebo zda jsou oba. Například předpokládat, že číslo je racionální i iracionální, je rozporuplné, ale nedostatečné k závěru, zda je toto číslo iracionální nebo ne. $\ lnot (A \ land B)$ $(\ lnot A) \ lor (\ lnot B)$ $A \ land B$ $NA$ $B$

Disjunkce

Výklad je: máme důkaz nebo důkaz . $A \ lor B$ $NA$ $B$

V intuiční logice máme následující větu:

$\ lnot (A \ lor B) \ Leftarrow (\ lnot A) \ land (\ lnot B)$

A a B se vzájemně vylučují a nejsou současně prokazatelné. Tato situace je srovnatelná s tím, co by bylo v klasické logice Boole a Karnaugh .

Na druhé straně následující věta:

$((\ lnot A) \ lor B) \ Rightarrow (A \ Rightarrow B)$

je platný v intuiční logice, ale ne jeho obrácení. Pokud je x skutečné číslo, víme, že pokud je racionální, pak to není iracionální, ale nejsme všichni schopni dospět k závěru, zda je toto číslo iracionální nebo ne.

Existenční kvantifikátor

Výklad je: můžeme vytvořit objekt a dokázat to . Existence x je zde účinná nebo konstruktivní. Nejde o teoretickou existenci ověřovacího prvku . $\ existuje xA (x)$ $X$ $A (x)$ $X$ $A (x)$

Máme následující větu:

$\ lnot (\ existuje xA (x)) \ Leftrightarrow \ pro všechny x (\ lnot A (x))$

Pokud neexistuje x, které splňuje A (x), pak pro všechna x neověřujeme A (x) , tedy ekvivalenci (která odpovídá intuici a je přirozeně formulována). Tato vlastnost je srovnatelná s tím, co by bylo v klasické logice.

Univerzální kvantifikátor

Interpretace je: máme důkaz, že pro každé x patřící do zadané množiny můžeme dokázat A (x) (srovnatelné s tím, co je v klasické logice). $\ všech xA (x)$

V intuiční logice máme následující větu:

$\ existuje x (\ lnot A (x)) \ Rightarrow \ lnot (\ pro všechny xA (x))$

Ale na rozdíl od toho, co by bylo v klasické logice, je obrácení falešné. Ve skutečnosti by tento konverzace vyžadoval, aby za předpokladu, že univerzálnost vlastnosti je rozporuplná , je člověk schopen explicitně vystavit neplatný objekt x , což je zřídka možné. $A (x)$ $A (x)$

Můžeme také říci, že v intuicionistické logice je potvrzením potvrzení účinné a konstruktivní existence validujícího objektu x , zatímco jeho jediná teoretická existence, vyjadřující pouze to, že je rozporuplná, je univerzálně rozporuplná. Klasická logika nerozlišuje mezi těmito dvěma existencemi, zatímco intuitivní logika považuje druhou za slabší než první. $\ existuje xA (x)$ $A (x)$ $\ lnot (\ forall x \ lnot A (x))$ $A (x)$

Třetí strana vyloučena

Následující návrh

$A \ lor \ lnot A$

je teorém klasické logiky, ale ne intuitivní logiky. Ve druhém případě by to znamenalo, že můžeme dokázat nebo dokázat , což není vždy možné. $NA$ $\ lnote A$

Například v aritmetice poskytované intuicionistickou logikou (známé jako Heytingova aritmetika ) je výraz platný, protože pro jakoukoli dvojici celých čísel můžeme dokázat, že jsou si rovni, nebo můžeme dokázat, že se liší. Je to stejné pro dvě racionály. Ale ve dvou realitách v konstruktivní analýze nemáme obecnou metodu, která by to dokázala nebo dokázala . Tato situace dobře odpovídá tomu, s čím se člověk setkává v algoritmu, kde rovnost nebo nerovnost mezi dvěma realitami může být nevypočitatelná, to znamená, že není rozhodnutelná. $(x = y \ lor x \ neq y)$ $x = y$ $x \ neq y$

Vztah mezi pravidly

Abychom lépe porozuměli, všimneme si, co předchází, že na rozdíl od toho, co je v logice Boole, spojení nelze přeformulovat z hlediska disjunkce a že existenční kvantifikátor nelze přeformulovat z hlediska univerzálního kvantifikátoru ; to na základě principu konstruktivismu. Jinak řečeno a možná blíže k počítačové vědě: není dovoleno omezovat omezení výrazu. $\ přistát$ $\ lor$ $\ existuje$ $\ pro všechny$

Interpretace výrazů se neprovádí pomocí a , ale díky konceptům Osvědčené a Protirečivé . $Skutečný$ $Nepravdivé$

Ponořit klasickou logiku do intuitivní logiky

Kurt Gödel navrhl překlad klasické logiky do intuitivní logiky: „ non-non-translation (in) “, díky čemuž je v intuitivní logice prokazatelný jakýkoli prokazatelný vzorec v klasické logice. V tomto přesném smyslu tedy intuitivní logika neprokazuje nic menšího než klasická logika.

Ekonomičtějším způsobem než nasycení vzorců a dílčích vzorců dvojitými negacemi si Gödel všiml, že pokud vezmeme v úvahu funkci množiny vzorců v sadě vzorců definovaných: $F$

$f (\ bot) = \ bot$
$f (A) = \ neg (\ neg A)$ , pro atomový vzorec odlišný od ⊥ $NA$
${\ displaystyle f (A \ land B) = f (A) \ land f (B)}$
${\ displaystyle f (A \ lor B) = \ neg \ vlevo [\ neg f (A) \ land \ neg f (B) \ vpravo]}$
$f (A \ Rightarrow B) = f (A) \ Rightarrow f (B)$
$f (\ forall xP (x)) = \ forall xf (P (x))$
$f (\ existuje xP (x)) = \ neg (\ pro všechny x \ neg f (P (x))$ ;

kde a jsou jakékoli vzorce a je vzorec mající jako parametr; $NA$ $B$ $P$ $X$

pak máme následující větu:

$\ Gamma \ vdash _ {c} A \ Leftrightarrow f (\ Gamma) \ vdash _ {i} f (A)$ .

Kde je klasická dedukce a intuitivní dedukce. $\ vdash _ {c}$ $\ vdash _ {i}$

Klasický modální logický překlad

Logiku intuice lze převést na klasickou modální logiku S4 opatřenou modalitou . Konstrukce zní „ je prokazatelná“. Překlad je definován: $\Krabice$ $\ Kolonka A$ $NA$

{\ displaystyle T (p) = \ box p}

pro jakoukoli výrokovou proměnnou ;

p

{\ displaystyle T (\ bot _ {i}) = \ bot _ {c}}

;

{\ displaystyle T (A \ land _ {i} B) = T (A) \ land _ {c} T (B)}

;

{\ displaystyle T (A \ lor _ {i} B) = T (A) \ lor _ {c} T (B)}

;

{\ displaystyle T (A \ až _ {i} B) = \ Box (T (A) \ až _ {c} T (B))}

Vzorec je platný v intuitivní logice tehdy a jen tehdy, když je platný v klasické modální logice S4 (tj. Platí pro reflexivní a tranzitivní Kripkeho modely). $NA$ ${\ displaystyle T (A)}$

Algoritmická složitost rozhodovacích problémů v intuitivní logice

Problém rozhodování o uspokojivosti a problém rozhodování o platnosti v intuiční výrokové logice jsou PSPACE-kompletní . Kromě toho zůstávají úplné PSPACE, i když omezíme vzorce na dvě proměnné.

Reference

Tato karikatura neprokázala iracionalitu konstanty Euler-Mascheroni je připomínána v domněnce 1.0.1 (ne) Jeffrey Lagarias , Eulerova konstanta: Eulerova práce a moderní vývoj, 98 stran, 258 odkazů. (2013) [ číst online ] [PDF]
(in) Stanfordská encyklopedie filozofie , „ intuitivní logika “ od Joan Moschovakis.
(en) Brouwer-Hilbert kontroverze
Glivenko, V., 1928, „O logice M. Brouwera“, Královská akademie v Belgii, Bulletin de la classe des sciences , 14: 225–228.
Kurt Godel, Collected Works , sv. III, Oxford: Oxford University Press (1995).
Andreï Kolmogorov , „ Na principu vyloučeného středu “ (1925), Jean van Heijenoort , 1967. Zdrojová kniha v matematické logice, 1879–1931 . Harvard Univ. Tisk: 414–37.
Proměny kalkulu. Úžasná historie matematiky , Paříž, Édition Le Pommier, kol. "Testy",2007, 223 s. ( ISBN 978-2-7465-0324-3 )
Tím by se mělo rozumět, že když programátor vytvoří funkci, jejíž specifikoval typ argumentů a výsledek, je nucen tuto specifikaci respektovat, protože musí poskytnout správně napsaný objekt. Závislé typy poskytují výkonnější psaní než většina jazyků a umožňují úplnou specifikaci programu.
Joseph Vidal-Rosset, „ Intuitionnism “ , University of Nancy 2 ,2006 (o výkladu výrazů a filozofie).
Kromě negace, pod kterou lze definovat pomocí false a implikace. Jinými slovy, nemůžeme definovat, jako v klasické logice , všechny konektory z jediného binárního konektoru, jako je Shefferova lišta, nebo ze dvou konektorů, jako je negace a implikace.
Saul A. Kripke , Sémantická analýza intuitivní logiky I , Elsevier , kol. "Formální systémy a rekurzivní funkce",1 st 01. 1965( číst online ) , s. 92–130.
R. David, K. Núr, C. Raffalli, Úvod do logiky: Teorie Důkaz: Course a opravených cvičení , Dunod ,2001, str. 159 „Objednávka v průběhu času“.
Structure and Logic , Springer Universitext, 1980. ( ISBN 3-540-20879-8 ) .
Michel Lévy, „ Překlad intuitivní logiky do modelové logiky “ , na LIG ,2011.
(in) Juliette Kennedy, „ Kurt Gödel, 2.5.3 Intuitionistic Propositional Logic je interpretovatelný v S4 “ na stanford.edu ,13. února 2007
(in) Richard Statman , „ Intuicionistická výroková logika je plná polynomiálního prostoru “ , Theoretical Computer Science , sv. 9,1 st 07. 1979, str. 67–72 ( DOI 10.1016 / 0304-3975 (79) 90006-9 , číst online , přístup k 12. dubna 2016 ).
(in) Mr. Rybakov, „ Complexity of intuitionistic and Visser's basic and formal logics in finiously Many variables “ , Proceedings of Advances in Modal Logic ,2006.

Dodatky

Bibliografie

Funguje

Jean Largeault , intuice a teorie demonstrací , Paříž, J. Vrin,1992, 566 s. ( ISBN 2-7116-1059-4 , online prezentace ) Texty Bernayse , Brouwera , Gentzena , Gödela , Hilberta , Kreisela a Weyla shromáždili, přeložili a uvedli Jean Largeault.
Arend Heyting Základy matematiky, intuicionismu, teorie demonstrací , Gauthier-Villars, Nauwelaerts, 1955, 91 stran.
Jean Largeault , L'Intuitionisme , Paříž, Presses Universitaires de France, 1992.
René David, Karim Nour a Christophe Raffali, Úvod do logiky , Dunod, 2001.
Jean-Yves Girard , Mrtvý bod , Tome I, Hermann, 2007.

externí odkazy

Richard Můťa a Christian Retoré, " jen" non-non "překlad Gödel-Kolmogorov " , University Bordeaux I ,2007nebo na serveru arXiv https://arxiv.org/abs/1602.07608
Étienne Lozes, „ TD non non-translation “ , Laboratoř specifikací a ověření - ENS Cachan ,2009
Alexandre Miquel, „ Realizovatelnost a extrakce programů “ , Laboratoř důkazů, programů a systémů (PPS) v Jussieu ,2005 (o intuiční logice a interpretaci Brouwer-Heyting-Kolmogorov - interpretace BHK)
Michel Lévy Proof v propoziční intuitivní logice

Související články