Teh­tä­vä:
To­dis­ta­mi­ses­ta

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Yk­sin­ker­tais­tet­tu­na ma­te­ma­tii­kan to­dis­tuk­set koos­tu­vat kol­mes­ta osas­ta, jot­ka ovat ole­tuk­set, väi­te eli to­dis­tet­ta­va asia ja it­se to­dis­tus. To­dis­tuk­ses­sa py­ri­tään joh­ta­maan väi­te ole­tus­ten avul­la käyt­täen loo­gis­ta päät­te­lyä.

Ter­me­jä ja temp­pu­ja

To­dis­tuk­siin liit­tyy pal­jon va­kiin­tu­nut­ta ja ylei­ses­ti käy­tös­sä ole­vaa ter­mis­töä. Nä­mä jää­vät hel­pos­ti huo­maa­mat­ta tai ne vai­kut­ta­vat köm­pe­löl­tä ka­pu­la­kie­lel­tä. Al­la esi­tel­lään joi­ta­kin niis­tä.

Mie­li­val­tai­nen al­kio: Usein ha­lu­taan osoit­taa to­dek­si väi­te, jo­ka kos­kee kaik­kia tie­tyn jou­kon al­kioi­ta. Täl­lai­nen on esi­mer­kik­si ”Jo­kai­sen pa­rit­to­man lu­vun ne­liö on pa­ri­ton.” Min­kä jou­kon al­kiois­ta sii­nä ol­laan kiin­nos­tu­nei­ta? Vas­tausPa­rit­to­mien lu­ku­jen jou­kon.

Jos edel­li­sen koh­dan jouk­koa mer­ki­tään `A`:lla, niin väi­te voi­daan il­mais­ta kaa­va­na prop_logic ok_text Oi­kein! only_no_yes_on hide_expr TT <=> hide_expr
`EE n: n^2 in A`
`AA n: n^2 in A`
`EE n in A: n^2 in A`
`AA n in A: n^2 in A`
tai

Hy­vin usein täl­lai­nen väi­te to­dis­te­taan ot­ta­mal­la tar­kas­tel­ta­vak­si yk­si al­kio, jo­ka kuu­luu pu­hee­na ole­vaan jouk­koon, mut­ta jos­ta ei tie­de­tä ei­kä ole­te­ta sen enem­pää. Sel­lais­ta al­kio­ta sa­no­taan mie­li­val­tai­sek­si. Mie­li­val­tai­suus tar­koit­taa, et­tä se voi ol­la mi­kä ta­han­sa pu­hee­na ole­van jou­kon al­kio.

Väi­te to­dis­te­taan täl­le yh­del­le al­kiol­le. Kun se on teh­ty, niin tie­de­tään, et­tä jos pu­hee­na ole­vas­ta jou­kos­ta va­li­taan mi­kä ta­han­sa al­kio, niin väi­te pä­tee sil­le. Se tar­koit­taa, et­tä väi­te pä­tee kai­kil­le pu­hee­na ole­van jou­kon al­kioil­le.

Esi­merk­kim­me ta­pauk­ses­sa päät­te­lyn ra­ken­ne on siis seu­raa­va:

Kos­ka täl­lai­sen päät­te­lyn al­ku- ja lop­pu­vai­he ovat ai­na sa­man­lai­set, ne jä­te­tään yleen­sä esit­tä­mät­tä. Esi­te­tään vain se, mi­kä il­mais­tiin edel­lä näin:

`n in "Parittomat" rArr n^2 in "Parittomat"`

Tä­mä lais­kuus vai­kut­taa kie­len­käyt­töön si­ten, et­tä usein unoh­de­taan sa­na ”jo­kai­sen” ja sa­no­taan ”pa­rit­to­man lu­vun ne­liö on pa­ri­ton”.

Ker­ra­taan vie­lä tär­kein: Mie­li­val­tai­suus tar­koit­taa to­dis­tus­ten yh­tey­des­sä si­tä, et­tei al­kios­ta teh­dä mi­tään mui­ta ole­tuk­sia kuin et­tä se kuu­luu ha­lut­tuun jouk­koon. Toi­sin sa­noen, mie­li­val­tai­nen al­kio voi ol­la mi­kä ta­han­sa jou­kon al­kio.

Mie­li­val­tai­sen al­kion käyt­tö ei ole sa­ma asia kuin väit­teen to­dis­ta­mi­nen tie­tyl­le lu­vul­le. On help­po huo­ma­ta, et­tä lu­vun `3` ne­liö `9` on to­del­la­kin pa­ri­ton, mut­ta sen pe­rus­teel­la ei voi­da pää­tel­lä mi­tään muis­ta pa­rit­to­mis­ta lu­vuis­ta. Sen si­jaan jos on­nis­tu­taan to­dis­ta­maan, et­tä mie­li­val­tai­sen pa­rit­to­man lu­vun `n` ne­liö on pa­ri­ton, on väi­te to­dis­tet­tu kai­kil­le pa­rit­to­mil­le lu­vuil­le. Pa­la­taan myö­hem­min sii­hen, mi­ten tä­mä voi­daan teh­dä käy­tän­nös­sä.

