Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce O oo ooooo ooo oooooooooo Základy matematiky a statistiky pro humanitní obory I Vojtěch Kovář Fakulta informatiky, Masarykova univerzita Botanická 68a, 602 00 Brno, Czech Republic xkovar3@fi.muni.cz část 2 Obsah přednášky Matematická logika oo Výroková logika ooooo Něco z predikátové logiky ooo Matematická indukce oooooooooo Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky O Matematická logika •o Výroková logika ooooo Něco z predikátové logiky ooo Matematická indukce oooooooooo Matematická logika - motivace 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ář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky O Matematická logika O* Výroková logika ooooo Něco z predikátové logiky ooo Matematická indukce oooooooooo Typy logik Typy logi k ■ 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) Obsah přednášky O Výroková logika Matematická logika oo Výroková logika •oooo Něco z predikátové logiky ooo Matematická indukce oooooooooo 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(Ä) — 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ář Základy matematiky a statistiky pro humanitní obory I Fl MU Brno Obsah přednášky O Logické funkce Matematická logika oo Výroková logika o«ooo Něco z predikátové logiky ooo Matematická indukce oooooooooo Logické funkce (1) ■ Základní logické funkce ■ necht A, B jsou výroky ■ negace -iA m V(^A) = 0, je-li v (A) = 1 ■ v(-^A) = 1, je-li v(A) = 0 ■ implikace A =4> B ■ v(A B) = 0, je-li v(A) = 1 a v(B) = 0 ■ v (A =4> B) = 1 v ostatních případech ■ kombinací těchto funkcí lze vyjádřit všechny ostatní logické funkce = -O ci (~v Vojtěch Kovář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky O Logické funkce Matematická logika oo Výroková logika oo»oo Něco z predikátové logiky ooo Matematická indukce oooooooooo Logické funkce (2) ■ Odvozené logické funkce ■ konjunkce A A B (logické „a") ■ V(A AB) = 1, je-li v(A) = 1 a v(B) ■ 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) ■ \/(yA V B) = 1 v ostatních případech ■ ekvivalence /4 44> 6 ■ (/4 B) A (B >A) Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Fl MU Brno Obsah přednášky O Matematická logika oo Výroková logika OOO0O Něco z predikátové logiky ooo Matematická indukce oooooooooo Odvozování Odvozování Schémata axiomů ■ pro libovolné výroky A, B, C platí m A=>(B=>A) m (A (B C)) {{A B)^(A^ C)) ■ (-.e ^A) ^ {A^ B) ■ dosazením konkrétních výroků vzniknou axiomy Odvozovací pravidlo modus ponens ■ pokud platí A a platí A =4> 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ář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky O Matematická logika oo Výroková logika oooo* Něco z predikátové logiky ooo Matematická indukce oooooooooo Odvozování Příklad dů kazu: X => X Schémata axiomů ■ A => (B => A) m (A => (B => C)) => {(A => B)^{A^ C)) m (-,e -nA) ^(A^ B) Dokazujeme, že pro libovolný výrok X platí X ^ X (X ((X => X) => X)) => ((X (X => X)) (X =x* >^)) / axiom 2 X ((X X) X) /axiom 1 (X (X X)) ^ (X ^ X) / aplikace modus ponens na 2. a 1. X (X X) / axiom 1 X X / aplikace modus ponens na 4. a 3. Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky O Matematická logika oo Výroková logika ooooo Něco z predikátové logiky •oo Matematická indukce oooooooooo Něco z predikátové logiky Něco z predikátové logiky ■ Ohodnocení proměnných ■ formule („výroky") mohou obsahovat proměnné (* = i) ■ 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) Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce o oo ooooo omo oooooooooo 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 ■ napr. 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ář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce o oo ooooo oom oooooooooo Něco z predikátové 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)) m 3x(Prime(x) A 3k(x = 2k)) u dokážete je přečíst? Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky O Matematická logika oo Výroková logika ooooo Něco z predikátové logiky ooo Matematická indukce •ooooooooo Matematická indukce 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ář Základy matematiky a statistiky pro humanitní obory I Fl MU Brno Obsah přednášky O Matematická logika oo Výroková logika ooooo Něco z predikátové logiky ooo Matematická indukce o«oooooooo 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+i = an + 2 Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Fl MU Brno Obsah přednášky O Matematická logika Výroková logika oo ooooo Něco z predikátové logiky ooo Matematická indukce OO0OOOOOOO Matematická indukce Induktivní definice (2) ■ Bází může být víc ■ Fibonacciho posloupnost: O, 1, 1, 2, 3, 5, 8, 13, ... ■ báze indukce: a\ — O ■ báze indukce: a2 = 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 —*(Ä) je výroková formule ■ indukční krok: pokud A a B jsou výrokové formule, pak (>A =4> B) je výroková formule Obsah přednášky O Matematická logika oo Výroková logika ooooo Něco z predikátové logiky ooo Matematická indukce 000*000000 Matematická indukce Důkaz matematickou indukcí ■ Princip ■ potřebujeme dokázat, že pro všechny prvky nějaké posloupnosti xq, ...,xn,... platí nějaký výrok A ■ Vn(A(xn)) ■ dokážeme výrok pro xq ■ —> báze indukce ■ dokážeme, že pokud výrok platí pro x/_i, pak platí i pro Xj pro libovolné / ■ 4(x;_i) => A(x;) ■ —> indukční krok ■ levá strana implikace výše se nazývá indukční předpoklad Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Fl MU Brno Obsah přednášky O Matematická logika oo Výroková logika ooooo Něco z predikátové logiky ooo Matematická indukce 0000*00000 Příklad indukce Příklad indukce ■ Dokážeme, že pro všechna přirozená n > 1 platí: ■ 1 + 2 + ... + n = n/2 * (1 + n) m 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)) = -O ci (~v Vojtěch Kovář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky O Příklad indukce Matematická logika oo Výroková logika ooooo Něco z predikátové logiky ooo Matematická indukce OOOOO0OOOO Příklad indukce (2) Indukční krok předpokládáme 1 + 2 + dokážeme: 1 + 2 + ... + k + (k + 1) 1 + 2 + 1 + 2 + 1 + 2 + . 1 + 2 + 1 + 2 + 1 + 2 + 1 + 2 + . + k .+ /c + (/c + l) + /c + (/c + l) . + k + (k + l) .+ /c + (/c + l) .+ /c + (/c + l) . + k + (k + l) + k = k/2*(l + k) {k + l)/2 * (1 + (k + 1)) : k/2* (1 + k) k/2 * (1 + /c) + (k + 1) (/c*(l + /c) + 2*(/c + l))/2 (/c + k2 + 2/c + 2)/2 (/c2 + 3/c + 2)/2 (/c + l)(/c + 2)/2 (/c + l)/2 * (1 + (k + 1)) n H^D — = Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Fl MU Brno Obsah přednášky O Matematická logika oo Korektnost matematické indukce Výroková logika ooooo Něco z predikátové logiky ooo Matematická indukce oooooo«ooo Proč to funguje? ■ Intuitivní overení korektnosti ■ báze platí A(xo) ■ indukční krok platí (A(xq) =4> A(xi)) m modus ponens —> platí i A(xi) m indukční krok —>> platí (A(xi) =4> A{x2)) ■ modus ponens —> platí i Afa) ■ atd. ad infinitum ■ Formální důkaz korektnosti matematické indukce ■ sporem - předpokládáme, že nějaké A(xn) neplatí Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I Fl MU Brno Obsah přednášky O Složitější typy indukce Matematická logika oo Výroková logika ooooo Něco z predikátové logiky ooo Matematická indukce ooooooo«oo Složitější typy indukce (1) ■ Složitější indukční předpoklad ■ např. platí yA(x/_i) i /4(x;_2) ■ musíme dokázat odpovídající bázi ■ tj. A(xq) i A(xľ) Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky O Složitější typy indukce Matematická logika oo Výroková logika ooooo Něco z predikátové logiky ooo Matematická indukce OOOOOOOO0O 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 -"(^l) ■ indukční krok 2: věta platí pro formule A a B =4> platí i pro (A =4> 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ář Základy matematiky a statistiky pro humanitní obory I Fl MU Brno Obsah přednášky O Příklad špatné indukce Matematická logika oo Výroková logika ooooo Něco z predikátové logiky ooo Matematická indukce ooooooooo* 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 = {Ki,Kn}, S2 = {K2lKn+i} ■ 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 = {K±,Kn+i\ mají všichni koně stejnou barvu Kde je problém? (zřejmě existují různí koně :) ) □ - = Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno