Predikátová logika - jazyk a sémantika

Úvod

Aj napriek tomu, že výroková logika je logický systém, ktorý má širokú škálu aplikácií, jej vyjadrovacia sila často nestačí na opis reálnych procesov v matematike a informatike.

Predikátová logika (niekedy nazývaná aj logika prvého rádu) rozširuje jazyk výrokovej logiky tak, že umožňuje narábanie:

• s objektami,
• s reláciami (vlastnosťami).

Zároveň prináša kvantifikáciu tvrdení v danej doméne tak, že umožňuje narábanie s tvrdeniami:

• ktoré platia pre všetky objekty danej domény,
• alebo vyjadruje existenciu aspoň jedného objektu domény, pre ktorý dané tvrdenie platí.

V rámci predikátovej logiky narábame v určitej doméne (predmetnej oblasti, svete, univerze), ktorá môže byť konečná aj nekonečná, napr. množina celých čísel, všetci ľudia na zemi, rodokmeň konkrétnej rodiny a pod.

Predikátová logika nám umožní formalizovať tvrdenia typu:

Všetci ľudia sú smrteľní.
Sokrates je človek.
-------------------------
Teda Sokrates je smrteľný.

(Tento sylogizmus vyslovil Aristoteles.)

Jazyk predikátovej logiky

Keďže jazyk predikátovej logiky má väčšiu vyjadrovaciu silu ako výroková logika, je potrebné do neho zaviesť nové logické operátory aj mimologické symboly, prostredníctvom ktorých je možné opísať detailnejšie štruktúru výrokov.

Symboly jazyka predikátovej logiky

je možné rozdeliť na dve skupiny:

• Logické symboly:
  • logické spojky: $∧,∨,⇒,¬$,
  • logické spojky: $\top,⊥$,
  • kvantifikátory: $∀$ (pre všetky), $∃$ (existuje),
  • pomocné symboly: zátvorky, čiarky $(,)$. $~$
• Mimologické symboly:
  • predikátové symboly: $P,Q,R,...$,
  • funkčné symboly: $f,g,h,...$,
  • konštanty: $a,b,c,...$,
  • premenné: $x,y,z,...$. $~$

• Každý predikátový a funkčný symbol musí mať definovanú aritu (početnosť argumentov, ktoré očakáva).
• Predikát je atomická formula označuje vlastnosť alebo reláciu nad termami danej domény:
  • $P(x)$ objekt $x$ má vlastnosť $P$ (unárny predikát vyjadruje vlastnosť),
  • $R(x,y)$ objekt $x$ je v relácií s objektom $y$ (binárny resp. viacárny predikát vyjadruje reláciu).
• Konštanta môže byť chápaná ako funkcia s aritou 0 (nulárna funkcia).
• Termom rozumieme objekt domény, resp. funkcia na ňom, ktorá vráti objekt domény.
• Rozlišujeme medzi formulou, ktorá môže byť pravda/nepravda a termom ktorý označuje objekty danej domény.
• Term nie je formula predikátovej logiky, ale môže byť jej súčasťou.

Termy jazyka

Induktívne je možné definovať termy jazyka:

• konštanta je term,
• premenná je term,
• každý výraz v tvare $f(t_1,...,t_n)$ je term, ak $f$ je $n$-árna funkcia a výrazy $t_1,...,t_n$ sú termy.

Syntax termov v BNF: $$t::= x ~|~ c ~|~ f(t,...,t),$$ kde:

• $x$ je ľubovoľná premenná,
• $c$ je konštanta (nie je logická $\bot, \top$),
• $f(t,...,t)$ je funkcia.

Term je uzavretý ak sa v ňom nevyskytujú premenné.

Syntax jazyka predikátovej logiky

Syntax jazyka predikátovej logiky je možné vyjadriť prostredníctvom BNF nasledovne: $$φ::= ⊥ ~|~ ⊤ ~|~ P(t,...,t) ~|~ ¬φ ~|~ φ ∧ φ ~|~ φ ∨ φ ~|~ φ ⇒ φ ~|~ (∀x)φ ~|~ (∃x)φ,$$ kde:

• $⊤,⊥$ sú logické konštanty,
• $P(t,...,t)$ je predikátový symbol,
• $¬φ, φ ∧ φ, φ ∨ φ, φ ⇒ φ$ sú logické spojky: negácia, konjunkcia, disjunkcia a implikácia. Chápané rovnako ako vo výrokovej logike.
• $(∀x)φ$ je formula, kde $x$ je premenná, $∀$ je všeobecný kvantifikátor a $φ$ je formula predikátovej logiky.
• $(∃x)φ$ je formula, kde $x$ je premenná, $∃$ je existenčný kvantifikátor a $φ$ je formula predikátovej logiky.
• Množinu všetkých formúl predikátovej logiky, ktorú opisuje vyššie uvedená BNF nazveme $FOL$.

Asociativita je rovnaká ako v prípade výrokovej logike, avšak kvantifikátory viažu silnejšie ako ostatné logické spojky, napríklad: $$ \begin{array}{rcl} (∀x)φ ∧ ψ & ≡ & ((∀x)φ) ∧ ψ \\ (∃x)φ ∧ ψ & ≡ & ((∃x)φ) ∧ ψ \\ \end{array} $$ Platia nasledujúce konvencia priority logických spojok:

Voľné a viazané premenné

• Premenná je vo formule voľná ak nie je v rozsahu viditeľnosti kvantifikátora s danou premennou.
• Premenná je vo formule viazaná ak je v rozsahu viditeľnosti kvantifikátora s danou premennou.

Formula je uzavretá

(niekedy nazývaná aj sentencia) ak neobsahuje voľné premenné.

Formula je otvorená

ak obsahuje aspoň jednu voľnú premennú.

Formula je základná

(z ang. ground formula) ak neobsahuje premenné.

Zákony predikátovej logiky

V predikátovej logike platia všetky zákony výrokovej logiky a rozšírené o pravidla pre kvantifikátory.

Nech $φ,ψ$ sú formuly predikátovej logiky a nech premenná $x$ nemá voľný výskyt vo formule $ψ$. Potom platia nasledujúce zákony: $$ \begin{array}{rcl} ¬(∀x)φ & ≡ & (∃x)¬φ\\ ¬(∃x)φ & ≡ & (∀x)¬φ\\ ψ∨(∀x)φ & ≡ & (∀x)(ψ ∨ φ)\\ ψ∨(∃x)φ & ≡ & (∃x)(ψ ∨ φ)\\ ψ∧(∀x)φ & ≡ & (∀x)(ψ ∧ φ)\\ ψ∧(∃x)φ & ≡ & (∃x)(ψ ∧ φ)\\ ψ⇒(∀x)φ & ≡ & (∀x)(ψ ⇒ φ)\\ ψ⇒(∃x)φ & ≡ & (∃x)(ψ ⇒ φ)\\ (∀x)φ ∧ (∀x)ψ & ≡ & (∀x)(φ ∧ ψ)\\ (∃x)φ ∨ (∃x)ψ & ≡ & (∃x)(φ ∨ ψ) \end{array} $$

Rozsah viditeľnosti kvantifikátorov

Nech $Q$ označuje ľubovoľný kvantifikátor $(∀,\exists)$ a nech $(...,x,...)$ je ľubovoľná formula. Potom rozsah viditeľnosti kvantifikátora $Q$ vo formule $(Qx)(...,x,...)$ je tá časť formuly, ktorá je vymedzená najbližšími zátvorkami nachádzajúcimi sa hneď za kvantifikátorom.

Vnorené kvantifikátory

Doteraz sme pracovali s atomickými formulami, ktoré boli kvantifikované najviac jedným kvantifikátorom. Avšak v praxi je často nutné využiť kvantifikáciu viacerými kvantifikátormi, ktoré budú vnorené, napríklad: $$(∀x)(∃y)P(x,y).$$

Poradie kvantifikátorov

Pri vnorených kvantifikátoroch môže ich poradie zmeniť význam formuly. Začnime najjednoduchším prípadom. Majme dvojicu kvantifikátorov (kvantifikátor s jedným vnoreným kvantifikátorom), čo nám v kombinácii s dvoma premennými vytvára osem možnosti kvantifikácie formuly $φ$:

$$ \begin{array}{ll} ~1. & (∀x)(∀y)φ \\ ~2. & (∀y)(∀x)φ \\ ~3. & (∃x)(∀y)φ \\ ~4. & (∃y)(∀x)φ \\ ~5. & (∀x)(∃y)φ \\ ~6. & (∀y)(∃x)φ \\ ~7. & (∃x)(∃y)φ \\ ~8. & (∃y)(∃x)φ \end{array} $$

Pracujme s doménou celých čísel $\mathbb{Z}$.

Nech $P(x,y)$ znamená výrok "$x+y=y+x$". Aké pravdivostné hodnoty môžu nadobudnúť formuly: $$ \begin{array}{l} (∀x)(∀y)P(x,y) \\ (∀y)(∀x)P(x,y). \end{array} $$

• Formulu $(∀x)(∀y)P(x,y)$ je možné prečítať nasledovne:
  • "Pre všetky celé čísla $x$ a pre všetky celé čísla $y$ platí, že $x+y=y+x$". Formula je pravdivá.
• Formulu $(∀y)(∀x)P(x,y)$ je možné prečítať nasledovne:
  • "Pre všetky celé čísla $y$ a pre všetky celé čísla $x$ platí, že $x+y=y+x$". Formula je pravdivá.

Prvá aj druhá formula má v tomto prípade rovnaký význam, sú ekvivalentné. To znamená, ak formula obsahuje iba vnorené všeobecné kvantifikátory, na ich poradí nezáleží.

Nech $Q(x,y)$ znamená výrok "$x+y=0$". Aké pravdivostné hodnoty môžu nadobudnúť formuly: $$ \begin{array}{l} (∃x)(∃y)Q(x,y) \\ (∃y)(∃x)Q(x,y). \end{array} $$

• Formulu $(∃x)(∃y)Q(x,y)$ je možné prečítať nasledovne:
  • "Existuje také celé číslo $x$, pre ktoré existuje tak celé číslo $y$, že platí $x+y=0$". Zjednodušene povedané, existuje dvojica čísel $x,y$ taká, že ich súčet je rovný $0$. Formula je pravdivá.
• Formulu $(∃y)(∃x)Q(x,y)$ je možné prečítať nasledovne:
  • "Existuje také celé číslo $y$, pre ktoré existuje tak celé číslo $x$, že platí $x+y=0$". Zjednodušene povedané, existuje dvojica čísel $y,x$ taká, že ich súčet je rovný $0$. Formula je pravdivá.

Prvá aj druhá formula má v aj tomto prípade rovnaký význam, sú ekvivalentné. To znamená, ak formula obsahuje iba vnorené existenčné kvantifikátory, na ich poradí nezáleží.

Nech $Q(x,y)$ znamená výrok "$x+y=0$". Aké pravdivostné hodnoty môžu nadobudnúť formuly: $$ \begin{array}{l} (∀x)(∃y)Q(x,y) \\ (∃x)(∀y)Q(x,y). \end{array} $$

• Formulu $(∀x)(∃y)Q(x,y)$ je možné prečítať nasledovne:
  • "Pre každé celé číslo $x$, existuje tak celé číslo $y$, že platí $x+y=0$". Zjednodušene povedané, každému celému číslu $x$ môžeme nájsť také celé číslo $y$, že ich súčet je rovný $0$. Formula je pravdivá.
• Formulu $(∃x)(∀y)Q(x,y)$ je možné prečítať nasledovne:
  • "Existuje také celé číslo $x$, ktoré ak prirátame ku každému celému číslu $y$, platí $x+y=0$". Zjednodušene povedané, táto formula tvrdí, že existuje aspoň jedno také celé číslo $y$, ktoré ak prirátame hocijaké celé číslo $y$, že ich súčet bude rovný $0$. Formula je nepravdivá.

To znamená, že formuly $(∀x)(∃y)Q(x,y)$ a $(∃x)(∀y)Q(x,y)$ nie sú sémanticky ekvivalentné. V prípade, že formula obsahuje rozdielne vnorené kvantifikátory na poradí kvantifikátorov záleží.

Tabuľka nižšie sumarizuje zmysel rôznych kombinácií vnorených kvantifikátorov.