Jos ja vain jos: Jos­kus lau­seet ovat muo­toa ”`varphi` pä­tee jos ja vain jos `psi` pä­tee”. Lo­gii­kan mer­kin­nöin tä­mä vas­taa pää­tel­mää ”`varphi hArr psi`”. Sa­maa tar­koit­ta­vat myös muo­toa ”`varphi` pä­tee täs­mäl­leen sil­loin kun `psi` pä­tee” ole­vat lau­seet. To­dis­tuk­ses­sa pi­tää täl­löin to­dis­taa kak­si asiaa:

• Jos `varphi` pä­tee, niin myös `psi` pä­tee, eli lo­gii­kan mer­kin­nöin `varphi rArr psi`.
• Jos `psi` pä­tee niin myös `varphi` pä­tee, eli lo­gii­kan mer­kin­nöin `psi rArr varphi`.

Toi­si­naan mo­lem­mat voi­daan to­dis­taa yh­tä­ai­kaa päät­te­ly­ket­jul­la muo­toa `varphi_1 hArr varphi_2 hArr ... hArr varphi_n hArr psi`, mut­ta usein ne jou­du­taan to­dis­ta­maan erik­seen.

Muut­tu­jien ni­meä­mi­nen: Tä­mä ei lii­ty pel­käs­tään to­dis­tus­teh­tä­viin, vaan mi­hin ta­han­sa ti­lan­tee­seen, jos­sa käy­te­tään muut­tu­jia. Pe­riaat­tees­sa muut­tu­jal­le an­net­tu ni­mi voi ol­la mi­tä vaan, mut­ta täs­sä­kin on kui­ten­kin joi­tain va­kiin­tu­nei­ta käy­tän­tö­jä. Kir­jai­mil­la `i, j, k, l, m, n` mer­ki­tään yleen­sä ko­ko­nais­lu­ku­ja, luon­nol­li­sia lu­ku­ja tai po­si­tii­vi­sia ko­ko­nais­lu­ku­ja. Kir­jai­mil­la `x, y, z, a, b, c` mer­ki­tään yleen­sä reaa­li­lu­ku­ja. Al­ku­lu­ku­ja mer­ki­tään usein `p` ja `q`, mut­ta `p` saat­taa tar­koit­taa myös to­den­nä­köi­syyt­tä, jol­loin se on reaa­li­lu­ku vä­lil­tä `0 <= p <= 1`. Muut­tu­jan tyy­pin voi jou­tua päät­te­le­mään asia­yh­tey­des­tä.

Eri­lai­sia to­dis­tus­tyyp­pe­jä

Täs­sä osios­sa tar­vit­set muu­ta­maa tie­toa pa­ril­li­suu­teen ja pa­rit­to­muu­teen liit­tyen. Täs­sä teh­tä­väs­sä näi­tä kä­sit­tei­tä ei kui­ten­kaan kä­si­tel­lä sen sy­väl­li­sem­min, vaan ai­noas­taan niil­tä osin mi­tä tar­vi­taan teh­tä­vien te­ke­mi­sek­si.

En­sin­nä­kin, lu­ku `n` on pa­ril­li­nen, jos ja vain jos se voi­daan kir­joit­taa muo­dos­sa `n = 2k`, mis­sä `k` on jo­kin ko­ko­nais­lu­ku. Jos et ole aiem­min tör­män­nyt täl­lai­seen mer­kin­tä­ta­paan, se voi vai­kut­taa ou­dol­ta. Poh­jim­mil­taan ky­se on kui­ten­kin yk­sin­ker­tai­ses­ta asias­ta. Jo­kai­nen pa­ril­li­nen lu­ku, ja vain pa­ril­li­set lu­vut, voi­daan siis kir­joit­taa lu­vun `2` ja jon­kin ko­ko­nais­lu­vun tu­lo­na. Esi­mer­kik­si lu­ku `6` on pa­ril­li­nen kos­ka `6 = 2*3` ja lu­ku `10` on pa­ril­li­nen, kos­ka `10 = 2 * 5`. En­täs lu­vut `16``16 = 2*8`, `0``0 = 2*0` tai `4n`Tä­mä riip­puu sii­tä, mi­tä lu­ku­tyyp­piä `n` on. Jos se on ko­ko­nais­lu­ku, niin `4n` on pa­ril­li­nen, kos­ka `4n = 2*2n` ja `2n` on ko­ko­nais­lu­ku. Jos `n = 1/4`, niin `4n = 1`, jo­ka ei ole pa­ril­li­nen. Täs­sä ta­pauk­ses­sa voit edel­lä ku­vat­tu­jen käy­tän­tö­jen pe­rus­teel­la olet­taa, et­tä `n` on ko­ko­nais­lu­ku. Sik­si on oi­kein vas­ta­ta, et­tä `4n` on pa­ril­li­nen.?

Sa­maan ta­paan voi­daan to­de­ta, et­tä lu­ku `n` on pa­ri­ton, jos ja vain jos se voi­daan kir­joit­taa muo­dos­sa `n = 2k + 1`, mis­sä `k` tar­koit­taa jäl­leen jo­ta­kin ko­ko­nais­lu­kua. Si­ten lu­ku `3` on pa­ri­ton, kos­ka `3 = 2 * 1 + 1`. Pe­rus­te­le, ovat­ko seu­raa­vat lu­vut pa­ril­li­sia vai pa­rit­to­mia: `1`Pa­ri­ton, kos­ka `1 = 2*0 + 1`, `15`Pa­ri­ton, kos­ka `15 = 2*7 + 1`, `-4`Pa­ril­li­nen, kos­ka `-4 = 2*(-2)` ja `4n + 3`Pa­ri­ton, kos­ka `4n + 3 = 2*(2n+1) + 1`.

