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 Výroková logika Něco z predikátové logiky Matematická indukce • oo ooooo ooo 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 Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce O • ooooo ooo oooooooooo 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ář 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 om ooooo ooo oooooooooo 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 Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce O oo •oooo ooo oooooooooo 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(Ä) — 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 :l MU Brno Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce O OO O0OOO ooo oooooooooo Logické funkce Logické funkce (1) ■ Základní logické funkce ■ necht A, B jsou výroky ■ negace -iA m v(-nA) = 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> 8) = 1 v ostatních případech ■ kombinací těchto funkcí lze vyjádřit všechny ostatní logické funkce = -O o. ("v Vojtěch Kovář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce o oo oo»oo ooo oooooooooo Logické funkce Logické funkce (2) ■ Odvozené logické funkce ■ konjunkce A A B (logické „a") ■ v(A A B) = 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 ^ B m (A B) A (B A) Vojtěch Kovář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce o oo ooo»o ooo 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)) ■ (-.6 ^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 Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce O OO oooo» OOO oooooooooo Odvozování Příklad dů kazu: X => X Schémata axiomů ■ A => (B => A) m (A (B C)) => {(A => B)^{A^ C)) m (-nB => ^A) ^(A^ B) Dokazujeme, že pro libovolný výrok X platí X X q (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 Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce O OO OOOOO »00 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 = O 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 090 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 = 2 k)) u 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 □ S1 :l MU Brno Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce O OO OOOOO OOO «000000000 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 :l MU Brno Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce O OO OOOOO OOO O0OOOOOOOO Matematická indukce Induktivní definice ■ Báze indukce ■ definujeme nejjednodušší prvky ■ Indukční krok ■ popíšeme, jak se z jednodušších prvku 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ář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce o oo ooooo ooo oo»ooooooo 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: 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 □ si - = i -o °s o Vojtěch Kovář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce O OO OOOOO OOO OOO0OOOOOO 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 x/ pro libovolné / ■ >A(x/_i) A{xs) ■ —>► indukční krok ■ levá strana implikace výše se nazývá indukční předpoklad Vojtěch Kovář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce o oo ooooo ooo oooo«ooooo 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)) = -O o. ("v Vojtěch Kovář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce O OO OOOOO OOO OOOOO0OOOO Příklad indukce Příklad indukce (2) ■ Indukční krok ■ předpokládáme: 1 + 2 + ... + k = k/2 * (1 + k) ■ dokážeme: l + 2 + ... + k + (k + l) = (k + l)/2 *(l + (k + 1)) ■ l + 2 + ... + /c + (/c + l) ■ k/2*(l + k) + (k + l) m (k + k2)/2 + {k + 1) ■ (k + k2 + 2/c + 2)/2 ■ (k2 + 3k + 2)/2 ■ {k + 2) * {k + l)/2 ■ (/c + l)/2*(/c + 2) ■ (/c + l)/2 * (1 + {k + 1)) Vojtěch Kovář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce O OO OOOOO OOO OOOOOO0OOO Korektnost matematické indukce Proč to funguje? ■ Intuitivní overení korektnosti ■ báze —>► platí A(xq) ■ indukční krok —>► platí (A(xq) =4> A(xi)) ■ modus ponens —>► platí i A(xi) ■ indukční krok —>► platí (A(xi) =4> A{x2)) ■ modus ponens —>► platí i Afa) m atd. ad infinitum ■ Formální důkaz korektnosti matematické indukce ■ existuje, ale nad rámec predmetu 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 OOO OOOOOOO0OO Složitější typy indukce Složitější typy indukce (1) ■ Složitější indukční předpoklad ■ např. platí /4(x;_i) i /4(x;_2) ■ musíme dokázat odpovídající bázi ■ tj. A(x0) i A(xľ) Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I □ S1 :l MU Brno Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce o oo ooooo ooo oooooooo»o 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 -"(^l) ■ 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 Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce O OO OOOOO OOO 000000000» 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 = {Ki,Kn}, S2 = {K2lKn+i} ■ podle předpokladu mají v Si i v S2 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ě 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