Matemaattinen todistus
Matemaattinen todistus tarkoittaa muodollista todistusta, joka täyttää seuraavat ehdot:
Matemaattisessa todistuksessa on kolme osaa:
Oletukset mainitaan usein väitteen yhteydessä, jolloin matemaattisen todistuksen osia ovat vain väite ja todistus. Todistus ei saa sisältää väitettä oletuksena missään muodossa, koska silloin kyseessä on kehäpäätelmä. Todistettaessa voidaan oletusten lisäksi käyttää hyväksi toisia jo aiemmin todistettuja lauseita. Usein matemaattisen todistuksen loppuun merkitään QED latinankielisistä sanoista "quod erat demonstrandum" ("mikä oli todistettava, MOT") tai piirretään pieni neliö (formula_1).
Kaikkia yksinkertaisiakaan väitteitä ei ole helppo todistaa matemaattisesti. Esimerkiksi Pierre de Fermat'n mukaan nimetty Fermat'n suuri lause säilyi todistamattomana yli 300 vuotta, kunnes 1990-luvulla englantilainen matemaatikko Andrew Wiles löysi todistuksen yli 10 vuoden työn tuloksena. Vaikka todistettava väite on erittäin yksinkertainen, niin vain harvat matemaatikot kykenevät ymmärtämään monimutkaisen todistuksen.
Matemaattisia todistuksia käytetään laajalti muun muassa tietojenkäsittelytieteissä, kun halutaan todistaa jokin algoritmi oikeaksi. Periaatteessa myös kokonaisia tietokoneohjelmia voidaan todistaa oikeiksi, mutta ohjelmien todistaminen on kuitenkin osoittautunut sen verran työlääksi, että käytännössä vain pieniä, kriittisiä osia todistetaan tarvittaessa.
Yleisiä todistustekniikoita ovat esimerkiksiOsoitetaan esimerkkinä suorasta todistuksesta, että kahden parittoman luvun tulo on pariton.
Oletukset: osittelulaki, pariteetti, kokonaisluku, peruslaskutoimitukset, rengas
Väite: Kahden parittoman kokonaisluvun tulo on pariton.
Todistus:
Olkoot luvut formula_2 ja formula_3 ovat parittomia, jolloin on olemassa sellaiset luvut formula_4, että formula_5. Nyt näiden lukujen tulo voidaan kirjoittaa muodossa
Tässä formula_7 on kokonaisluku, koska formula_8 ja formula_9 ovat kokonaislukuja. Koska lauseke on muotoa formula_10, niin on osoitettu, että tulo formula_11 on pariton. formula_1
Matemaattisen induktion ja yllä olevan todistuksen avulla voitaisiin edelleen todistaa, että mielivaltaisen monen parittoman kokonaisluvun tulo on pariton.
Epäsuorassa todistuksessa oletetaan, että väite ei olekaan voimassa ja osoitetaan, että tästä "vastaoletuksesta" seuraa jokin ristiriita joko oletuksen, aksiooman tai jonkin aikaisemmin todistetun lauseen kanssa.
Väite: formula_13 on irrationaaliluku. (Oletetaan, että aiemmin on jo todistettu luvun formula_13 olemassaolo.)
Todistus:
Tehdään vastaoletus, että formula_13 on rationaaliluku. Silloin on olemassa kokonaisluvut formula_16, joille formula_17 ja murtoluku formula_18 on supistettu mahdollisimman yksinkertaiseen muotoon. Korottamalla molemmat puolet toiseen potenssiin saadaan formula_19, eli formula_20. Lukuteoriasta tiedetään, että jos kokonaisluvun neliö on parillinen, niin itse lukukin on parillinen. Koska luvun formula_21 neliö on edellä saadun nojalla parillinen, niin on siis olemassa luku formula_22, jolle on voimassa formula_23. Sijoittamalla tämä luvun formula_21 paikalle saadaan formula_25 eli formula_26. Nyt luvun formula_21 lisäksi myös formula_28 on parillinen, joten murtoluvussa formula_18 voidaan jakaa sekä osoittaja että nimittäjä luvulla formula_30. Tämä on ristiriita, sillä alussa oletettiin, että luku formula_18 oli jo supistettu mahdollisimman yksinkertaiseen muotoon. Tämä ristiriita osoittaa, että vastaoletus on väärin ja alkuperäinen väite oikein. Siispä formula_13 on irrationaaliluku. formula_1