Na rozdíl od výrokové logiky si predikátová logika (PL) všímá struktury vět samotných. Rozlišuje v každé větě individuum, resp. individua, o němž, resp. o nichž, se něco predikuje - predikát intuitivně chápeme jako vlastnost nebo vztah. Většina z toho, co jsme formulovali ve výrokové logice zůstává v platnosti i v rámci predikátové logiky. Nejdříve formulujeme PL prvního řádu.

PREDIKÁTOVÁ LOGIKA PRVNÍHO ŘÁDU (PL 1)

ZÁKLADNÍ ÚVAHA

Uvažme tři dívky, Annu, Báru a Gabrielu. Tyto tři dívky tvoří naše univerzum úvahy, univerzum U. Označme si je po řadě (metajazykovými) výrazy a, b, g. Tedy U={a, b, g}, univerzum je množina individuí. Jména zastupující tyto dívky označíme individuovými konstantami a, b, c (tyto konstanty budou mít vždy stejnou interpretaci - a pro a, b pro b, g pro c). Individuové proměnné x, y, z, x₁, y₂, z₂,... zastupují individua "neurčitě" (v závislosti na valuaci). Mějme větu "Gabriela je dívka", nahradíme-li jméno Gabriela proměnnou x, pak získáme větu "x je dívka" (kde x nabude hodnotu a, nebo b, či g). Predikátový symbol je výraz označující predikát, tedy vlastnost nebo vztah, který lze predikovat (vypovídat) o individuu, nebo individuích (např. "být dívka" je predikát). Vlastnost "být dívka" je predikovatelná (jednotlivě) o třech individuích, tyto tři tvoří množinu "dívek"; píšeme pak P(x). Můžeme dále tvrdit, že "pro všechna x platí, že x je dívka"; v zápisu užijeme znak obecného kvantifikátoru xP(x). Jiným příkladem je "být černovlasá", což se týká např. jen Gabriely, tedy "pro některá x platí, že x je černovlasé"; v zápisu užijeme existenční (částečný) kvantifikátor xP(x). Obecný kvantifikátor lze v případě konečného univerza nahradit konjunkcí P(a₁)...P(a_n), existenční kvantifikátor zase disjunkcí P(a₁)...P(a_n) (kde a₁,..., a_n jsou individuové konstanty). Vlastnosti jsou tedy v PL chápány jako množiny. Predikát pro vlastnost může být predikován jen o nějakém individuu; je to monadický> predikát. V našem univerzu můžeme však také konstatovat např. vztah, že Gabriela je vyšší než Anna; zapisujeme ho P(x,y) (je-li Gabriela vyšší než Bára, i vyšší než Anna, můžeme psát P(c,x), kde c je konstanta pro g). Vztahy jsou chápány v PL jako n-ární relace. Predikáty, které platí o nějakých dvojicích se nazývají binární predikáty (o trojicích ternární, atd.); arita (četnost) predikátu je počet míst predikátu. Co je to relace? Nejprve uvažme kartézský součin univerza - je-li U={a, b, g} máme při U² množinu {[aa], [ab], [ag], [ba], [bb], [bg], [ga], [gb], [gg]}, tj. množinu 3² uspořádaných dvojic (kde 3 je počet prvků U, 2 je násobnost součinu); obecně je možný kartézský součin U^k. Relace jsou podmnožinami kartézského součinu daného U; při U² je možných podmnožin 2⁹ (kde 9 je počet n-tic U²). Např. relace "být vyšší než", platí (je-li Bára vyšší než Anna, Gabriela vyšší než Anna, Gabriela vyšší než Bára) jen o podmnožině daného kartézského součinu, totiž {[ba], [ga], [gb]}; lze říci, že predikátový symbol je interpretován touto podmnožinou. Výpověď je pravdivá nebo nepravdivá podle toho, zda ten prvek patří do té množiny nebo ne.

JAZYK PL1

Abeceda:

1) symboly pro individuové proměnné x, y, z, ... x₁, y₁, z₁, ...
2) symboly pro individuové konstanty a₁, ..., a_n
3) symboly pro predikáty (k značí aritu predikátu; k>1) P^k, Q^k, R^k, ..., P^k₁, P^k₂, ...
4) symboly pro logické spojky , , , , , ...
5) symboly pro kvantifikátor obecný a částečný ,
6) pomocné symboly (, ), a ,

(Pozn.: PL1 může být rozšířena o funkcionální symboly (f₁^k, f₂^k, ...) a o identitu (=).)

