Důkazové metody. Teoretická informatika Tomáš Foltýnek

Teoretická informatika Tomáš Foltýnek [email protected]

Důkazové metody

Teoretická informatika

Matematický důkaz •  Jsou dány axiomy a věta (tvrzení, teorém), o níž chceme ukázat, zda platí. •  Matematický důkaz je nezpochybnitelné zdůvodnění pravdivosti určitého tvrzení za předpokladu platnosti daných axiomů


Typy matematických vět •  Dva typy matematických vět –  Obecná matematická věta: (∀x)V(x) –  Existenční věta: (∃x)V(x)

•  V(x) je obvykle psána jako –  implikace P(x) ⇒ Z(x), nebo –  ekvivalence P(x) ⇔ Z(x) •  P je předpoklad (premisa) •  Z je závěr (konkluze)


Metody matematických důkazů •  Důkazy obecných vět –  Přímý důkaz –  Nepřímý důkaz –  Důkaz sporem –  Důkaz matematickou indukcí

•  Důkazy existenčních vět –  Konstrukční důkaz –  Ryze existenční důkaz


Přímý důkaz •  Jediný formálně uznatelný důkaz –  Ostatní metody je ale vždy možno převést na přímý důkaz

•  Posloupnost tvrzení T1, T2, … Tn, kde Ti je buďto –  –  –  – 

předpoklad P(x) axiom závěr odvozovacího pravidla s předpoklady Tj, j
•  Posloupnost formulí, které ze sebe logicky vyplývají


Přímý důkaz - příklad •  Dokažte, že na množině přirozených čísel platí (∀x)((x≥2)⇒(6x + 3 > 13)) •  Vyjdeme z předpokladu, že x ≥ 2 a postupně dojdeme k závěru, že 6x+3>13 –  –  –  –  – 

x≥2 6x ≥ 12 6x + 1 ≥ 12 + 1 6x + 1 ≥ 13 6x + 3 > 13


Nepřímý důkaz •  Nepřímý důkaz je přímé dokázání obměny implikace •  Příklad: Dokažte, že pro všechna celá čísla platí: je-li n2 liché, pak i n je liché. –  (∀n)(L(n2)⇒L(n)) –  Obměna: (∀n)(S(n)⇒S(n2)) –  Což je snadné dokázat


Nepřímý důkaz – příklad •  Dokažte, že pro libovolné prvočíslo p platí: p|n2 ⇒ p|n •  Obměna implikace ¬p|n ⇒ ¬p|n2 •  Pokud p nedělí n, pak n=pt+r pro vhodná celá t,r taková, že 0

Důkaz sporem •  Předpokládáme neplatnost dokazovaného tvrzení a poté přímým důkazem (tj. nezpochybnitelnými implikacemi) dojdeme k evidentní kontradikci. •  Dokazovaná věta tudíž musí (za předpokladu bezespornosti teorie) platit


Důkaz sporem – příklad I. •  Dokažte, že pro všechna celá čísla platí: je-li n2 liché, pak i n je liché. –  (∀n)(L(n2)⇒L(n))

•  Vyslovíme negaci dokazovaného tvrzení –  (∃n)(L(n2)∧S(n))

•  Protože ale S(n) ⇒ n = 2k, k∈N ⇒ n2 = (2k)2 = 2*2*k2 ⇒ S(n2) •  Dostáváme tedy spor –  L(n2) ∧ S(n2)

•  Negace věty nemůže platit, musí tedy platit dokazovaná věta


Důkaz sporem – příklad II. •  Dokažte, že nemůže existovat sudé prvočíslo větší než 2 •  Jinými slovy: Všechna prvočísla větší než 2 jsou lichá. •  Předpokládejme, že existuje sudé prvočíslo X > 2. •  Pak platí: X není dělitelné žádným jiným číslem kromě 1 a X •  Tedy X není dělitelné dvěma •  X je sudé, tedy X je dělitelné dvěma •  X tedy zároveň je a není dělitelné dvěma


Důkaz matematickou indukcí •  Používá se při důkazu tvrzení platného pro všechna přirozená čísla •  Tvrzení dokážeme pro první prvek •  Dokážeme, že platí-li pro nějaký prvek, platí i pro jeho následníka •  Tím pádem víme, že platí pro všechny prvky


