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

[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

  1. velkých písmen P, Q, R,… značících predikátové proměnné.
  2. malých písmen a, b, c,… značících konstanty (vyjadřující se o individuích).
  3. malých písmen x, y, z,… značících proměnné (vyjadřující se o individuích).
  4. malých písmen f, g, h,… značících funkční proměnné.
  5. symbolů označujících logické operátory: ¬ (negace), \wedge (konjunkce), \vee (disjunkce), → (implikace), ↔ (ekvivalence).
  6. symbolů označujících kvantifikátory: \forall (univerzální kvantifikátor), \exists (existenční kvantifikátor).
  7. 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:

  1. 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.
  2. Je-li φ dobře utvořená formule, je i ¬ φ dobře utvořená formule.
  3. Jsou-li φ a ψ dobře utvořené formule, jsou i (\phi \wedge \psi), (\phi \vee \psi), (φ → ψ), (φ ↔ ψ) dobře utvořené formule.
  4. 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.)
  5. 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)

[editovat] Odvozovací pravidla

Odvozovací pravidlo může být formulováno takto:

\mathit{Pokud} \vdash Z(x), \mathit{pak} \vdash \forall x Z(x)

kde Z(x) značí pravdivou formuli predikátové logiky a ∀xZ(x) je jeho rozšířením vzhelem k proměnné X.