Yk­si­tyis­koh­dat ovat tär­kei­tä. Mi­tä `k`:n pai­kal­le kaa­vois­sa `n = 2k` ja `n = 2k+1` tu­le­vis­ta lu­vuis­ta täy­tyy var­mis­taa? Vas­tausSen on ol­ta­va ko­ko­nais­lu­ku. Edel­lä `k`:n pai­kal­la oli­vat `8`, `0`, `2n`, `0`, `7`, `-2`, `` ja `2n+1`. Sel­väs­ti `8`, `0`, `7` ja `-2` ovat ko­ko­nais­lu­ku­ja. Kos­ka ko­ko­nais­lu­ku­jen sum­mat ja tu­lot ovat ko­ko­nais­lu­ku­ja, ja kos­ka `n` ole­tet­tiin ko­ko­nais­lu­vuk­si, ovat myös `2n` ja `2n+1` ko­ko­nais­lu­ku­ja. . Kiin­ni­tä jat­kos­sa huo­mio­ta eri­tyi­ses­ti pe­rus­te­lui­hin, myös niis­sä koh­dis­sa jot­ka näyt­tä­vät al­kuun jo­pa it­ses­tään­sel­vil­tä. Jo­kai­nen päät­te­lyas­kel pi­tää huo­lel­la tar­kis­taa oi­keak­si.

Suo­ra to­dis­tus

Suo­ras­sa to­dis­tuk­ses­sa ole­te­taan ole­tus­ten ole­van tot­ta, mut­ta väit­tees­tä ei ole­te­ta mi­tään. Väit­teen pää­tel­lään to­del­la pi­tä­vän paik­kan­sa ole­tuk­sia ja mui­ta poh­ja­tie­to­ja käyt­täen. Sa­nal­li­nen se­los­tus voi kuu­los­taa epä­mää­räi­sel­tä, jo­ten tar­kas­tel­laan asiaa esi­mer­kin kaut­ta. To­dis­te­taan seu­raa­va lau­se:

Jos lu­ku `n` on pa­ri­ton, niin myös lu­ku `n^2` on pa­ri­ton.

Pu­re­taan lau­set­ta osiin en­nen sen to­dis­ta­mis­ta.

• Mi­tä ole­tuk­sia on an­net­tu? Vas­tausLu­ku `n` on pa­ri­ton lu­ku.
• Mi­kä on lau­seen väi­te? Vas­tausLu­ku `n^2` on pa­ri­ton.

Usein on hyö­dyl­lis­tä en­nen var­si­nais­ta to­dis­tus­ta kir­joit­taa väi­te au­ki ma­te­maat­ti­sin mer­kin­nöin. Täs­sä ta­pauk­ses­sa väi­te oli­si mi­kä`EE k: n^2 = 2k + 1`? En­tä mi­kä oli­si ole­tus ma­te­maat­ti­sin mer­kin­nöin`EE k: n = 2k + 1`?

Edel­lä käy­tet­tiin ole­tuk­sen ja väit­teen ma­te­maat­ti­ses­sa muo­toi­lus­sa sa­man­ni­mis­tä apu­muut­tu­jaa. Nii­den ar­vot ei­vät kui­ten­kaan tu­le vält­tä­mät­tä ole­maan sa­mat, jo­ten oli­si pa­rem­pi käyt­tää eri­ni­mi­siä muut­tu­jia. Sik­si muo­toi­le väi­te uu­del­leen käyt­täen apu­muut­tu­ja­na `h`.
ok_text Oi­kein! modulo 12 f_nodes 10 hide_expr EE k: n^2 = 2k + 1 <=> h: n^2 tai

Lau­se voi­daan siis to­dis­taa muok­kaa­mal­la lu­ku `n^2` tä­hän muo­toon. Sii­nä to­den­nä­köi­ses­ti aut­taa lau­seen ole­tus.

Aloi­te­taan to­dis­tus. Ole­tuk­sen an­sios­ta tie­däm­me, et­tä on ole­mas­sa ko­ko­nais­lu­ku `k`, jol­le `n =`
ok_text Oi­kein! f_nodes 5 hide_expr 2k + 1 = tai

Huom!Täs­tä eteen­päin täs­sä to­dis­tuk­ses­sa ole­va `k` on ai­na sa­ma lu­ku.

Täl­löin `n^2 =`
ok_text Oi­kein! f_nodes 13 hide_expr (2k + 1)^2 = tai

Muok­kaa edel­li­sen laa­ti­kon tu­los muo­toon, josta osa on annettu val­mii­na.
ok_text Oi­kein! f_nodes 13 hide_expr (2k + 1)^2 = 2() + 1 tai

Siis `n^2` on väit­teen muo­toa, mis­sä `h`:n pai­kal­la on
ok_text Oi­kein! f_nodes 9 hide_expr 2k^2 + 2k = tai

Tä­mä lu­ku on ko­ko­nais­lu­ku, kos­ka ___ko­ko­nais­lu­ku­jen sum­mat, tu­lot ja ne­liöt ovat ko­ko­nais­lu­ku­ja.

