Predikátorvá logika

Predikátová logika

Úvod (pre

čo nám nestačí výroková logika)

Výroková logika nie je dosť silná na prezentovanie rôznych typov tvrdení alebo na vyjadrenie
určitých vzťahov, ktoré sa používajú v informatika a v matematike. Napríklad tvrdenie x>1, kde x
je premenná, nie je výrok, lebo pokiaľ nepoznáme hodnotu premennej x, nevieme povedať, či je to
pravda alebo nie. Výroková logika nevie s takýmito vetami pracovať, pričom vety takéhoto typu sa
vyskytujú v matematike dosť často. Takisto na nasledujúci úsudok nám už výroková logika nestačí.

P: Každý človek je smrteľný.

Q: Sokrates je človek.

R: Sokrates je smrteľný.

Úsudok je intuitívne úplne správny, ale tvrdenie R nie je korektným dôsledkom tvrdení P a Q vo
výrokovej logike. Výroková logika totiž nemá prostriedky na vyjadrenie tvrdení P a Q.

Na vyjadrenie týchto a ďalších problémov potrebujeme teda silnejšiu logiku. Zavádzame
predikátovú logiku (logika 1. rádu), ktorá bude mať v porovnaní s výrokovou ďalšie dva pojmy:
predikát a kvantifikátory.

Predikát
Predikát je slovná predloha (vzor), ktorá popisuje vlastnosť objektov alebo vzťah medzi objektami.

Pr. 1

Obloha je modrá. Moje pero je modré. Tvoje auto je modré. Sú podľa vzoru niečo je modré. Táto
fráza je modré je predikát - popisuje vlastnosť byť modrý. Predikáty zvykneme označovať veľkými
písmenami (napr. P, Q). Pomenujme náš predikát je modré písmenom M. Potom vety, ktoré
vyjadrujú niečo je modré môžeme zapísať ako M(x), kde x zastupuje ľubovoľný objekt.

Pr. 2

Mama to natrela otcovi. Otec to natrel babke. Babka to natrela dedkovi. .... x to natrel y. Vzor ... to
natrel ... je predikát a vyjadruje vzťah medzi dvoma objektami. Označíme ho napríklad N(x,y).

Pr. 3

x je prvočíslo, x>1, x

∨y, a/b

Pri predikáte je dôležité stanoviť univerzum – množinu objektov, ktoré nás zaujímajú. Univerzom
môže byť R, N, Z, množina všetkých študentov v tejto triede, množina všetkých áut na parkovisku.

Predikát - funkcia, ktorej hodnoty, sú logické.

Kvantifikátory
Predikát sám o sebe ešte nie je výrok. Napríklad tvrdenie x>1 nie je výrok. Aby sme z predikátu
spravili výrok, môžeme buď nahradiť premennú x konkrétnou hodnotou (5>1) alebo kvantifikovať
premennú použitím kvantifikátora (a to sa robí v predikátovej logike).

Všeobecný kvantifikátor
∀x P(x) – pre každý objekt x z univerza platí P(x) (pre každé x, pre všetky x). Keď špecifikujeme
univerzum, bude to výrok.

Pr.
∀x (x>1)
a) nech univerzum je Z, potom

∀x (x>1) je nepravdivý výrok

b) nech univerzum je {5,6,7,…}, potom

∀x (x>1) je pravdivý výrok

Pr.

Vetu Všetky autá majú kolesá. môžeme zapísať do výrokovej formy

∀x P(x), kde univerzum je

množina áut a P(x) je predikát vyjadrujúci x má kolesá.

Existenčný kvantifikátor
∃x P(x) – pre nejaký objekt z univerza platí P(x). Keď špecifikujeme univerzum, bude to výrok.
Pr.
∃x (x>1)
a) nech univerzum je Z, potom

∃x (x>1) je pravdivý výrok

b) nech univerzum sú záporné čísla, potom

∃x (x>1) je nepravdivý výrok

Pr.

Vetu Niekto ťa má rád. môžeme zapísať do výrokovej formy

∃x P(x), kde univerzum je množina

ľudí a P(x) je predikát vyjadrujúci x ťa má rád.
Kvantifikátory na konečných množinách

Ak univerzum je konečná množina {a1,a2, …, an}, tak
∀x P(x) = P(a

1)

∧ P(a

2)

∧ …∧ P(a

n)

∃x P(x) = P(a

1)

∨ P(a

2)

∨ … ∨ P(a

n)

Pr.

Univerzum D={2,3,4,5,6}
∀x (x>4) = (2>4) ∧ (3>4) ∧ (4>4) ∧ (5>4) ∧ (6>4) = 0

0

0

0

1

1

∃x (x>4) = (2>4) ∨ (3>4) ∨ (4>4) ∨ (5>4) ∨ (6>4) = 1
Pr.

Univerzum

∅, x∈∅ je 0

∀x (x>4) t.z. ∀x (x∈∅ ⇒ x>4) = 1
∃x (x>4) t.z. ∃x (x∈∅ ∧ x>4) = 0

Formula predikátovej logiky (logický výraz)
Df. Formula predikátovej logiky (logický výraz)
1. Každý predikát s nula alebo viac premennými je formula.
2. Ak

