Nepřímý důkaz

Z Wikipedie, otevřené encyklopedie

Nepřímý důkaz se v matematice používá k dokázání matematických vět tvaru implikace P \rightarrow T, tj. vět tvaru „Jestliže platí předpoklad P, pak platí také tvrzení T“. Spočívá v tom, že se z negace výroku T odvodí negace výroku P, tj. dokáže se tvrzení \neg T \rightarrow \neg P.

Obsah

[editovat] Zdůvodnění správnosti

Dokázáním implikace \neg T \rightarrow \neg P je již skutečně dokázáno i P \rightarrow T. Pokud totiž P platí, musí platit i T, jinak by totiž platilo \neg T a podle dokázané implikace \neg P, tedy by neplatilo P.

[editovat] Souvislost s důkazem sporem

Nepřímý důkaz je úzce spjatý s důkazem sporem. Každý nepřímý důkaz lze převést na důkaz sporem. Dokazujeme-li totiž implikaci P \rightarrow T nepřímo, tj. dokazujeme-li \neg T \rightarrow \neg P, lze před celý důkaz tohoto tvrzení přidat větu „Předpokládejme pro spor, že platí P neplatí T.“ a po dokázání \neg P zakončit důkaz konstatováním „…, což je spor s předpokladem.“ Tím je nepřímý důkaz převeden na důkaz sporem.

[editovat] Příklady

Nepřímý důkaz tvrzení „Pro každá dvě celá čísla \,a, \,b, pokud a\cdot b=0, pak \,a=0 nebo \,b=0“ lze provést následovně:

  • Nechť platí negace závěru, tj. \,a i \,b jsou nenulové.
  • Pak \,|a| i \,|b| jsou \geq 1.
  • Tedy |a\cdot b|=|a|\cdot|b|\geq 1.
  • A proto a\cdot b \neq 0.

[editovat] Podívejte se také na