Kos­ka `n^2` on­nis­tut­tiin esit­tä­mään ha­lu­tus­sa muo­dos­sa, on to­dis­tet­tu sen ole­van pa­ri­ton jos lu­ku `n` on pa­ri­ton. To­dis­tuk­sen päät­ty­mis­tä mer­ka­taan usein pie­nel­lä ne­liöl­lä to­dis­tuk­sen lo­pus­sa.

Epä­suo­ra to­dis­tus

Täs­sä ala­lu­vus­sa ole­te­taan, et­tä väi­te on mää­ri­tel­ty kai­kil­la muut­tu­jien ar­vo­yh­dis­tel­mil­lä.

Epä­suo­ras­sa to­dis­tuk­ses­sa ole­te­taan to­dek­si väit­teen ne­gaa­tio. Tä­tä kut­su­taan vas­ta­väit­teen tai an­ti­tee­sin muo­dos­ta­mi­sek­si. Tä­män jäl­keen vas­ta­väit­tees­tä teh­dään pää­tel­miä, ja yri­te­tään pääs­tä kiis­tat­ta epä­to­teen ti­lan­tee­seen. Usein, mut­ta ei vält­tä­mät­tä, pää­dy­tään ris­ti­rii­taan vas­ta­väit­teen kans­sa. Jos ol­laan var­mo­ja, et­tä jo­kai­nen vä­lis­sä teh­ty pää­tel­mä pi­tää paik­kan­sa, niin ai­noa mah­dol­li­suus on, et­tä vas­ta­väi­te on epä­to­si. Jos vas­ta­väi­te on epä­to­si, sen ne­gaa­tion, eli al­ku­pe­räi­sen väit­teen on ol­ta­va tot­ta.

Epä­suo­ran to­dis­tuk­sen vas­ta­väit­teen muo­dos­ta­mi­ses­sa tu­lee her­käs­ti vir­hei­tä. Mit­kä ovat seu­raa­vien väit­tei­den ne­gaa­tiot?

• Kaik­ki opis­ke­li­jat saa­vat opin­to­tu­kea. Ne­gaa­tioOn ole­mas­sa ai­na­kin yk­si opis­ke­li­ja, jo­ka ei saa opin­to­tu­kea.
• Jou­kos­sa on pa­ril­li­nen lu­ku. Ne­gaa­tioKaik­ki jou­kon lu­vut ovat pa­rit­to­mia.
• Kaik­ki voit­ta­vat, mut­ta vain yk­si voit­taa ka­ton. Ne­gaa­tioOn jo­ku jo­ka ei voi­ta, ka­ton­voit­ta­jia on enem­män kuin yk­si, tai ku­kaan ei voi­ta kat­toa.

Teh­dään esi­merk­ki­to­dis­tus:

Jouk­ko `A` si­säl­tyy jouk­koon `B` mut­ta `A` ei si­säl­ly jouk­koon `C`. Täl­löin jouk­ko `B` ei si­säl­ly jouk­koon `C`.

Aloi­te­taan sa­moin kuin aiem­min­kin. Mi­kä on lau­seen ole­tus? Vas­tausJouk­ko `A` si­säl­tyy jouk­koon `B` ja `A` ei si­säl­ly jouk­koon `C`, eli `A ⊆ B ^^ A ⊈ C`.. Mi­kä on lau­seen väi­te? Vas­tausJouk­ko `B` ei si­säl­ly jouk­koon `C`, eli `B ⊈ C`.. Kos­ka aiom­me teh­dä epä­suo­ran tods­tuk­sen, tar­vit­sem­me myös vas­ta­väit­teen. Mi­kä se on? Vas­tausJouk­ko B si­säl­tyy jouk­koon `C`, eli `B ⊆ C`..

Aloi­te­taan to­dis­tus: Ole­te­taan, et­tä vas­ta­väi­te pä­tee. Ole­tuk­sen mu­kaan jouk­ko `A` si­säl­tyy jouk­koon ___`B` ja vas­ta­väit­teen mu­kaan ___jouk­ko `B` si­säl­tyy jouk­koon `C`. Mi­tä voit näil­lä tie­doil­la pää­tel­lä jouk­ko­jen `A` ja `C` suh­tees­ta? Vas­taus`A` si­säl­tyy jouk­koon `C`. Mik­sei se voi pi­tää paik­kan­sa? Vas­tausSe on ris­ti­rii­das­sa ole­tuk­sen kans­sa..

Kos­ka vas­ta­väi­te ei pi­dä paik­kaan­sa, al­ku­pe­räi­nen ­väi­te pi­tää paik­kan­sa.

Suo­ran ja epä­suo­ran to­dis­tuk­sen kans­sa on ol­ta­va tark­ka­na. Epä­suo­ras­sa to­dis­tuk­ses­sa teh­dyt pää­tel­mät ra­ken­ne­taan väit­tees­tä muo­dos­te­tun vas­ta­väit­teen pääl­le. Suo­ras­sa to­dis­tuk­ses­sa pää­tel­miä ei saa mis­sään ni­mes­sä pe­rus­tel­la väit­teel­lä, kos­ka seu­rauk­se­na oli­si ke­hä­pää­tel­mä.

Kont­ra­po­si­tioon pe­rus­tu­va to­dis­tus (proof by cont­ra­po­si­tion)

