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 základní logický kalkulus používá nejen v čisté matematice, ale „stojí" na něm také 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).
Petr Hliněný, Fl MU Brno, 2011
1/17
Fl: IB000: Úvod do Logiky
7.1   Výroky v přirozené podobě
Prvním úkolem našeho výukového materiálu je vytvořit pevný „most" mezi přirozenou lidskou mluvou a formálním jazykem matematiky.
Definice: V přirozené mluvě za výrok považujeme (každé) tvrzení, o kterém má smysl prohlásit, že je bud' pravdivé nebo nepravdivé.c
Ukážeme si několik příkladů - které z nich jsou výroky?
• Dnes už v Brně pršelo.c
• Předmět Fl: IB000 se vyučuje v prvním ročníku.c
• Platí 2 + 3 = 6.c
• 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.
• Z více jednoduchých výroků vytváříme výroky složitější pomocí tzv. logických spojek.
Petr Hliněný, Fl MU Brno, 2011
2/17
Fl: IB000: Úvod do Logiky
Nasleduje několik dalších příkladů.
• Kateřina přijela ve 12:00 a šli jsme spolu do kina.c
• Množina {a, b} má více než jeden prvek a není nekonečná.c
• Jestliže má Karel přes 90 kg váhy, nejedu s ním výtahem.c
• Jestliže má tato kráva 10 nohou, mají všechny domy modrou střechu.c
Zastavme se na chvíli nad posledním výrokem. Co nám říká? Je pravdivý? Skutečně mají všechny domy modrou střechu a před námi stojí kráva s 10 nohama?
Přirozené vs. formální
• Schopnost porozumět podobným 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").c
• Formální (matematická) logika pak v podobném duchu definuje jazyk matematiky a přitom odstraňuje nejednoznačnosti přirozeného jazyka.
Petr Hliněný, Fl MU Brno, 2011
3/17
Fl: IB000: Úvod do Logiky
7.2   Formální výroková logika Definice 7.1. Syntaxe výrokové logiky.
Buď 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) AT C $. c
(2) Jestliže ip, V> £     pak také -.(</?) G $ a (</?)     (-0) é$.c
(3) Každý prvek <í> vznikne konečně mnoha aplikacemi pravidel (1) a (2).c
Značení: Symbol —■ je zván negácia =4> je nazýván implikací.
Příklady několika správně utvořených formulí:
A,    (A) => (B),    ((A) => (^(B))) => ((-■(£)) => A také příklady několika ne zcela správně utvořených formulí:
A^B,    -iA =4> B
Petr Hliněný, Fl MU Brno, 2011
4/17
Fl: 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ů.)
Dále si zavedeme, že
* ipVip    (disjunkce) je jiný zápis formule    -np =4> tp,\z
* tp Aip    (konjunkce) je jiný zápis formule V ~'V')>I=
* ip 44> V    (ekvivalence) je jiný zápis formule    (ip     ip) A (ip </?).c
Například formule (-((A) (B))) => ((->(B)) => (C)) se dá s naší konvencí zapsat jako
(A^B)VBVC.
Petr Hliněný, Fl MU Brno, 2011
5/17
Fl: IB000: Úvod do Logiky
Definice 7.3. Sémantika výrokové logiky.
Valuace (ohodnocení) je funkce v : ÄT —> {true, falše}. Pro každou valuaci v definujeme funkci Sv : í> —> {true, falše} (vyhodnocení) induktivně takto:
• SV(A) = u{A) pro každé A e ÄT. c
Poznámka: Tento předpis podává nejen definici funkce Sv, ale také návod na to, jak ji pro daný argument vypočítat.
Tvrzení 7.4. Důsledkem Definice 7.3 je následovné:
• Sv(ip V V>) = true    právě když    Sv((p) = true nebo Sv(ip) = trne. c
• Sv((p/\Tp) = tme     právě když    Sv((p) = true a současně Sv(ip) = trua
• Su(ip 44> V) = true   právě když    platí jedna z následujících podmínek
* Sv(ip) = tme a současně Sv(ip) = true,
* Sv(ip) = false a současně Sv(ip) = false.
true   jestliže Sv(ip) — false:
false   jestliže Sv(ip) — true a Sv(ip) — false:
c
c
Petr Hliněný, Fl MU Brno, 2011
6/17
Fl: IB000: Úvod do Logiky
Pravdivostní tabulky
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 trne, falše píšeme 1,0.
Pro naše účely postačí uvést pravdivostní tabulku instruktážním příkladem. Příklad 7.5. Jaká je pravdivostní tabulka pro formuli (A =>• B) V B V C?
A	B	c	A B	(A     B) V B V 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ý, Fl MU Brno, 2011
7/17
Fl: IB000: Úvod do Logiky
Definice: Formule ip G 3> je splnitelná, pokud pro některou valuaci v platí, že
Sv{ip) = trne. c
Formule </? G 3> je vždy pravdivá, neboli výroková tautologie, psáno |= ip, pokud pro každou valuaci v platí, že Sv{ip) = true.n
Řekneme, že dvě formule <p,ip & & jsou ekvivalentní, právě když |= <p 44> tp. c
Tvrzení 7.6. Několik užitečných tautologií:
A V -iA ->->A Ac (AA(A^B))^Bc {^B     -iA)     (A B)c
(nA^(BAnfi)) A
Kde jsme se s užitím takových tautologií už setkali? A jak poznáme tautologii v pravdivostní tabulce?
Petr Hliněný, Fl MU Brno, 2011
8/17
Fl: IB000: Úvod do Logiky
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).c
„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ě:
Definice: Formule ip G 3> 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" (-> •<=> 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 =4> povolíme i užívání odvozených spojek A a V. c
• Pro ilustraci k ^(A =>• B) je ekvivalentní A A ^B,
• k -.(C A (^A => B)) je ekvivalentní      V (^A A -tB).
Petr Hliněný, Fl MU Brno, 2011
9/17
Fl: IB000: Úvod do Logiky
Normální tvar (formální postup)
„Znegováním formule ip" se obvykle myslí převod -np do normálního tvaru.
Metoda 7.8. Převod formule ip do normálního tvaru F{ip). Definujeme funktory F a Q pro náš převod induktivními předpisy
F(A) =  A g (A) =
f^)     = g(ip) g^ip)     = Fiip)
T(ip^Tp)   =   F(ip)^F(ijj) G(<p^ý)   = ^)A5(ií)
^(yAV)    =   F(tp)AF(ý) g(ifAib)    = G(<p)VG($)
F(ipVib)    =  F(tp)VF(ý) G&Vý)    = G(<p)AG(tI>)
Uvažme formuli -n(A =í> -n(i3 V -n(C =^ ^
ř(-.(i4^n(flVn(C7=^nA)))) =
T-(A) A V -(C     -A))) =
iA(J(B)VJHC^^))) AA(BV(7(C)AM) A A (B V (CA A))
). Užitím postupu 7.8 získáme:
iAJ(BV-(C^^)) = □
iA(BV(CAJ(i)))
Petr Hliněný,  Fl MU Brno, 2011
10/17
Fl: IB000: Úvod do Logiky
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) F{p) je ekvivalentní formule k tp v normálním tvaru
b) a G{p) je formule v normálním tvaru ekvivalentní negaci -np. c
Důkaz povedeme tzv. „indukcí ke struktuře formule", tedy indukci povedeme podle „délky" £ - počtu aplikací induktivních pravidel (Definice 7.1) při sestavování formule ip. c
• Báze indukce {£ = 0): Pro všechny atomy, tj. výrokové proměnné, zřejmě platí, že F{Ä) = A je ekvivalentní A a G (A) = -A je ekvivalentní -iA c
• V indukčním kroku předpokládejme, že a) i b) platí pro všechny formule p délky nejvýše i. Vezmeme si formuli tp délky £ + 1, která je utvořená jedním z následujících způsobů:
Petr Hliněný,  Fl MU Brno, 2011
11/17
Fl: IB000: Úvod do Logiky
* ip = -op ( = je „definiční rovnítko" pro formule).
Podle výše uvedeného induktivního předpisuje F{ip) = F{-^p) = Q{p). Podle indukčního předpokladu pak je Q{p) formule v normálním tvaru ekvivalentní —np = ip. c
Obdobně pro funktor Q vyjádříme Q{ip) = Q{~^p) = F{p). Podle indukčního předpokladu pak je F{p) formule v normálním tvaru ekvivalentní p a to je dále ekvivalentní -i-k/j = -iip podle Tvrzení 7.6. c
* tp = (p1^ p2).
Podle výše uvedeného induktivního předpisu je F{ip) = F{p\ =4> p2) = F{pi) F{p2). Podle indukčního předpokladu jsou F{p\) i F{p2) formule v normálním tvaru ekvivalentní p\ a p2. Potom i F{p\) =4> F{p2) je v normálním tvaru dle definice a podle sémantiky =4> je ta ekvivalentní formuli {p\ =4> p2) =ip. c
Obdobně rozepíšeme Q{ip) = í?(</?i =^ </>2) = •7r(</'i) A ^(^2)- Jelikož A je pro nás jen zkratka, výraz dále rozepíšeme Q{ip) = ~^{F{pi) =4> -it/((/?2))- Podle indukčního předpokladu (a dvojí negace) jsou F{p\) a -<G(p2) po řadě ekvivalentní formulím p\ a p2. Tudíž nakonec odvodíme, že Q{ip) je ekvivalentní negaci formule p\ =4> p2, což jsme zde měli dokázat.
Petr Hliněný,  Fl MU Brno, 2011
12/17
Fl: IB000: Úvod do Logiky
* V> = (tpi v ip2).
Zde si musíme opět uvědomit, že spojka V je pro nás jen zkratka, a přepsat ip = (-<tpi ipz)- Potom podle předchozích dokázaných případů víme, že J-{ip) = J-{—np\ =4> ^2) = •7r(_,(/>i) =** ^(^2) je ekvivalentní formuli (-></?i (^2) = "0. c°ž bylo třeba dokázat. Stejně tak G(ip) = G(~«pi (^2) = •7r(_,(/'i) A^((/?2) Je podle předchozích případů důkazu ekvivalentní (—^pi A -x/^) = _,V'- c
* ip = (</>i A ÍP2) a V = (</>i ^ V2) už dokončíme analogicky.
Petr Hliněný,  Fl MU Brno, 2011
13/17
Fl: IB000: Úvod do Logiky
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ě.
* Predikátová logika pracuje s predikáty. Predikáty jsou „parametrizované výroky", které jsou bud' pravdivé nebo nepravdivé pro každou konkrétní volbu parametrů. nVýr. prom. lze chápat jako predikáty bez parametrů.c
Pro neformální přiblížení si uvedeme několik ukázek predikátů:
* x > 3 (parameterem je zde x e R),c
* R je ekvivalence na M (parametr R C M x M),c
* čísla x a y jsou nesoudělná (parametry x, y E N),
* obecnejšou predikáty psány P (x, y), kde x, y jsou libovolné parametry.c
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. tp    „pro každou volbu parametru x platí formule </?",
• 3x. tp    „existuje alespoň jedna volba parametru x, pro kterou platí </?".
Petr Hliněný,  Fl MU Brno, 2011
14/17
Fl: IB000: Úvod do Logiky
Fakt: Je-li každá proměnná - parametr predikátu - v dané formuli kvantifikovaná (tj. formule je uzavřená), pak je formule bud' pravdivá nebo nepravdivá.c
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,... ).c
* Poukud není z kontextu jasné, co lze za daný parametr dosazovat, užívá se notace Vx 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 „ : ".□
* Místo Va?i. Va?2 . • • • Vxn . p se někdy krátce píše Vx±,X2, ■ ■ ■ ,xn (p). Podobně u existenčního kvantifikátoru 3xi,X2,--- ,xn (p).
Petr Hliněný,  Fl MU Brno, 2011
15/17
Fl: IB000: Úvod do Logiky
Příklad 7.12. Ukažme si vyjádření následujících slovních výroků v predikátové logice:
• Každé prvočíslo větší než 2 je liché;
Vn G N . (Pr(n) A n>2)       Lí(n). c
• Každé číslo n > 1, které není prvočíslem, je dělitelné nějakým číslem y kde y
a y > 1;
Vn G N . (n > 1 A -<Pr(n)) =>■ 3y(y\n An^y Ay>í). 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
VMVi?,^ : (Eq(M, R) A Eq(M, S)) => Eq(M,RUS).
C
Petr Hliněný,  Fl MU Brno, 2011
16/17
Fl: IB000: Úvod do Logiky
Jak „negovat" formule predikátové logiky?
Na závěr jen stručně rozšíříme výše uvedenou metodu formálního negování.
Metoda 7.13. Převod predikátové formule p do normálního tvaru F{p). Dřívější Metodu 7.8 rozšíříme o následující indukční pravidla:
J:{P{x1,...,xn))   =   P(xi,...,xn) Q(P(xi,...,xn))   =   ^P(xi,... ,xn)
F{y/x.ip) —   \fx. F{p) Q(\fx.p) — 3x.Q{p)
J7(3x. (p) —   3x . ^{p) Q(3x.p) — \/x.Q(p)c
Uvažme například negaci výše uvedené formule
-n(VMViž,5 : {Eq{M, R) A Eq{M, S)) => Eq(M,RUS)).
Pak
J"HVM \/R,S : (Eq(M, R) A Eq{M, S)) => Eq(M,RUS))) = □£(VMViž,S : {Eq{M, R) A Eq{M, S)) => Eq(M,RUS)) n3M3R,S : Q{{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ý,  Fl MU Brno, 2011
17/17
Fl: IB000: Úvod do Logiky