Základy matematiky a statistiky pro humanitní obory 1 Vojtěch Kovář Fakulta informatiky, Masarykova univerzita Botanická 68a, 60200 Brno, Czech Republic xkovar38fi.muni.cz část 2 VojtĚch Kovář (Fl MU Brno) PLINDD4 Obsah přednášky Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce VojtĚch Kovář (Fl MU Brno) PLINDD4 Ěást 2 2/22 Matematická logika - motivace ► Jazyk matematiky ► přirozený jazyk je víceznačný ► ,, k jednaní X na úřadě YZ potřebujete pas a řidičský průkaz nebo občanský průkaz" ► matematická fakta potřebujeme zapisovat přesně ► Formalizace pojmu důkaz ► důkaz = posloupnost elementárních kroků ► to, co je ,,elementární'" je individuální ► logika zavádí přesnou definici elementárního kroku VojtĚch Kovář (Fl MU Brno) PLIN004 Matematická logika Typy logik Typy logik ► Výroková logika ► výroky, logické funkce, pravidlo modus ponens ► Predikátová logika ► predikáty, kvantifikátory ► Další typy logik ► modálni, temporální, fuzzy, intenzionální, ... ► nebudeme se jimi zabývat ► Naším cílem je naučit se logiku prakticky používat ► —> číst a psát ► nikoli zkoumat její temná zákoutí (viz předmět ,, Matematická logika" na Fl) Vojtech Kovář (Fl MU Brno) PLIN004 rast 2 4/22 Výroková logika Výroková logika Výroková logika ► Výrok ► základní jednotka ► tvrzení, jemuž lze přiřadit pravdivostní hodnotu ► např. ,,a = 1", ,,4 je prvočíslo" ► Pravdivost ► přiřazení hodnoty 0 nebo 1 každému výroku ► zapisujeme v (A) = 1 (,,výrok A platí") ► v(A) = 0 („výrok A neplatí") ► Logické funkce ► konstrukce složitějších výroků z výroků jednodušších VojtĚch Kovář (Fl MU Brno) PLINDD4 Ěást 2 5/22 Výroková logika Logické funkce Logické funkce (1) ► Základní logické funkce ► necht A, B jsou výroky ► negace -*A ► v(^A) = 0, je-li v(A) = 1 ► v(^A) = 1, je-li v(A) = 0 ► implikace A => B ► v(A =>B) = Q, je-li v(A) = 1 a v(B) = 0 ► v [A 4- S) = 1 v ostatních případech ► kombinací těchto funkcí lze vyjádřit všechny ostatní logické funkce VojtĚch Kovář (Fl MU Brno) PLINDD4 Ěást 2 6/22 Výroková logika Logické funkce Logické funkce (2) ► Odvozené logické funkce ► konjunkce A / B (logické „a") ► v(A A S) = 1, je-li v(A) = 1 a i/(S) = 1 ► v(A A B) = 0 v ostatních případech ► disjunkce AV B (logické ,,nebo") ► v (A V B) = 0, je-li v(A) = 0 a v(B) = 0 ► v {A V B) = 1 v ostatních případech ► ekvivalence A B *■ (A^B)A(B^A) VojtĚch Kovář (Fl MU Brno) PLIN004 Ěást 2 7/22 Výroková logika Odvozováni Odvozování ► Schémata axiomů ► pro libovolné výroky A, B, C platí ► A^ (B => A) ► (A^(B^ Q) => ((A B)^{A^ C)) ► (-.£? ->A) ^{A^ B) ► dosazením konkrétních výroků vzniknou axiomy ► Odvozovací pravidlo modus ponens ► pokud platí A a platí A B, pak platí B ► Formální definice důkazu ► posloupnost výroků, z nichž každý je bud axiom nebo výsledek aplikace odvozovacího pravidla na předchozí výroky VojtĚch Kovář (Fl MU Brno) PLIN004 Výroková logika Odvozování Příklad důkazu: X => X ► Schémata axiomů ► A^(B^A) ► (A^{B^ C)) ((A B)^{A^ C)) ► (-.6 =*(/4^ e) ► Dokazujeme, že pro libovolný výrok X platí X =$- X 1. (X => ((X => X) X)) => ((X => (X => X)) => (X => X)) / 2. X ^ ((X => X) =*X) /„„mi 3. (X (X =>■ X)) =4> (X X) / aplikace modus poníns na 2 a 1 4 X (X =4- X) /,Ämi 5. X =r" X / aplikace modu; ponens na 4 a 3 Vojtech Kovář (Fl MU Brno) PLIN004 tást 2 9/22 N.w; ,- (;n\likát2vá Icfiky Nic; z prcdikaccvá logiky Něco z predikátové logiky ► Ohodnocení proměnných ► formule („výroky") mohou obsahovat proměnné (x = 1) ► pravdivost pak závisí na ohodnocení, tj. přiřazení hodnot proměnným ► Kvantifikátory ► 3 - existuje alespoň jedno ohodnocení, při kterém formule platí ► V - výrok platí pro všechna možná ohodnocení ► např.: 3x(x = 0 A x = 1) V; -ich -í.-vir M., ŕirn .. PLIN004 Něco z predikátově logiky Něco z predikátové logiky Něco z predikátové logiky (2) ► Funkční symboly ► kombinuji'objekty, se kterými zacházíme (množiny, čísla) ► výsledkem je další objekt ► např. plus, množinové sjednocení ► napr -f(x,y), resp. x + y" ► Predikáty ► vyjadřují fakta o konstantách a proměnných ► výstupem je pravdivostní hodnota ► např. Prime(x) - „x je prvočíslo" ► např. € (x, V), resp. x € Y - ,,prvek x patří do množiny V" Vojtech Kovář (Fl MU Brno) PLINDD4 část 2 11/22 N ŕ r.-; i;rr;lik.-:cv= Icgiky N i cc z prcdikacc-.é logiky Něco z predikátové logiky (3) ► Příklady složitějších formulí ► 3x(3k(x = 2k + 1) A 3m(x = 2m)) ► Vx(Pr/me(x) => 3k(x = 2k)) 3x(Prime(x) A 3k{x = 2k)) ► dokážete je přečíst? Vojtech Kovář (Fl MU Bum) PLINDD4 část 2 12/22 Matematická indukce Matematickí indukci'' Matematická indukce ► Obecný matematický princip ► použitelný pro definice, důkazy ► napřed vyrobíme/dokážeme něco jednoduchého ► —> báze indukce ► pak vyrobíme z obecného jednoduchého objektu o krok složitější objekt ► případně dokážeme, že z platnosti pro jednoduchý objekt vyplývá platnost pro složitější objekt ► —► indukční krok ► tím dostaneme nekonečnou řadu definic/důkazů Vojtěch Kovář (Fl MU Brno) PLINDD4 část 2 13/22 Matematická indukce Matematická indukce Induktivní definice ► Báze indukce ► definujeme nejjednodušsí prvky ► Indukční krok ► popíšeme, jak se z jednodušších prvků vyrobí složitější ► Příklad: induktivně definované posloupnosti ► definujeme nekonečnou posloupnost 3, 5,7, 9,... ► báze indukce: ai = 3 ► indukční krok: an+\ = an + 2 Vojtěch Kovář (Fl MU Brno) PLINDD4 část 2 14/22 Matematická indukce ■" indukce Induktivní definice (2) ► Bází může být víc ► Fibonacciho posloupnost: 0, 1, 1, 2, 3, 5, 8, 13, ... ► báze indukce: a\ = 0 ► báze indukce: 32 = 1 ► indukční krok: an+2 = ^n+i + 3n ► Indukčních kroků může být víc ► definice toho, jak vypadá správná výroková formule ► báze indukce: libovolný jednoduchý výrok A je výroková formule ► indukční krok: pokud A je výroková formule, pak -<(A) je výroková formule ► indukční krok: pokud A a B jsou výrokové formule, pak (A =£• B) je výroková formule Vojtech Kovář (Fl ML) Brno) PLINDD4 část 2 15/22 Matematická indukce Matematická indukce Důkaz matematickou indukcí ► Princip ► potřebujeme dokázat, že pro všechny prvky nějaké posloupnosti xo,xn,... platí nějaký výrok A ► Vn(/4(x„)) ► dokážeme výrok pro xo ► —> báze indukce ► dokážeme, že pokud výrok platí pro x,_i, pak platí i pro x, pro libovolné / ► A(xi-i) => A(xí) ► —> indukční krok ► levá strana implikace výše se nazývá indukční předpoklad Vojtech Kovář (Fl MU Brno) PLINDD4 íást 2 16/22 Matematická indukce PriTílad indukce Příklad indukce ► Dokážeme, že pro všechna přirozená n > 1 platí: ► 1 + 2 + ... + n = n/2*(l + n) ► Báze ► 1 = 1/2* (1 + 1) ► Indukční krok ► předpokládáme: 1 + 2 + ... + k = k/2 * (1 + k) ► dokážeme: 1 + 2 + ... + k + (k + 1) = (k + l)/2 * (1 + (k + 1)) VojtĚch Kovář (Fl MU Brno) PLINDD4 část 2 17/22 Matematická indukce Příklad indukce Příklad indukce (2) ► Indukční krok ► předpokládáme: 1 + 2 + ... + k = k/2 * (1 + k) ► dokážeme: 1 + 2 + ... + k + [k + 1) = [k + l)/2 * (1 + [k + 1)) ► l + 2 + ... + ŕt + (ŕt + l) ► ŕt/2*(l + ŕt) + (ŕt + l) ► {k + k2)/2 + {k + l) ► {k + k2 + 2k + 2)/2 ► {k2 + 3k + 2)/2 ► (ŕt + 2)*(ŕt + l)/2 ► (ŕt + l)/2*(ŕt + 2) ► (ŕt + l)/2*(l + (ŕt + l)) VojtĚch Kovář (Fl MU Brno) PLINDD4 část 2 18/22 Matematická indukce Korektnost matematické indukce Proč to funguje? ► Intuitivní ověřeni' korektnosti ► báze —> platí A(xq) ► indukční krok —> platí {A{xq) =^ A{x\)) ► modus ponens —> platí i A{x{) ► indukční krok —> platí (/4(xi) =^ -4(x2)) ► modus ponens —> platí i <4(x2) ► atd. ad infinitum ► Formální důkaz korektnosti matematické indukce ► existuje, ale nad rámec předmětu VojtĚch Kovář (Fl MU Brno) PLIIM004 část 2 19/22 Matematická indukce Složitější" typy indukce Složitější typy indukce (1) ► Složitější indukční předpoklad ► např. platí A(xj-i) i A{xj-2) ► musíme dokázat odpovídající bázi ► tj. A(x0) i A{X1) Vojtčch Kovář (Fl MU Brno) PLINDD4 část 2 20/22 Matematická indukce Složitější' typy indukce Složitější typy indukce (2) ► Strukturální indukce ► aplikujeme na induktivně definované objekty (např. výrokové formule) ► báze indukce: věta platí pro jednoduché výroky ► indukční krok 1: věta platí pro formuli A platí i pro ^{A) ► indukční krok 2: věta platí pro formule A a B platí i pro {A =4- S) ► Princip zůstává stejný, pouze vedení důkazu je komplikovanější ► Důkaz, že každá formule podle definice výše má sudý počet závorek? VojtĚch Kovář (Fl MU Brno) PLINDD4 Část 2 21/22 Matematická indukce Příklad špatné indukce Všichni koně mají stejnou barvu ► Věta: V každém stádě mají všichni koně stejnou barvu. ► Důkaz: indukcí vzhledem k velikosti stáda ► báze: Ve stádě o 1 koni mají všichni stejnou barvu. ► indukční krok: Předp., že věta platí pro dvě stáda o n koních; dokážeme, že platí pro stádo o velikosti n + 1 ► Si = {Ku...,Kn}, S2 = {K2,...,Kn+1} ► podle předpokladu mají v 5i i v 52 všichni koně stejnou barvu ► koně K2,Kn+i jsou v obou stádech => i barva obou stád je stejná ► tedy i ve stádě 5 = {K\,Kn+i} mají všichni koně stejnou barvu ► Kde je problém? (zřejmě existují různí koně :) ) Vojtčch Kovář (Fl MU Brno) PLINDD4 část 2 22/22