Täs­sä­kin ala­lu­vus­sa ole­te­taan, et­tä väi­te on mää­ri­tel­ty kai­kil­la muut­tu­jien ar­vo­yh­dis­tel­mil­lä.

Tä­mä to­dis­tus­ta­pa pe­rus­tuu loo­gi­seen yh­tä­pi­tä­vyy­teen `varphi rarr psi hArr not psi rarr not varphi`. Yh­tä­pi­tä­vyys on jo tek­ni­ses­ti osoi­tet­tu to­dek­si teh­tä­väs­sä Sie­ven­tä­mi­nen pro­po­si­tio­lo­gii­kas­sa, jo­ten mie­ti­tään ly­hyes­ti vain sen mer­ki­tys­tä. Loo­gi­sen yh­tä­pi­tä­vyy­den hah­mot­ta­mi­sen hel­pot­ta­mi­sek­si on usein hyö­dyl­lis­tä miet­tiä sa­nal­lis­ta esi­merk­kiä `varphi`:n, `psi`:n ja mui­den ti­lal­le. Jos `varphi` on ”Ul­ko­na sa­taa.” ja `psi` on ”Py­syn si­säl­lä.”, täl­löin `varphi rarr psi` tar­koit­taa ”Jos ul­ko­na sa­taa, py­syn si­säl­lä”. Mi­tä yh­tä­pi­tä­vyy­den oi­kea puo­li oli­si täl­löin? Vas­tausJos olen ul­ko­na, siel­lä ei sa­da.. Poh­di sa­nal­li­sen esi­mer­kin avul­la, tun­tuu­ko yh­tä­pi­tä­vyys in­tui­tii­vi­ses­ti oi­keal­ta! Poh­din­taaOle­te­taan en­sin va­sen puo­li to­dek­si, eli jos ul­ko­na sa­taa, py­sy­tään si­säl­lä. Jos täl­löin olen ul­ko­na, siel­lä ei voi sa­taa (kos­ka jos sa­tai­si, oli­sin si­säl­lä). Vas­taa­va päät­te­ly pi­tää teh­dä myös toi­seen suun­taan, kos­ka ky­sees­sä on yh­tä­pi­tä­vyy­den tar­kas­te­lu..

Mi­ten tä­mä sit­ten liit­tyy to­dis­ta­mi­seen? Jos­kus on vai­keaa aloit­taa ole­tuk­ses­ta `varphi` ja pää­tel­lä väi­te `psi`, mut­ta hel­pom­paa aloit­taa ole­tuk­ses­ta `not psi` ja pää­tel­lä väi­te `not varphi`. Toi­sin sa­noen, jos­kus on vai­kea to­dis­taa `varphi rArr psi` mut­ta hel­pom­pi to­dis­taa `not psi rArr not varphi`. Kos­ka imp­li­kaa­tiot ovat yh­tä­pi­tä­viä kes­ke­nään, riit­tää kun to­dis­taa toi­sen niis­tä oi­keak­si. Huo­maa, et­tä tä­mä on eri asia kuin mi­tä edel­li­ses­sä kap­pa­lees­sa kä­si­tel­tiin. Sii­nä tar­kas­tel­tiin yh­tä­pi­tä­vyyt­tä it­seään, ja poh­dit­tiin sen paik­kan­sa­pi­tä­vyyt­tä. Täs­sä kap­pa­lees­sa yh­tä­pi­tä­vyys us­ko­taan oi­keak­si, ja mie­ti­tään kuin­ka si­tä voi­si hyö­dyn­tää.

Ko­keil­laan! To­dis­ta kont­ra­po­si­tion avul­la, et­tä seu­raa­va väit­tä­mä pä­tee:

Jos lu­ku `n^2` on pa­ril­li­nen, niin myös lu­ku `n` on pa­ril­li­nen.

Aloi­ta jäl­leen pur­ka­mal­la lau­se pa­la­siin. Mi­kä on ole­tus, mi­kä väi­te? Ole­tuk­setLu­ku `n^2` on pa­ril­li­nen. Väi­teLu­ku `n` on pa­ril­li­nen.

Jos mie­ti­tään kont­ra­po­si­tioon liit­ty­vää yh­tä­pi­tä­vyyt­tä, mi­kä lau­sees­sa on `varphi` ja mi­kä `psi`? Vas­tauk­set: `varphi`Sa­ma kuin lau­seen ole­tuk­set, siis lu­ku `n^2` on pa­ril­li­nen. `psi`Sa­ma kuin lau­seen väi­te, siis lu­ku `n` on pa­ril­li­nen.

Muo­dos­ta myös näi­den ne­gaa­tiot ja imp­li­kaa­tio `not psi rArr not varphi`. Tar­kis­ta vas­tauk­se­si al­ta:
`not varphi`Lu­ku `n^2` on pa­ri­ton. `not psi`Lu­ku `n` on pa­ri­ton. `not psi rArr not varphi`Jos lu­ku `n` on pa­ri­ton, niin lu­ku `n^2` on myös pa­ri­ton.

Olet­ko jos­kus näh­nyt sa­man­tyyp­pi­sen lau­seen kuin tä­män teh­tä­vän `not psi rArr not varphi`? Vink­kiMuis­te­le mil­lai­sia lau­sei­ta täs­sä teh­tä­väs­sä on to­dis­tet­tu jo..

