Výroková logika (VL) je teorií výrokově logických spojek chápaných jako jména pravdivostních funkcí. Zkoumány jsou výroky složené z dílčích výroků (ty jsou označovány výrokovými proměnnými). Je uplatňován Frege-Churchův princip skladebnosti - pravdivostní hodnota složeného výrazu je jednoznačně určena pravdivostními hodnotami jeho složek.

PRAVDIVOSTNÍ FUNKCE

Každá n-ární spojka je funkcí definovanou na n-tici pravdivostních hodnot, kterým přiřazuje určitou pravdivostní hodnotu. Počet těchto n-árních pravdivostních funkcí je 2ⁿ-tá mocnina dvou. (V následujících tabulkách označujeme pravdivostní hodnou pravda jako 1, nepravda jako 0.)

Nulární funkce

f10	f20
1	0

Jednoargumentové funkce

argument	f11	f21 (Id)	f31 ()	f41
1	1	1	0	0
0	1	0	1	0

Dvouargumentové funkce

	argu-		f12	f22	f32	f42	f52	f62	f72	f82	f92	f102	f112	f122	f132	f142	f152	f162
	ment										/						|
	<1 ,	1>	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0
	<1 ,	0>	1	1	1	1	0	0	0	0	1	1	1	1	0	0	0	0
	<0 ,	1>	1	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0
	<0 ,	0>	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0

(Pozn. / je Shefferova funkce - "... je neslučitelné s ...", | je Nicodova (Peirceova) funkce - "ani..., ani..."; f₁₀²je vylučovací disjunkce.)

Nejznámější výrokové spojky

negace (ne)	konjunkce (a)	disjunkce (nebo)	implikace (jestliže,pak)	ekvivalence (právě tehdy, když)
p	p q	p q	p q	p q
0 1	1 1 1	1 1 1	1 1 1	1 1 1
1 0	1 0 0	1 1 0	1 0 0	1 0 0
	0 0 1	0 1 1	0 1 1	0 0 1
	0 0 0	0 0 0	0 1 0	0 1 0

Příklady:

"Neprší." (), "Není pravda, že je horko." ()
"Prší a je mlha." (), "Petr a Pavel mají auto." ()
"Prší nebo je mlha." ()
"Jestliže svítí slunce, pak je hezky." (), "Je-li Praha větší než Brno, pak v Praze prší." ()
"Prší tehdy a jen tehdy, když padá voda." ()

JAZYK (SYNTAX) VÝROKOVÉ LOGIKY

Abeceda:

i) výrokové symboly p, q, r, ... p₁, q₁, r₁, ... (symboly výrokových proměnných)
ii) symboly pro výrokové spojky , , , ,
iii) pomocné symboly (, )

Gramatika:

i) výrokové symboly (p, q, r, ...) jsou správně utvořené formule (s.u.f.)
ii) jestliže A, B jsou s.u.f., pak A, (AB), (AB), (AB), (AB) jsou s.u.f.
ii) nic jiného není s.u.f.

Pozn.1: Bod gramatiky ii) se může v různých systémech VL lišit. Např. stačí uvést a , nebo jen / či jen |; ostatní výrokové spojky (pravdivostní funkce) lze pak odvodit.
Pozn.2: Symboly A a B jsou výrazy metajazyka, jenž mohou označovat jakékoli, tedy i složené výroky.
Pozn. 3: Budeme užívat konvenci o vynechávání závorek všude tam, kde to nebude na újmě jednoznačnosti zápisu dané formule.

SÉMANTIKA VÝROKOVÉ LOGIKY

Interpretace - pravdivostní ohodnocení (valuace) je zobrazení , které přiřazuje každé atomické formuli (výrokové proměnné) dané úvahy určitou pravdivostní hodnotu.

Formule A nabývá při interpretaci pravdivostní hodnotu pravda, platí-li:
1. A je výrokový symbol a _(A)= 1.
2. A je tvaru B a _(B)=0.
3. A je tvaru BC a _(B)= _(C) = 1.
4. A je tvaru BC a _(B)= 1 nebo _(C)= 1.
5. A je tvaru BC a _(B)= 0 nebo _(C)= 1.
6. A je tvaru BC a _(B)=_(C).

