Základy matematiky a statistiky pro humanitní obory 1 Vojtěch Kovář Fakulta informatiky, Masarykova univerzita Botanická 68a, 602 00 Brno, Czech Republic xkovar3@f i.muni.cz část 2 Vojtěch Kovář (Fl MU Brno) PLIN004 část 2 1/22 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) PLIN004 část 2 2/22 Matematická logika Matematická logika - motivace Matematická logika - motivace ► Jazyk matematiky ► přirozený jazyk je víceznačný ► „k jednání 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 část 2 3/22 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) Vojtěch Kovář (Fl MU Brno) PLIN004 část 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) PLIN004 čá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(-iA) = 0, je-li v(A) = 1 ► v(-iA) = 1, je-li v(A) = 0 ► implikace A B ► v(A B) = 0, je-li v(A) = 1 a v(B) = 0 ► v(A =>■ B) = 1 v ostatních případech ► kombinací těchto funkcí lze vyjádřit všechny ostatní logické f u n kce Vojtěch Kovář (Fl MU Brno) PLIN004 část 2 6/22 Výroková logika Logické funkce Logické funkce (2) ► Odvozené logické funkce ► konjunkce A A B (logické „a ") ► v(A A 6) = 1, je-li v(A) = 1 a v(B) = 1 ► v(A A B) = 0 v ostatních případech ► disjunkce A V 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 <3> B ► {A B) A (6 A) Vojtěch Kovář (Fl MU Brno) PLIN004 část 2 7/22 Výroková logika Odvozování Odvozování ► Schémata axiomů ► pro libovolné výroky A, B, C platí ► A^(B^ A) ► (A=>(B=> C)) => ((A B)^(A^ C)) ► (-.6 => -.4) => (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 buď axiom nebo výsledek aplikace odvozovacího pravidla na předchozí výroky Vojtěch Kovář (Fl MU Brno) PLIN004 část 2 8/22 Výroková logika Odvozování Příklad důkazu: X^X ► Schémata axiomů ► a => (b => a) ► (a => (b => C)) ((/» => 6) => (/» => C)) ► (-.e =► -./») =4> (/A =► b) ► Dokazujeme, že pro libovolný výrok X platí X =>■ X 1. (X =► ((X =► X) =► X)) => ((X (X =► X)) (X =► X)) / axiom 2 2. X ((X => X) =► X) /axiomi 3. Í^C =t> (>X =^> -X")) —^ (-X" zz^" ^C) / aplikace modus ponens na 2. a 1. 4. X => (X X) / axiom 1 5. >X" =7> >X" / aplikace modus ponens na 4. a 3. Vojtěch Kovář (Fl MU Brno) PLIN004 část 2 0 22 Něco z predikátové logiky Něco z predikátové 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 ► El - 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) Vojtěch Kovář (Fl MU Brno) PLIN004 část 2 10 22 Něco z predikátové logiky Něco z predikátové logiky Něco z predikátové logiky (2) ► Funkční symboly ► kombinují objekty, se kterými zacházíme (množiny, čísla) ► výsledkem je další objekt ► např. plus, množinové sjednocení ► např. +(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ř. G (x, Y), resp. x G Y - „prvek x patří do množiny Y" Vojtěch Kovář (Fl MU Brno) PLIN004 část 2 11/22 Něco z predikátové logiky Něco z predikátové logiky Něco z predikátové logiky (3) ► Příklady složitějších formulí ► E!x(E!/c(x = 2k + 1) A E!m(x = 2m)) ► Vx(Pr/me(x) => 3k(x = 2k)) ► 3x(Prime(x) A 3k(x = 2k)) ► dokážete je přečíst? Vojtěch Kovář (Fl MU Brno) PLIN004 část 2 12/22 Matematická indukce Matematická indukce Matematická indukce ► Obecný matematický princip ► použitelný pro definice, důkazy ► napred 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) PLIN004 část 2 13/22 Matematická indukce Matematická indukce Induktivní definice ► Báze indukce ► definujeme nejjednodušší 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: a\ = 3 ► indukční krok: an+\ = an + 2 Vojtěch Kovář (Fl MU Brno) PLIN004 cist 2 14/22 Matematická indukce Matematická 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 = 3n+i + an ► 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 6 jsou výrokové formule, pak (A => B) je výroková formule Vojtěch Kovář (Fl MU Brno) PLIN004 čá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, ...,x„,... platí nějaký výrok A ► Vn{A{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é i ► /A(x,_i) =► A{Xi) ► —^ indukční krok ► levá strana implikace výše se nazývá indukční předpoklad Vojtěch Kovář (Fl MU Brno) PLIN004 část 2 16/22 Matematická indukce Příklad indukce Příklad indukce ► Dokážeme, že pro všechna přirozená n > 1 platí: ► 1 + 2 + ... + n = n/2 * (1 + 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) 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 + (/c + 1)) 1 + 2 + ... + /C =/c/2*(l + /c) 1 + 2 + ... + k + {k + 1) = /c/2 * (1 + k) + {k + 1) 1 + 2 + ... +/c + (/c + l) = (k * (1 + k) + 2 * (/c + l))/2 1 + 2 + ... + /c + (/c + 1) = (/c + k2 + 2/c + 2)/2 1 + 2 + ... + /c + (/c + 1) = (k2 + 3k + 2)/2 1 + 2 + ... + /c + {k + 1) = {k + l)(/c + 2)/2 1 + 2 + ... + k + (/c + 1) = (k + l)/2 * (1 + (/c + 1)) Vojtech Kovář (Fl MU Brno) 18/22 Matematická indukce Korektnost matematické indukce Matematická indukce Složitější typy indukce Proč to funguje? Složitější typy indukce (1) ► Intuitivní ověření korektnosti ► báze —> platí A(xq) ► indukční krok —> platí (-4(xo) =^ A(xi)) ► modus ponens —> platí i A(x\) ► indukční krok platí (A(x1) A(x2)) ► modus ponens —> platí i A(x2) ► atd. ad infinitum ► Formální důkaz korektnosti matematické indukce ► sporem - předpokládáme, že nějaké A(xn) neplatí ► Složitější indukční předpoklad ► např. platí/\(x/_i) i /\(x/_2) ► musíme dokázat odpovídající bázi ► tj. A(x0) i A(Xl) Vojtěch Kovář (Fl MU Brno) 19/22 Vojtěch Kovář (Fl MU Brno) 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 =4> platí i pro -i(A) ► indukční krok 2: věta platí pro formule A a B platí i pro (A B) ► 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) 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 = {KuKn}, S2 = {K2,Kn+1} ► podle předpokladu mají v Si i v S2 všichni koně stejnou barvu ► koně K2,Kn jsou v obou stádech i barva obou stád je stejná ► tedy i ve stádě S = {Ki,Kn+i} mají všichni koně stejnou barvu ► Kde je problém? (zřejmě existují různí koně :) ) Vojtěch Kovář (Fl MU Brno) 22/22