DIMA - Teorie grafů



Druhy matematických důkazů

Obsah ⇫

Teorie ⇫

V této kapitole si shrneme matematické důkazy, jejich druhy a používání. Důkazy je dobré studovat především proto, že kdo porozumí důkazům, porozumí většinou i dané látce. Pokud student pochopí, proč daná věc funguje, snadněji si ji zapamatuje a i po čase bude látce rozumnět.

Matematická věta je výrok o matematických objektech.

Často má tvar:

  • ∀x∈M: A(x)⇒B(x)
  • ∀x∈M: A(x)⇔B(x)

Složený výrok je soubor dvou a více výroků složených pomocí logických operací. V následující tabulce je znázorněn přepis mluveného vyjádření logické podmínky na její matematický zápis pomocí symbolů:

Složené výroky

Chceme vyjádřit, že Vytvoříme výrok Symbol
Platí každý z výroků A, B. A a zároveň B A∧B
Platí alespoň jeden z výroků A, B. A nebo B A∨B
Jestliže platí A, platí i B (platnost A se nevyžaduje) Jestliže A, pak B A⇒B
Výroky A, B mají stejnou pravdivostní hodnotu A právě tehdy, když B A⇔B

Axióma – elementární tvrzení, které považujeme za pravdivé bez důkazu.

Mějme větu typu: ∀x∈M: A(x)⇒B(x). Definujeme:

  • obměněná věta: ∀x∈M: B´(x)⇒A´(x) (má stejnou pravdivostní hodnotu jako původní věta)
  • obrácená věta: ∀x∈M: B(x)⇒A(x) (nemusí mít stejnou pravdivostní hodnotu)
  • negace věty: ∃x∈M: A(x)∧B´(x) (má opačnou pravdivostní hodnotu než původní věta)

Tabulka pravdivostních hodnot složených výrazů:

A B A´ B´ A⇒B B´⇒A´ B⇒A A∧B´
1 1 0 0 1 1 1 0
1 0 0 1 0 0 1 1
0 1 1 0 1 1 0 0
0 0 1 1 1 1 1 0

Důkaz věty, resp. daného tvrzení je logický proces, kterého cílem je ukázat pravdivost tvrzení pomocí axióm, definic a již předtím dokázaných vět. Důkazy mohou mít různou formu. Nejznámější druhy důkazů jsou přímý důkaz, nepřímý důkaz a důkaz matematickou indukcí.

Důkaz přímo:

Přímý důkaz jednoduchého výroku vychází z pravidla, kdy při dokazování výroku T, musíme nejdříve najít nějaký výrok T1, o němž víme, že je pravdivý, a dále pravdivou implikaci T1 ⇒ T. Takovou implikaci obvykle hned nenajdeme, ale sestavíme ji postupně z několika dílčích, u kterých víme, že jsou pravdivé.

Přímý důkaz matematické implikace dokážeme z již ověřených a známých faktů. Chceme-li dokázat výrok B, základní myšlenka je následující: Platí-li výrok A a výrok A ⇒ B, pak musí platit také výrok B.

  1. tvrzení T: Sestavíme konečný řetězec implikací:
    • T1⇒T2⇒T3⇒…⇒Tn⇒T, kde T1,…,Tn jsou axiómy resp. dokázaná tvrzení, každé je logickým  důsledkem předchozího. Posledním členem je dokazované tvrzení T.
  2. implikace A⇒B: Předpokládáme, že A platí a sestavíme řetězec implikací:
    • A⇒B1⇒B2⇒…⇒Bn⇒B, kde B1,…,Bn jsou axiómy nebo dokázaná tvrzení. Vyjdeme z předpokladu implikace a přímým řetězcem implikací se dopracujeme k závěru.

Příklad

Dokažte: ∀n∈N: 2|(n2-3n).

pro n sudé: n = 2k ⇒ n2- 3n = (2k)2 - 3∙2k = 4k2 - 6k = 2(2k2 - 3k), n2 - 3n je násobkem čísla 2 ⇒ 2|(n2 - 3n),

pro n liché: n = 2k + 1 ⇒ n2- 3n = (2k + 1)2-3∙(2k + 1) = 4k2 - 2k - 2 = 2(2k2 - k - 1) ⇒ n2 - 3n je násobkem 2 ⇒ 2|(n2 - 3n)

Máte-li zájem, můžete se podívat na zajímavá videa (klip 1, klip 2), které zobrazují postup dokazování matematického výroku pomocí přímého důkazu krok za krokem.

Důkaz nepřímo:

Nepřímý důkaz se podobně jako přímý důkaz používá při dokazování platnosti vět tvaru A⇒B. Při nepřímém důkazu se nedokazuje platnost původního výroku, ale platnost obměněného výroku B´⇒A´.