Matematická indukce – příklad •  Dokažte, že pro všechna přirozená čísla platí 1+2+…+n = n(n+1)/2 •  Dokážeme platnost pro n = 1: –  1 = 1*2/2 = 1 •  Dokážeme, že platí-li tvrzení pro k∈N, platí i pro k+1 –  1+2+…+k = k(k+1)/2 ⇒ 1+2+…+k+(k+1) = (k+1)(k+2)/2 –  Upravujeme výraz na pravé straně implikace –  1+2+…+k+(k+1) = (k+1)(k+2)/2 –  k(k+1)/2 + (k+1) = (k+1)(k+2)/2 –  k/2 + 1 = (k+2)/2 –  k + 2 = k + 2 –  Implikace je tedy pravdivá •  Uvedené tvrzení platí pro všechna přirozená čísla


Matematická indukce – příklady

•  Dokažte, že pro všechna přirozená n platí

•  Dokažte, že je-li r ∈  libovolné, r≠1, pak pro každé n ∈ 0 platí


Konstrukční důkaz •  Máme-li dokázat existenci určitého objektu, zkonstruujeme jej •  Příklad: Dokažte, že existuje pravoúhlý trojúhelník s celočíselnými délkami stran. •  Důkaz: –  Na základě Pythagorovy věty můžeme větu přeformulovat jako ∃a,b,c ∈  : a2 + b2 = c2 –  Pak snadno ukážeme, že pro a = 3, b = 4 a c = 5 uvedené tvrzení platí


Ryze existenční důkaz •  Dokážeme existenci požadovaného objektu, aniž bychom jej museli konstruovat •  Příklad: Je dán bílý čtverec 10x10cm a v něm je 101 bodů obarveno na červeno. Dokažte, že při libovolném obarvení těchto bodů existuje trojúhelník s obsahem 1cm2 který obsahuje alespoň dva červené body. •  Důkaz: Obsah čtverce je 100cm2, obsah trojúhelníka je 1cm2. Do čtverce lze vepsat právě 100 trojúhelníků. Kdyby v každém z nich byl 1 červený bod, museli bychom 101. bod umístit do trojúhelníka, kde už jeden červený bod je. •  Použili jsme tzv. Dirichletův princip


Ryze existenční důkaz – příklad •  Algebraické číslo je takové komplexní číslo, které je kořenem žádné algebraické rovnice s racionálními koeficienty. •  Číslo, které není algebraické, se nazývá transcendentní. •  Věta: Existuje transcendentní číslo. •  Důkaz: Algebraických rovnic je spočetně mnoho, tedy algebraických čísel je spočetně mnoho. Reálných čísel je však nespočetně mnoho, musí mezi nimi být i taková, která jsou transcendentní. –  vysvětlení pojmů viz předáška o nekonečných číslech


Příklady • 

Dokažte přímým důkazem –  ∀n ∈  : 5|n ⇒ 30 | (n3 – n) –  ∀n ∈  : ¬2|n ⇒ 16 | (n4 – 1)

• 

• 

•  Dokažte uvedená tvrzení sporem Dokažte, že aritmetický průměr dvou nezáporných reálných čísel je větší nebo roven jejich průměru geometrickému –  tj. a + b

• 

• 

Dokažte nepřímým důkazem –  ∀n ∈  : 5|(n2+1) ⇒ ¬5|n –  ∀n ∈  : 3|(n2+1) ⇒ ¬6|n

• 

–  ∀n ∈  : 9|(4n+15n – 1) –  ∀n ∈  : 2n > 2n + 1

2

≥ a⋅ b

Dokažte matematickou indukcí –  ∀n ∈  : 6|(n3+11n) €

Dokažte, že součet třetích mocnin každých po sobě jdoucích přirozených čísel je dělitelný devíti. Turista zahájí při východu slunce výstup na horu a dosáhne vrcholu při západu slunce. Následujícího dne začne po východu slunce sestupovat po stejné cestě a sestup dokončí se západem slunce. Dokažte, že existuje míso, jímž turista projde ve stejnou denní dobu jak při výstupu, tak při sestupu.

Důkazové metody. Teoretická informatika Tomáš Foltýnek

Recommend Documents