To­dis­tus: Ko­kei­le kek­siä to­dis­tus it­se. Kat­so vas­taus täs­täTo­dis­tet­ta­van lau­seen kont­ra­po­si­tio to­dis­tet­tiin aiem­min täs­sä teh­tä­väs­sä suo­ral­la to­dis­tuk­sel­la. Kos­ka lau­seen kont­ra­po­si­tio pä­tee, myös it­se lau­se pä­tee..   □

To­dis­tuk­sia ra­ken­taes­sa (ja to­ki muu­ten­kin) kan­nat­taa muis­tel­la, on­ko eh­kä aiem­min teh­nyt sa­man­tyyp­pi­siä teh­tä­viä.

To­dis­tuk­sia

Alus­sa to­det­tiin, et­tä to­dis­tuk­set koos­tu­vat kol­mes­ta osas­ta, ole­tuk­sis­ta, väit­tees­tä ja to­dis­tuk­ses­ta. To­dis­tuk­sen ra­ken­ta­mi­seen kuu­luu nel­jäs­kin vai­he, jo­ta ei val­miis­sa to­dis­tuk­ses­sa kir­joi­te­ta nä­ky­viin. Se on to­dis­tuk­sen suun­nit­te­lu. Jo­kai­ses­sa edel­li­sen kap­pa­leen to­dis­tuk­ses­sa oli pie­ni poh­din­ta en­nen var­si­nais­ta to­dis­tus­ta. Vaik­ka se ei näy­kään lo­pul­li­ses­sa to­dis­tuk­ses­sa, se on erit­täin tär­keä vai­he sii­nä koh­taa, kun to­dis­tuk­sia teh­dään it­se.

To­dis­ta seu­raa­vat lau­seet.

Lu­ku `n` on pa­ril­li­nen jos, ja vain jos lu­ku `n^2` on pa­ril­li­nen.

Ker­taa en­sin teh­tä­vän alus­ta, mi­ten tä­män tyyp­pi­set lau­seet to­dis­te­taan.

Aloi­te­taan to­dis­tus. Ole­te­taan en­sin, et­tä va­sen puo­li pä­tee ja oi­kea puo­li on to­dis­tet­ta­va. Täl­löin ole­tuk­se­na on ___Lu­ku `n` on pa­ril­li­nen ja väit­tee­nä on ___Lu­ku `n^2` on pa­ril­li­nen.

Ole­tuk­ses­ta saa­daan, et­tä on ole­mas­sa ko­ko­nais­lu­ku `k`, jol­le `n =`
ok_text Oi­kein! f_nodes 3 hide_expr 2k = tai

Täl­löin `n^2 =`
ok_text Oi­kein! hide_expr (2k)^2 = tai

Muok­kaa edel­li­sen laa­ti­kon tu­los sel­lai­seen muo­toon, jos­ta voit näh­dä sen ole­van pa­ril­li­nen. Täl­löin puo­let lau­sees­ta on to­dis­tet­tu.
ok_text Oi­kein! f_nodes 7 hide_expr (2k)^2 = 2()
tai

Ole­te­taan seu­raa­vak­si oi­kean puo­len ole­van tot­ta, ja yri­te­tään sen avul­la osoit­taa va­sen puo­li to­dek­si. Nyt ole­tus on ___Lu­ku `n^2` on pa­ril­li­nen ja väit­tee­nä on ___Lu­ku `n` on pa­ril­li­nen. To­dis­ta tä­mä it­se ja ver­taa vas­taus­ta­si tä­hän Tä­mä osoi­tet­tiin kont­ra­po­si­tion avul­la aiem­min..   □

Jos lu­ku `a` on jaol­li­nen lu­vul­la `b` ja lu­ku `b` on jaol­li­nen lu­vul­la `c`, niin lu­ku `a` on jaol­li­nen lu­vul­la `c`.

Mää­rää en­sin ole­tusLu­ku `a` on jaol­li­nen lu­vul­la `b` ja `b` on jaol­li­nen lu­vul­la `c`. ja väi­teLu­ku `a` on jaol­li­nen lu­vul­la `c`..

Mil­lä ta­val­la voi­daan pää­tel­lä väit­teen pi­tä­vän paik­kan­sa? Vih­jeKat­so luen­to­ma­te­riaa­leis­ta, mi­tä siel­lä pu­hu­taan jaol­li­suu­des­ta ja te­ki­jöis­tä. Vas­tausLu­ku `a` on jaol­li­nen lu­vul­la `c`, jos ja vain jos `c` on `a`:n te­ki­jä. On siis löy­det­tä­vä jo­kin ko­ko­nais­lu­ku `k`, jol­le `a=ck`.

Mi­ten ole­tus­ta voi­si hyö­dyn­tää? Kir­joi­ta pre­di­kaat­ti, jo­ka sa­noo `b`:n ole­van jaol­li­nen `c`:llä. Jos tar­vit­set apu­muut­tu­jaa, va­lit­se `h`.
ok_text Oi­kein! modulo 12 f_nodes 6 hide_expr EE h: b = c h <=>

tai

