Todistusmenetelmiä

Matematiikassa lauseet voidaan yleensä esittää loogisina seurauksina \(p \Rightarrow q\), jossa oletuksesta \(p\) seuraa väite \(q\). Toinen yleinen muotoilu on looginen ekvivalenssi \(p \Leftrightarrow q\), joka voidaan ekvivalenssilain nojalla muotoilla myös samaan aikaan voimassa olevina seurauksina \(p \Rightarrow q\) ja \(q \Rightarrow p\). Oletusten ja väitteen väliin on kehitettävä todistus, joka on oikeastaan vain aukoton päätelmien ketju.

Väitettä todistaessa valitaan varsin usein jokin seuraavista menetelmistä. Kaikki niistä eivät aina käy jonkin tietyn väitteen todistamiseen, ja joillakin on hyvin rajatut soveltuvuusalueet. Tämän vuoksi on tärkeää osata valita oikea menetelmä oikeassa tilanteessa.

1. Suora todistus. Oletusten ja aikaisempien tulosten perusteella tehdään päätelmiä, jotka johtavat suoraan väitteeseen.
2. Epäsuora todistus. Tämä menetelmä voidaan muotoilla kontrapositiotodistuksena tai ristiriitatodistuksena. Kontrapositiotodistuksessa hyödynnetään kontrapositiolakia ja pyritään todistamaan looginen seuraus \(\neg q \Rightarrow \neg p\). Ristiriitatodistuksessa tehdään vastaoletus \(\neg q\) ja pyritään osoittamaan jokin ristiriita \(r \land \neg r\).
3. Esimerkkitodistus. Jos on todistettava muotoa \(\exists x : p(x)\) oleva lause, niin riittää esittää yksi esimerkki alkiosta \(x\), jolla on ominaisuus \(p\). Jos puolestaan on todistettava muotoa \(\forall x : p(x)\) oleva lause vääräksi, niin negaation vaihtosäännön nojalla riittää esittää yksi esimerkki alkiosta \(x\), jolla ei ole ominaisuutta \(p\). Tätä kutsutaan vastaesimerkiksi.
4. Induktiotodistus. Käsitellään myöhemmin.

Esimerkki.

Osoita, että \(x^2 + x + 1 > 0\) aina, kun \(x > 0\).

Todistus.

Oletetaan, että \(x > 0\). Tällöin reaalilukujen järjestysaksioomien nojalla myös \(x^2 > 0\), ja lisäksi \(1 > 0\). Nyt siis \(x^2 + x + 1 > 0\). \(\square\)

Esimerkki.

Olkoon \(n\) kokonaisluku. Osoita, että jos \(n^2\) on parillinen, niin \(n\) on parillinen.

Todistus.

Todistetaan väite kontraposition avulla, eli osoitetaan, että jos \(n\) ei ole parillinen, niin \(n^2\) ei ole parillinen. Oletetaan siis, että \(n\) on pariton kokonaisluku, jolloin löydetään sellainen kokonaisluku \(k\), että \(n = 2k + 1\). Tällöin

\[n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1,\]

missä \(2k^2 + 2k \in \mathbb Z\). Siis myös \(n^2\) on pariton kokonaisluku. \(\square\)

Esimerkki.

Osoita, että \(\sqrt{2}\) on irrationaaliluku.

Todistus.

Todistetaan väite ristiriidan avulla. Tehdään vastaoletus, jonka mukaan \(\sqrt{2}\) on rationaaliluku. Tällöin \(\sqrt{2} = \frac{m}{n}\) joillakin \(m, n \in \mathbb Z\) ja \(n \not= 0\). Oletetaan lisäksi, että \(\frac{m}{n}\) on supistetussa muodossa, eli luvuilla \(m\) ja \(n\) ei ole yhteisiä tekijöitä.

Neliöimällä nähdään, että \(2 = \frac{m^2}{n^2}\), eli \(m^2 = 2n^2\). Tässä \(n^2 \in \mathbb Z\), joten luku \(m^2\) on parillinen. Edellisen esimerkin nojalla nyt myös luku \(m\) on parillinen, eli \(m = 2k\) jollakin kokonaisluvulla \(k\). Mutta nyt \(m^2 = 4k^2 = 2n^2\), eli \(n^2 = 2k^2\), missä \(k^2 \in \mathbb Z\). Siis \(n^2\), ja siten myös \(n\) ovat parillisia.

On osoitettu, että luvut \(m\) ja \(n\) ovat parillisia, ja täten niillä on yhteinen tekijä \(2\). Mutta oletuksen nojalla luvuilla \(m\) ja \(n\) ei ole yhteisiä tekijöitä, joten tämä on ristiriita. Vastaoletus on siis väärä ja \(\sqrt{2}\) on irrationaaliluku. \(\square\)

Esimerkki.

Tutki, onko \(a^2 - 3ab + b^2 \geq 0\) aina, kun \(a, b \geq 0\).

Ratkaisu.

Valitaan \(a = b = 1\), jolloin \(a^2 - 3ab + b^2 = -1 < 0\). On löydetty vastaesimerkki, joka osoittaa lauseen \(\forall a \geq 0 \ \forall b \geq 0 : a^2 - 3av + b^2 \geq 0\) epätodeksi.

Huomautus.

Tee huolellisesti ero todistettavan väitteen ja oletusten välille! Loogista implikaatiota \(p \Rightarrow q\) ei ole mahdollista todistaa olettamalla lauseen \(q\) ja osoittamalla yleisen totuuden. Pyritään osoittamaan edellisen esimerkin väite todeksi väärin perustein.

Oletetaan, että \(a \geq 0\) ja \(b \geq 0\), jolloin myös \(ab \geq 0\). Kirjoittamalla \(a^2 - 3ab + b^2 \geq 0\) nähdään, että

\[a^2 - 3ab + b^2 + ab = a^2 - 2ab + b^2 = (a - b)^2 \geq 0.\]

Tässä \((a - b)^2 \geq 0\) riippumatta lukujen \(a\) ja \(b\) valinnasta, joten väite on todistettu. \(\boxtimes\)

Päättely lähtee liikkeelle lausumasta \(a^2 - 3ab + b^2 \geq 0\), joten tämän on oltava oletus! Yllä osoitetaan siis, että jos \(a^2 - 3ab + b^2 \geq 0\), niin \((a - b)^2 \geq 0\).

Palautusta lähetetään...