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
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 1 / 18
Obsah přednášky
Obsah přednášky
Matematická logika
Výroková logika
Něco z predikátové logiky
Matematická indukce
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 2 / 18
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
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 3 / 18
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)
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 4 / 18
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ář (FI MU Brno) PLIN004 část 2 5 / 18
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
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 6 / 18
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)
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 7 / 18
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
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 8 / 18
Výroková logika Odvozování
Příklad důkazu: X ⇒ X
Schémata axiomů
A ⇒ (B ⇒ A)
(A ⇒ (B ⇒ C)) ⇒ ((A ⇒ B) ⇒ (A ⇒ C))
(¬B ⇒ ¬A) ⇒ (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) / axiom 1
3. (X ⇒ (X ⇒ X)) ⇒ (X ⇒ X) / aplikace modus ponens na 2. a 1.
4. X ⇒ (X ⇒ X) / axiom 1
5. X ⇒ X / aplikace modus ponens na 4. a 3.
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 9 / 18
Něco z predikátové logiky Něco z predikátové logiky
Něco z predikátové logiky (1)
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
∃ – existuje alespoň jedno ohodnocení, při kterém formule platí
∀ – výrok platí pro všechna možná ohodnocení
např.: ∃x(x = 0 ∧ x = 1)
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 10 / 18
Něco z predikátové logiky Něco z predikátové logiky
Něco z predikátové logiky (2)
Predikáty
funkční symboly – vyjadřují fakta o konstantách a proměnných
např. Prime(x) – „x je prvočíslo”
např. ∈ (x, Y ), resp. x ∈ Y – „prvek x patří do množiny Y ”
Příklady složitějších formulí
∃x(∃k(x = 2k + 1) ∧ ∃m(x = 2m))
∀x(Prime(x) ⇒ ∃k(x = 2k))
∃x(Prime(x) ∧ ∃k(x = 2k))
dokážete je přečíst?
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 11 / 18
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
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 12 / 18
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 + 1)/2 ∗ (1 + (k + 1))
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 13 / 18
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 + 1)/2 ∗ (1 + (k + 1))
1 + 2 + ... + k + (k + 1)
k/2 ∗ (1 + k) + (k + 1)
(k + k2)/2 + (k + 1)
(k + k2 + 2k + 2)/2
(k2 + 3k + 2)/2
(k + 2) ∗ (k + 1)/2
(k + 1)/2 ∗ (k + 2)
(k + 1)/2 ∗ (1 + (k + 1))
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 14 / 18
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
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 15 / 18
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
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 16 / 18
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ší
Důkaz, že každý výraz podle definice výše má sudý počet závorek?
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 17 / 18
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?
Vojtěch Kovář (FI MU Brno) PLIN004 část 2 18 / 18