Výroková logika
• Výrok je sdělení, u něhož má smysl otázka, zda je či není pravdivé. Může nastat právě jedna z možností.
• Sdelení, o nichž jsme dosud neurčili jednoznačne, zda-li jsou pravdive či nikoli, avsak v principu jedna z techto mozností musí nastat, se nazávají hýpotézý (domněnky). Hypoteza je vírok.
• Jestlize je vírok pravdiví, prirazujeme mu výrokoví znak 1; jestlize je nepravdiví, prirazujeme mu znak 0.
• Slova nebo znaky, pomocí nichz tvoríme nove výroky, se nazývají logické spojký.
• Atomární výrok je vírok bez logickích spojek. Pokud vírok obsahuje logicke spojky nazíví se sloZený.
Nejpouzívanejsí logicke spojky:
1. Negace ... negací vyroku A rozumíme vyrok: "Není pravda, ze platí A".
výrok	negace
aspoň a nejvís a príve a	nejvíse a — 1 aspoň a + 1 nejvíse a — 1 nebo aspoň a + 1
A	-A
1	0
0	1
2. Konjunkce ... spojka „a" (ve smyslu a zároveň) — A A B - konjunkce víyroku je pravdivaí jen v pňrípadňe, ňze jsou prav-divíe oba víyroky
3. Disjunkce ... spojka „nebo" — A V B
- disjunkce vyíroku je pravdivía, je-li pravdivyí asponň jeden z vyroku
4. Implikace ... spojka „jestliže, pak" — A == B
- implikace vyíroku je pravdivía, jen tehdy, je-li pravdivyí víyrok A i B nebo je-li víyrok A nepravdivyí. Implikace je nekomutativní
5. Ekvivalence ... spojka „tehdy a jen tehdy; práve tehdy, když ..." — A <=> B
- ekvivalence víroku je pravdiva, jenom v prípade, ze oba víyroky mají stejnou hodnotu pravdivosti
A	A	B
1	1	1
1	0	0
0	0	1
0	0	0
A	V	B
1	1	1
1	1	0
0	1	1
0	0	0
A	=	B
1	1	1
1	0	0
0	1	1
0	1	0
í vyplyne coko		
A	^	B
1	1	1
1	0	0
0	0	1
0	1	0
1
Priority logických spojek:
1. negace
2. konjunkce a disjunkce
3. implikace a ekvivalence
Tautologie je vždy pravdivý složený výrok, bez ohledu na pravdivostní hodnotu jednotlivých castí takoveho výroku.
Príklady tautologií:
—(a a —a) - zakon o vyloučení třetího (a a —a) == b - zakon Dunse Scota
(a == b) ^ (—b == —a) - Obmena (a == b) <=> (—a v b) —(a == b)     (a a—b) (a <=> b) <=> ((a == b) a (b == a)) (a a b) v c      (a v c) a (b v c) (a v b) a c     (a a c)v (b a c) —(a a b)       — a v—b 1 _ ka —(a v b) ^ —a a — B j De Mořganova přavidla
1. Zapište symbolicky nasledující výroky:
(a) Petr nemí hlad ani žízeň.
(b) Prijde Adam, ale Božena ne.
(c) Půjdu na navstevu ke znamím, nedostanu-li lístek do divadla.
(d) Prijde alespoň jeden z rodicu.
(e) Jestlize prijde matka, tak neprijde otec.
(f) Prijde nejvís jeden z rodicu.
2. Rozhodnete, kterí z uvedeních sdelení jsou víroky. Ke vsem uvedením vyrokum prirad'te jejich pravdivostní hodnotu a vytvorte negaci:
(a) Snezka je nejvyssí hora v Cechích.
(b) Snazte se!
(c) Existuje alespoň jedno sude prvocíslo.
(d) Mars je planeta nejblizsí Slunci.
(e) Prijedete take zítra?
(f) x je vetsí nez 3.
3. Vyjadrete strucne (bez pouzití obratu "není pravda,ze...") negace techto vyroku:
(a) Nemrzne ani nefoukí vítr.
(b) Zustanu-li v Praze, pujdu na vístavu.
(c) Míame pivo a mineraílky.
(d) Osvezím se cajem nebo kavou.
(e) Je mokro, ale neprňsíí.
4. Vysetrete pravdivostní hodnoty techto formulí:
Distributivní zákon
2
(a) p == (q == p)
(b) -(p V q) A (-p == q)
(c) (-p V q)     (p == q)
(d) (-p == q)     (p V q)
5. Rozhodnete, zda dané dvojice výrokových formulí jsou logicky ekvivalentní:
(a) -(p     q),    (p A-q) V (-p A q)
(b) -(p ^ q),    (-p V-q) A (p V q)
6. V dílne pracují tri stroje podle techto podmínek:
(a) Pracuje-li první stroj, pracuje i druhy stroj.
(b) Pracuje druhy nebo tretí stroj.
(c) Nepracuje-li první stroj, nepracuje ani tretí.
Rozhodnete jake jsou možnosti pro praci techto trí stroju.
7. Logicka spojka |, definovana tabulkou pravdivostních hodnot:
A	B	AjB
l	l	O
l	O	l
O	l	l
O	O	l
se nazyva Shefferův symbol. Da se dokazat, že pomocí Shefferova symbolu lze vyjídrit každou z logických spojek A, V, ==, <í=>. Rozhodnete, ktera z uvedených logickích spojek je vyjadrena vztahem:
(a) A|(A|B)
(b) (A|B)|(A|B).
8. Naleznete vyrokovou formuli v promennych A, B, C s nísledující tabulkou pravdivostních hodnot:
A	B	C		
l	l	l		~r
l	l	O		O
l	O	l		O
l	O	O		O
O	l	l		O
O	l	O		l
O	O	l		O
O	O	O		O
Domáci úkol: Petr a Pavel cekají pred kinem na sve spoluzaky Adama, Bret'u a Cyrila. Petr tvrdí: „Prijde-li Adam a Breta, prijde i Cyril."
Pavel ríkí: „Jí myslím, ze kdyz prijde Adam a neprijde Cyril, neprijde ani Bret'a." Na to odpovídí Petr: „To ovsem ríkís totez, co jí." Rozhodnete, zda oba skutecne ríkají totez.
3
9. Vyšetřete, zda uvedené formule jsou tautologie:
(a) p <í=> -p
(b) -(p ^-p)
(c) p V (p ^ -p)
(d) (p == q) == (q == p)
(e) (p == -q)     (-p V -q)
(f) (-p == q)    (p V q).
Predikát (výroková forma) je sdelení, ktere obsahuje jednu nebo více pramenných, za ktere kdyz dosadíme, dostaneme výrok. ZnaCíme ji např. V (x). Promennou take muzeme vazat kvantifikýtorem.
(a) obecný (velký) kvantifikator - symbol obecnosti; znaCíme V. Použití ve smyslu „pro kazde", „pro vsechna", „pro libovolne".
(Vx G R;... — pro vsechna reílna císla platí ...)
(b) ExistenCní (maly) kvantifikítor - znacíme 3. Pouzití ve smyslu „existuje alespoň jedno", „pro alespoň jedno". Nekdy se pouzíva 3! ve smyslu „próve jedno".
(3x G R;... — existuje alespoň jedno x, pro ktere platí ...)
Negace kvantifikovaných sdelení: Obecny kvantifikator nahradíme existencním, existencní obecnyím a podmínku nahradíme její negací.
V x G R; x2 > 0 (nepravda) — 3 x G R; x2 < 0 (pravda)
10. Rozhodnete, zda jsou nísledující formule pravdive v N, Z, R, C.
(a) (Vx)(Vy)(x < y == (3z)(x < z < y))
(b) (Vx)(Vy)(3z)(x + z = y)
(c) (3z)(Vx)(z < x)
(d) (Vx)(Vy)(3z)(z|x A z|y A (Vu)((u|x A u|y) == u|z))
(e) (3x)(Vy)(y + x = x + y = y)
11. Znegujte formule z predesleho príkladu a upravte je do tvaru, ve kterem se bude negace vyskytovat jen u atomickíych formulí.
12. Popiste nísledující formule a diskutujte jejich pravdivost v císelnem oboru N.
(a) kazde císlo je delitelne prvocíslem;
(b) existuje nejmenňsí spoleňcníy níasobek libovolníe dvojice ňcísel.
13. Je mozne zamenit v libovolne formuli predikatove logiky obecní a existencní kvantifikator? Diskutujte obe implikace. Konkretne mejme formuli predikatove logiky se dvema volnymi promennymi f (x, y). Platí (Vx)(3y)f (x, y) ^ (3y)(Vx)f (x, y)? Jako príklad formule f (x, y) uvazujte x < y.
4