Teoria ja esimerkit

2018-05-17T10:41:00+03:00

Suora todistus

Perustuu tautologiaan A ⋀ (A ⇒ B) ⇒ B (Modus ponens).

A on tosi. Implikaatio A ⇒ B on tosi, jos sekä A ja B ovat tosia. Implikaation A ⇒ B todistamiseen riittää siis osoittaa, että B on tosi.

Rakenne Oletus: A

Väite: B

Todistus: Päätellään oletuksesta A väite B käyttäen hyväksi tunnettuja tosiasioita, esim. aksioomeja tai aiemmin todeksi osoitettuja lauseita.

HUOM! Parillinen luku eli 2:lla jaollinen luku on muotoa 2m, missä m ∈ ℤ ja pariton muotoa 2m + 1, m ∈ ℤ. Luvulla 3 jaollinen on muotoa 3m, m ∈ ℤ.

ESIM 1. Osoita, että kahden parittoman luvun tulo on aina pariton.

Oletus: Luvut m ja n ovat parittomia.

Väite: m * n on pariton

Todistus: Oletuksen mukaan
m = 2a + 1 , a € Z
n = 2b + 1 , b € Z

tulo m * n = (2a + 1)(2b + 1) = 4ab + 2a + 2b + 1 = 2(2ab + a + b) + 1 = 2k + 1, k € Z
(2ab + a + b) € Z

Siis kahden parittoman luvun tulo on pariton.

ESIM 2. Todista, että kolmion kulman vieruskulma on yhtä suuri kuin kolmion muiden kulmien summa.

Oletus: α, β ja γ ovat kolmion kulmia ja α' on kulman α vieruskulma.

Väite: α' = β + γ

Todistus:

α + α' = 180^O(vieruskulmat)
α' = 180^O - α (kolmion kulmien summa)
α' = (α + β + γ) - α (sievennetään)
α' = β + γ

Siis kolmion kulman vieruskulma on yhtä suuri kuin kolmion muiden kulmien summa.
(Siis väite on tosi.)

HUOM! Ekvivalenssimuotoinen lause A <=> B (”A jos ja vain jos B”) todistetaan osoittamalla implikaatiot molempiin suuntiin todeksi eli
osoitetaan lause A ⇒ B ja sen
käänteislause B ⇒ A todeksi.

ESIM 3. Todista, että a < 0 jos ja vain jos a < –a. (eli a < 0 <=> a < –a)

Todistus:
(1) todistetaan ensin a < 0 => a < -a
Oletus: a < 0
Väite: a < -a
Todistus:
a < 0 || -a
0 < -a
siis a < -a ( lukusuora: ___ a ____ 0 ___ -a ____> )
(2) todistetaan sitten a < -a => a < 0
Oletus: a < -a
Väite: a < 0
Todistus:
a < -a || +a
2a < 0 || :2
a < 0

Koska sekä (1) että (2) saatiin todistettua, niin a < 0 <=> a < -a.

Epäsuora todistus
Epäsuorassa todistuksessa tehdään vastaväite eli antiteesi ("vastaoletus"). Todistetaan, että vastaväitteestä seuraa ristiriita alkuperäisen oletuksen kanssa tai jonkun yleisesti tiedetyn toden kanssa. Tällöin vastaväite on väärä eli väite on oikea. Epäsuora todistus perustuu
kontrapositiolakiin (A ⇒ B) ⇔ (¬B ⇒ ¬A) tai
kontradiktioon eli todettuun ristiriitaan (A ⇒ B) ⇔ ((A ∧¬B) ⇒ ristiriita)

ESIM 4. Todista, että jos n² on pariton, niin luku n ∈ ℤ on pariton.
Oletus: n² on pariton eli n² = 2r + 1, r ∈ ℤ.
Väite: n ∈ ℤ on pariton eli n = 2s + 1, s ∈ ℤ.
Todistus:
Vastaväite: n on parillinen eli n = 2s , s ∈ ℤ.
n² = (2s)² = 4s² = 2* 2s² = 2r, r ∈ ℤ.
Päädytään ristiriitaan oletuksen kanssa, joten alkuperäinen väite on tosi.

ESIM 5. Osoita, että irrationaaliluvun ja rationaaliluvun summa on irrationaaliluku.

ESIM 6, Osoita, että luku √2 on irrationaaliluku.
(Oletus: Rationaaliluku voidaan kirjoittaa täysin supistetussa muodossa murtolukuna m/n (m, n ∈ ℤ, n ≠ 0). )

4.2 Suora ja epäsuora todistus

Teoria ja esimerkit