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
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.
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)
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)
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)
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?
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
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))
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
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))
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ší
Důkaz, že každý výraz podle definice výše má sudý počet závorek?
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