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, 2012 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, 2012 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, 2012 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, 2012 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í.n • 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^^.\z • 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, 2012 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, 2012 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 tentkrá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, 2012 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, 2012 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, 2012 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) = (-!).(+!) = -I < O.c Dané tvrzení není platné. a Petr Hliněný, Fl MU Brno, 2012 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 2012.C Důkaz: Existuje pouze konečně mnoho možných výsledků losování 45. tahu sportky v roce 2012. 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 2012 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, 2012 11/21 Fl: IB000: Základní formalismy 1.4 Výroky a základ výrokové 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é.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. Petr Hliněný, Fl MU Brno, 2012 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, 2012 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 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 • (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, 2012 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 definujeme funkci Sv{a) [vyhodnoceníformule a) induktivně 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, 2012 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, 2012 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( 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 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, 2012 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 (parameterem 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 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). □ Petr Hliněný, Fl MU Brno, 2012 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.14. 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, 2012 20/21 Fl: IB000: Základní formalismy Metoda 1.15. 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(• ^(BV^(C Užitím uvedeného postupu 1.15 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, 2012 21/21 Fl: IB000: Základní formalismy