Vytvoříme obměnu implikace t.j. B´⇒A´ a tuto dokazujeme přímo: B´⇒B1⇒B2⇒…⇒Bn⇒A´. Využíváme skutečnost, že implikace a její obměna mají vždycky stejnou pravdivostní hodnotu, a proto namísto implikace můžeme dokazovat její obměnu.

Příklad

Dokažte: ∀ n ∈ N : 5 | (n2 + 6) ⇒ 5 nedělí n.

Obměna: ∀ n ∈ N :5 | n ⇒ 5 ∤ (n2 + 6)

5 | n ⇒ ∃k ∈ N, n = 5k ⇒ n2 + 6 = (5k)2 + 6 = 25k2 + 5 + 1 ⇒ n2 + 6 = 5(5k2+1)+1 ⇒

⇒ n2 + 6 při dělení 5 dá zbytek 1 ⇒ 5 nedělí n2 + 6 ⇒

⇒ ∀n∈N : 5|(n2+6) ⇒ 5 nedělí n.

Důkaz sporem:

Důkaz sporem je typ logického důkazu, ve kterém se prokáže, že předpoklad vede k nesmyslnému výsledku (ke sporu). Používáme zde negaci původní věty a tedy fakt, že neplatí-li negovaný výrok, platí výrok původní a opačně.

  1. tvrzení T:
    • Vytvoříme negaci výroku T t.j. T´ a z něho odvozujeme logické důsledky tak dlouho, až odvodíme tvrzení S, o kterém víme, že je určitě nepravdivé. Hovoříme, že jsme přišli ke sporu.
    • Vyhlásíme: T´ neplatí, pravdivý je původní výrok T.
  2. implikace A⇒B:
    • Předpokládáme, že platí negace věty t.j. A∧B´. Z této negace odvodíme logický nepravdivý výrok S.
    • Závěr: negace věty neplatí, platí tedy původní veta.

Příklad

Jestliže p je prvočíslo větší než 2, pak p je liché.

Provedeme negaci věty: Nechť p je prvočíslo větší než 2 a zároveň je sudé.

Je-li p sudé, pak můžeme psát p = 2·k pro libovolné k > 1, k je celé číslo ⇒ pak p je dělitelné k ⇒

⇒ p není prvočíslo ⇒ spor s předpokladem, že p je prvočíslo.

Negace věty neplatí, platí tedy původní výrok.

Důkaz matematickou indukcí:

Matematická indukce je důležitý prostředek na dokazování tvrzení, že prvky nějaké množiny mají určitou vlastnost. Pomocí matematické indukce se dokazuje pravdivost výroků tvaru: ∀n∈N, n≥ n0: V(n), kde n0 je dané přirozené číslo.

Nechť V je nějaké tvrzení, které závisí na množině přirozených čísel. Chceme ukázat, že tvrzení V(n) platí pro přirozená čísla n=n0, n0 + 1, n0 + 2, ...

Důkaz matematickou indukcí má 2 kroky a závěr:

  1. Dokážeme platnost tvrzení pro první prvek n0, resp. pro nejmenší prvek z uvažované množiny.
  2. Předpokládáme, že dané tvrzení V platí pro jakékoliv přirozené číslo n = k ≥ n0 a (za tohoto předpokladu) dokážeme, že platí pro následující přirozené číslo n = k + 1. Takže ukážeme, že z platnosti V(k) vyplívá platnost V(k + 1).

Na závěr můžeme prohlásit, že v kroku 1 jsme dokázali, že platí tvrzení V(n0). Dále z kroku 2 vyplývá platnost tvrzení V(n0 + 1). Z toho opět na základě kroku 2 vyplývá platnost pro V(n0 + 2), V(n0+3),...

Tím je tedy tvrzení V splněné pro všechna přirozená čísla n≥n0.

Příklad

Dokažte: ∀n ∈ N : 2 + 4 + 6 + ... + 2n = n(n + 1)

Dokážeme indukcí:

  1. n = 1

    2∙1 = 1(1 + 1)

    2 = 2 - V(1) platí

  2. dokazujeme implikaci: ∀a∈N: V(a)⇒V(a+1)

    předpokládáme, že platí V(a): 2 + 4 + ... + 2a = a(a + 1) - tomu říkáme IP (indukční předpoklad)

    dále dokážeme, že V(a+1) platí s využitím indukčního předpokladu:

    V(a+1): 2 + 4 + ... + 2(a+1) = (a+1)(a+2)

    2 + 4 + ... + 2a + 2(a+1) = a(a+1) + 2(a+1) = (žlutá část výrazu je podle IP rovna a(a+1))

    = (a+1)(a+2)... dokázané V(a+1) pomocí V(a)

    platí V(a) ⇒ V(a+1)