Splnitelnost definovaná na základě pojmu interpretace

Interpretace splňuje formuli A, platí-li:
1. A je výrokový symbol a _(A)= 1.
2. A je tvaru B a nesplňuje B.
3. A je tvaru BC a splňuje B i C.
4. A je tvaru BC a splňuje B nebo C.
5. A je tvaru BC a nesplňuje B nebo splňuje C.
6. A je tvaru BC a splňuje B i C nebo nesplňuje B i C.

Formule je splnitelná, je-li splňována aspoň jednou interpretací, kterou pak nazýváme model této formule.

Tautologie je formule (věta), která nabývá hodnoty pravda při každé interpretaci (tedy formule, která je každou interpretací splňována).

Kontradikce je formule (věta), která nabývá hodnoty nepravda při každé interpretaci (tedy formule, která není žádnou interpretací splňována).

Seznam některých tautologií

A)

(p p)	zákon sporu
(p p)	zákon vyloučeného třetího
p p	zákon totožnosti
p p	zákon dvojí negace
p (p p)	zákon idempotence
p (p p)	zákon idempotence

B)

(pp) q	zákon Dunse Scota
p (qp)	zákon simplifikace

C) De Morganovy zákony

(pq)       (pq)	"negovaná disjunkce je konjunkce negací"
(pq)       (pq)	"negovaná konjunkce je disjunkce negací"

D)

(pq)         (q p)	transpozice implikace
(pq)      (p q)	"negovaná implikace je konjunkce negace"
(pq)         (p q)	"implikace je negace disjunkce"
(pq)          (p q)	"disjunkce je negace implikace"
(pq)         ((pq) (qp))	"ekvivalence je implikace oběma směry"

E)

komutativita	(pq) (qp)	(pq) (qp)	(pq) (qp)
asociativita	(p (qr)) (pq)r)	(p(qr)) ((pq)r)	(p(qr))((pq)r)
distributivita	((p(qr))((pq)(pr))                   ((p(qr))((pq) (pr))
tranzitivita	((pq)(qr)) (pr)

F) (kde T je tautologie a K je kontradikce)

(p T) p	neutrálnost tautologie ke konjunkci
(p K) K	agresívnost kontradikce ke konjunkci
(p T) T	agresívnost tautologie k disjunkci
(p K) p	neutrálnost kontradikce k disjunkci

Pravidlo substituce

Tautologie zůstane tautologií, i když v ní nahradíme každý výskyt určité proměnné jednou a toutéž správně utvořenou formulí.

Pravidlo ekvivalentního nahrazení

Nechť A je s.u.f., která obsahuje alespoň na jednom místě podformuli B. Jestliže platí, že B je ekvivalentní s C, a jestliže formule A' vznikne nahrazením libovolného počtu výskytů formule B formulí C ve formuli A, pak A je ekvivalentní s A'.

(Pozn. o rozdílech: Podle pravidla substituce nahrazujeme proměnné, podle pravidla ekvivalentního nahrazení nahrazujeme formule. Při užití pravidla substituce dosazujeme za každý výskyt, při užití pravidla ekvivalentního nahrazení dosazujeme za libovolný počet výskytů.)

Výrokově logické vyplývání

Věta B výrokově logicky vyplývá z vět A₁, A₂, ..., A_n, jestliže nabývá hodnoty pravda za všech takových uděleních hodnot proměnným, při nichž nabývají hodnoty pravda všechny věty A₁, A₂, ..., A_n. (, )

(Pozn.: Zapisujeme A₁, A₂, ..., A_n-1, A_n B, přičemž (A₁, A₂, ..., A_n-1, A_n B)   (A₁A₂ ... A_n)B.)

ÚPLNÝ SYSTÉM SPOJEK VÝROKOVÉ LOGIKY

Věta o reprezentaci

Každou pravdivostní n-ární funkci f  lze reprezentovat formulí výrokové logiky, která obsahuje pouze spojky a , resp. , : A(p₁, p₂, ..., p_n).

Učiňme dohodu, že výrazem konjunkce, resp. disjunkce, rozumíme formuli, která spojuje spojkou konjunkce, resp. disjunkce, n atomických formulí.

Literály jsou atomické formule a negace atomických formulí.

Formule A je normální disjunktivní formou nad atomickými formulemi p₁, p₂, ..., p_n, je-li A tvaru disjunkce, jejíž každý člen je konjunkcí nějakých literálů z p₁, p₂, ... p_n nebo literálem.

Formule A je normální konjunktivní formou nad atomickými formulemi p₁, p₂, ..., p_n, je-li A tvaru konjunkce, jejíž každý člen je disjunkcí nějakých literálů z p₁, p₂, ... p_n nebo literálem.

Elementární konjunkcí nad p₁, p₂, ..., p_n je každá konjunkce literálů z těchto formulí, v níž se každý z těchto symbolů vyskytuje jako literál právě jednou.

Elementární disjunkcí nad p₁, p₂, ..., p_n je každá disjunkce literálů z těchto formulí, v níž se každý z těchto symbolů vyskytuje jako literál právě jednou.

Úplnou normální disjunktivní formou (ÚDNF) je každá disjunkce různých elementárních konjunkcí nad p₁, p₂, ... p_n.

Úplnou normální konjunktivní formou (ÚKNF) je každá konjunkce různých elementárních disjunkcí nad p₁, p₂, ... p_n.

Ke každé formuli A výrokové logiky, která není tautologií (kontradikcí), lze najít formuli B, která je ve tvaru ÚDNF (ÚKNF) a je ekvivalentní s A (ÚDNF nelze zkonstruovat pro kontradikce a ÚKNF tedy nelze zkonstruovat pro tautologie).

AXIOMATIZACE VÝROKOVÉ LOGIKY

1) Formální jazyk

