1   Základní formalismy matematiky
Motivace: Studium informatiky neznamená jen „naučit se nějaký programovací jazyk", nýbrž zahrnuje celý soubor dalších relevantních předmětů, mezi nimiž najdeme i matematicko-teoretické (formální) základy moderní informatiky, c
Náplní první lekce našeho předmětu pak je právě studenty do potřebných matematických formalismů uvést a dát jim tak první ochutnávku „matematiky vysokoškolské úrovně". Tato matematika je (možná na rozdíl od vaší dosavadní středoškolské zkušenosti) založena na přesném formálním vyjadřování a chápání a na rigorózním úsudku podloženém poctivou matematickou logikou, c
Stručný přehled lekce
* Pochopení přirozeného i formálního zápisu a významu matematických tvrzení (vět) a jejich důkazů.
* Rozbor logické struktury matematických vět, potřebné úrovně formality a diskuse konstruktivnosti důkazů.
* Pojem výroku a základy výrokové logiky. Velmi jemný úvod do matematické logiky.
Petr Hliněný, Fl MU Brno, 2014
1/21
Fl: IB000: Základní formalismy
:f—;-
1.1   Uvod do matematického dokazování
Matematika (a tudíž i teoretická informatika jako její součást) se vyznačuje velmi přísnými formálními požadavky na korektnost argumentace, c
• Uvažme matematickou větu (neboli tvrzení) tvaru
„Jestliže platí předpoklady, pak platí závěr", c
• Důkaz této věty je konečná posloupnost tvrzení, kde
každé tvrzení je bud'
- předpoklad, nebo
- obecně přijatá „pravda" - axiom, nebo
- plyne z předchozích a dříve dokázaných tvrzení podle nějakého „akceptovaného" logického principu - odvozovacího pravidla;
* poslední tvrzení je závěr, c
0 potřebné úrovni formality matematických důkazů a o běžných důkazových technikách se dozvíme dále v této a příští lekci.. .
Nyní si jen celou problematiku uvedeme názornými příklady.
Petr Hliněný, Fl MU Brno, 2014
2/21
Fl: IB000: Základní formalismy
Příklad 1.2. Uvažujme následující matematické tvrzení (které jistě už znáte).
Věta. Jestliže x je součtem dvou lichých čísel, pak x je sudé. Poznámka pro připomenutí:
- Sudé číslo je celé číslo dělitelné 2, tj. tvaru 2k.
- Liché číslo je celé číslo nedělitelné 2, tj. tvaru 2k + 1. c
Důkaz postupuje v následujících formálních krocích: tvrzení zdůvodnění
1)	a	= 2k + 1, k celé	předpoklad
2)	b	= 21 + 1, l celé	předpoklade
3)	X	= a + b = 2k + 2l + l + l	1,2) a komutativita sčítání (axiom)c
4)	X	= 2{k + l) + 2-l	3) a distributivnost násobenie
5)	X	= 2{k + l + l)	4) a opět distributivnost násobenie
6)	X	= 2m, m celé	5)am = fc + Z + lje celé číslo (axiom)
□
Petr Hliněný, Fl MU Brno, 2014
3/21
Fl: IB000: Základní formalismy
Příklad 1.3. Dokažte následující tvrzení:
Věta. Jestliže x a y jsou racionální čísla pro která platí x < y, pak existuje racionální číslo z pro které platí x < z < y.
Důkaz po krocích (s již trochu méně formálním zápisem) zní:
1) Nechť z = ^ =x+'^ =y-y^.
2) Číslo zje racionální, neboť x a y jsou racionální.
3) Platí z > x, neboť ^ > 0.
4) Dále platí z < y, neboť opět ^ > 0.
5) Celkem x < z < y.
□
Petr Hliněný, Fl MU Brno, 2014
4/21
Fl: IB000: Základní formalismy
1.2   Význam matematických vět
• První krok formálního důkazu je uvědomit si, co říká věta, která se má dokázat; tedy co je předpoklad a co závěr dokazovaného tvrzení. Pravdivost takového tvrzení pak je třeba chápat v následujícím významu:
Pro každou situaci, ve které jsou splněny všechny předpoklady, je platný i závěr tvrzení.^
• Příklady běžné formulace matematických vět:
* Konečná množina má konečně mnoho podmnožin.c
* sin2(a) +cos2(a) = l.c
* Graf je rovinný, jestliže neobsahuje podrozdělení      nebo K^^.t.
• Co přesně nám uvedené matematické věty říkají?
Často pomůže pouhé rozepsání definic pojmů, které se v dané větě vyskytují.
• Všimněte si také, jaký je správný logický význam matematického tvrzení vysloveného touto formou implikace („jestliže ... , pak .. . "). Především, pokud předpoklady nejsou splněny nebo jsou sporné, tak celé tvrzení je platné bez ohledu na pravdivost závěru!
Petr Hliněný, Fl MU Brno, 2014
5/21
Fl: IB000: Základní formalismy
O pravdivosti implikace
Příklad 1.4. Je pravdivé následující matematické tvrzení?
Věta. Mějme dvě kuličky, červenou a modrou. Jestliže červená kulička je těžší než modrá a zároveň je modrá kulička těžší než ta červená, tak jsou obě kuličky ve skutečnosti zelené, c
„ To přece nemůže být pravda, jak může být jedna kulička těžší než druhá a naopak zároveň? Jak mohou být nakonec obě zelené? To je celé nějaká blbost... "c
Ano, výše uvedené jsou typické laické reakce na uvedenou větu. Přesto však tato věta pravdivá je!
Stačí se vrátit o kousek výše ke kritériu - Pro každou situaci, ve které jsou splněny všechny předpoklady, je platný i závěr tvrzení - které je zjevně naplněno. Nenaleznete totiž situaci, ve které by byly splněny oba předpoklady zároveň, a tudíž ve všech takových neexistujících situacích si můžete říkat cokoliv, třeba že kuličky jsou zelené. □
Petr Hliněný, Fl MU Brno, 2014
6/21
Fl: IB000: Základní formalismy
Příklad 1.5. Anna a Klára přišly na přednášku a usadily se do lavic. Proč je pravdivé toto matematické tvrzení?
Věta. Jestliže Anna sedí v první řadě lavic a zároveň Anna sedí v poslední řadě lavic, tak Klára nesedí v druhé řadě lavic, c
Opět je třeba se hluboce zamyslet nad významem předpokladů a závěru, ale tentokrát není situace předpokladů tak triviálně sporná, jako v Příkladu 1.4. Kdy tedy nastávají oba předpoklady zároveň? Když první řada lavic je zároveň řadou poslední! Neboli posluchárna má jen (nejvýše) jednu řadu lavic a Klára tudíž v druhé řadě nemůže sedět. Důkaz je hotov. □
Petr Hliněný, Fl MU Brno, 2014
7/21
Fl: IB000: Základní formalismy
1.3   Struktura matematických vět a důkazů
Jak „moc formální" mají správné matematické důkazy vlastně být?
• Záleží na tom, komu je důkaz určen — konzument musí být schopen „snadno" ověřit korektnost každého tvrzení v důkazu a plně pochopit, z čeho vyplývá.
• Je tedy hlavně na vás zvolit tu správnou úroveň formálnosti zápisu vět i důkazů podle situace, c
A jak na ten správný matematický důkaz máme přijít?
• No. .., nnalézání matematických důkazů je tvůrčí činnost, která není vůbec snadná a vyžaduje od vás přímo „umělecké" vlohy. Přesto se jí alespoň trochu musíte přiučit.
Petr Hliněný, Fl MU Brno, 2014
8/21
Fl: IB000: Základní formalismy
Dokazovat či vyvracet tvrzení?
Představme si, že našim úkolem je rozhodnout platnost matematického tvrzení. Jak matematicky správně zdůvodníme svou odpověď?
• Záleží na odpovědi samotné. .. c
• Pokud je to ANO, prostě podáme důkaz tvrzení podle uvedených zvyklostí.
• Pokud je odpověď NE, tak naopak podáme důkaz negace daného tvrzeníx
Poměrně častým případem pak je matematická věta T, která tvrdí nějaký závěr pro širokou oblast vstupních možností. Potom platí následující:::
• Pokud T je pravdivá, nezbývá než podat vyčerpávající důkaz platnosti pro všechny vstupyx
• Avšak pokud T je nepravdivá, stačí „uhodnout" vhodný vstupní protipříklad a jen pro něj dokázat, že závěr tvrzení není platný.
Petr Hliněný, Fl MU Brno, 2014
9/21
Fl: IB000: Základní formalismy
Příklad 1.6. Rozhodněte platnost následujícího tvrzení: Pro všechna reálná x platí
x2 + 3x + 2 > O.c
Důkaz: Standardními algebraickými postupy si můžeme upravit vztah na x2 + 3x + 2 = {x + 1) • {x + 2) > 0. Co nám z něj vyplývá? Například to, že k porušení daného tvrzení stačí volit x tak, aby jedna ze závorek byla kladná a druhá záporná. To nastane třeba pro x = —|. c
Pro vyvrácení tvrzení nám tedy stačí začít volbou protipříkladu x = — | (není nutno zdůvodňovat, jak jsme jej „uhodli"!) a následně dokázat úpravou
x2+3x + 2 = {x + 1).{x + 2) = (_3 + 1).(_3+2) = (-!).(+!) = -\<0.n Dané tvrzení není platné. a
Petr Hliněný,  Fl MU Brno, 2014
10/21
Fl: IB000: Základní formalismy
Konstruktivní a existenční důkazy
Z hlediska praktické využitelnosti je potřeba rozlišit tyto dvě kategorie důkazů (třebaže z formálně-matematického pohledu mezi nimi kvalitativní rozdíl není).
• Důkaz Věty 1.3 je konstruktivní. Dokázali jsme nejen, že číslo z existuje, ale podali jsme také návod, jak ho pro dané x a y sestrojit.
• Existenční důkaz je takový, kde se prokáže existence nějakého objektu bez toho, aby byl podán použitelný návod na jeho konstrukci, c
Příklad 1.7. čistě existenčního důkazu.
Věta. Existuje program, který vypíše na obrazovku čísla tažená ve 45. tahu
sportky v roce 2014. c Důkaz: Existuje pouze konečně mnoho možných výsledků losování 45. tahu sportky v roce 2014. Pro každý možný výsledek existuje program, který tento daný výsledek výpise na obrazovku. Mezi těmito programy je tedy jistě ten, který vypíše právě ten výsledek, který bude ve 45. tahu sportky v roce 2014 skutečně vylosován, c a
To je ale „podvod", že? nA přece není... Formálně správně to je prostě tak a tečka.
Petr Hliněný,  Fl MU Brno, 2014
11/21
Fl: IB000: Základní formalismy
1.4   Výroky a základ logiky
• Pojem výroku se dá považovat za důležitý „pevný most" mezi běžnou mluvou a přesným matematickým formalismem.
Definice 1.8. Výrok v přirozené mluvě:
V běžné mluvě za výrok považujeme (každé) tvrzení, o kterém má smysl platně prohlásit, že je bud' pravdivé nebo nepravdivé.
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.
Petr Hliněný,  Fl MU Brno, 2014
12/21
Fl: IB000: Základní formalismy
* Z více jednoduchých výroků vytváříme výroky složitější pomocí tzv. logických spojek.
Následuje několik dalších příkladů.
• 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, pak mají všechny domy modrou střechu.
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? c
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, 2014
13/21
Fl: IB000: Základní formalismy
1.5   Střípky matematické logiky
Všimněte si, že podle Definice 1.8 každému výroku běžné mluvy můžeme přiřadit logickou hodnotu 0 (falše) nebo 1 (true) a dále se nestarat o jazykový význam. ..
Proto (jazykové) výroky v matematice vyjádříme výrokovými proměnnými, které značíme velkými písmeny A, B,C,... a přiřadíme jim hodnotu 0 nebo 1. c
Definice: Výroková formule (značíme </?, a, tp,...) vzniká z výrokových proměnných pomocí závorek a logických spojek -> negace a =4> implikace.c
Zároveň používáme v zápise následujících zkratek
* ip V tp    (disjunkce/„nebo") je jiný zápis formule    -np =4> tp,\z
* tpAip    (konjunkce/„a") je jiný zápis formule    -<(-iíp V-np),c
* ip 44> V    (ekvivalence) je jiný zápis formule    (ip     ip) A (ip </?).c
Při zápise výrokových formulí je potřeba dávat pozor na správné závorkování, aby formule měla jednoznačný význam. Na intuitivní úrovni to ilustrujeme takto:
Správně A,    (A) =>• (B),    A^>B,   ^A^>B, AVBV^C
a nesprávně    A => B => C   — znamená to (A => B) => C nebo A => (B => C)l
Petr Hliněný,  Fl MU Brno, 2014
14/21
Fl: IB000: Základní formalismy
Definice 1.9. Sémantika (význam) výrokové logiky.
Nechť valuace (ohodnocení) je funkce v : Prom —> {0,1} na všech (dotčených) výrokových proměnných. Pro každou valuaci v definujeme funkci Sv(a), vyhodnoceníformule <r, induktivně (tj. po krocích) takto:
• SV{Ä) = v{A) pro každé A G Prom. c
Tvrzení 1.10. Důsledkem Definice 1.9 je následovně:
• Su(ip V V>) = 1    právě když    Sv(tp) = 1 nebo Sv{ip) = 1. c
• Sv(tp A tp) = 1     právě když    Sv(tp) = 1 a současně Sv{ip) = 1.
• Sv(tp 44> V) = 1   právě když    platí jedna z následujících podmínek
* Sv(tp) = 1 a současně Sv{ip) = 1,
* Sv(tp) = 0 a současně Sv{ip) = 0.
1 jestliže Sv((p) — 0; 0 jinak.
0   jestliže Sv((p) — la Sv(i/)) — 0;
c
c
Petr Hliněný,  Fl MU Brno, 2014
15/21
Fl: IB000: Základní formalismy
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.
Příklad 1.11. Jaká je pravdivostní tabulka pro formuli {A =4> 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, 2014
16/21
Fl: IB000: Základní formalismy
Splnitelnost formulí a tautologie
Definice: Formule ip G 3> je splnitelná, pokud pro některou valuaci v platí, že
Su(<p) = lx
Formule </? G 3> je vždy pravdivá, neboli výroková tautologie, psáno |= ip, pokud pro každou valuaci v platí, že Sv{ip) = lx
Řekneme, že dvě formule </?, V £ í> jsou ekvivalentní, právě když |= ip 4^ V- c
Tvrzení 1.12. Následující formule jsou tautologiemi:
A V -iA ->->A Ac (AA(A^B))^Bc {^B     -iA)     (A B)c
(nA^(BAnfi)) A
Jak poznáme tautologii v pravdivostní tabulce?
Petr Hliněný,  Fl MU Brno, 2014
17/21
Fl: IB000: Základní formalismy
Kvantifikace a predikátová logika
Výše popsaná výroková logika je velmi omezená faktem, že každý výrok musí být („absolutně") vyhodnocen jako pravda nebo nepravda.
* 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 (parametrem je zde x e R),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: Z predikátů lze vytvářet predikátové formule pomocí už známých 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í </?".□
Pozorného čtenáře napadne, ze které množiny že „volíme parametr x"l
To je v matematické logice obvykle implicitní (řečeno mimo samotnou formuli).
Petr Hliněný,  Fl MU Brno, 2014
18/21
Fl: IB000: Základní formalismy
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á.
Příklad 1.13. Ukažme si vyjádření násl. slovních výroků v predikátové logice:
• Každé prvočíslo větší než 2 je liché;
VneN. [(Pr(n)An>2)       Li(n)], c
přičemž lze rozepsat Li(n) = 3k G N . n = 2k + 1. c
• Každé číslo n > 1, které není prvočíslem, je dělitelné nějakým číslem y kde
n ^ y a y > 1;
VneN. (n > 1 A -iPr(ra))      3y (y\n A n^y A y>l).
□
Příklad 1.14. Dále si ukažme, že na pořadí kvantifikátorů velmi záleží:
• Pro každého studenta A v posluchárně platí, že existuje student B v posluchárně takový, že A je kamarád B.
• Existuje student B v posluchárně, že pro každého studenta A v posluchárně platí, že A je kamarád B. □
Petr Hliněný,  Fl MU Brno, 2014
19/21
Fl: IB000: Základní formalismy
Mechanický postup negace výroků
Přesný význam formulí se zanořenými negacemi je někdy skutečně obtížné zjistit.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ě:c
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."
Tvrzení 1.15. Každou výrokovou 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, 2014
20/21
Fl: IB000: Základní formalismy
Metoda 1.16. Převod formule p do normálního tvaru F{p). Používame F {X) jako „je pravda, že X" a Q {X) jako „není pravda, že X".
F{Ä) =  A g (A) = ^A
= g(p) g^tp)     = Fiip)
T{p A -0)    =   T((p)AT(ip) G(tpAý)    = G(<p)VG($)
F(pVib)    =   T(tp) VTty) G&Vý)    = G(<p)AG(ý)
Hv       = Hv)-&H-V)      g&^ip) = (%)Ag^))v(%)AJW))[
Pro predikátové formule toto rozšíříme ještě o pravidla:
F{y/x.ip) — y x. ľ{ip)        g(\/x.ip) — 3x.g(p)
T(3x.p)   —   3x.J:{p) g(3x.p)   — \/x.g(p)c
Uvažme formuli       =>• ^(BV^(C Užitím uvedeného postupu 1.16 získame:
ř(-.(i4^n(flVn(C=^nA)))) = 5(A ^ -(B V -(C ^ ^)))      = Ľ
J(a)AgKBV-(C^^))) = AAJ(BV-(C^^)) = ľ
ilA(J(B)VJHC=^nA))) = AA(Bvg(C^^))
AA(BV(J(C)A5H))) = AA(BV(CAJ(a))) A A (B V (C A A))
Petr Hliněný,  Fl MU Brno, 2014
21/21
Fl: IB000: Základní formalismy