Negace výroků

Výrok (Negace výroku) ⇆ Negace výroku (Výrok)
Každý ... je ... Alespoň jeden ... není ...
Žádný ... není ... Alespoň jeden ... je ...
Alespoň n ... je ... Nejvýše n-1 ... je ...
Právě n ... je ... Nejvýše n-1 nebo alespoň n+1 ... je ...

Negace složených výroků

(A∧B)´ ⇔ A´∨B´
(A∨B)´ ⇔ A´∧B´
(A⇒B)´ ⇔ A∧B´
(A⇔B)´ ⇔ (A∧B´)∨(A´∧B)

Řešený příklad ⇫

1. Dokažte: ∀n∈N: 2∣n2 ⇒ 2∣n.

Krok 1

Důkaz nepřímo (obměna): ∀n∈N: 2∤n ⇒ 2∤n2, 2∤n ⇒ n je liché ⇒ ∃k∈N: n = 2k+1 ⇒ n2 = (2k+1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1 ⇒ n2 je liché číslo. Můžeme tedy prohlásit, že 2∤n2. Pravdivý je tedy i původní výrok.

2. Sestavte negaci výroku ∀a>1 : a2>a.

Krok 1

Kvantifikátor ∀ nahradíme výrazem ∃ a operand > nahradíme operandem ≤

Krok 2

Takže výsledný výraz bude ∃a1 : a2≤a

Úlohy k řešení ⇫

1. Utvořte negaci výroku: Číslo 72 je dělitelné dvěma a zároveň 72 je dělitelné třemi.

Výsledek

Číslo 72 není dělitelné dvěma nebo číslo 72 není dělitelné třemi.

2. Utvořte negaci výroku: Žádné prvočíslo není sudé.

Výsledek

Alespoň jedno prvočíslo je sudé.

3. Utvořte negaci a obměnu následujícího výroku: Jestliže číslo X je liché, pak číslo Y dělí číslo 30.

Výsledek

Negace: Číslo X je liché a zároveň číslo Y nedělí číslo 30.

Obměna: Jestliže číslo Y nedělí číslo 30, pak číslo X není liché.

4. Dokažte: ∀n∈N: 2∣n2 ⇒ 2∣n

Výsledek

nepřímý důkaz:

  • Obměněný výrok: ∀n∈N: 2∤n ⇒ 2∤n2
  • Důkaz: ∀n∈N: 2∤n ⇒ n je liché, tj. ∃k∈N: n = 2k+1 ⇒ n2 = (2k+1)2 ⇒ n2 = 4k2+4k+1 ⇒ n2 = 2(2k2+2k)+1 ⇒ n2 je liché číslo ⇒ 2∤n2
  • Platí obměněný výrok, platí tedy i původní výrok.

5. Dokažte: ∀n∈N: 2∤n3 ⇒ 4∤n

Výsledek

Důkaz sporem:

  • Negace: ∃n∈N: 2∤n3∧4∣n

    4∣n ⇒ n = 4k ⇒ n3 = (4k)3 = 64k3 = 2∙32k3 ⇒ n3 je sudé, což je spor s předpokladem 2∤n3 (n3 není dělitelné 2, tj. n3 není sudé číslo)

  • Negace neplatí, tedy platí původní výrok.

6. Negujte výroky:

  • Příjde Petr nebo Pavel.
  • Když příjde Michal, příjde i Jan.
  • Karel příjde právě tehdy, když příjde i Josef.
  • Příjde Anna a Hana.

Výsledek

  • Petr nepříjde a Pavel také nepříjde.
  • Michal příjde a Jan nepříjde.
  • Buď Karel příjde a Josef nepříjde nebo Karel nepříjde a Josef příjde.
  • Anna nepříjde nebo Hana nepříjde.

Zdroje textů

  1. DIMA - diskrétní matematika, http://oliva.uhk.cz
  2. Rácová, Marta Matematika - prehľad stredoškolského učiva pre maturantov a uchádzačov o štúdium na vysokých školách, Nitra: ENIGMA, 1994, ISBN 80-85471-22-1
  3. Šedivý, Lukátšová, Odvárko, Zöldy, Úlohy o výrokoch a množinách pre 1. ročník gymnázia, 1970
  4. Kovář, Petr DISKRÉTNÍ MATEMATIKA a ÚVOD DO TEORIE GRAFŮ ( příklady k procvičení ), 2012
  5. Matematika polopatě, http://www.matweb.cz/dukazy