Rámcová náplň cvičení

• Probírají se důkazové techniky. Důkaz obrácením implikace a důkaz sporem. Zopakování správného logického významu implikace a negace výroků v tomto kontextu.
  • Proč je důkaz sporem tak "mocný" a užitečný - "přibírá" si ke své práci více předpokladů získaných negací původního závěru.
  • Klasická velmi hezká ukázka na důkaz sporem: Odmocnina ze 2 není racionální číslo.
• Pokračuje se (ano, zase znovu, neboť je to důležité) s vysvětlením významu implikace v zapeklitém případě sporných předpokladů, viz příklady níže a ze cvičných odpovědníků.
  • Najděte minimální podmnožiny z následujících tří předpokladů; y<0, x>y>0, x=y; z nichž ještě vyplývá, že x^2-y>0.
• Důkazy matematickou indukcí, podrobné rozebrání některých ukázek z přednášky či podobných, třeba důkazy sumačních vzorců a jiných kombinatorických identit (náměty dole). Vysvětlení techniky "zesílení" dokazovaného tvrzení, a proč tento přístup tak dobře pomáhá matematické indukci (získáváme silnější indukční předpoklad pro další odvozování).
  • Především na zesílení tvrzení je Příklad 2.9 z přednášky, nebo třeba následující:
    Nechť máme rekurentní posloupnost f(0)=0, f(n+1)=2*f(n)+3, pak f(n)<3*2^n pro všechna přirozená n. 
• Zvlášť vysvětlení významu báze indukce (první kostička musí "spadnout"!), opětovné rozebrání falešného příkladu s koňmi stejné barvy z přednášky - Příklad 2.11 z přednášky - kde je podstata falešnosti tohoto "důkazu".

Jelikož je látka tohoto cvičení poměrně obtížná, bude spíše "přednášena" cvičícím než interaktivně procvičována.

Možné další příklady k demonstraci důkazů

(Libovolný výběr z nabídky, která doplňuje obsah přednášky.)

• Jestliže x^2 je celé sudé, pak také x je sudé. Jinak řečeno (proč je to totéž?): Součin dvou lichých celých čísel je lichý.
• Pro všechna x existuje y takové, že x+y>2014 (jaký je číselný obor?).
• Existuje x takové, že pro všechna y platí x+y>2014. Je toto vůbec platné tvrzení (podle číselného oboru)?
• Jestliže p je prvočíslo, tak p+1 je složené. Jaký dodatečný předpoklad je třeba přijmout?
• 2^(6k)-1 pro celé k je dělitelné sedmi.
• 2^n >= 2n pro celé n>=1 (pro n=0 platí taky, ale špatně se dokazuje první ind. krok, lépe je udělat dva zákl. kroky).

• 1+3+5+...+(2*n+1) = (n+1)^2,
  1^2+2^2+...+n^2 = n*(n+1)*(2*n+1)/6,
  1^3+2^3+...+n^3 = (1+2+...+n)^2  (zkuste "zesílení" tvrzení, čemu se obě strany rovnají?),
  f_0+f_1+...+f_(n-1) = f_(n+1)-1  (součet členů Fibonacciho posl.).

A případně trochu složitější důkazy.

• Jestliže p i p+2 jsou prvočísla, tak p+4 je složené. Jaký dodatečný předpoklad je třeba přijmout?
• Šachovnici 2^n*2^n lze pokrýt "tříčtverečkovými L-segmenty” tak, aby právě jedno předem zvolené pole zůstalo nepokryto.
• Šachovnici 8x8 s vystřiženým levým dolním a pravým horním rohem nelze pokrýt 31 obdélníčky 2x1.
• Na kolik nejvýše částí rozdělí rovinu n kružnic (obdoba přímek z přednášky).

• Obecně řešení a důkaz jednoduchých rekurentních posloupností; příkladem f(n+1)=2*f(n)+3 kde f(0)=1 a podobné.
  Jak "uhodnout" správný výsledek 2^(n+2)-3 v tomto případě a jak jej dokázat indukcí?
  Proč se ve výsledku vyskytuje mocnina 2? A mocnina kterého základu by se vyskytovala při řešení f(n+1)=5*f(n)-1 ?
• Obecně řešení a důkaz jednoduchých polynomiálních sumací, jako zmíněná 1^2+2^2+...+n^2 = n*(n+1)*(2*n+1)/2. Proč je výsledek vždy opět polynomem a jakého je stupně? Jak "uhodnout" správný výsledek takové konkrétní sumace? Kolik počátečních členů nám stačí k "uhodnutí" koeficientů polynomu?