Matemaattinen todistus

Wikipedia

Matemaattinen todistus tarkoittaa muodollista todistusta, joka täyttää seuraavat ehdot:

1. Väite on muotoiltu siten, että se voidaan kirjoittaa täsmällisen yksikäsitteisesti käyttäen tyypillisesti matemaattisia symboleita; relaatioita, vertailuoperaattoreita sekä absoluuttisia lukuarvoja
2. Väite todistetaan niin, että todistus etenee käyttäen pelkästään sovittuja matemaattisia ja loogisia lainalaisuuksia sekä aksioomia

Todistettaessa voidaan käyttää hyväksi toisia todistettuja lauseita.

Luonnollisesti todistus ei saa sisältää väitettä oletuksena missään muodossa, muuten kyseessä on kehäpäätelmä. On myös tärkeää, että väitteessä on mainittu riittävän selvästi käytetyt oletukset. Oletukset rajaavat ja määrittävät ongelmaa tarkemmin, esimerkiksi todistettavan väitteen sisältämät luvut saattavat olla aina ei-negatiivisia kokonaislukuja.

Valitettavasti kaikkia selvästi todentuntuisia väitteitä ei ole helppo todistaa matemaattisesti. Esimerkiksi Pierre de Fermat'n tunnettu teoreema säilyi todistamattomana yli 300 vuotta, kunnes viime vuosikymmenellä englantilainen matemaatikko Andrew Wiles löysi sille todistuksen yli 10 vuoden työn tuloksena. Vaikka todistettava väite itsessään on erittäin yksinkertainen, on sen todistus niin mutkikas, että vain harvat matemaatikot ovat kykeneväisiä ymmärtämään sen.

Matemaattisia todistuksia käytetään laajalti muun muassa ohjelmistotieteessä, kun halutaan todistaa jokin algoritmi oikeaksi. Periaatteessa myös kokonaisia tietokone-ohjelmia voidaan todistaa oikeaksi, mutta ohjelmien todistaminen on kuitenkin osoittautunut sen verran työlääksi, että käytännössä vain pieniä, kriittisiä osia todistetaan tarvittaessa.

Sisällysluettelo 1 Todistusmenetelmiä 2 Esimerkkejä 2.1 Suora todistus 2.2 Epäsuora todistus

[muokkaa] Todistusmenetelmiä

Yleisiä todistustekniikoita ovat esimerkiksi

• Suora todistaminen: johtopäätös saavutetaan loogisesti aksioomia, määritelmiä ja aiempia todistuksia hyväksikäyttäen
• Induktiotodistus: kun yksittäinen tapaus (pohja) on todistettu, inkdutiosäännön perusteella todistetaan (yleensä ääretön määrä) muita tapauksia
• Epäsuora todistus: näytetään että jos jokin lause on epätosi, siitä seuraa looginen ristiriita, jolloin toisen lauseen tulee olla tosi
• Rakenteinen todistus: todistetaan näyttämällä konkreettinen esimerkki joka osoittaa tietyn ominaisuuden paikkansapitävyyden (käytetään usein, kun halutaan osoittaa jokin epätodeksi)

[muokkaa] Esimerkkejä

[muokkaa] Suora todistus

Osoitetaan esimerkkinä suorasta todistuksesta, että kahden parittoman luvun tulo on pariton.

Väite: kahden parittoman kokonaisluvun tulo on pariton.

Todistus:

Koska luvut n ja m ovat parittomia, on olemassa luvut siten, että .

Nyt m:n ja n:n tulo voidaan kirjoittaa muodossa

nm = (2p − 1)(2q − 1) = 4pq − 2p − 2q + 1 = 2(2pq − p − q) + 1.

Koska pq-p-q on kokonaisluku kun p ja q ovat kokonaislukuja, on määritelmän perusteella mn pariton.

Matemaattisen induktion avulla ja yllä olevan todistuksen tulosta käyttäen voitaisiin edelleen helposti todistaa, että mielivaltaisen monen (ei siis vain kahden alkion) parittomista kokonaisluvuista koostuvan joukon tulo on pariton.

[muokkaa] Epäsuora todistus

Epäsuorassa todistuksessa oletetaan, että lause ei olekaan voimassa ja osoitetaan, että tästä oletuksesta seuraa jokin ristiriita joko aksiooman tai aikaisemmin todistetun lauseen kanssa.

Väite: on irrationaaliluku.

(Oletetaan tässä, että aiemmin on todistettu luvun olemassaolo)

Todistus:

Oletetaan vastoin väitettä, että on rationaaliluku. Tällöin on olemassa kokonaisluvut , joille ja murtoluku a / b on loppuunsupistetussa muodossa. Tällöin olisi 2 = a² / b², eli 2b² = a².

Lukuteoriasta tiedetään, että jos kokonaisluvun neliö on parillinen, itse lukukin on. Tällöin on siis olemassa jolle a = 2c. Näin ollen pätee 2b² = (2c)² = 4c², eli b² = 2c². Mutta nyt b:kin on parillinen, jolloin murtoluku a / b voidaan supistaa kahdella. Tämä on ristiriita, sillä oletettiin, ettei luku a / b supistuisi. Siispä on irrationaaliluku.