Analogicky tieto vlastnosti platia aj pre viac ako dva vnorené kvantifikátory.

Majme predikát $R(x,y,z)$, ktorý označuje vlastnosť $x+y=z$. Potom formula: $$(∀x)(∀y)(∃z)R(x,y,z),$$ znamená "pre všetky celé čísla $x$ a pre všetky celé čísla $y$, existuje také celé číslo $z$, že platí $x+y=z$". Formula je pravdivá.

Avšak formula: $$(∃z)(∀x)(∀y)R(x,y,z),$$ je nepravdivá. Znamená "existuje také celé číslo $z$, že pre všetky celé čísla $x$ a pre všetky celé čísla $y$, že platí $x+y=z$". Zjednodušene povedané "existuje také $z$, že súčet akejkoľvek dvojice čísel $x,y$ je rovný číslu $z$", čo nie je pravda.

De Morganove zákony pri vnorených kvantifikátoroch

Formula ktorá obsahuje vnorené kvantifikátory môže byť prepísaná na ekvivalentný tvar prostredníctvom De Morganových zákonov definovaných vyššie, postupným aplikovaním daných zákonov ako v prípade formuly s jedným kvantifikátorom.

Substitúcia

Substitúcia v predikátovej logike je dôležitý koncept, ktorý umožňuje dosadzovať termy za premenné. Je definovaná zvlášť pre termy a pre formuly.

Substitúcia v termoch

Zápis $$t[s/x]$$ znamená, že v terme $t$ nahradíme všetky voľné výskyty premennej $x$ termom $s$.

Substitúcia na termoch je definovaná induktívne:

$$ \begin{array}{lcl} y[s/x] & = & \begin{cases} \quad y \quad \text{ak} \quad y ≠ x \\ \quad s \quad \text{ak} \quad y = x \end{cases}\\ c[s/x] & = & c\\ f(t_1,...,t_n)[s/x] & = & f(t_1[s/x],...,t_n[s/x]). \end{array} $$

Substitúcia v formulách

Zápis $$φ[s/x]$$ znamená, že vo formule $φ$ nahradíme všetky voľné výskyty premennej $x$ termom $s$.

Substitúcia vo formulách je definovaná induktívne:

$$ \begin{array}{lcl} ⊥[s/x] & = & ⊥\\ ⊤[s/x] & = & ⊤\\ P(t_1,...,t_n)[s/x] & = & P(t_1[s/x],...,t_n[s/x])\\ ~ & ~ & ~\\ (φ∧ψ)[s/x] & = & φ[s/x]∧ψ[s/x]\\ (φ∨ψ)[s/x] & = & φ[s/x]∨ψ[s/x]\\ (φ⇒ψ)[s/x] & = & φ[s/x]⇒ψ[s/x]s\\ ~ & ~ & ~\\ (∀y)φ[s/x] & = & \begin{cases} \quad (∀y)φ[s/x] \quad \text{ak} \quad y ≠ x \\ \quad (∀y)φ \quad \text{ak} \quad y = x \end{cases}\\ (∃y)φ[s/x] & = & \begin{cases} \quad (∃y)φ[s/x] \quad \text{ak} \quad y ≠ x \\ \quad (∃y)φ \quad \text{ak} \quad y = x \end{cases} \end{array} $$

Sémantika predikátovej logiky

Pojem doména bol v predchádzajúcej kapitole spomenutý niekoľko krát. To z dôvodu, že sémantiku formúl predikátovej logiky definujeme pre určitú doménu (svet, univerzum, predmetnú oblasť) v ktorej pracujeme.

Sémantika predikátovej logiky definovaná ako model

Sémantika predikátovej logiky definovaná je definovaná ako model, ktorý je usporiadaná dvojica: $$M=(D,I),$$ kde:

• $D$ je doména (predmetná oblasť, svet, univerzum) napríklad: celé čísla $\mathbb{Z}$, množina všetkých ľudí na zemi $\{$ľudia$\}$, ročné obdobia $\{$jar, leto, jeseň, zima$\}$ a pod.
• $I$ je interpretácia, ktorá:
  • každej konštante $c$ jednoznačne priradí prvok domény $d∈D$:$$c=d.$$
  • každému $n$-árnemu funkčnému symbolu $f$ jednoznačne priradí funkciu: $$f:D×...×D→D,$$
  • každému $n$-árnemu predikátovému symbolu $P$ jednoznačne priradí predikát: $$P:D×...×D→\{1,0\}.$$