α a β sú formuly a x je premenná, potom formulami sú aj:

a)

α ∧ β, α ∨ β, α ⇒ β, α ⇔ β

b)

∀x (α), ∃x (α)

Pr.
∀x P(x) ∨ ∀x Q(x)
∀x (P(x) ∨ ∃x Q(x))
Viazané a voľné premenné

Premenná vo formule je viazaná, ak je kvantifikovaná alebo je jej priradená konkrétna hodnota.
Premenná, ktorá nie je viazaná, je voľná. Oblasť platnosti kvantifikátora – buď je daná zátvorkami,
alebo platí len pri najbližšom predikáte.

Pr.

• ∃x P(x,y) – x je viazaná, y je voľná

• ∀x [∃y P(x, y) ∨ Q(x, y) ] – x a y sú viazané v P(x,y), y je voľná v Q(x,y), lebo platnosť ∃y sa

viaže len na P(x, y). Oblasť platnosti

∀x je [∃y P(x, y) ∨ Q(x, y) ].

Interpretácia formuly

Formula vo všeobecnosti nie je výrok. Uvažujme napríklad o formule

∀x P(x). Nech P(x) znamená x

je nezáporné celé číslo. Formula je pravdivá, ak univerzum je napríklad {1,3,5}, {2,4,6} alebo N,
nepravdivá ak univerzum je napríklad {-1,3,6} alebo Z. Pravdivostná hodnota formuly teda závisí
od univerza a špecifikácie predikátov.

Interpretácia formuly znamená:
1. špecifikácia univerza (neprázdnej oblasti D)
2. špecifikácia predikátov (priradenie predikátu každému symbolu predikátu)
3. priradenie hodnôt všetkým voľným premenným

Pr.

P(x,y)

⇒ ∃z (P(x,z) ∧ P(z,y))

1. D = R
2. P(x,y)

≡ x<y

3. x

∈R, y∈R

x<y

⇒ ∃z (x<z ∧ z<y)

5<8

⇒ ∃z (5<z ∧ z<8) … 1

1. D = N
2. P(x,y)

≡ x<y

3. x

∈N, y∈N

x<y

⇒ ∃z (x<z ∧ z<y)

5<6

⇒ ∃z (5<z ∧ z<6) … 0

1. D ={a,b,c}
2. P(x,y) je dané tabuľkou

x

y

P(x,y)

⇒ ∃z (P(x,z) ∧ P(z,y))

dôvod

a

a

1

1

1

z=b; a

→b→a

a

b

1

1

1

z=a; a

→a→b

a

c

0

1

b

a

1

1

1

z=a; b

→a→a

b

b

0

1

b

c

1

1

1

z=c; b

→c→c

c

a

0

1

c

b

1

1

1

z=c; c

→c→b

c

c

1

1

1

z=b; c

→b→c

Formula sa nazýva všeobecne pravdivou, ak je pravdivá pre každú interpretáciu.

Negácia kvantifikátorov
¬∀x P(x) = ∃x (¬P(x)) … Nie je pravda, že každý je šťastný. = Niekto je nešťastný.
¬∃x P(x) = ∀x (¬P(x)) … Neexistuje osoba, ktorá je šťastná. = Všetci sú nešťastní.

Poradie kvantifikátorov

Keď je viac kvantifikovaných premenných, aplikujú sa v poradí od vnútorného. Napríklad

∃x∀y

P(x,y) znamená

∃x (∀y P(x,y)). Kvantifikátory rovnakého druhu možno prehadzovať. Rôzne

kvantifikátory nemožno prehadzovať.
∀x ∀y α = ∀y ∀x α
∃x ∃y α = ∃y ∃x α
∃x ∀y α ⇒ ∀y ∃x α
Pr.

P(x,y)

≡x<y, D=R

∀x ∃y P(x,y)

pre každé číslo x, existuje číslo y, ktoré je väčšie ako číslo x

pravda

∃y ∀x P(x,y)

existuje číslo y také, že všetky čísla sú od neho väčšie

nepravda

Pr.

D = N, x<y
∀x∀y x<y 0 ∃x∀y x<y 0
∀y∀x x<y 0 ∀y∃x x<y 0
∃y∀x x<y 0 ∃y∃x x<y

1

∀x∃y x<y 1 ∃x∃y x<y

1

Pr.

D – množina ľudí, O(x,y) – x je otcom y
∀x∀y O(x,y) 0 pre každých dvoch ľudí platí, že prvý je otcom druhého
∀y∀x O(x,y) 0 pre každých dvoch ľudí platí, že druhý je otcom prvého
∃y∀x O(x,y)

0

existuje taký človek, ktorému sú všetci ľudia otcom

∀x∃y O(x,y)

0

každý človek má dieťa

∃x∀y O(x,y)

0

existuje taký človek, ktorému sú všetci ľudia deťmi

∀y∃x O(x,y)

1

každý človek má otca

∃y∃x O(x,y)

1

existujú dvaja ľudia takí, že druhý je otcom prvého

∃x∃y O(x,y)

1

existujú dvaja ľudia takí, že prvý je otcom druhého