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…“ (
) nebo „pro každé x platí…“ (
), 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 |
[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),
(konjunkce),
(disjunkce), → (implikace), ↔ (ekvivalence). - symbolů označujících kvantifikátory:
(univerzální kvantifikátor),
(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)
(Q → P). Ve skutečnosti dokážeme všechny logické operátory vyjádřit pomocí operátoru NAND a kvantifikátor
pomocí ¬
.
[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 Pa1,...,an je dobře utvořená formule. If 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
,
, (φ → ψ), (φ ↔ ψ) dobře utvořené formule. - Je-li φ dobře utvořená formule obsahující volný výskyt proměnné x, pak
a
jsou dobře utvořené formule (proměnná x se pak nazývá vázaná v
a
.) - 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:

- PRED-2:

- PRED-3:

- PRED-4:

[editovat] Odvozovací pravidla
Odvozovací pravidlo může být formulováno takto:
kde Z(x) značí pravdivou formuli predikátové logiky a ∀xZ(x) je jeho rozšířením vzhelem k proměnné X.


