Hilbertovský kalkulus

Hilbertovský kalkulus (také hilbertovský klasický kalkulus) je jeden z logických kalkulů, kterými se zabývá logika. Jde o kalkulus jednoznačně nejpoužívanější; je v něm formalizována celá matematika. Nazván byl po německém matematikovi Davidu Hilbertovi, který podobný kalkulus poprvé zavedl. Jiným typem logického kalkulu je například gentzenovský kalkulus.

Definice

Hilbertovský kalkulus je možné rozlišit na verze pro výrokovou a predikátovou logiku.

Výrokové axiomy

Výrokový hilbertovský kalkulus je tvořen následujícími výrokovými axiomy a odvozovacím pravidlem modus ponens (viz dále). Tato soustava axiomů se také souhrnně nazývá axiomy výrokové logiky; tedy za axiomy výrokové logiky jsou (není-li řečeno jinak) považovány axiomy výrokového hilbertovského kalkulu. Výrokové axiomy jsou následující:

• $\mathrm{\phi <!--\; \phi \; -->}⟹<!--\; ⟹\; -->(\mathrm{\psi <!--\; \psi \; -->}⟹<!--\; ⟹\; -->\mathrm{\phi <!--\; \phi \; -->})$
• $(\mathrm{\phi <!--\; \phi \; -->}⟹<!--\; ⟹\; -->(\mathrm{\psi <!--\; \psi \; -->}⟹<!--\; ⟹\; -->\mathrm{\chi <!--\; \chi \; -->}\left)\right)⟹<!--\; ⟹\; -->\left(\right(\mathrm{\phi <!--\; \phi \; -->}⟹<!--\; ⟹\; -->\mathrm{\psi <!--\; \psi \; -->})⟹<!--\; ⟹\; -->(\mathrm{\phi <!--\; \phi \; -->}⟹<!--\; ⟹\; -->\mathrm{\chi <!--\; \chi \; -->}\left)\right)$
• $(\mathrm{\neg <!--\; \neg \; -->}\mathrm{\phi <!--\; \phi \; -->}⟹<!--\; ⟹\; -->\mathrm{\neg <!--\; \neg \; -->}\mathrm{\psi <!--\; \psi \; -->})⟹<!--\; ⟹\; -->(\mathrm{\psi <!--\; \psi \; -->}⟹<!--\; ⟹\; -->\mathrm{\phi <!--\; \phi \; -->})$

Kde $\mathrm{\phi <!--\; \phi \; -->}$, $\mathrm{\psi <!--\; \psi \; -->}$ a $\mathrm{\chi <!--\; \chi \; -->}$ jsou libovolné formule jazyka L.

Axiomy pro predikátovou logiku

Predikátový hilbertovský kalkulus obsahuje všechny výrokové axiomy, dvě odvozovací pravidla – modus ponens a generalizace (viz dále) a také následující predikátové axiomy. Systém těchto axiomů se podobně jako u výrokové verze nazývá souhrnně axiomy predikátové logiky (prvního řádu). Predikátové axiomy hilbertovského kalkulu jsou:

• Axiom substituce: $\left(\mathrm{\forall <!--\; \forall \; -->}x\right)\left(\mathrm{\phi <!--\; \phi \; -->}\right(x,y_1,...,y_n\left)\right)⟹<!--\; ⟹\; -->\mathrm{\phi <!--\; \phi \; -->}(x/t,y_1,...,y_n)$, je-li term t substituovatelný za x do $\mathrm{\phi <!--\; \phi \; -->}$.
• Axiom $\mathrm{\forall <!--\; \forall \; -->}$-distribuce: $\left(\right(\mathrm{\forall <!--\; \forall \; -->}x\left)\right(\mathrm{\phi <!--\; \phi \; -->}⟹<!--\; ⟹\; -->\mathrm{\psi <!--\; \psi \; -->}\left)\right)⟹<!--\; ⟹\; -->(\mathrm{\phi <!--\; \phi \; -->}⟹<!--\; ⟹\; -->(\mathrm{\forall <!--\; \forall \; -->}x\left)\mathrm{\psi <!--\; \psi \; -->}\right)$, není-li proměnná x volná ve $\mathrm{\phi <!--\; \phi \; -->}$.

V případě predikátové logiky prvního řádu s rovností se k axiomům predikátové logiky prvního řádu přidávají ještě axiomy pro rovnost.

Axiomy rovnosti

• $\left(\mathrm{\forall <!--\; \forall \; -->}x\right)(x=x)$
• $(x_1=y_1\wedge <!--\; \wedge \; -->...\wedge <!--\; \wedge \; -->x_n=y_n)⟹<!--\; ⟹\; -->\left(R\right(x_1,...,x_n)⟹<!--\; ⟹\; -->R(y_1,...,y_n\left)\right)$, kde R je libovolný relační symbol jazyka L.
• $(x_1=y_1\wedge <!--\; \wedge \; -->...\wedge <!--\; \wedge \; -->x_n=y_n)⟹<!--\; ⟹\; -->\left(F\right(x_1,...,x_n)=F(y_1,...,y_n\left)\right)$, kde F je libovolný funkční symbol jazyka L.

Odvozovací pravidla

Velkou roli v axiomatizaci logiky hrají takzvaná odvozovací pravidla, která nejsou žádným druhem axiomů, ale pro svůj blízký vztah k nim se mezi ně někdy zařazují. Odvozovací pravidla jsou dvě, jedno pro výrokovou i predikátovou logiku (Modus Ponens), druhé jen pro predikátovou logiku.

• Pravidlo modus ponens: Z $\mathrm{\phi <!--\; \phi \; -->},\mathrm{\phi <!--\; \phi \; -->}⟹<!--\; ⟹\; -->\mathrm{\psi <!--\; \psi \; -->}$ odvoď $\mathrm{\psi <!--\; \psi \; -->}$;
• Pravidlo generalizace: Z $\mathrm{\phi <!--\; \phi \; -->}$ odvoď $\left(\mathrm{\forall <!--\; \forall \; -->}x\right)\mathrm{\phi <!--\; \phi \; -->}$.

Důkaz v hilbertovském kalkulu

Za důkaz nějakého tvrzení $\mathrm{\phi <!--\; \phi \; -->}$ v jazyce L v teorii T ve výrokové resp. predikátové logice je pak považována libovolná posloupnost formulí jazyka L, jejímž je $\mathrm{\phi <!--\; \phi \; -->}$ členem a splňující, že pro každý její člen C platí alespoň jedna z následujících podmínek:

• C je logický axiom (případně axiom rovnosti)
• C je vlastní axiom teorie T
• C je odvozen z předchozích členů resp. předchozího členu posloupnosti podle pravidla Modus Ponens resp. pravidla generalizace.

Odkazy

Související články

• Gentzenovský kalkulus

Literatura

• ŠVEJDAR, Vítězslav. Logika, neúplnost, složitost a nutnost. Praha: Academia, 2002. ISBN 80-200-1005-X.