Formální jazyk (abeceda a gramatika-s.u.f.) je relativní k danému axiomatickému systému. Např. v případě standardního axiomatického systému jsme vybrali a . Formální jazyk tak je částí jazyka, který jsme uvedli výše.

2) Zadání axiómů

Axiómy jsou základní vybrané pravdivé věty (tautologie) daného sytému.

Standardní axiómy VL

Axióm 1: p(qp)
Axióm 2: (p(qr)) ((pq)(pr))
Axióm 3: (qp) (pq)

3) Zadání odvozovacích pravidel

Modus ponens (pravidlo odloučení)

Tvrdíme-li A i AB, pak můžeme tvrdit i B.

A, AB
----------
    B

Pravidlo substituce

Tvrdíme-li nějakou větu, pak můžeme tvrdit i větu, která vznikne z původní věty tím, že všechny určité proměnné a nahradíme nějakou správně utvořenou formulí.

A
A[B/a]          (pomocí [B/a] vyznačujeme nahrazení proměnné a formulí B)

Axióm-schémata

Axióm 1: A(BA)
Axióm 2: (A(BC)) ((AB)(AC))
Axióm 3: (BA) (AB)

(Axióm-schémata nám na rozdíl od axiómů generují nekonečně mnoho vět daného axiomatického systému, proto v takovémto systému nepotřebujeme pravidlo substituce.)

DALŠÍ POJMY

Důkaz

Důkaz je v daném systému konečná posloupnost správně utvořených formulí (kroků důkazu), z nichž každá je buď axiómem nebo byla odvozena aplikací některého pravidla odvození na některé předcházející správně utvořené formule.

Dokazatelnost

Určitá formule je dokazatelná v daném systému tehdy a jen tehdy, když v tomto systému existuje důkaz, jehož je tato formule členem. ()

Teorém je v systému S formule, která je dokazatelná v systému S.

Důkaz z hypotéz

Důkaz je v daném systému konečná posloupnost správně utvořených formulí, přičemž formule A_i je v daném systému dokazatelná z množiny hypotéz H (tj. formulí, které nejsou tautologiemi), jestliže pro každé i platí buď 1.) A_i je jednou z hypotéz, nebo 2.) A_i je axiómem, nebo 3.) vzniklo jako závěr odvozovacího pravidla MP, jehož předpoklady leží mezi A₁, ...,A_i-1. Řekneme, že formule A_i je dokazatelná z předpokladů H (H A_i).