Gramatika:

termy
i) každá proměnná je term
ii) každá individuová konstanta je term

správně utvořené formule
1) atomické formule
i) jestliže P^k je k-místný predikátový symbol a jestliže d₁, .., d_k jsou termy, pak P^k(d₁, .., d_k) je atomická formule (s.u.f.)
2) molekulární formule
i) jestliže A, B jsou s.u.f., pak A, (A*B) (kde * je nebo , či , či ) jsou s.u.f.
ii) jestliže x je proměnná a A je s.u.f., pak xA a xA jsou s.u.f.
3) nic jiného není s.u.f.

(Pozn.: Budeme psát x₁...x_nA místo x₁, x₂, ... , x_nA, stejně tak pro .)

SÉMANTIKA PL1

Valuace. Individua lze uspořádávat do nekonečně mnoha nekonečných sekvencí. V těchto sekvencích rozpoznáváme pozice. Valuace je pak funkce, která každé proměnné přiřadí přesně jedno individuum, a to - pro proměnnou x_i - právě to individuum, které je na i-té pozici (v(x_i)=x).
Např. pro U={a,b} máme sekvence aaaa..., baaa..., abaa..., aaba..., ..., bbaa..., baba..., ..., přičemž v₁ přiřazuje x₁ prvek a, x₂ také a, stejně tak i x₃, x₄, ..., v₂ přiřazuje x₁ prvek b, x₂ i x₃ i x₄ prvek a, atd.

Sémantická funkce S je funkce, která predikátovým k-argumentovým symbolům přiřadí podmnožiny univerza U (při k=1), či množiny uspořádaných n-tic individuí z U (při k>1), individuovým konstantám prvky U.

Interpretace je funkce _S,v, která přiřazuje každé atomické formuli A určitou pravdivostní hodnotu v závislosti na valuaci v a sémantické funkci S takto:

termy
a) je-li A proměnná x_i, pak _S,v(A) = v(x_i)
b) je-li A individuální konstanta a_i, pak _S,v(A) = S(a_i)

predikátové symboly
a) je-li A predikátový symbol P^k, pak _S,v(A) = S(P^k)

atomické formule
a) je-li A atomická formule P^k(d₁, ..., d_k), pak _S,v(A) = 1,
jestliže n-tice [_S,v(d₁), ..., _S,v(d_k)] S(P^k); 0 v opačném případě

molekulární formule
a) je-li A tvaru B, pak _S,v(A) = 1, jestliže _S,v(B) = 0; 0 v opačném případě
b) je-li A tvaru BC, pak _S,v(A) = 1, jestliže _S,v(B) = _S,v(C)= 1; 0 v opačném případě
c) je-li A tvaru BC, pak _S,v(A) = 0, jestliže _S,v(B) = _S,v(C) = 0; 1 v opačném případě
d) je-li A tvaru BC, pak _S,v(A) = 0, jestliže _S,v(B) = 1 a _S,v(C) = 0; 1 v opačném případě
e) je-li A tvaru BC, pak _S,v(A) = 1, jestliže _S,v(B) = _S,v(C); 0 v opačném případě

f) je- li A tvaru xB, pak _S,v(A) = 1, jestliže _S,v' (B) = 1 při každé valuaci v', která přiřazuje volné proměnné stejnou hodnotu jako v, avšak vázané proměnné přiřadí jakoukoli hodnotu z U; 0 v opačném případě
g) je- li A tvaru xB, pak _S,v(A) = 1, jestliže _S,v' (B) = 1 alespoň při jedné valuaci v'; 0 v opačném případě

Komentář k interpretaci

termy (interpretace přiřazuje pouze individuum jako i valuace)
a) Interpretace individuové proměnné je totéž co valuace pro tuto proměnnou (je to nějaký prvek univerza, xU, v závislosti na valuaci).
b) Interpretace individuové konstanty je prvek univerza, xU, (interpretace není ovlivněna valuacemi).

predikátové symboly (interpretace přiřazuje n-tice individuí z kartézského součinu univerza)
a) V případě predikátového symbolu P^k je v závislosti na v jednotlivou interpretací přiřazena - je-li k=1 - podmnožina univerza, resp. - je-li k>1 - množina uspořádaných n-tic.

