Algoritmit ja looginen päättely

Tässä luvussa tutustutaan alkulukuihin, joukkoihin ja logiikkaan sekä kokonaislukujen jaollisuuteen. Opit kuvaamaan laskuja summamerkinnällä ja perustelemaan väitteitä induktion ja muiden todistusmenetelmien avulla. Lopuksi kerrataan reaalilukujen laskulakeja sekä eksponentti- ja logaritmifunktioiden keskeisiä ominaisuuksia.

• Tunnistat alkulukuihin, joukkoihin ja logiikkaan liittyvät perusmerkinnät.
• Osaat käyttää jakoyhtälöä ja Eukleideen algoritmia.
• Ymmärrät summamerkinnän ja matemaattisen induktion perusidean.

Alkuluvut ja aritmetiikan peruslause

Alkuluku on kokonaisluku \(p>1\), jonka positiiviset tekijät ovat vain 1 ja \(p\). Kokonaislukua \(n>1\), joka ei ole alkuluku, kutsutaan yhdistetyksi luvuksi. Jokainen ykköstä suurempi kokonaisluku voidaan esittää alkulukujen tulona, ja esitys on tekijöiden järjestystä lukuun ottamatta yksikäsitteinen. Tätä tulosta kutsutaan aritmetiikan peruslauseeksi.

Esimerkiksi

\[100=2\cdot50=2^2\cdot25=2^2\cdot5^2.\]

Alkutekijähajotelma auttaa muun muassa löytämään suurimman yhteisen tekijän ja pienimmän yhteisen monikerran.

Joukko-opin alkeet

Joukko on alkioidensa kokoelma. Esimerkiksi \(A=\{0,1,2\}\). Merkintä \(1\in A\) tarkoittaa, että 1 kuuluu joukkoon; \(4\notin A\) tarkoittaa, ettei 4 kuulu siihen. Tyhjässä joukossa ei ole alkioita, ja sitä merkitään \(\varnothing\).

Joukon voi kuvata myös ominaisuuden avulla. Parittomien kokonaislukujen joukko on

\[B=\{m\in\mathbb{Z}\mid m=2n+1\text{ jollakin }n\in\mathbb{Z}\}.\]

Joukko-operaatioista tärkeimmät ovat yhdiste, leikkaus, erotus ja komplementti:

• Yhdiste \(A\cup B\) sisältää alkiot, jotka ovat joukossa \(A\) tai \(B\) (tai molemmissa).
• Leikkaus \(A\cap B\) sisältää alkiot, jotka kuuluvat sekä joukkoon \(A\) että joukkoon \(B\).
• Erotus \(B\setminus A\) sisältää joukon \(B\) alkiot, jotka eivät kuulu joukkoon \(A\).
• Komplementti \(A^c\) sisältää tarkasteltavan perusjoukon alkiot, jotka eivät kuulu joukkoon \(A\).

Komplementti riippuu aina valitusta perusjoukosta. Jos esimerkiksi \(A=\{1,2\}\) ja perusjoukko on \(U=\{1,2,3,4\}\), niin \(A^c=\{3,4\}\).

Logiikan peruskäsitteet

Logiikassa tarkastellaan väitteitä ja niiden totuusarvoja: väite on joko tosi tai epätosi. Propositiot yhdistetään konnektiiveilla, kuten negaatiolla, konjunktiolla ja implikaatiolla.

• \(\neg A\): ei \(A\); negaatio kääntää totuusarvon.
• \(A\land B\): \(A\) ja \(B\); tosi vain, kun molemmat ovat tosia.
• \(A\lor B\): \(A\) tai \(B\); tosi, kun ainakin toinen on tosi.
• \(A\Rightarrow B\): jos \(A\), niin \(B\); epätosi vain silloin, kun \(A\) on tosi ja \(B\) epätosi.
• \(A\Leftrightarrow B\): \(A\) jos ja vain jos \(B\); tosi, kun \(A\) ja \(B\) ovat samanarvoiset.

Totuustaulu kokoaa konnektiivin totuusarvot kaikille mahdollisille syötteille:

T tarkoittaa totta ja E epätotta. Lause, joka on tosi kaikilla mahdollisilla totuusarvoilla, on tautologia. Esimerkiksi kaksoisnegaatio ja De Morganin lait ovat tautologioita:

\[\neg(\neg A)\Leftrightarrow A,\qquad \neg(A\lor B)\Leftrightarrow(\neg A\land\neg B),\qquad \neg(A\land B)\Leftrightarrow(\neg A\lor\neg B).\]

Predikaatit ja kvanttorit

Predikaatti on avoin väite, jonka totuus riippuu muuttujan arvosta. Esimerkiksi \(x^2<4\) on tosi joillakin reaaliluvuilla \(x\), mutta ei kaikilla. Muuttujan arvot valitaan perusjoukosta.

Eksistenssikvanttori \(\exists\) tarkoittaa ”on olemassa”, ja universaalikvanttori \(\forall\) tarkoittaa ”kaikilla”. Esimerkiksi

\[\exists x\in\mathbb{R}:x^2<4\]