Věta o dedukci (metateorém dedukce)

Je-li věta B dokazatelná z vět A₁, A₂,..., A_n, pak věta A_nB je dokazatelná z vět A₁, A₂, ..., A_n-1 (tedy je-li A₁, A₂, ..., A_n-1, A_n B, pak A₁, A₂, ..., A_n-1 A_nB).

Sémantický výklad pravidla modus ponens

Jestliže formule A a formule AB jsou tautologie, pak i B je tautologií. (Modus ponens je tedy pravidlo, které zachovává i pravdivost.)

Sémantická varianta věty o dedukci

B vyplývá z A₁, A₂, ..., A_n-1, A_n (tedy A₁, A₂, ..., A_n-1, A_n B), právě když A₁, A₂, ..., A_n-1 A_nB.

VLASTNOSTI FORMÁLNÍCH SYSTÉMŮ

Rozhodnutelnost

Množina A je rozhodnutelná ve své nadmnožině B tehdy a jen tehdy, když existuje efektivní procedura (procedura o konečném počtu kroků) aplikovatelná na prvky množiny B taková, že umožní rozhodnout o každém prvku množiny B zda je, či není, prvkem množiny A.

Abeceda musí být rozhodnutelná v množině všech možných symbolů.

Množina správně utvořených formulí musí být rozhodnutelná v množině všech možných kombinací znaků abecedy.

Množina axiomů musí být rozhodnutelná v množině správně utvořených formulí.

Daný systém je rozhodnutelný tehdy a jen tehdy, když množina jeho teorémů je rozhodnutelná v množině všech správně utvořených formulí.

Bezespornost (=konzistence)

Daný systém je syntakticky bezesporný, platí-li, že v něm není dokazatelná věta AA (spor).

Daný systém je sémanticky bezesporný (korektní), platí-li pro každou větu A, že je-li tato věta dokazatelná, pak je taky logicky pravdivá (je tautologií). (Je-li A, pak A.)

Úplnost

Daný systém je syntakticky úplný, platí-li, že přidáme-li k množině axiomů správně utvořenou formuli (větu), která není teorémem, pak dostaneme sporný systém.

Daný systém je sémanticky úplný, platí-li pro každou větu A, že je-li tato věta tautologií, pak je v daném systému dokazatelná (je teorémem). (Je-li A, pak A.)

(Pozn.: Když je každý teorém tautologií, jde o sémantickou bezespornost (korektnost), když je každá tautologie teorémem, jde o sémantickou úplnost. Když je systém jak bezesporný, tak i úplný, tak množina teorémů je totožná s množinou tautologií.)

Systém výrokové logiky je rozhodnutelný, bezesporný i úplný.

ZÁVĚREM

Při aplikaci výrokové logiky na přirozený jazyk narazíme (při všech výhodách jednoduchosti, rozhodnutelnosti, bezespornosti a úplnosti VL) na určitá úskalí - ne všechny případy vyplývání jsou totiž výrokovou logikou zachytitelné. Uvažme např. následující úsudky:

Ačkoli závěr v nich zjevně vyplývá z premis, VL, analyzující dané výroky jako p, q, r a celý úsudek pak jako (pq)r, není s to toto vyplývání prokázat z hlediska správnosti - lze totiž nalézt takové ohodnocení výrokových proměnných (po řadě: 1, 1, 0), kterým celý úsudek nabude pravdivostní hodnoty nepravda. (VL tedy analyzuje výrazy příliš hrubozrnně.) Můžeme formulovat následující tvrzení: Jestliže věta B výrokově vyplývá z vět A₁, A₂,..., A_n, pak z nich také vyplývá. Neplatí ovšem obrácené tvrzení: Jestliže věta B vyplývá z vět A₁, A₂,..., A_n, pak z nich také výrokově logicky vyplývá.

1.10.1999, v.č. VI