*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. Náplní prvních dvou lekcí našeho předmětu 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í, chápání a odvozování a na rigorózním úsudku podloženém poctivou matematickou logikou. □ Stručný přehled lekce * Pochopení přirozeného i formálního zápisu a významu matematických tvrzení (vět). * Pochopení správného formálního způsobu argumentace v matematice (důkazů). * Rozbor logické struktury matematických vět a pojem výroku. Základy výrokové logiky. Petr Hliněný, Fl MU Brno, 2023 1/14 Fl: IB000: Základní formalismy 1.1 Význam matematických tvrzení Matematika (tudíž i teoretická informatika jako její součást) se vyznačuje velmi přísnými formálními požadavky na korektnost vyjadřování a argumentace. • Matematické tvrzení je obvykle vysloveno ve tvaru „Jestliže platí předpoklady, pak platí závěr. • Tomuto tvaru se odborně říká implikace. • Pro pochopení významu je klíčové vždy správně identifikovat, co jsou vdané větě ony zmíněné předpoklady a co je závěrem. • Příklady běžné formulace matematických vět. * Je-li x > 1, pak platí x2 > x.n * Konečná množina má konečně mnoho podmnožin. * sin2 (a) +cos2(qí) = l.n * Graf je rovinný, jestliže neobsahuje podrozdělení K§ nebo K^^.l • 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í. Petr Hliněný, Fl MU Brno, 2023 2/14 Fl: IB000: Základní formalismy O pravdivosti implikace Hned na začátek výkladu zdůrazňujeme, jak moc důležité je pochopit správný logický význam matematického tvrzení vysloveného zmíněnou formou implikace („jestliže ..., pak ... "). □ Pravdivost takového tvrzení 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í. Volně řečeno, z předchozího kritéria (*) vyplývá, že pokud předpoklady nejsou splněny nebojsou sporné, tak celé tvrzení je platné bez ohledu na pravdivost závěru! NEPRAVDA COKOLIV Petr Hliněný, Fl MU Brno, 2023 3/14 Fl: IB000: Základní formalismy Příklad 1.1. 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é. „ 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, 2023 4/14 Fl: IB000: Základní formalismy Příklad 1.2. 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. Opět je třeba se pečlivě zamyslet nad významem předpokladů a závěru. Avšak tentokrát není situace předpokladů tak triviálně sporná, jako byla v Příkladu 1.1. Kdy tedy mohou nastat oba předpoklady (o tom, kde sedí Anna) zároveň? i 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. Pravdivost celé věty je tímto potvrzena. □ Petr Hliněný, Fl MU Brno, 2023 5/14 Fl: IB000: Základní formalismy :f—:- 1,2 Uvod do matematického dokazování S přísnými formálními požadavky na korektnost vyjádření a argumentace v matematice se pojí otázka, jak správně svá tvrzení zdůvodňovat. Krátce lze říci, že korektně postavená matematická argumentace musí vést od přijatých předpokladů v elementárních krocích směrem k požadovanému závěru (a nikdy ne naopak!). • Uvažme matematickou větu (neboli tvrzení) tvaru „Jestliže platí předpoklady, pak platí závěr". • Důkaz této věty je konečná posloupnost tvrzení, kde * každé tvrzení je buď - 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. Petr Hliněný, Fl MU Brno, 2023 6/14 Fl: IB000: Základní formalismy ■r Příklad 1.4. 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. 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 + 21 + 1 + 1 z 1,2) a komutativity sčítání (axiom) 2) 6 = 2/ + l, l celé předpoklad ze 3) a distributivnosti násobení (axiom)c ze 4) a opět distributivnosti násobenie z5)am = fc + Z + lje celé číslo (axiom) □ Petr Hliněný, Fl MU Brno, 2023 7/14 Fl: IB000: Základní formalismy Příklad 1.5. 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-^.n 2) Číslo z ]e 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, 2023 8/14 Fl: IB000: Základní formalismy 1.3 Výroky * Důležitým pevným mostem mezi běžnou mluvou a přesným matematickým formalismem je pojem výroku. Definice 1.6. 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 buď pravdivé, nebo nepravdivé. Ukážeme si několik příkladů - které z nich jsou výroky? * Dnes už v Brně pršelox * Předmět Fl: IB000 se vyučuje v prvním ročníkux * Platí 2 + 3 = 6.n * To je bez problémů. (Co?)c * Platí x > 3. * Pro každé celé číslo x platí, že x > 3x 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, 2023 9/14 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áx * 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ý? nSkutečně mají všechny domy modrou střechu a před námi stojí kráva s 10 nohama? i 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"). • 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, 2023 10/14 Fl: IB000: Základní formalismy 1.4 Formální výroková logika Všimněte si, že podle Definice 1.6 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, £>, C,... a přiřadíme jim hodnotu 0 nebo l.c Definice: Výroková formule (značíme cr, ^,...) vzniká z výrokových proměnných pomocí závorek a logických spojek -i negace a implikace.^ Zároveň používáme v zápise následujících zkratek * (/}V^ (disjunkce / „nebo11) je jiný zápis formule -k^ ^, c * (/}A^ (konjunkce/„a") je jiný zápis formule -i(-k^ V * ^ (ekvivalence) je jiný zápis formule ^) A (^).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, A V B V ->C a nesprávně A =^> B =^> C - znamená toto (A B) C nebo A (B C)? Petr Hliněný, Fl MU Brno, 2023 11/14 Fl: IB000: Základní formalismy ■r Definice 1.8. 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{o\ vyhodnoceníformule a, induktivně (tj. po krocích) takto: • SU(A) = v (A) pro každé A ) = í ? jestl,iže 5"(¥?) = 1 a 5"W = 0; □ V7^ ^y 1 jinak. Tvrzení 1.9. Přímým důsledkem Definice 1.8 a zkratek V za -k^ ^, 'A' za -"(-■<£ V -i^) a '<^>' za (<^ ^) A (íp 92), jsoív tato fakta: • B) V B V C 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 Petr Hliněný, Fl MU Brno, 2023 13/14 Fl: IB000: Základní formalismy ■r Splnitelnost formulí a tautologie Definice: Formule (p je splnitelná, pokud pro některou valuaci v platí, že Su((f) = 1. Formule je nesplnitelná (říká se kontradikce), pokud není splni-telnáj Formule (p ]e vždy pravdivá, neboli výroková tautologie, psáno |= (p, pokud pro každou valuaci v platí, že Sv(tp) — l.c Řekneme, že dvě formule jsou ekvivalentní, právě když |= 99 <^> 7/^. Tv zení 1.11. Následující formule jsou tautologiemi. = iV -i Au = -n^A^ Ac (AA(A=>B)) ^Bu (-.S -iA) (A S) (-■A =>(BA -.S)) A Jak poznáme tautologie v pravdivostní tabulce? A jak ekvivalentní formule? Petr Hliněný, Fl MU Brno, 2023 14/14 Fl: IB000: Základní formalismy