Predikátová logika prvního řádu

Z Wikipedie, otevřené encyklopedie

Predikátová logika prvního řádu je predikátová logika, která dovoluje používání kvantifikovaných tvrzení ve tvaru „existuje x tak, že…“ ( $\exists x$ ) nebo „pro každé x platí…“ ( $\forall x$ ), pokud je x individuem a ne predikátem. Pokud bychom dovolili kvantifikování predikátů, nejedná se o predikátovou logiku prvního, ale vyššího řádu.

I přes tato omezení je ale tato logika schopna formalizovat mnohá tvrzení teorie množin. Omezení začnou být překážkou až ve chvíli, kdy začneme studovat topologii.

Obsah

1 Definice
- 1.1 Abeceda
- 1.2 Stavba formulí
2 Axiomy
- 2.1 Odvozovací pravidla

[editovat] Definice

Výroková logika se skládá ze

syntaktických pravidel (určují, kdy je formule správně utvořená)
odvozovacích pravidel
(nejvýše spočetné) množiny axiomů a axiomatických schémat.

Predikátová logika je jejím rozšířením.

[editovat] Abeceda

Abeceda se skládá z

velkých písmen P, Q, R,… značících predikátové proměnné.
malých písmen a, b, c,… značících konstanty (vyjadřující se o individuích).
malých písmen x, y, z,… značících proměnné (vyjadřující se o individuích).
malých písmen f, g, h,… značících funkční proměnné.
symbolů označujících logické operátory: ¬ (negace), $\wedge$ (konjunkce), $\vee$ (disjunkce), → (implikace), ↔ (ekvivalence).
symbolů označujících kvantifikátory: $\forall$ (univerzální kvantifikátor), $\exists$ (existenční kvantifikátor).
levé a pravé závorky .

Některé z těchto symbolů nejsou pro vyjádření nutné, například (P ↔ Q) je zkrácením (P → Q) $\wedge$ (Q → P). Ve skutečnosti dokážeme všechny logické operátory vyjádřit pomocí operátoru NAND a kvantifikátor $\forall$ pomocí ¬ $\exists$ .

[editovat] Stavba formulí

Množina dobře utvořených formulí je definována rekursivně takto:

Je-li P n-ární (n ≥ 0) predikát, pak $P a 1,..., a n$ je dobře utvořená formule. Pokud n ≤ 1, P je atomická formule.
Je-li φ dobře utvořená formule, je i ¬ φ dobře utvořená formule.
Jsou-li φ a ψ dobře utvořené formule, jsou i $(\phi \wedge \psi)$ , $(\phi \vee \psi)$ , (φ → ψ), (φ ↔ ψ) dobře utvořené formule.
Je-li φ dobře utvořená formule obsahující volný výskyt proměnné x, pak $\forall x \, \varphi$ a $\exists x \, \varphi$ jsou dobře utvořené formule (proměnná x se pak nazývá vázaná v $\forall x \, \varphi$ a $\exists x \, \varphi$ ).
Nic jiného není dobře utvořená formule.

[editovat] Axiomy

Pokud vhodně nastavíme axiomy predikátové logiky, stačí nám přidat následující 4 axiomy:

PRED-1: $\forall x Z(x) \rightarrow Z(y)$
PRED-2: $Z(y) \rightarrow \exists x Z(x)$
PRED-3: $\forall x (W \rightarrow Z(x)) \rightarrow (W \rightarrow \forall x Z(x))$
PRED-4: $\forall x (Z(x) \rightarrow W) \rightarrow (\exists x Z(x) \rightarrow W)$