Kir­joi­ta seu­raa­vak­si pre­di­kaat­ti, jo­ka sa­noo `a`:n ole­van jaol­li­nen `b`:llä. Jos tar­vit­set apu­muut­tu­jaa, va­lit­se `k`.
ok_text Oi­kein! modulo 12 f_nodes 6 hide_expr EE h: a = b h <=>

tai

Yh­dis­tä kah­den edel­li­sen pre­di­kaa­tin tie­dot niin, et­tä lu­kua `b` ei enää mai­ni­ta. Väit­teen al­ku on an­net­tu val­mii­na.
ok_text Oi­kein! modulo 12 f_nodes 9 hide_expr (EE h: EE k: a = c h k) <=>∃ h: ∃ k: a =
tai

To­dis­tus: Ko­kei­le muo­toil­la to­dis­tus it­se pa­pe­ril­le edel­li­sis­sä koh­dis­sa an­net­tu­jen tie­to­jen poh­jal­ta. Kat­so mal­li­to­dis­tus sen jäl­keen täs­täKos­ka `a` on jaol­li­nen lu­vul­la `b`, on ole­mas­sa sel­lai­nen ko­ko­nais­lu­ku `k`, et­tä `a = k b`. Edel­leen, kos­ka `b` on jaol­li­nen lu­vul­la `c`, on ole­mas­sa sel­lai­nen ko­ko­nais­lu­ku `h`, et­tä `b = h c`. Nä­mä yh­dis­tä­mäl­lä ja hyö­dyn­tä­mäl­lä ker­to­las­kun omi­nai­suuk­sia saa­daan `a = k b = k (h c) = (k h) c`. Lu­vut `k` ja `h` ovat ko­ko­nais­lu­ku­ja, jo­ten nii­den tu­lo on myös ko­ko­nais­lu­ku. Siis­pä `a` voi­daan kir­joit­taa `c`:n ja jon­kin ko­ko­nais­lu­vun tu­lo­na, jo­ten se on jaol­li­nen lu­vul­la `c`.  □ ja ver­taa omaa­si sii­hen.

Ol­koot `a` ja `b` reaa­li­lu­ku­ja. Täl­löin `(a + b)^2 <= 2(a^2 + b^2)`.

To­dis­tuk­sen idea: muo­ka­taan lau­se­ket­ta `(a + b)^2` ja yri­te­tään saa­da se muo­toon `2(a^2 + b^2)`. Lau­se­ket­ta voi muo­ka­ta vain ar­vol­taan sa­mak­si tai suu­rem­mak­si lau­sek­keek­si. Ko­keil­laan aluk­si ava­ta va­sem­man puo­len su­lut, jol­loin saam­me tun­tu­maa sii­tä, mi­tä epä­yh­tä­löl­le kan­nat­taa teh­dä:

`(a + b)^2 =`
ok_text Oi­kein! hide_expr a^2 + b^2 + 2a b = tai

Täs­tä muo­dos­ta huo­ma­taan, et­tä oi­keal­la ja va­sem­mal­la puo­lel­la on hy­vin pie­ni ero. Jos mo­lem­mil­ta puo­lil­ta vä­hen­ne­tään `a^2 + b^2`, niin va­sem­mal­le puo­lel­le jää
ok_text Oi­kein! hide_expr f_nodes 5 2a b = tai

ja oi­keal­le puo­lel­le jää
ok_text Oi­kein! hide_expr f_nodes 7 a^2 + b^2 = tai

Seu­raa­vak­si on poh­dit­ta­va, mi­ten epä­yh­tä­lö `2a b <= a^2 + b^2` voi­daan osoit­taa to­dek­si. Si­tä voi­daan muo­ka­ta vä­hen­tä­mäl­lä mo­lem­mil­ta puo­lil­ta lu­ku `2a b`. Si­ten sii­tä tu­lee ___`0 <= a^2 + b^2 - 2a b`. Tä­mä epä­yh­tä­lö on ai­na to­si, sil­lä ___tie­de­tään, et­tä kaik­kien reaa­li­lu­ku­jen ne­liöt ovat ei-ne­ga­tii­vi­sia ja `a^2 + b^2 - 2a b = (a-b)^2 >= 0`.

Muo­toi­le to­dis­tus jäl­leen pa­pe­ril­le, ja ver­taa si­tä mal­li­to­dis­tuk­seenOl­koot `a` ja `b` reaa­li­lu­ku­ja. Kos­ka `0 ≤ (a-b)^2 = a^2 + b^2 - 2a b`, huo­ma­taan et­tä `2a b <= a^2 + b^2`. Täl­löin
`(a+b)^2 = a^2 + b^2 + 2ab`
`<= a^2 + b^2 + (a^2 + b^2)` \\ kos­ka `2a b <= a^2 + b^2`
`= 2(a^2 + b^2)`, ku­ten ha­lut­tiin­kin.  □.

