Matemaattinen todistus

Matemaattinen todistus tarkoittaa muodollista todistusta, joka täyttää seuraavat ehdot:
 väite on muotoiltu siten, että se voidaan kirjoittaa täsmällisen yksikäsitteisesti käyttäen tyypillisesti matemaattisia symboleita: relaatioita, vertailuoperaattoreita ja absoluuttisia lukuarvoja, ja
 väite todistetaan käyttäen pelkästään sovittuja matemaattisia ja loogisia lainalaisuuksia sekä aksioomia. 

Matemaattisessa todistuksessa on kolme osaa:
 ongelmaa rajaavat ja määrittävät oletukset
 todistusta vaativa väite
 varsinainen todistus, jossa oletuksien nojalla näytetään väite todeksi.

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ö ().

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.

Todistusmenetelmiä
Yleisiä todistustekniikoita ovat esimerkiksi

 Suora todistus: väite todistetaan oletuksia, aksioomia, määritelmiä ja aiemmin todistettuja lauseita hyödyntämällä
 Epäsuora todistus: tehdään vastaoletus ja näytetään, että siitä seuraa looginen ristiriita, jolloin alkuperäinen väite on tosi
 Induktiotodistus: osoitetaan väite todeksi ensimmäisellä mahdollisella arvolla (induktion pohja), oletetaan sen pätevän mielivaltaisella arvolla ja todistetaan väitteen pätevän mielivaltaista arvoa seuraavallakin arvolla
 Rakenteinen todistus: konstruoidaan esimerkki, joka osoittaa väitteen paikkansapitävyyden (käytetään usein, kun halutaan osoittaa jokin epätodeksi)

Esimerkkejä

Suora todistus
Osoitetaan 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  ja  ovat parittomia, jolloin on olemassa sellaiset luvut , että . Nyt näiden lukujen tulo voidaan kirjoittaa muodossa

Tässä  on kokonaisluku, koska  ja  ovat kokonaislukuja. Koska lauseke on muotoa , niin on osoitettu, että tulo  on pariton. 

Matemaattisen induktion ja yllä olevan todistuksen avulla voitaisiin edelleen todistaa, että mielivaltaisen monen parittoman kokonaisluvun tulo on pariton.

Epäsuora todistus
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:  on irrationaaliluku. (Oletetaan, että aiemmin on jo todistettu luvun  olemassaolo.)

Todistus:
Tehdään vastaoletus, että  on rationaaliluku. Silloin on olemassa kokonaisluvut , joille  ja murtoluku  on supistettu mahdollisimman yksinkertaiseen muotoon. Korottamalla molemmat puolet toiseen potenssiin saadaan , eli . Lukuteoriasta tiedetään, että jos kokonaisluvun neliö on parillinen, niin itse lukukin on parillinen. Koska luvun  neliö on edellä saadun nojalla parillinen, niin on siis olemassa luku , jolle on voimassa . Sijoittamalla tämä luvun  paikalle saadaan  eli . Nyt luvun  lisäksi myös  on parillinen, joten murtoluvussa  voidaan jakaa sekä osoittaja että nimittäjä luvulla . Tämä on ristiriita, sillä alussa oletettiin, että luku  oli jo supistettu mahdollisimman yksinkertaiseen muotoon. Tämä ristiriita osoittaa, että vastaoletus on väärin ja alkuperäinen väite oikein. Siispä  on irrationaaliluku.

Katso myös 
 Ohjelman oikeaksi todistaminen

Lähteet 

Matemaattinen logiikka

Seulonnan keskeiset artikkelit