atomické formule
a) Interpretace atomické formule P^k(d₁, ..., d_k) je 1, jestliže n-tice prvků (daná interpretací termů) je prvkem interpretace daného predikátu P^k (tedy [_S,v(d₁), ..., _S,v(d_k)] S(P^k) ).

molekulární formule
a-e) Interpretace výrokově logických formulí v prostředí PL je snadno nahlédnutelná. Umožňuje nám to ústrojně včlenit VL do PL.

f-g) Valuace v', je taková valuace, která je zcela podobná valuaci v, až na přisouzení různých hodnot vázané proměnné x. Jinými slovy řečeno, daná valuace v je akceptována jen pro proměnné (případně se vyskytující v B), které jsou odlišné od x. Je to omezení valuace v tak, že se netýká x.

Pravdivost

Věta A nabývá v interpretaci _S,v hodnoty pravda nebo nepravda při valuaci v. (Věta A je splňována valuací v v interpretaci , jestliže _S,v (A) = pravda.)

Věta A je pravdivá v interpretaci _S,v, jestliže nabývá hodnoty pravda při každé valuaci v.

Věta A je logicky pravdivá (tautologie), jestliže je pravdivá při každé interpretaci.

Vyplývání

Věta B logicky vyplývá z vět A₁, ..., A_n, jestliže je pravdivá při každé interpretaci, při níž jsou pravdivé věty A₁, ..., A_n.

Volnost a vázanost proměnných

i) výskyt x v x je volný
ii) výskyt x je volný v A, A*B, je-li volný v A, resp. i v B
iii) výskyt x je volný v yA, yA, je-li volný v A a jde-li o proměnnou odlišnou od proměnné y

(Pozn.: Proměnná je tedy volná v A, jestliže má v A alespoň jeden výskyt volný; naopak - proměnná je vázaná v A, jestliže jsou všechny její výskyty v A vázány kvantifikátorem.)

Uzavřená formule je formule, v níž jsou všechny proměnné vázány.

Term t je substituovatelný za proměnnou x ve formuli A, je-li term individuová konstanta nebo individuová proměnná taková, že po dosazení do formule A není v dosahu kvantifikátoru, který váže proměnnou x. Formuli, v níž je každý volný výskyt x nahrazen termínem t, zapisujeme A[x/t].

Tautologie predikátové logiky

Z jakékoli tautologie výrokové logiky lze substitucí jakékoli formule PL za výrokové symboly získat tautologii PL. Např. v případě pp můžeme za p dosadit např. xP(x): xP(x) xP(x), anebo dosadit třeba jen P(x): P(x) P(x). Specifické tautologie PL jsou pak např. níže uvedené.

A) De Morganovy zákony pro kvantifikátory
xA xA
xA xA

xA xA
xA xA

B) (kde t musí být substituovatelný za x)

xA A[x/t]	zákon konkretizace
A[x/t] xA	zákon abstrakce
xA xA	zákon partikularizace

C) zákony distributivnosti kvantifikátorů

(xA xB)		x(AB)
(xA xB)		x(AB)
(xA xB)		x(AB)
x(AB)		(xA xB)

D)

xy P(x,y)		yx P(x,y)
yx P(x,y)		xy P(x,y)

AXIOMATIZACE PL1

1) Formální jazyk (viz výše)

2) Axiomy

a) (axiom-schémata VL)
Ax. 1: A(BA)
Ax. 2: (A(BC)) ((AB)(AC))
Ax. 3: (BA) (AB)
b)
Ax. 4: xA A[x/t]
Ax. 5: x(AB) (AxB)      (kde A neobsahuje volnou proměnnou x)

3) Pravidla odvození

Modus ponens (MP) (pravidlo odloučení)
Jsou-li A i AB teorémy, pak je také B teorémem.

A, AB
     B

Pravidlo generalizace (PG)
Nechť B neobsahuje žádnou volnou proměnnou x. Jestliže můžeme dokázat větu BA[x], pak můžeme dokázat i větu BA[x]. Při kvantifikaci se z volné proměnné (jakou je x v první formuli) stává proměnná vázaná. Tímto pravidlem zajišťujeme bezespornost (věta BA[x] by měla být logicky pravdivá, tj. pravdivá pro všechna udělení hodnot proměnné x), ale nikoli pravdivost (totiž když je BA[x] při nějakém udílení hodnot pravdivá, není nutné, že i BA[x] je pravdivá).

BA[x]
BA[x]

DALŠÍ POJMY

Pojmy, které jsme si definovali ve výrokové logice zůstávají v platnosti, modifikovat je třeba jen definici důkazu z hypotéz.

