Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Základy matematiky a statistiky pro humanitní obory I Pavel Rychlý Vojtěch Kovář Fakulta informatiky, Masarykova univerzita Botanická 68a, 602 00 Brno, Czech Republic {pary, xkovar3}@fi.muni.cz část 2 Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Obsah přednášky 1 Matematická logika 2 Výroková logika 3 Něco z predikátové logiky 4 Matematická indukce Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Matematická logika – motivace Matematická logika – motivace Jazyk matematiky přirozený jazyk je víceznačný „k jednání XY 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 Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce 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ální, 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 FI) Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce 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 Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Logické funkce Logické funkce (1) Základní logické funkce nechť 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) = 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é funkce Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Logické funkce Logické funkce (2) Odvozené logické funkce konjunkce A ∧ B (logické „a”) v(A ∧ B) = 1, je-li v(A) = 1 a v(B) = 1 v(A ∧ B) = 0 v ostatních případech disjunkce A ∨ B (logické „nebo”) v(A ∨ B) = 0, je-li v(A) = 0 a v(B) = 0 v(A ∨ B) = 1 v ostatních případech ekvivalence A ⇔ B (A ⇒ B) ∧ (B ⇒ A) Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce 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)) (¬B ⇒ ¬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 buď axiom nebo výsledek aplikace odvozovacího pravidla na předchozí výroky Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Něco z predikátové logiky Něco z predikátové logiky (1) Valuace proměnných výroky mohou obsahovat proměnné (x = 1) pravdivost pak závisí na valuaci, tj. přiřazení hodnot proměnným Kvantifikátory ∃ – existuje alespoň jedna valuace, při které výrok platí ∀ – výrok platí pro všechny možné valuace např.: ∃x(x = 0 ∧ x = 1) Predikáty funkční symboly – vyjadřují fakta o konstantách a proměnných např. Prime(x) – „x je prvočíslo” např. Plus(x, 2) = 5 – „x + 2 = 5” Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Něco z predikátové logiky Něco z predikátové logiky (2) Příklady složitějších formulí ∃x(∃k(x = 2k + 1)) ∧ (∃l(x = 2l)) ∀x(Prime(x) ⇒ ∃k(x = 2k)) ∃x(Prime(x) ∧ ∃k(x = 2k)) dokážete je přečíst? Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Matematická indukce Matematická indukce Princip potřebujeme dokázat, že pro všechny prvky nějaké posloupnosti x0, ..., xn, ... platí nějaký výrok A ∀n(A(xn)) dokážeme výrok pro x0 → báze indukce dokážeme, že pokud výrok platí pro xi−1, pak platí i pro xi pro libovolné i A(xi−1) ⇒ A(xi ) → indukční krok levá strana implikace výše se nazývá indukční předpoklad Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Korektnost matematické indukce Proč to funguje? Intuitivní ověření korektnosti báze → platí A(x0) indukční krok → platí (A(x0) ⇒ A(x1)) modus ponens → platí i A(x1) indukční krok → platí (A(x1) ⇒ A(x2)) modus ponens → platí i A(x2) atd. ad infinitum Formální důkaz korektnosti matematické indukce existuje, ale nad rámec předmětu Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Složitější typy indukce Složitější typy indukce (1) Složitější indukční předpoklad např. platí A(xi−1) i A(xi−2) musíme dokázat odpovídající bázi tj. A(x0) i A(x1) Induktivní definice umožňují popsat potenciálně nekonečné struktury př.: definice číselných výrazů se sčítáním a násobením číslo je výraz (x + y), kde x a y jsou výrazy, je výraz (x ∗ y), kde x a y jsou výrazy, je výraz Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Složitější typy indukce Složitější typy indukce (2) Strukturální indukce aplikujeme na induktivně definované objekty (např. výrazy) báze indukce: výrok platí pro čísla indukční krok 1: výrok platí pro x a y ⇒ platí i pro (x + y) indukční krok 2: výrok platí pro x a y ⇒ platí i pro (x ∗ y) Princip zůstává stejný, pouze vedení důkazu je komplikovanější Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004 Obsah přednášky Matematická logika Výroková logika Něco z predikátové logiky Matematická indukce Příklad 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 − 1 koních; dokážeme, že platí pro stádo o velikosti n S1 = {K1, ..., Kn−1}, S2 = {K2, ..., Kn} podle I. P. mají v S1 i v S2 všichni koně stejnou barvu koně K2, ..., Kn−1 jsou v obou stádech ⇒ i barva obou stád je stejná tedy i ve stádě S = {K1, ..., Kn} mají všichni koně stejnou barvu Kde je problém? (všichni studenti oboru PLIN mají stejné pohlaví?) Pavel Rychlý, Vojtěch Kovář FI MU Brno PLIN004