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 úsudků. Logika jako filozofická disciplína se intenzivně vyvíjí už od dob antiky, avšak ke skutečnému rozmachu logiky coby součásti matematiky došlo až začátkem 20. století.
í>
Dnes se samozřejmě základní logický kalkulus používá nejen v matematice, ale „stojí" na něm veškeré logické obvody a počítače.
Stručný přehled lekce
*  Výroky v přirozené mluvě a formální výroková logika.
*   Mechanický postup negace výrokových formulí.
*   Neformální zmínka o predikátové logice (a kvantifikátorech).
3etr Hliněný,   Fl MU Brno
IB000: Úvod do Logiky
r
7.1    Výroky v „přirozené" podobě
Definice: V přirozené mluvě za výrok považujeme (každé) tvrzení, o kterém má smysl prohlásit, zeje buď pravdivé nebo nepravdivé.c
Několik příkladů, které z nich jsou výroky?
•   Dnes už v Brně pršelo.u
•   Předmět Fl: IB000 se vyučuje v prvním ročníku.c
•   Platí 2 + 3 = 6.
•   To je bez problémů. (Co?)c
•   Platí x > 3.
•   Pro každé celé číslo x platí, že x > 3.c
Všimněte si, že pravdivost výroku by mělo být možné rozhodnout bez skrytých souvislostí (kontextu), a proto čtvrtý a pátý příklad za výroky nepovažujeme.
Fakt: Z jednoduchých výroků můžeme vytvářet výroky složitější pomocí tzv. logických spojek.
3etr Hliněný.   Fl MU Brno     _______________________________   Fl: IB000: Úvod do Logiky
•   Kateřina přijela ve 12:00 a šli jsme spolu do kina.u
•   Množina {a, 6} má více než jeden prvek a není nekonečná.d
•   Jestliže má Karel přes 90 kilo váhy, nepojedu s ním výtahem.c
•   Jestliže má kráva 10 nohou, mají všechny domy modrou střechu.
Schopnost porozumět takovýmto větám je součást lidského způsobu uvažování a z tohoto hlediska nemá přímou souvislost s matematikou (je to „přirozená logika").
Formální (matematická) logika pak definuje jazyk matematiky a odstraňuje nejednoznačnosti přirozeného jazyka.
3etr Hliněný.   Fl MU Brno     _______________________________   Fl: IB000: Úvod do Logiky
Definice 7.1. Syntaxe výrokové logiky.
Bud 'AT = {A, B,C,...} spočetně nekonečná množina výrokových proměnných (tzv. atomů).
Množina výrokových formulí í> je definována induktivně následujícími pravidly:
(1)  ATC&.C
(2)   Jestliže p, íp € <£, pak také -i(ip) € í> a (p) => (■0) e$.c
(3)   Každý prvek í> vznikne konečně mnoha aplikacemi pravidel (1) a (2).d
Značení: Symbol -> je zván negací a => je nazýván implikací.
Příklady několika správně utvořených formulí:
A,     (A) => (B),      ((A) => (-.(B))) => (h(B)) => (C))c A také příklady několika ne zcela správně utvořených formulí: A =>B,     A=>B=>C,     ~^A=>B
Petr Hliněný,   Fl MU Brno   ____________________________________IB000: Úvod do Logiky
í
Konvence 7.2. Pro zvýšení čitelnosti budeme závorky vynechávat, pokud to nepovede k nejednoznačnostem za předpokladu, že negace -> má „vyšší prioritu" než =>. (Touto úmluvou se nemění množina í>; mění se jen způsob reprezentace jejích prvků.) c Dále si zavedeme, že
*   p\/ip     (disjunkce) je jiný zápis formule     -iip=>ip,íz
*   p Aip     (konjunkce) je jiný zápis formule     _,(_,<r> V -,V0>C
*   p <^ ip     (ekvivalence) je jiný zápis formule     (<£>=> ip) A (ip => p).c
Například formule (-■((A) => (B))) => ((-i(B)) => (C)) se dá s naší konvencí zapsat jako
(A^B)VBVC.
3etr Hliněný,   Fl MU Brno     _______________________________   Fl: IB000: Úvod do Logiky
r
Definice 7.3. Sémantika výrokové logiky.
Valuace (ohodnocení) je funkce v : AT —>■ {true, false}.    Pro každou valuaci v definujeme funkci Sv : í> —>■ {true, false} (vyhodnocení) induktivně takto:
•  SV(Á) = v (A) pro každé A e AT. c
c (      \ _   í  true    jestliže Sv(ip) = false;
•  ö„{-n<p) - j false    jinak
c  ,          i\ — í fa^se    jestliže Sv(<p) = true a <S„(V>) = false;
vW -     f J — i  irue    jjna^
Tvrzení 7.4. Důsledkem této definice je následovné:
•  Sv(<fi V ip) = true     právě když     Sv(<p) = true nebo Sv(ijj) = ŕrue. c
•  Su(ipAip) = true      právě když     cv(<r>) = írue a současně Sv(ijj) = ŕrue.
•  cv((£> <£>• ip) = true    právě když     platí jedna z následujících podmínek
*  Sv(<p) = ŕrue a současně Sv(ijj) = ŕrue,
*  Sv(<p) = false a současně Sv(ijJ) = false.a
Poznámka: Tento předpis podává nejen definici funkce Sv, ale také návod na to, jak ji pro daný argument vypočítat, c
Petr Hliněný,   Fl MU Brn____________________________________Fl: IB000: Úvod do Logiky
Pravdivostní hodnoty
V praxi často vyhodnocení Sv logické výrokové formule zapisujeme do tzv. pravdivostní tabulky. Tato tabulka typicky má sloupce pro jednotlivé proměnné, případné „meziformule" (pomůcka pro snazší vyplnění) a výslednou formuli. Řádků je 2P (počet valuací), kde p je počet použitých proměnných. Místo true, false píšeme 1,0.
Pro naše účely postačí uvést pravdivostní tabulku instruktážním příkladem,   i Příklad 7.5. Jaká je pravdivostní tabulka pro formuli (A => B) V B V C?
A	B	c	A => B	(A=>B)V BvC
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
3etr Hliněný,   Fl MU Brno
D
: IB000: Úvod do Logiky
Definice: Formule p € í> je splnitelná, pokud pro některou valuaci v platí, že
Sv(p) = true.a
Formule p € í> je vždy pravdivá, neboli výroková tautologie, psáno |= (£>, pokud pro každou valuaci v platí, že Sv(p) = true.o
Řekneme, že dvě formule p, íp € í> jsou ekvivalentní, právě když |= t£> <ř» ■0.
Tvrzení 7.6. Několik užitečných tautologií:
iV-.Ac -. -.A ^ Ac
(->5=>-.A) ^(A^ß): (-,A ^(5A -.5)) => A
Kde jsme se s užitím takových tautologií už setkali?
3etr Hliněný,   Fl MU Brno
rl: IB000: Úvod do Logiky
r
7.3    Jak správně „znegovat formuli"?
Přesný význam formulí se zanořenými negacemi je někdy obtížné zjistit (podobně jako v běžné řeči).
„Není pravda, že nemohu neříct, že není pravda, že tě nemám nerad." c
Výrokové formule se proto obvykle prezentují v tzv. normálním tvaru, kde se negace vyskytují pouze u výrokových proměnných, formálně:c
Definice: Formule ip € í> je v normálním tvaru, pokud se v ní operátor negace aplikuje pouze na výrokové proměnné.
Například, pokud přijmeme pravidlo „dvojí negace" (-1-1A <(=> A), tak výše napsanou větu si převedeme na lépe srozumitelný tvar:
„Nemusím říct, že tě mám nerad." c
Tvrzení 7.7. Každou 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. □
•   Pro ilustraci k -*(A =>• B) je ekvivalentní A A -*B,
•   k -.(C A (-.A => B)) je ekvivalentní -.C V (-.A A -.B).
3etr Hliněný.   Fl MU Brn____________________________________Fl: IBOOO: Úvod do Logilo
„Znegováním formule ip" se obvykle myslí převod -tip do normálního tvaru.
Metoda 7.8. Převod formule p do normálního tvaru J7{(p).
Definujeme funkce T a Q pro náš převod induktivními předpisy
T {A)           =   A	É?(A)            =   -A
Fir?)         =   Q{v)	£(-¥>)          =   .Ffc)
H<P^*I>)    =   T{v)^T{$)	g(<p=>ý)  =  ^)A£(vo
%A*)     =   T(v)l\T($)	Ö(^AV)      =    G(¥>)VG(ý)
%Vý)     =   T(v)\lT($)	Ö(^VV)       =    0(¥>)AÍ?(VO
T (#<*$)    =    T(v)<*T(?l>)	Sfa^VO     =     (^)AeW)V(ff^)A^))
Uvažme formuli -i(A => -i(B V -i(C =>	-■A))). Užitím postupu 7.8 získáme:
T(-^(A => -<(B V -.(C => -A))))	=   £(A =>-.(B V-.(C =>-.A)))    =d
^(A) A Ö(-.(B V ^(C => -A)))	=    A A J"(ß V -.(C => -A))
A A (J-(ß) V ^(-.(C => -A)))	=   Aa(BvQ(C ^^A))
A A (B V (.F(C) A 0(-.A)))	=   A A (B V (C A T (A)))
iA(BV(CAi)):	
	^y
Uvedené formální předpisy takto vyjadřují „intuitivní postup negace" v matematicky přesném tvaru. Důkaz tohoto tvrzení je zároveň velmi hezkou ukázkou použití strukturální matematické indukce.
Věta 7.9. Pro libovolnou výrokovou formuli p platí, že
a)  T^p) je jí ekvivalentní formule v normálním tvaru
b)  a G(p) je formule v normálním tvaru ekvivalentní negaci -<p. c
Důkaz povedeme tzv. „indukcí ke struktuře formule", tedy indukci povedeme podle „délky" i - počtu aplikací induktivních pravidel (Definice 7.1) při sestavování formule p. c
•   Báze indukce (í = 0): Pro všechny atomy, tj. výrokové proměnné, zřejmě platí, že F (A) = A je ekvivalentní A a G (A) = ->A je ekvivalentní ->A.
•  V indukčním kroku předpokládejme, že a) i b) platí pro všechny formule p délky nejvýše l. Vezmeme si formuli íp délky £ + 1, která je utvořená jedním z následujících způsobů:
V
'etr Hliněný.   Fl MU Brno
lilBOOO: Úvod do Logiky
*   íp = -líp (= je „definiční rovnítko" pro formule).
Podle výše uvedeného induktivního předpisu je F(ip) = J7{-,f) = G(<f)-Podle indukčního předpokladu pak je G(<p) formule v normálním tvaru ekvivalentní ->ip = íp. c
Obdobně pro funktor Q vyjádříme G(ip) = G{-^<p) = F{<p)- Podle indukčního předpokladu pak je T{íp) formule v normálním tvaru ekvivalentní íp a to je dále ekvivalentní -i-iip = ->íp podle Tvrzení 7.6. c
*   íp = (<pi => íp2).
Podle výše uvedeného induktivního předpisu je ^(ip) = T{ip\ => f 2) = F(<Pi) => T(}pi2)- Podle indukčního předpokladu jsou T{ip\) i T{$2) formule v normálním tvaru ekvivalentní ip\ a ip2- Potom i F(<pi) => T{}P2) je v normálním tvaru dle definice a podle sémantiky => je ta ekvivalentní formuli (ipi => (^2) = íp- c
Obdobně rozepíšeme G(ip) = G(<fi => ^2) = F(<Pi) A G(<f2)- Jelikož A je pro nás jen zkratka, výraz dále rozepíšeme G(ip) = ^{^{'Pi) => ^G{<P2))- Podle indukčního předpokladu (a dvojí negace) jsou F(<pi) a "'GiSPz) po řadě ekvivalentní formulím ip\ a ip2- Tudíž nakonec odvodíme, že G(ip) je ekvivalentní negaci formule ipi => ^2, což jsme zde měli dokázat.
^etr Hliněný,   Fl MU Bri________________________________________IB000: Úvod do Logiky
ip = (lpi V^2)-
Zde si musíme opět uvědomit, že spojka V je pro nás jen zkratka, a přepsat ip = (-i<fi => <f2)- Potom podle předchozích dokázaných případů víme, že F(ip) = f(^fi => ^2) = F{~^Vi) => ^(^2) je ekvivalentní formuli (-i<£i => P2) = ip, což bylo třeba dokázat. Stejně tak G(ip) = Q{~^Lp\ => LP2) = ^(-itfi) AQ((f2) je podle předchozích případů důkazu ekvivalentní (-x^i A -'(^2) = _,V;- c
^ = ((/?i A LP2) a ip = (<fi <^ P2) už dokončíme analogicky.
3etr Hliněný.   Fl MU Brno____________________________________Tl: IB000: Úvod do Logiky
r
7.4    Predikátová logika, kvantifikace
*   Predikátová logika je obecnější než logika výroková; každá formule výrokové logiky je i formulí predikátové logiky, ale ne obráceně.u
*   Predikátová logika pracuje s predikáty. Predikáty jsou „parametrizované výroky", které jsou buď pravdivé nebo nepravdivé pro každou konkrétní volbu parametrů. uVýrokové proměnné lze chápat jako predikáty bez parametrů.u
Pro neformální přiblížení si uvedeme několik ukázek predikátů:
*  x > 3 (parameterem je zde x),c
*   R je ekvivalence na M (parametr i?),c
*   čísla x a y jsou nesoudělná (parametry x,y),
*  obecně psáno P(x,y).
Definice 7.10. Syntaxe i sémantika predikátové logiky.
Z predikátů lze vytvářet predikátové formule pomocí už známých (viz Definice 7.1) výrokových spojek a následujících tzv. kvantifikátorů:
•  \/x . ip     „pro každou volbu parametru x platí formule <p",
•   3x . ip     „existuje alespoň jedna volba parametru x, pro kterou platí <p".
._________Hliněný,   Fl MU Brn____________________________________ Fl: IB000: Úvod do Logiky
Fakt: Je-li každá proměnná v dané formuli kvantifikovaná (tj. formule je uzavřená), pak je celá formule buď pravdivá nebo nepravdivá.u
Konvence 7.11. Pro lepší srozumitelnost zápisu formulí predikátové logiky se domluvíme na následujícím.
*   „Neuzavřené" proměnné vyskytující se v predikátech ve formuli p někdy pro referenci vypisujeme jako „parametry" samotné formule p(x,y,...).
*   Poukud není z kontextu jasné, co lze za daný parametr dosazovat, užívá se notace \/x G M. p a 3x G M. p. (Platí, jen pokud je kvantifikovaný parametr prvkem nějaké fixní množiny!), ľ
*   Tečka za symbolem kvantifikátoru se někdy vynechává (při vhodném uzávorkování formule), nebo se používá symbol „ : ".c
*   Místo Mx\. \/x2 ■ ■ ■ ■ Vxn . p se někdy krátce píše \/x\,X2, ■ ■ ■ ,xn .p. Podobně u existenčního kvantifikátoru 3a;i,X2, ■ ■ ■ ,xn . p.
3etr Hliněný.   Fl MU Brno____________________________________Tl: IB000: Úvod do Logiky
Příklad 7.12. Ukažme si vyjádřeni následujících slovních výroků v predikátové logice:
•   Každé prvočíslo větší než 2 je liché, VnGN.   (Pr(n) A n>2)   =>   Li(n). c
•   Každé číslo n > 1, které není prvočíslem, je dělitelné nějakým číslem y kde n^ y a y > 1,
VnGN.   (n > 1 A -iPr(n) =>   3y . (y| n A n^y A y>l)). c
•   Jsou-li R a S ekvivalence na M, je také RU S ekvivalence na M. Zde například můžeme mít dva pohledy na toto tvrzení-v jednom bereme množinu M za pevnou
VR,S   :   (EqM(R)AEqM(S))   =>   EqM(RUS),
kdežto ve druhém je i množina M parametrem
VMVR,S :   (Eq(M,R)AEq(M,S))  =>  Eq(M,RuS).
D
3etr Hliněný,   Fl MU Brno____________________________________Tl: IB000: Úvod do Logiky
ŕ
Jak „negovat" formule predikátové logiky?
Metoda 7.13. Převod predikátové formule <p do normálního tvaru J7{(p).
Dřívější Metodu 7.8 rozšíříme o následující indukční pravidla:
F{P{xi,...,Xn))       =      P(xi,...,X„)                   Q{P{xi,...,Xn))       =      -nP(xi,...,Xn)
P(Vx . ip)                 =    Vx. T(p>)                  G (y x .p)                 =    3x . G{p)
P(3x. p)                 =    3x.T{p)                  G(3x.p)                 =   Vx.G(p>)c
Uvažme například formuli
-n(VMVi?,S  :   (Eq(M,R)AEq(M,S))  =>  Eq(M,RuS)). Pak
T(^(VMVR,S :   (Eq(M, R) A Eq(M,S))  =>  Eq(M,RuS)))    =
g(VMVR,S : (Eq(M,R)AEq(M,S)) => Eq(M,RuS)) zi3M3R,S : G((Eq(M, R) A Eq(M,S)) => Eq(M,RuS)) 3M 3R, S :   (Eq(M, R) A Eq(M, S) A -nEq(M, RUS)).
Petr Hliněný,   Fl MU Brno____________________________________Tl: IBOOO: Úvod do Logiky