r.
7   Jemný úvod do Logiky
Základem přesného matematického vyjadřování je správné používání (matematické) logiky a logických UsudkU. Logika jako filožoficka disciplína se intenzivně vyvíjí už od dob antiky, avsak ke skutecnemu rozmachu logiky coby soucasti matematiky doslo až začátkem 20. století.
Dnes se samozrejme žakladní logicky kalkulus používa nejen v matematice, ale „stojí na nem veskere logicke obvody a počítače.
Stručný přehled lekce
* Výroky v přirozené mluve a formální výroková logika.
* Mechanický postup negace výrokových formul í.
* Neformaln í zm ínka o predikatove logice (a kvantifikatorech).
Petr Hliněný.  FI MU Brno___FI: IB000: Úvod do Logiky
7.1   Výroky v „přirozené" podobě
Definice: V přirozené mluve za výrok považujeme (každé) tvrzení, o kterém má smysl prohlásit, Zeje bud' pravdive nebo nepravdive.c
Několik príkladU, ktere z nich jsou vyroky?
• Dnes uz v Brne prselo.c
• Predmet FI: IB000 se vyučuje v prvním roCníku.c
• Platí 2 +3 = 6.c
• To je bez problemm. (Co?)c
• Platí x > 3.c
• Pro kazde cele Císlo x platí, ze x > 3.c
Vsimnete si, ze pravdivost vyroku by melo byt mozne rozhodnout bez skrytých souvislostí (kontextu), a proto Ctvrty a paty příklad za vyroky nepovazujeme.
Fakt: Z jednoduchych výroku muzeme vytvíret vyroky slozitejsí pomocí tzv. logických spojek.
Petr Hliněný,  FI MU Brno
ľI: IB000: Úvod do Logiky
r.
Několik dalších príkladu.
• Kateřina prijěla vě 12:00 a šli jšmě špolu do kina.c
• Množina {a, b} mí vícě něžjěděn prvěk a nění někoněCna.c
• Jěštližě ma Karěl přěš 90 kilo vahy, něpojědu š ním výtahem.c
• Jěštližě ma tato krava 10 nohou, mají všechny domy modrou štřěchu.c
Zaštavmě šě na chvíli nad pošlědním výrokěm. Co nam říka? Jě pravdivý? nSkutěCně mají všěchny domy modrou štřěchu a prěd nami štojí krava š 10 nohama?
Schopnošt porozumět takovymto větam jě šoucašt lidškěho žpušobu uvažovaní a ž tohoto hlědiška něma prímou šouvišlošt š matěmatikou (jě to „prirožěna
Formalní (matěmaticka) logika pak děfinujě jažyk matěmatiky a odštraňujě nějědnožnacnošti prirožěněho jažyka.
logika"). c
Petr Hliněný.  FI MU Brno
ľI: IB000: Úvod do Logiky
7.2   (Formální) výroková logika Definice 7.1. Syntaxe výrokové logiký.
Bud' AT = {A,B,C,...} spočetně nekonečná množina výrokových proměnných (tžv. atomU).
Množina výrokových formulí $ je definována induktivně následujícími pravidly:
(1) AT C $. □
(2) Jestliže <p,ip € $, pak take        € $ a (<£•) == (VO € $. □
(3) Každy prvek $ vznikne konečne mnoha aplikacemi pravidel (1) a (2)x
ZnaCení: Symbol - je žvan negaci a == je nažyvan implikaci.
Příklady nekolika spravne utvorených formulí:
A,    (A) == (B),    ((A) == (-(B))) == ((-(B)) == (C ))□ A take příklady nekolika ne žcela spravne utvořenych formulí:
A == B,    A == B == C,    -A == B
Petr Hliněný,  FI MU Brno___FI: IB000: Úvod do Logiky
r.
Konvence 7.2. Pro zvýšení čitelnosti budeme závorky vynechávat, pokud to nepovede k nejednoznačnostem za předpokladu, Ze negace - ma „vyšší prioritu" neZ ==. (Touto Úmluvou se nemení mnoZina $; mení se jen zpUsob reprezentace jejích prvku.) c Dále si zavedeme, ze
* p V p    (disjunkce) je jiný zápis formule    —p == p,c
* p A p    (konjunkce) je jiný zápis formule p V —p),c
* p <4> p    (ekvivalence) je jiná zápis formule    (p == p) A (p == p).c
Například formule (—((A) == (B))) == ((—(B)) == (C)) se dá s nasí konvencá
zapsat jako
(A == B) V B V C
Petr Hliněný,  FI MU Brno
ľI: IB000: Úvod do Logiky
Definice 7.3. Sémantika výrokové logiky.
Valuace (ohodnocení) je funkce v : AT — {true, false}. nPro každou valuaci v definujeme funkci Sv : $ — {true, false} (vyhodnoceni) induktivně takto:
• Sv (A) = v (A) pro každe A e AT. c
Sv (-p) = j
true jestliže Sv(p) = false; false jinak.
, S (p == ///)     <| •        jestliže a
tru jinak.
Tvrzení 7.4. Důsledkem této definice je následovné:
• Sv(p V //) = true    prave když    Sv(p) = true nebo Sv (//) = true. c
• Sv (p A //) = true    práve když    Sv (p) = true a současně Sv (//) = tru c
• Sv(p <ř» //) = true   práve když    platí jedna ž nasledujúcich podmínek
* Sv (p) = true a současne Sv (//) = true,
* Sv(p) = false a současne Sv(//) = false.c
Poznámka: Tento předpis podava nejen definici funkce Sv, ale take navod na to, jak ji pro dany argument vypočítat. c
Petr Hliněný,  FI MU Brno___FI: IB000: Úvod do Logiky
c
Pravdivostní hodnoty
V praxi casto vyhodnocení Sv logické výrokové formule zapisujeme do tzv. pravdivostní tabulky. Tato tabulka typicky ma sloupce pro jednotlive promenne, připadne „meziformule" (pomucka pro snaZSí vyplnení) a výslednou formuli. Radku je 2p (pocet valuací), kde p je pocet pouZitych promennych. Místo true, false píšeme 1,0.
Pro nase ucely postací uvest pravdivostní tabulku instruktaZním příkladem. c Příklad 7.5. Jaká je pravdivostní tabulka pro formuli (A == B) V B V C ?
A	B	C	A =>• B	(A^ B)V BV C
0	0	0	1	1
0	1	0	1	1
1	0	0	0	0
1	1	0	1	1
0	0	1	1	1
0	1	1	1	1
1	0	1	0	1
1	1	1	1	1
□
Petr Hliněný,  FI MU Brno
-I: IB000: Uvod do Logiky
r.
Definice: Formule p € $ je splnitelná, pokud pro některou valuaci v platí, že
Formule p € $ je vždy pravdivá, neboli výroková tautologie, psáno |= p, pokud pro každou valuaci v platí, že Sv(p) = true.c
Řekneme, že dve formule p,ip € $ jsou ekvivalentní, práve když |= p o- -0. c
Tvrzení 7.6. Několik užitečnách tautologií:
• |= A V -A
• |= - -A ^ Ac
• = (A A (A    B)) Bc
• = (-B    -A)     (A B)c
• = (-A    (B A -B)) A
Sv (p) = true.
Kde jsme se s užitím takových tautologií už setkali?
Petr Hliněný,  FI MU Brno
ľI: IB000: Úvod do Logiky
r.
7.3   Jak správně „znegovat formuli"?
Přěšny vyžnam formulí šě žanořěnymi něgacěmi jě někdy obtížně žjištit
„Něn í pravda, žě němohu něríct, žě něn í pravda, žě tě němam něrad." c
Vyrokově formulě šě proto obvyklě prěžěntuj í v tžv. normaln ím tvaru, kdě šě něgacě vyškytuj í použě u vyrokovych proměnnych, formalně:c
Definice: Formulě <p € $ jě v normálním tvaru, pokud šě v n í opěrator něgacě aplikujě použě na vyrokově proměnně.
Například, pokud přijměmě pravidlo „dvoj í něgacě" (——A A), tak vyšě napšanou větu ši prěvěděmě na lěpě šrožumitělny tvar:
„Němuším říct, žě tě mam něrad." c
Tvrzení 7.7. Kazdou výrokou formuli lze převést do normálního tvaru, pokud k == povolíme i užívání odvozených spojek A a V. c
(podobně jako v běžně řěci).
• Pro iluštraci k —(A == B) jě ěkvivalěntn í A A —B,
• k ^ C A (—A == B) jě ěkvivalěntn í —C V (—A A—B).
'etr Hliněný.  FI MU Brno
I: IB000: Úvod do Logiky
Normáln í tvar (formáln í postup)
„Zněgovan ím formulě p" šě obvyklě myšl í přěvod —p do normaln ího tvaru.
Metoda 7.8. Prevod formule p do normáln ího tvaru F(p). Definujeme funktoiy F a Q pro nás převod induktivními předpisy
F (A) = A Q (A) = —A
F(—p) = Q(p) Q(—p) = F(p)
F (p = ý) = F (p) ==F (ý) Q (p = ý) = F (p) AQ(ý)
F (p A ý) = F (p) A F (ý) Q (p A ý) = Q (p) vQ(ý)
F(p V ý)  = F(p) V F(ý)      Q(p V ý)  = Q(p) A Q(ý)
F(p ■ ý) = F(p) ■ F(ý)     Q(p ■ ý) = (F(p) A Q(ý)) V (Q(p) A F(ý))
Uvažmě formuli —(A == —(B V —(C == —A))). Užit ím poštupu 7.8 žíškamě:
F (—(A = —(B V—(C =—A))))   =   Q (A = —(B V—(C = —A)))   = c
F (A) AQ(—(B V—(C = —A))) A A (F (B) V F (—(C = —A))) A A (B V (F(C) A Q(—A))) A A (B V (C A A))c
Petr Hliněný.  FI MU Brno_
A A F (B V—(C == —A))
A A (B V Q (C ==—A)) A A (B V (C A F (A)))
= c
FI: IB000: ývod do Logiký
r.
Uvedene formální predpisy takto vyjadrují „intuitivní postup negace" v matematický přesnem tvaru. Dukaz tohoto tvrzení je zaroveř velmi hezkou ukazkou pouzití strukturalní matematicke indukce.
Veta 7.9. Pro libovolnou výrokovou formuli p platí, ze
a) F (p) je jí ekvivalentní formule v normálním tvaru
b) a G (p) je formule v normalním tvaru ekvivalentni negaci —p. c
Důkaz povedeme tzv. „indukcí ke struktuře formule", tedy indukci povedeme podle „delky" l - poctu aplikací induktivních pravidel (Definice 7.1) pri sestavovaní formule p. c
• Baze indukce (l = 0): Pro vsechny atomy, tj. vyrokove promenne, zrejme
platí, ze F (A) = A je ekvivalentní A a G (A) = —A je ekvivalentní —A. c
• V indukcním kroku předpokladejme, ze a) i b) platí pro vsechny formule p delky nejvyse l. Vezmeme si formuli p delky l +1, ktera je utvořena jedním z nasledujících zpusobu:
Petr Hliněný,  FI MU Brno
FI: IB000: Úvod do Logiky
* 0 = -p ( = je „definiCn í rovn ítko" pro formule).
Podle vyše uvedeneho induktivn ího predpisu je F(0) = F(-p) = G(p). Podle indukCn ího predpokladu pak je G (p) formule v normaln ím tvaru ekvivalentn í -p = 0. c
Obdobne pro funktor G vyjadríme G(0) = G(-p) = F(p). Podle indukCn ího predpokladu pak je F(p) formule v normaln ím tvaru ekvivalentn í p a to je dale ekvivalentn í --p = -0 podle Tvržen í 7.6. c
* 0 = (pi == p2).
Podle výse uvedeneho induktivn ího predpisu je F(0) = F(p1 == p2) = F(p1) == F(p2). Podle indukCn ího předpokladu jsou F(p1) i F(p2) formule v normaln ím tvaru ekvivalentn í p1 a p2. Potom i F(p1) == F(p2) je v normaln ím tvaru dle definice a podle semantiky == je ta ekvivalentn í formuli (p1 == p2) = 0. c
Obdobne rožepíseme G(0) = G(p1 == p2) = F(p1) A G(p2). Jelikož A je pro nas jen žkratka, vyraž dale rožepíseme G(0) = -(F(p1) == -G(p2)). Podle indukCn ího predpokladu (a dvoj í negace) jsou F(p1) a -G(p2) po řade ekvivalentn í formul ím p1 a p2. Tud íž nakonec odvod íme, že G(0) je ekvivalentn í negaci formule p1 == p2, což jsme žde mřeli dokažat.
Petr Hliněný, FI MU Brno_12_FI: IB000: ývod do Logiky
Zde si musíme opet uvedomit, že spojka V je pro nas jen žkratka,
a přepsat p = (-<pi == <p2). Potom podle predčhožíčh dokažanych případu víme, že F(p) = == (£>2) = == F(y>2) je ekvi-
valentní formuli == <p2) = p, což bylo treba dokažat. Stejne tak G(p) = G(—<fi == ¥>2) = AG(<ŕ>2) je podle předchožích prípadu
dukažu ekvivalentní        A -<£>2) = -p. □
* p =      A (£>2) a p = ((pi ^ (p2) už dokoncíme analogicky.
□
Petr Hliněný,  FI MU Brno
FI: IB000: ývod do Logiky
7.4   Predikátová logika, kvantifikace
* Predikýtový logika je obecnejsí nez logika výroková; kazdí formule vyrokove logiky je i formulí predikítove logiky, ale ne obrícenex
* Predikátová logika pracuje s predikýtý. Predikíty jsou „parametrizovane víroky", ktere jsou bud' pravdive nebo nepravdive pro kazdou konkretní volbu parametru. Vyrokove promenne lze chípat jako predikíty bez parametru.c
Pro neformalní priblízení si uvedeme nekolik ukazek predikatu:
* x > 3 (parameterem je zde x),c
* R je ekvivalence na M (parametr R),c
* císla x a y jsou nesoudelna (parametry x, y),
* obecne psíno P (x,y).c
Definice 7.10. Syntaxe i semantika predikátove logiky.
Z predikítu lze vy^ret predikýtove formule pomocí uz známych (viz Definice 7.1) vírokovych spojek a nísledujících tzv. kvantifikýtorU:
• Vx . (p    „pro kazdou volbu parametru x platí formule (£>",
• 3x . (p    „existuje alespoř jedna volba parametru x, pro kterou platí p".
Petr Hliněný,  FI MU Brno___FI: IB000: ývod do Logiky
r.
^
Fakt: Je-li kaZda promenna v dane formuli kvantifikovana (tj. formule je uzavřená), pak je cela formule bud' pravdiva nebo nepravdiva.c
Konvence 7.11. Pro lepsí srozumitelnost zapisu formul í predikatove logiky se domluv íme na nasleduj íc ím.
* „Neuzavrene" promenne vyskytuj ící se v predikatech ve formuli <p nekdy pro referenci vypisujeme jako „parametry" samotne formule <f(x,y,... ).c
* Poukud nen í z kontextu jasne, co lze za dany parametr dosazovat, uz íva se notace Vx € M .<p a 3x € M. <p. (Plat í, jen pokud je kvantifikovany parametr prvkem nejake fixn í mnoziny!). c
* Tecka za symbolem kvantifikatoru se nekdy vynechava (při vhodnem uzavorkovan í formule), nebo se pouz íva symbol, : "c
* M ísto Vxi. Vx2 . • • • Vxn . <p se nekdy kratce p íse Vxi, x2, • • • , xn(<p). Podobne u existencn ího kvantifikatoru 3x1,x2, ••• , xn(y>).
Petr Hliněný,  FI MU Brno
FI: IB000: UUvod do Logiky
Príklad 7.12. Ukažme si vyjádření následujících slovních výroků v predikátové logice:
• Každe prvocíslo vetsí než 2 je l ich e,
Vn G N . (Pr(n) A n>2) == Li(n). c
• Každe císlo n > 1, ktere není prvocíslem, je delitelne nejakym císlem y kde n = y
a y > 1,
Vn G N . (n > 1 A-Pr(n)) => 3y(y| n A n=y A y>l). c
• Jsou-li R a S ekvivalence na M, je take R U S ekvivalence na M.
Zde napríklad mužeme mít dva pohledy na toto tvržení- v jednom bereme množinu M ža pevnou
VR, S :  (EqM(R) A EqM(S))        EqM(RUS),
kdežto ve druhem je i množina M parametrem
V M VR, S : (Eq(M,R) A Eq(M,S))       Eq(M,RuS).
□
Petr Hliněný.  FI MU Brno
I: IB000: Úvod do
Logiky
Jak „negovat" formule predikatove logiky?
Metoda 7.13. Prevod predikatove formule p do normalního tvarú F(p). Dřívejší Metodu 7.8 rozšírime o následující indukční pravidla:
F (P (xi ,...,Xn))     =    P (x1,...,Xn) G(P (xi ,...,Xn))     =    -P (x1 ,...,Xn)
F (Vx . p) =   Vx . F (p) G(Vx.p) =   3x . G(p)
F (3x . p) =   3x . F (p) G(3x.p) =   Vx . G(p)c
Uvažme například formuli
-(VM VR,S : (Eq(M,R) A Eq(M, S)) == Eq(M, RUS)).
Pak
F(-(VM VR,S : (Eq(M,R) A Eq(M,S)) == Eq(M, RUS))) cG(VM VR,S : (Eq(M,R) A Eq(M, S)) == Eq(M, RUS)) □3M 3R,S : G((Eq(M,R) A Eq(M, S)) == Eq(M, RUS)) 3M 3R,S : (Eq(M,R) A Eq(M, S) A —Eq(M, RUS)).
Petr Hliněný.  FI MU Brno
FI: IB000: Úvod do Logiky