on tosi, sillä esimerkiksi \(x=1\) toteuttaa ehdon. Väite

\[\forall x\in\mathbb{R}:x^2<4\]

on epätosi, koska esimerkiksi \(x=4\) ei toteuta sitä.

Jaollisuus, jakoyhtälö ja kongruenssi

Kokonaisluku \(a\) on jaollinen kokonaisluvulla \(b\ne0\), jos \(a=bq\) jollakin kokonaisluvulla \(q\). Tätä merkitään \(b\mid a\), ja luetaan ”\(b\) jakaa \(a\):n”. Esimerkiksi \(4\mid24\), sillä \(24=4\cdot6\).

Jakoyhtälö kertoo kokonaisluvun jakamisen osamäärän ja jakojäännöksen avulla. Kun \(a\in\mathbb{Z}\) ja \(b\) on positiivinen kokonaisluku, on olemassa yksikäsitteiset kokonaisluvut \(q\) ja \(r\), joille

\[a=bq+r,\qquad 0\le r

Esimerkiksi \(34=6\cdot5+4\), joten osamäärä on 5 ja jakojäännös 4. Jakojäännös on aina epänegatiivinen ja jakajaa pienempi.

Kaksi kokonaislukua ovat kongruentteja modulo \(n\), jos niiden erotus on jaollinen \(n\):llä. Merkintä on

\[a\equiv b\pmod n\quad\Longleftrightarrow\quad n\mid(a-b).\]

Esimerkiksi \(53\equiv17\pmod4\), koska \(53-17=36\) on jaollinen neljällä. Sama näkyy siitä, että molempien jakojäännös neljällä jaettaessa on 1.

Suurin yhteinen tekijä ja pienin yhteinen monikerta

Lukujen \(a\) ja \(b\) suurin yhteinen tekijä, merkitään \(\operatorname{syt}(a,b)\), on suurin positiivinen kokonaisluku, joka jakaa molemmat luvut. Pienin yhteinen monikerta \(\operatorname{pym}(a,b)\) on pienin positiivinen kokonaisluku, joka on molempien monikerta.

Alkutekijähajotelmien avulla saadaan esimerkiksi

\[36=2^2\cdot3^2,\qquad20=2^2\cdot5,\]

joten \(\operatorname{syt}(36,20)=2^2=4\) ja \(\operatorname{pym}(36,20)=2^2\cdot3^2\cdot5=180\).

Eukleideen algoritmi

Eukleideen algoritmissa suurin yhteinen tekijä säilyy, kun luku korvataan jakojäännöksellä: jos \(a=bq+r\), niin \(\operatorname{syt}(a,b)=\operatorname{syt}(b,r)\). Jatketaan jakoa, kunnes jakojäännös on nolla. Viimeinen nollasta poikkeava jakojäännös on syt.

Esimerkiksi

\[\begin{aligned} 177&=129\cdot1+48,\\ 129&=48\cdot2+33,\\ 48&=33\cdot1+15,\\ 33&=15\cdot2+3,\\ 15&=3\cdot5+0. \end{aligned}\]

Viimeinen nollasta poikkeava jakojäännös on 3, joten \(\operatorname{syt}(177,129)=3\).

Summamerkintä

Sigma- eli summamerkintä tiivistää peräkkäisten termien summan. Merkinnässä

\[\sum_{i=m}^{n}a_i=a_m+a_{m+1}+\cdots+a_n\]

indeksi \(i\) käy läpi kokonaisluvut alarajasta \(m\) ylärajaan \(n\). Esimerkiksi

\[\sum_{i=2}^{6}i=2+3+4+5+6=20.\]

Summauksessa vakion voi siirtää summan ulkopuolelle, ja summan voi jakaa termeittäin:

\[\sum_{i=m}^{n}ca_i=c\sum_{i=m}^{n}a_i,\qquad \sum_{i=m}^{n}(a_i\pm b_i)=\sum_{i=m}^{n}a_i\pm\sum_{i=m}^{n}b_i.\]

Hyödyllisiä kaavoja ovat

\[\sum_{i=1}^{n}1=n,\qquad \sum_{i=1}^{n}i=\frac{n(n+1)}{2},\qquad \sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}.\]

Luonnolliset luvut ja induktiotodistus

Matemaattinen induktio todistaa väitteen kaikille luonnollisille luvuille tai kaikille tietyn aloitusarvon ylittäville kokonaisluvuille. Todistuksessa on kaksi vaihetta:

1. Alkuaskel: tarkistetaan väite ensimmäisellä tarkasteltavalla arvolla, esimerkiksi \(n=1\).
2. Induktioaskel: oletetaan väite todeksi arvolla \(n=k\) ja osoitetaan tämän avulla, että se pätee myös arvolla \(n=k+1\).

Jos molemmat vaiheet onnistuvat, väite pätee induktioperiaatteen nojalla kaikilla kyseisillä arvoilla.

Esimerkki: ensimmäisten kokonaislukujen summa

Todistetaan, että \(1+2+\cdots+n=n(n+1)/2\), kun \(n\ge1\).

