Matemaattinen Todistus

1. 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
2. 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ö (${\displaystyle \square }$).

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 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)

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 ${\displaystyle n}$  ja ${\displaystyle m}$  ovat parittomia, jolloin on olemassa sellaiset luvut ${\displaystyle p,q\in \mathbb {Z} }$ , että ${\displaystyle n=2p-1,\ m=2q-1\in \mathbb {Z} }$ . Nyt näiden lukujen tulo voidaan kirjoittaa muodossa

${\displaystyle nm=(2p-1)(2q-1)=4pq-2p-2q+1=2(2pq-p-q)+1.}$ 

Tässä ${\displaystyle 2pq-p-q}$  on kokonaisluku, koska ${\displaystyle p}$  ja ${\displaystyle q}$  ovat kokonaislukuja. Koska lauseke on muotoa ${\displaystyle 2k+1}$ , niin on osoitettu, että tulo ${\displaystyle mn}$  on pariton. ${\displaystyle \square }$ 

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: ${\displaystyle {\sqrt {2}}}$  on irrationaaliluku. (Oletetaan, että aiemmin on jo todistettu luvun ${\displaystyle {\sqrt {2}}}$  olemassaolo.)

Todistus: Tehdään vastaoletus, että ${\displaystyle {\sqrt {2}}}$  on rationaaliluku. Silloin on olemassa kokonaisluvut ${\displaystyle a,b\in \mathbb {Z} _{+}}$ , joille ${\displaystyle {\sqrt {2}}=a/b}$  ja murtoluku ${\displaystyle a/b}$  on supistettu mahdollisimman yksinkertaiseen muotoon. Korottamalla molemmat puolet toiseen potenssiin saadaan ${\displaystyle 2=a^{2}/b^{2}}$ , eli ${\displaystyle 2b^{2}=a^{2}}$ . Lukuteoriasta tiedetään, että jos kokonaisluvun neliö on parillinen, niin itse lukukin on parillinen. Koska luvun ${\displaystyle a}$  neliö on edellä saadun nojalla parillinen, niin on siis olemassa luku ${\displaystyle c\in \mathbb {Z} }$ , jolle on voimassa ${\displaystyle a=2c}$ . Sijoittamalla tämä luvun ${\displaystyle a}$  paikalle saadaan ${\displaystyle 2b^{2}=(2c)^{2}=4c^{2}}$  eli ${\displaystyle b^{2}=2c^{2}}$ . Nyt luvun ${\displaystyle a}$  lisäksi myös ${\displaystyle b}$  on parillinen, joten murtoluvussa ${\displaystyle a/b}$  voidaan jakaa sekä osoittaja että nimittäjä luvulla ${\displaystyle 2}$ . Tämä on ristiriita, sillä alussa oletettiin, että luku ${\displaystyle a/b}$  oli jo supistettu mahdollisimman yksinkertaiseen muotoon. Tämä ristiriita osoittaa, että vastaoletus on väärin ja alkuperäinen väite oikein. Siispä ${\displaystyle {\sqrt {2}}}$  on irrationaaliluku. ${\displaystyle \square }$ 

• Ohjelman oikeaksi todistaminen