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 právě je 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í, chápání a odvozová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 celé matematické logiky. Petr Hliněný, Fl MU Brno, 2015 1/22 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.. . Pro úplný začátek si jen celou problematiku uvedeme názornými ukázkami. Petr Hliněný, Fl MU Brno, 2015 2/22 Fl: IB000: Základní formalismy r 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 3) x = a + b = 2k + 2l + l + l z 1,2) a komutativity sčítání (axiom)c 2) b = 21+ 1,1 celé předpoklade 4) x = 2(fe + /) + 2-l 5) x = 2(k + l + l) 6) x = 2m, m celé ze 3) a distributivnosti násobení (axiom)c ze 4) a opět distributivnosti násobenie z5)am = fe + / + lje celé číslo (axiom) □ Petr Hliněný, Fl MU Brno, 2015 3/22 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. c Důkaz po krocích (s již trochu méně formálním zápisem) zní: 1) Nechť z = ^±2 = x + ^ = 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. Všimněte si, že klíčový krok (1) popisuje námi vymyšlenou (prostě uhodnutou) algebraickou konstrukci, která vede k požadovanému číslu z. Zbylé kroky (2-5) pak jen snadno zdůvodňují, že nalezené z má všechny požadované vlastnosti. □ Petr Hliněný, Fl MU Brno, 2015 4/22 Fl: IB000: Základní formalismy 1.2 Význam matematických tvrzení • První krok formálního důkazu je uvědomit si, co tvrdí 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í. • Především je třeba správně pochopit, jaký je logický význam matematického tvrzení vysloveného typicky formou implikace („jestliže . .., pak ... "). Z předchozího (*) totiž vyplývá, že 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, 2015 5/22 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, 2015 6/22 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í ve 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ň? c 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, 2015 7/22 Fl: IB000: Základní formalismy 1.3 Tvoření matematických důkazů Jak „moc formální" mají správné matematické důkazy vlastně být? c • Záleží, 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 • Avšak vůbec neplatí, že čím více formálních matematických symbolů v důkaze použijete místo běžného jazyka, tím by byl důkaz přesnější! 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 jako taková vyžaduje tvůrčí (přímo „umělecké") matematické vlohy. Přesto sejí alespoň trochu musíte přiučit. Petr Hliněný, Fl MU Brno, 2015 8/22 Fl: IB000: Základní formalismy Dokazovat či vyvracet tvrzení? Představme si, že našim úkolem je rozhodnout platnost matematického tvrzení. Jak pak matematicky správně zdůvodníme nalezenou odpověď? • Záleží na odpovědi samotné. .. c • Pokud je to ANO (platí), prostě podáme důkaz 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 je matematická věta T, která tvrdí nějaký závěr pro širokou oblast vstupních možností. Potom je postup následující::: • Pokud T platí, nezbývá než podat vyčerpávající důkaz platnosti pro všechny vstupy, c • 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, 2015 9/22 Fl: IB000: Základní formalismy Příklad 1.6. Rozhodněte platnost následujícího tvrzení: Pro všechna reálná 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 na'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 < Ox Dané tvrzení tudíž není platné. a Petr Hliněný, Fl MU Brno, 2015 10/22 Fl: IB000: Základní formalismy Konstruktivní a existenční důkazy Z hlediska praktické využitelnosti je vhodné rozlišovat tyto dvě kategorie důkazů (třebaže z formálně-matematického pohledu mezi nimi kvalitativní rozdíl není). • Důkaz z Příkladu 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. Příklad 1.7. Cistě existenčního důkazu. Věta. Existuje program, který vypíše na obrazovku čísla tažená ve 45. tahu sportky v roce 2015.C Důkaz: Existuje pouze konečně mnoho možných výsledků losování 45. tahu sportky v roce 2015. 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 2015 skutečně vylosován, c ^ 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, 2015 11/22 Fl: IB000: Základní formalismy 1.4 Výroky a základ logiky • Důležitým „pevným mostem" mezi běžnou mluvou a přesným matematickým formalismem je následující pojem výroku. Definice 1.9. 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. • 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, 2015 12/22 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 Karel váží přes 90 kg, 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, 2015 13/22 Fl: IB000: Základní formalismy 1.5 Střípky matematické logiky Všimněte si, že podle Definice 1.9 každému výroku běžné mluvy lze 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 můžeme nahradit 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 l.c Definice: Výroková formule (značíme ip,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=$-ip,\z * tpAip (konjunkce/„a") je jiný zápis formule -i(-np V- V (ekvivalence) je jiný zápis formule (ip =4> tp) A (tp =4> (p).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, 2015 14/22 Fl: IB000: Základní formalismy r Definice 1.11. 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(cr), vyhodnoceníformule a, induktivně (tj. po krocích) takto: • SV(Ä) = v(A) pro každé A G Prom. c Tvrzení 1.12. Přímým důsledkem Definice 1.11 a zkratek V za -np =4> ip, 'A' za -i(-np V -iV) 3 'o' za (ip ip) A (ip tp), je následovně: • Sv(ip V V>) = 1 právě když Sv(ip) = 1 nebo Sv(ip) = 1. c • Sv(ip Aip) = 1 právě když Sv(ip) = 1 a současně Sv(ip) = 1. • Sv(ip ip) = 1 právě když platí jedna z následujících podmínek * Sv(ip) = 1 a současně Sv(ip) = 1, * Sv(ip) = 0 a současně Sv(ip) = 0. 0 jestliže Sv((p) = 1 a ) = 0; c c Petr Hliněný, Fl MU Brno, 2015 15/22 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.13. Jaká je pravdivostní tabulka pro formuli {A =4> B) V B V C? A B c A ^B (A^8)V8VC 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, 2015 16/22 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(ip) = 1. Formule je nesplnitelná (říká se kontradikce), pokud není splnitelná: Formule ip G 3> je vždy pravdivá, neboli výroková tautologie, psáno |= jsou ekvivalentní, právě když |= V- c Tvrzení 1.14. Následující formule jsou tautologiemi: AV-.A (AA(i^B))^Bc (-.5 =*> -iA) ^ (A ^ £)c (nA^(BAnfi)) A Jak poznáme tautologii v pravdivostní tabulce? Petr Hliněný, Fl MU Brno, 2015 17/22 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 (tzv. 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ů. ľ Výrok, prom. lze chápat jako predikáty bez parametrů. 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 2) => Li{n)], c přičemž lze rozepsat Li(n) = 3k G N . n = 2k + 1. i • Každé celé číslo n > 1, které není prvočíslem, je dělitelné nějakým celým číslem y kde n ^ y a y > 1; VneZ. (n > 1 A-iPr(n)) By G Z(y| n A n^y A y>l). c □ Příklad 1.16. Proč 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, 2015 19/22 Fl: IB000: Základní formalismy Normální tvar formulí s negací Přesný význam tvrzení se zanořenými negacemi je někdy skutečně obtížné pochopit.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, ve kterém se negace zanořených podformulí nevyskytují, 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é. • Pro ilustraci, k formuli -^(A =>• B) je ekvivalentní A A -^B, • k formuli -.(C A (^A B)) je ekvivalentní V (^A A ^B). Tvrzení 1.18. 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 Například, pokud přijmeme přirozené pravidlo dvojí negace (|= -> ^A •<=> A), tak výše napsanou větu si převedeme na lépe srozumitelný tvar: „Nemusím říct, že tě mám nerad." c Petr Hliněný, Fl MU Brno, 2015 20/22 Fl: IB000: Základní formalismy Metoda 1.19. 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". T{A) = A g (A) = ^A f{^p) = g{p) g^tp) = T{p^ip) = T{p)^T{ip) g(p^Tp) = F {p) A Q {íl)) T{p a ip) = T{p)AT{ib) g{• ^{BV^{C Užitím uvedeného postupu Metody 1.19 získáme: 7Hi^-(BV-(C^ni)))) = g{A =>• -^{B V -n(C =>■ -i-A))) =c F{A) A g{~^{B V -n(C =>■ = AAJ(BV-(C^^)) iA(J(B)VJHC^^))) = AA(Bvg(C^^)) A A {BV {F{C) A g{-^A))) = AA{B\/{CA J7{A))) Aa{BV{CA A)) Petr Hliněný, Fl MU Brno, 2015 21/22 Fl: IB000: Základní formalismy r Petr Hliněný, Fl MU Brno, 2015 22 /22 Fl: IB000: Základní formalismy