Poznámka: Každý prvok domény budeme považovať za konštantu.

Ohodnotenie $e$ premenných je funkcia, ktorá každej premennej jednoznačné priradí prvok domény v modely $M$: $$e(x)∈D.$$ Je špecifikovaná nasledovne: $$e:Vars → D,$$ definovaná na termoch: $$ \begin{array}{rcl} c^e & = & c,\\ x^e & = & e(x),\\ f(t_1,..., t_n)^e & = & f(t_1^e,..., t_n^e).\\ \end{array} $$

Relácia platnosti formuly $φ$ v modeli $M$ je definovaná: $$M\models φ.$$

Formula $φ$ predikátovej logiky je:

• Tautológia ak $$\models φ.$$
• Platná v modeli $M$ ak $$M\models φ.$$
• Splniteľná v modeli $M$ ak existuje také ohodnotenie $e$, že $$M^e\models φ.$$
• Nesplniteľná v modeli $M$ ak neexistuje také ohodnotenie $e$ také, že $M^e\models φ$: $$M\nvDash φ.$$
• Kontradikcia ak $$\nvDash φ.$$

Sémantika formúl predikátovej logiky

Na vyjadrenie významu formúl v modeli $M$, pri ohodnotení $e$ použijeme sémantické zátvorky: $$⟦~~⟧,$$ ktoré môžeme považovať za sémantická funkciu: $$⟦~~⟧:\{\text{symboly jazyka}\}→\{1,0\}.$$

Význam formúl v modeli $M$ pri ohodnotení $e$ definujeme induktívne:

$$ \begin{array}{rcl} ⟦\bot⟧ & = & 0 \\ ⟦\top⟧ & = & 1 \\ ⟦P(t_1,...,t_n)⟧ & = & P(t_1^{e},...,t_n^{e}) \\ ⟦φ∧ψ⟧ & = & \begin{cases} \quad 1 \quad ak \quad ⟦φ⟧=1 \quad a \quad ⟦ψ⟧=1 \\ \quad 0 \quad inak \end{cases} \\ ⟦φ∨ψ⟧ & = & \begin{cases} \quad 1 \quad ak \quad ⟦φ⟧=1 \quad alebo \quad ⟦ψ⟧=1 \\ \quad 0 \quad inak \end{cases} \\ ⟦φ⇒ψ⟧ & = & \begin{cases} \quad 1 \quad ak \quad ⟦φ⟧=0 \quad alebo \quad ⟦ψ⟧=1 \\ \quad 0 \quad inak \end{cases} \\ ⟦¬φ⟧ & = & \begin{cases} \quad 1 \quad ak \quad ⟦φ⟧=0 \\ \quad 0 \quad inak \end{cases} \\ ⟦(∀x)φ⟧ & = & \begin{cases} \quad 1 \quad ak \quad ∀a ∈ D : ⟦φ[a/x]⟧=1 \\ \quad 0 \quad inak \end{cases} \\ ⟦(∃x)φ⟧ & = & \begin{cases} \quad 1 \quad ak \quad ∃a ∈ D : ⟦φ[a/x]⟧=1 \\ \quad 0 \quad inak \end{cases} \end{array} $$

• V prípade predikátového symbolu $⟦P(t_1,...,t_n)⟧$ výsledkom je predikát $P$, pričom na všetky jeho argumenty (termy) aplikujeme funkciu ohodnotenia $e$.
• Pri kvantifikátoroch sa za viazanú premennú $x$ substituujú jednotlivé prvky domény.
  • Formula $(∀x)φ$ je pravdivá vtedy, ak po substitúcii $x$ vo $φ$ je formula $φ$ je pravdivá pre všetky prvky domény.
  • Formula $(∃x)φ$ je pravdivá vtedy, ak po substitúcii $x$ vo $φ$ je formula $φ$ je pravdivá pre aspoň jeden prvok domény.