Ku­ten huo­maat, to­dis­tus­ta kek­sit­täes­sä päät­te­ly­ket­ju voi ede­tä hy­vin eri jär­jes­tyk­ses­sä kuin var­si­nai­nen to­dis­tus. Sik­si val­mii­ta to­dis­tuk­sia lu­kies­sa he­rää usein ky­sy­mys, mis­tä sen te­ki­jä on kek­si­nyt, mi­tä kan­nat­taa teh­dä. To­dis­tuk­sis­sa, ku­ten ylei­ses­ti­kin päät­te­ly­teh­tä­vis­sä, kan­nat­taa usein en­sin käy­dä lä­pi mi­tä tie­de­tään (to­dis­tus­teh­tä­väs­sä tä­mä on ole­tus­ten lis­taa­mi­nen), sit­ten mi­tä ha­lu­taan (to­dis­tus­teh­tä­väs­sä väit­teen tun­nis­ta­mi­nen) ja sen jäl­keen poh­tia ja pää­tel­lä mi­ten nä­mä saa­daan yh­dis­tet­tyä. Var­si­nai­ses­sa to­dis­tuk­ses­sa nä­mä päät­te­lyt py­ri­tään kir­joit­ta­maan sel­keään ja hel­pos­ti seu­rat­ta­vaan muo­toon.

Tot­ta vai ei?

Ovat­ko seu­raa­vat to­dis­tuk­set pä­te­viä? Pe­rus­te­le.

Jo­kai­nen pa­ri­ton lu­ku on myös pa­ril­li­nen.

To­dis­tuk­sen idea: va­li­taan mie­li­val­tai­nen pa­ri­ton lu­ku ja osoi­te­taan sen ole­van myös pa­ril­li­nen. Kos­ka va­li­tul­le lu­vul­le ei ole­te­ta mi­tään mui­ta omi­nai­suuk­sia kuin pa­rit­to­muus, to­dis­tus pä­tee kai­kil­le pa­rit­to­mil­le lu­vuil­le.

To­dis­tus: Ol­koon `n` jo­kin pa­ri­ton ko­ko­nais­lu­ku. Kos­ka `n` on pa­ri­ton, se voi­daan kir­joit­taa muo­dos­sa `n = 2k + 1`, kun `k` on jo­kin ko­ko­nais­lu­ku. Tä­tä muok­kaa­mal­la saa­daan `n = 2k+1 = 2(k+1/2)`, eli lu­ku `n` voi­daan kir­joit­taa lu­vun `2` ja jon­kin toi­sen lu­vun tu­lo­na. Lu­ku `n` on siis pa­ril­li­nen.

On­ko to­dis­tus pä­te­vä?Ei ole. To­dis­tuk­ses­sa on vir­he: lu­ku `k+1/2` ei ole ko­ko­nais­lu­ku.

Jos on ole­mas­sa suu­rin reaa­li­lu­ku, niin se on lu­ku `1`.

To­dis­tus: Ole­te­taan, et­tä on ole­mas­sa suu­rin reaa­li­lu­ku, ja mer­ki­tään si­tä kir­jai­mel­la `s`. Kos­ka `s` on suu­rin reaa­li­lu­ku, kai­kil­le reaa­li­lu­vuil­le `x` pä­tee `x <= s`. Kos­ka se pä­tee jo­kai­sel­le reaa­li­lu­vul­le, se pä­tee sil­loin­kin kun `x = s^2 - s + 1`. Niin­pä `s^2 - s + 1 <= s`. Vä­hen­tä­mäl­lä kum­mal­ta­kin puo­lel­ta `s` saa­daan `s^2 - 2s + 1 <= 0`.

Kos­ka `(s-1)^2 = s^2 - 2s + 1`, saa­daan `(s-1)^2 <= 0`.

Jo­kai­sel­le reaa­li­lu­vul­le `x` pä­tee `x^2 >= 0`. Myös `s-1` on reaa­li­lu­ku, jo­ten `(s-1)^2 >= 0`.

Kos­ka `(s-1)^2 <= 0` ja `(s-1)^2 >= 0`, saa­daan `(s-1)^2 = 0` eli `(s-1)(s-1) = 0`. Kah­den reaa­li­lu­vun tu­lo on nol­la jos ja vain jos sen jom­pi­kum­pi te­ki­jä on `0`, jo­ten `s-1 = 0` tai `s-1 = 0`. Sii­tä saa­daan `s = 1`.

Siis suu­rin reaa­li­lu­ku on `1`.

On­ko to­dis­tus pä­te­vä?On. Kaik­ki to­dis­tuk­ses­sa teh­dyt päät­te­lyt pi­tä­vät paik­kan­sa. On tot­ta, et­tä jos on ole­mas­sa suu­rin reaa­li­lu­ku, niin se on lu­ku `1`. Edel­lä esi­tet­ty to­dis­tus on täy­sin pä­te­vä to­dis­tus täl­le lau­seel­le. Lau­se on tot­ta sik­si, et­tä sen ole­tus ei ole iki­nä to­si.

Mi­kä jat­ko­pää­tel­mäEpä­suo­ra to­dis­tus sil­le, et­tä suu­rin­ta reaa­li­lu­kua ei ole ole­mas­sa, al­kaa ole­tuk­ses­ta et­tä se on­kin ole­mas­sa ja joh­taa mah­dot­to­man tu­lok­sen. Juu­ri niin­hän edel­lä teh­tiin. Tu­los, et­tä suu­rin reaa­li­lu­ku on `1`, on mah­do­ton, kos­ka `2 > 1`. Olem­me siis to­dis­ta­neet epä­suo­ras­ti (ja tar­peet­to­man mo­ni­mut­kai­ses­ti), et­tä suu­rin­ta reaa­li­lu­kua ei ole ole­mas­sa. voi­daan teh­dä epä­suo­ran to­dis­tuk­sen me­ne­tel­mäl­lä?