Důkaz z hypotéz Důkaz z hypotéz je konečná posloupnost správně utvořených formulí (vedle axiomů a vět odvozených odvozovacími pravidly tu mohou být i jednotlivé hypotézy). Podmínkou je, že je-li mezi kroky důkazu hypotéza A_i, která obsahuje proměnnou x, pak někde dále v důkazu bude krok vzniklý uplatněním pravidla generalizace (což povede ke kvantifikaci proměnné x; píšeme pak A_i |- _xiB).

PL1 je úplná, bezesporná, ale není rozhodnutelná.

ARISTOTELSKÁ LOGIKA

Aristotelská a posléze tradiční logika pracovala jen s jednomístnými predikáty, je jen částí PL1. Věty byly analyzovány jako určitá spojení subjektu a predikátu (budeme je označovat po řadě A a B). Kvalita (kladný/záporný výrok) a kvantita (obecný/částečný výrok) vytváří čtyři možnosti typů výroků, přičemž tyto možnosti byly ve středověku označovány a, e, i, o (z latinských slov affirmo - tvrdím, nego - popírám).

Druhy soudů

obecný kladný	Každé A je B. [a]
obecný záporný	Žádné A není B. [e]
částečný kladný	Některá A jsou B. [i]
částečný záporný	Některá A nejsou B. [o]

Srovnání vyjádření v tradiční logice, predikátové logice; v posledním sloupci tzv. Russellovy přechody (univerzum je v nich omezeno):

tradiční logika	predikátová logika		Russellovy přechody
AaB	x (A(x) B(x))		(xA) B(x)
AiB	x (A(x) B(x))		(xA) B(x)
AeB	x (A(x) B(x))	či x (A(x) B(x))	(xA) B(x)
AoB	x (A(x) B(x))	či x (A(x) B(x))	(xA) B(x)

Obraty

obrat prostý (kvantita je zachována):	obrat po případě (kvantita je oslabena):
SiPPiS	SaPPiS
SePPeS	SePPoS

Kategorický sylogismus

Aristotelův kategorický (tedy bezpodmínečný) sylogismus je úsudek, který má dvě premisy (vyšší a nižší), jeden závěr. Premisy a závěr jsou složeny ze tří termínů (následující terminologie není shodná s terminologhií predikátové logiky): subjektu S, predikátu P a středního (mediálního) členu M. Premisy a závěr jsou vždy o dvou termínech (tedy subjekt a predikát). Celkem jsou možné čtyři figury (poslední je středověká), přičemž pro každou je 64 možných distribucí a, i, e, o mezi termíny premis a závěru. Celkem je tedy 256 modů (typů úsudků), z nichž Aristoteles vybral jen ty, kde závěr vyplývá z premis. (Např. v první figuře jsou platné čtyři mody: barbara, celarent, darii, ferio.)

M P S M S P

P M S M S P

M P M S S P

P M M S S P

(Pozn. Stoiky zpracovaný hypotetický sylogismus je struktury AB, BC AC; hypoteticko-kategorický sylogismus je struktury A, AB B.)

Ověřování úsudků Vennovými diagramy

Vennovy diagramy jsou v podstatě množinovým vyjádřením úsudků. Každý ze tří termínů je zastoupen jedním z kruhů. Jednotlivé premisy (založené na nějakém poměru dvou množin) pak vyznačíme následovně: vyšrafujeme vždy tu část kruhu, tj. jednu ze sedmi (resp. osmi) podmnožin, kde se nenachází individua mající vlastnosti zmíněné v obou termínech (volíme např. šrafování zleva doprava, zprava doleva), nevyšrafovánu tedy necháváme tu část, o níž nic bližšího nevíme; v případě, že se tvrdí, že v nějaké podmnožině je alespoň jeden prvek, pak do ní vyznačíme křížek. Úsudek je korektní, pokud to, co dostaneme vymodelováním premis, se shoduje s tím, co vymodelujeme ze závěru.

