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
12. 10. 2010
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 12. 10. 2010 1 / 15
Obsah přednášky
Obsah přednášky
Matematická logika
Výroková logika
Něco z predikátové logiky
Matematická indukce
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 12. 10. 2010 2 / 15
Matematická logika 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 12. 10. 2010 3 / 15
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á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 12. 10. 2010 4 / 15
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
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 12. 10. 2010 5 / 15
Výroková logika 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 12. 10. 2010 6 / 15
Výroková logika 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 12. 10. 2010 7 / 15
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))
(¬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 12. 10. 2010 8 / 15
Něco z predikátové logiky 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 12. 10. 2010 9 / 15
Něco z predikátové logiky 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 12. 10. 2010 10 / 15
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 12. 10. 2010 11 / 15
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 12. 10. 2010 12 / 15
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 12. 10. 2010 13 / 15
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 12. 10. 2010 14 / 15
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 12. 10. 2010 15 / 15