Alkuaskel \(n=1\) pätee, koska \(1=1\cdot2/2\). Oletetaan sitten, että kaava pätee arvolla \(k\): \(1+2+\cdots+k=k\(k+1\)/2\). Tällöin

\[\begin{aligned} 1+2+\cdots+k+\(k+1\) &=\frac{k\(k+1\)}{2}+\(k+1\)\\ &=\frac{\(k+1\)(k+2)}{2}. \end{aligned}\]

Tämä on sama kaava arvolla \(k+1\), joten induktioaskel pätee ja väite on todistettu.

Reaalilukujen laskulait

Reaaliluvut muodostavat järjestetyn kunnan. Keskeisiä laskulakeja ovat yhteen- ja kertolaskun vaihdannaisuus ja liitännäisyys, nolla- ja ykkösalkion olemassaolo sekä vastaluvun ja nollasta poikkeavan luvun käänteisluvun olemassaolo:

\[a+b=b+a,\quad (a+b)+c=a+(b+c),\quad ab=ba,\quad (ab)c=a(bc),\]

\[a+0=a,\quad a\cdot1=a,\quad a+(-a)=0,\quad a\cdot\frac1a=1\quad(a\ne0).\]

Kertolasku osittelee yhteenlaskun suhteen: \(a(b+c)=ab+ac\). Järjestys säilyy, kun epäyhtälön molemmille puolille lisätään sama luku. Positiivisella luvulla kertominen säilyttää järjestyksen; negatiivisella kertominen kääntää epäyhtälön suunnan.

Reaalilukujen täydellisyys tarkoittaa muun muassa, että jokaisella epätyhjällä ylhäältä rajoitetulla reaalilukujoukolla on pienin yläraja. Tässä luvussa riittää tunnistaa tämä reaalilukujen ominaisuus; sitä ei tarvitse käyttää laskusääntönä.

Todistamisen tapoja

Todistuksessa oletuksista johdetaan loogisesti väite. Menetelmän valinta riippuu siitä, millainen väite on kyseessä.

Suora todistus

Suorassa todistuksessa lähdetään oletuksesta ja muokataan sitä tunnettujen sääntöjen avulla väitteeksi. Jos \(a-b\).

Ristiriitatodistus

Ristiriitatodistuksessa oletetaan väitteen vastakohta ja osoitetaan, että siitä seuraa ristiriita. Jos esimerkiksi tiedetään \(x^3+x-1>0\), väite \(x>0\) voidaan todistaa olettamalla vastoin väitettä \(x\le0\). Koska \(x^2+1>0\), saadaan \(x(x^2+1)=x^3+x\le0\), joten \(x^3+x-1\le-1<0\), mikä on ristiriidassa oletuksen kanssa.

Vastaesimerkki

Yleinen väite voidaan osoittaa vääräksi yhdellä vastaesimerkillä. Esimerkiksi väite \(x^2-4x+1>0\) kaikilla reaaliluvuilla ei päde, sillä arvolla \(x=1\) saadaan \(-2<0\).

Laskulakien johtaminen

Aksioomista voidaan johtaa uusia tuloksia. Esimerkiksi nollasääntö seuraa osittelulaista:

\[0\cdot a=(0+0)a=0\cdot a+0\cdot a.\]

Vähentämällä yhtälön molemmilta puolilta \(0\cdot a\) saadaan \(0=0\cdot a\). Tästä seuraa tulon nollasääntö: \(ab=0\) täsmälleen silloin, kun \(a=0\) tai \(b=0\). Jos \(a\ne0\), voidaan yhtälö \(ab=0\) kertoa luvulla \(1/a\), jolloin saadaan \(b=0\).

Eksponentti- ja logaritmifunktio

Eksponenttifunktio voidaan määritellä potenssisarjana

\[e^x=\exp(x)=\sum_{k=0}^{\infty}\frac{x^k}{k!} =1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots.\]

Sen keskeisiä laskulakeja ovat

\[\exp(0)=1,\qquad \exp(x+y)=\exp(x)\exp(y),\qquad \exp(-x)=\frac{1}{\exp(x)}.\]

Luonnollinen logaritmi \(\ln(x)\) on eksponenttifunktion käänteisfunktio. Se on määritelty, kun \(x>0\), ja

\[\ln(x)=y\quad\Longleftrightarrow\quad e^y=x.\]

Logaritmin laskulakeja ovat

\[\ln(1)=0,\qquad \ln(ab)=\ln(a)+\ln(b),\qquad \ln\left(\frac{a}{b}\right)=\ln(a)-\ln(b),\qquad \ln(a^r)=r\ln(a),\]

kun \(a>0\), \(b>0\) ja \(r\in\mathbb{R}\). Yleisen logaritmin kanta \(b\) täyttää ehdot \(b>0\) ja \(b\ne1\), ja kannanvaihto antaa

\[\log_b(a)=\frac{\ln(a)}{\ln(b)}\qquad(a>0).\]

Käänteisfunktioina eksponentti ja logaritmi kumoavat toisensa: \(e^{\ln x}=x\), kun \(x>0\), ja \(\ln(e^x)=x\), kun \(x\in\mathbb{R}\).