Příklad nekorektního úsudku:
Žádný můj známý (Z) není logik (L). (\\\)
Žádný logik (L) není Indián (I). (///)
_______________________________
Žádný můj známý (Z) není Indián (I).

ROZŠÍŘENÍ PL1 O IDENTITU

Identita je relace (ne mezi symboly, ale mezi denotáty), která je reflexivní: x R(x,x), symetrická: xy ((x=y)(y=x)) a tranzitivní: xyz ((x=y) ((y=z)(x=z)). Je třeba rozšířit jazyk, interpretaci a přidat axiom i pravidlo.

Rozšíření abecedy: symbol rovnosti (=)

Rozšíření gramatiky: d₁=d₂ je s.u.f.

Interpretace: _S,v(d₁=d₂) = 1 právě tehdy, když _S,v(d₁) = _S,v(d₂) (přiřadíme-li tedy stejné individuum)

Axiomy pro identitu:
Ax. 6: x (x=x)
Schéma pravidla pro identitu:
Ax. 7: xy ((x=y) (A[x]A[y/x]))

ROZŠÍŘENÍ PL1 O FUNKČNÍ TERMY

Pro některé aplikace PL je třeba přidat speciální termy pro funkce. Opět je třeba rozšířit jazyk i axiomy PL1.

Rozšíření abecedy: Je-li P_i^k k-členný predikátový symbol, pak f_i^k-1 je příslušný k-1-členný funkční symbol.

Rozšíření gramatiky: Jsou-li t₁...t_k termy, pak f_i^k(t₁...t_k) je term.

Axiomy pro funkční termy:

Ax. 8: x₁...x_k-1 !y P_i^k (x₁...x_k-1 y) (kde !y znamená přesně jedno y)
Ax. 9: x₁...x_k y P_i^k-1(x₁...x_kf_i (x₁...x_k))

RELACE

(Pozn. v našem zápisu neužíváme notace infixní, tj. např. xRy, ale prefixní.)

Doplněk relace	R'(x,y) =df R(x,y)
Inkluze relací	RÍS =df xy (R(x,y) S(x,y))
Rovnost relací	R=S =df xy (R(x,y) S(x,y))
Sjednocení relací	RÈS(x,y) =df R(x,y) S(x,y)
Průnik relací	RÇS(x,y) =df R(x,y) S(x,y)
Univerzální relace	U(x,y) =df R(x,y) R(x,y)
Prázdná relace	Æ(x,y) =df R(x,y) R(x,y)
Inverzní relace	R-1(x,y) =df R(y,x)
Kompozice relací	R.S(x,y) =df z (R(x,z) S(z,y) )

PREDIKÁTOVÁ LOGIKA PRVNÍHO ŘÁDU (PL2)

V PL2 jsou na rozdíl od PL1 povoleny i predikátové proměnné, které nabývají jako hodnoty množiny (tj.podmnožiny univerza), a navíc tyto predikátové proměnné mohou být kvantifikovány. PL2 je bezesporná, není ale úplná. Příkladem výrazu PL2 je např. zápis Leibnizovy identity nerozlišitelných entit: xy ( (x=y) P(P(x)P(y)) ), tedy že x a y jsou identické právě tehdy, když mají všechny vlastnosti stejné. Předmětem PL2 jsou zejména vlastnosti binárních relací.

Vlastnosti binárních relací

Reflexivita	Refl(R) =df x R(x,x)
Poloreflexivita	Polorefl(R) =df x R(x,x) x R(x,x)
Antireflexivita	Antirefl(R) =df x R(x,x)
Ireflexivita	Irefl(R) =df x R(x,x)
Symetrie	Sym(R) =df xy (R(x,y) R(y,x))
Polosymetrie	Polosym(R) =df xy ( (R(x,y) R(y,x)) (R(x,y)R(y,x)) )
Asymetrie	Asym(R) =df xy (R(x,y) R(y,x))
Antisymetrie	Antisym(R) =df xy ( (R(x,y)R(y,x)) (x=y) )
Tranzitivita	Trans (R) =df xyz ( (R(x,y)R(y,z)) R(x,z) )
Polotranzitivita	Polotrans(R) =df xyz((R(x,y)R(y,z)R(x,z))R(x,y)R(y,z)R(x,z)))
Intranzitivita	Intrans(R) =df xyz ( (R(x,y)R(y,z)) R(x,z) )
Konexnost	Con(R) =df xy ( (x¹y) (R(x,y)R(y,x)) )
Inkonexnost	Incon(R) =df xy ( (x¹y) R(x,y) R(y,x) )

Speciální relace

Relace typu ekvivalence	Refl(R) Sym(R) Trans(R)
Ostré uspořádání	Refl(R) Asym(R) Trans(R)
Částečné uspořádání	Refl(R) Antisym(R) Trans(R)

1.10.1999, v.č. IV