Teh­tä­vä:
Ma­te­maat­ti­ses­ta päät­te­le­mi­ses­tä

Täs­sä teh­tä­väs­sä käy­dään lä­pi ma­te­maat­ti­seen päät­te­lyyn liit­ty­viä pe­rus­kä­sit­tei­tä: (avoin) väi­te, vas­ta­esi­merk­ki, päät­te­ly­imp­li­kaa­tio, päät­te­ly­ek­vi­va­lens­si, päät­te­lyn asia­yh­teys, päät­te­ly­as­kel ja päät­te­ly­ket­ju. Teh­tä­väs­sä ko­ros­te­taan si­tä, et­tä vaik­ka päät­te­lys­sä usein käy­te­tään ma­te­maat­ti­sia sään­tö­jä, pä­te­vän päät­te­lyn erot­taa epä­pä­te­väs­tä vii­me kä­des­sä vain se, on­ko mil­le­kään päät­te­ly­as­ke­leel­le ole­mas­sa vas­ta­esi­merk­kiä. Lo­puk­si käy­dään lä­pi oh­jel­moin­tia si­vua­va esi­merk­ki.

Jos käy­tät Math­Checkiä en­sim­mäis­tä ker­taa, niin tee en­sin teh­tä­vä Yleis­tä Math­Checkis­tä. Jos et muual­ta löy­dä mi­ten jo­kin sym­bo­li kir­joi­te­taan, niin kat­so MathCheck Brief Instructions.

Väi­te ja vas­ta­esi­merk­ki

Väi­te on täs­sä teh­tä­väs­sä mi­kä ta­han­sa, jo­ka tuot­taa to­tuus­ar­von to­si (T) tai epä­to­si (F). Las­kem­me al­ka­jai­sik­si väit­teen x² − 2y > x + 1 to­tuus­ar­von pa­ris­sa ti­lan­tees­sa.

Avoin väi­te on väi­te, jos­sa esiin­tyy ti­lan­tees­ta riip­pu­vaa ar­voa tar­koit­ta­va il­maus. Sel­lais­ta il­maus­ta sa­no­taan muut­tu­jak­si. Esi­mer­kik­si ”siel­lä on yli­opis­to” on avoin väi­te, kos­ka ”siel­lä” on muut­tu­ja. Se­hän voi tar­koit­taa mi­tä ta­han­sa paik­ka­kun­taa. Vaik­ka tie­täi­sim­me, mi­tä ”siel­lä” täl­lä ker­taa tar­koit­taa, se on sil­ti muut­tu­ja.

Sul­jet­tu väi­te on väi­te, jos­sa ei esiin­ny ti­lan­tees­ta riip­pu­vaa ar­voa tar­koit­ta­vaa il­maus­ta. Esi­mer­kik­si ”Jy­väs­ky­läs­sä on yli­opis­to” on sul­jet­tu väi­te.

On ta­val­lis­ta, et­tä avoi­men väit­teen to­tuus­ar­vo riip­puu muut­tu­jien saa­mis­ta ar­vois­ta. Esi­mer­kik­si x + 1 = 2 on to­si jos x:n ar­vo on 1, ja epä­to­si muil­la x:n ar­voil­la. On kui­ten­kin ole­mas­sa myös avoi­mia väit­tei­tä, joi­den to­tuus­ar­vo ei rii­pu muut­tu­jien saa­mis­ta ar­vois­ta. Esi­mer­kik­si x + 0 = x on to­si riip­pu­mat­ta sii­tä, mi­kä lu­ku lai­te­taan x:n pai­kal­le.

Vas­ta­esi­merk­ki väit­teel­le on muut­tu­jien ar­vo­yh­dis­tel­mä, jol­la väi­te ei ole to­si. An­na jo­kai­sel­le seu­raa­vis­ta vas­ta­esi­merk­ki kir­joit­ta­mal­la jo­kai­seen vas­taus­ruu­tuun lu­ku.

Täs­sä vai­hees­sa on tar­peen poh­tia, mi­tä tar­koit­taa ”muut­tu­jien ar­vo­yh­dis­tel­mä”. Il­maus ”x:n ar­vo on 2 ja y:n ar­vo on 5” an­taa ar­vo­yh­dis­tel­män kah­del­le muut­tu­jal­le, ni­mit­täin muut­tu­jil­le x ja y. Se voi­daan esit­tää kaa­va­na x = 2 ∧ y = 5. Kaa­va x = 2 ∨ y = 5 ei esi­tä yh­tä ar­vo­yh­dis­tel­mää vaan ää­ret­tö­män mon­ta, muun muas­sa sel­lai­sen jos­sa se­kä x = 5 et­tä y = 5.

Il­maus ”x:n ar­vo on 2” an­taa ar­vo­yh­dis­tel­män yh­del­le muut­tu­jal­le. Il­maus ”” an­taa ar­vo­yh­dis­tel­män nol­lal­le muut­tu­jal­le. Ar­vo­yh­dis­tel­mää nol­lal­le muut­tu­jal­le voi ol­la han­ka­la aja­tel­la, kos­ka se on tyh­jä, mut­ta se on sil­ti hyö­dyl­li­nen ma­te­maat­ti­nen kä­si­te. Se mm. kel­paa vas­ta­esi­mer­kik­si väit­teel­le 1 + 1 = 3, sil­lä 1 + 1 = 3 ei ole to­si sil­loin kun muut­tu­jil­la on ne ar­vot, jot­ka tyh­jä ar­vo­yh­dis­tel­mä mää­rää.

Kel­paa­ko tyh­jä ar­vo­yh­dis­tel­mä vas­ta­esi­mer­kik­si väit­teel­le 1 + 1 = 2? Vas­tausEi kel­paa, sil­lä 1 + 1 = 2 on to­si sil­loin kun muut­tu­jil­la on ne ar­vot, jot­ka tyh­jä ar­vo­yh­dis­tel­mä mää­rää.

On ta­val­lis­ta il­mais­ta ma­te­maat­ti­sia lain­alai­suuk­sia avoi­mi­na väit­tei­nä, jot­ka ovat to­sia riip­pu­mat­ta muut­tu­jien ar­vois­ta. Täs­sä kak­si tut­tua esi­merk­kiä:

• a(b + c) = ab + ac (ker­to­las­kun osit­te­lu­la­ki)
• (a + b)² = a² + 2ab + b² (bi­no­min ne­liö)

Päät­te­ly­esi­merk­ki: it­seis­ar­vo­epä­yh­tä­lö

Saa­dak­sem­me päät­te­le­mi­sen ideas­ta kiin­ni aloi­tam­me esi­mer­kil­lä: mil­lä x:n ja y:n ar­vo­yh­dis­tel­mil­lä pä­tee |x − y| + x + y < 6?

It­seis­ar­vo­mer­kis­tä |…| pää­see eroon ja­ka­mal­la teh­tä­vä kah­teen ta­pauk­seen it­seis­ar­von mää­ri­tel­män mu­kaan:

|x| =

x	, jos x ≥ 0
−x	, jos x < 0

Ylem­pi ta­paus

Huo­maa äs­kei­sen pa­laut­teen alus­sa ”As­su­me x ≥ y”. Se tar­koit­taa, et­tä vas­ta­esi­mer­keik­si kel­paa­vat vain sel­lai­set x:n ja y:n ar­vo­yh­dis­tel­mät, joil­le pä­tee x ≥ y. Pa­lau­te on siis muo­dos­tet­tu olet­taen ylem­män ta­pauk­sen jos-eh­to.

Tä­män ym­mär­tä­mi­sek­si kan­nat­taa ko­keil­la, mi­tä ta­pah­tuu, jos tä­mä ole­tus pois­te­taan. Pois­ta edel­lä ol­lut va­lin­ta, jon­ka koh­dal­la lu­ki ”An­na tä­män ol­la aluk­si pääl­lä”. Ko­kei­le, min­kä­lai­sen pa­laut­teen nyt saat edel­li­ses­tä koh­das­ta. On­ko se asian­mu­kai­nen pa­lau­te it­seis­ar­vo­teh­tä­vän rat­kai­se­mi­sen kan­nal­ta? Open mie­li­pi­dePa­laut­tees­sa an­ne­tul­le vas­ta­esi­mer­kil­le ei pä­de x ≥ y. Kos­ka nyt kä­si­tel­lään ta­paus­ta x ≥ y, ei täl­lai­nen vas­ta­esi­merk­ki ole asian­mu­kai­nen, kos­ka se on sen ti­lan­teen ul­ko­puo­lel­la, jo­ta nyt kä­si­tel­lään. Vir­he on sa­man­lai­nen kuin jos jo­ku an­tai­si väit­teel­le ”Ke­säl­lä jo­kai­ses­sa kuu­kau­des­sa on 30 tai 31 päi­vää” vas­ta­esi­mer­kik­si ”hel­mi­kuus­sa on 28 päi­vää”. Hel­mi­kuu­han ei ole ke­säl­lä.

Olem­me tä­hän men­nes­sä ja­ka­neet päät­te­ly­teh­tä­väm­me kah­teen ta­pauk­seen ja aloit­ta­neet ta­pauk­sen x ≥ y kä­sit­te­lyn muun­ta­mal­la al­ku­pe­räi­sen väit­teen |x − y| + x + y < 6 muo­toon x − y + x + y < 6. Nyt sie­ven­nän tä­män mah­dol­li­sim­man yk­sin­ker­tai­seen muo­toon. Ha­vain­nol­lis­taak­se­ni mis­tä päät­te­lys­sä on ky­se, näy­tän ta­val­lis­ta enem­män vä­li­vai­hei­ta:

Alem­pi ta­paus

Ta­paus­ten yh­dis­tä­mi­nen

Kun päät­te­ly jae­taan ta­pauk­siin, niin ta­paus­ten lop­pu­tu­lok­set yh­dis­te­tään täl­lä pe­riaat­teel­la:

	ta­pauk­sen 1 eh­to	ja	ta­pauk­sen 1 tu­los
tai	ta­pauk­sen 2 eh­to	ja	ta­pauk­sen 2 tu­los
tai	ta­pauk­sen 3 eh­to	ja	ta­pauk­sen 3 tu­los
tai	ta­pauk­sen 4 eh­to	ja	ta­pauk­sen 4 tu­los

Jat­ka sa­maan mal­liin

Nyt teh­tä­vä­si on rat­kais­ta |2a + b − 9| + b ≥ 2a + 1 edel­lä ku­va­tul­la ta­val­la. Jo­kai­ses­sa koh­das­sa on tar­koi­tus, et­tä en­sin muok­kaat vas­tauk­sen muo­toon jos­sa ei tu­le muu­ta kuin komp­lek­si­suus­il­moi­tus, ja sen jäl­keen muok­kaat sen tar­peek­si ly­hyeen muo­toon yh­del­lä tai useam­mal­la vä­li­vai­heel­la. Jä­tä vä­li­vai­hei­ta­si nä­ky­viin ja ero­ta ne toi­sis­taan sym­bo­lil­la <=>.

Päät­te­ly­ope­raat­to­rit

Olet edel­lä kir­joit­ta­nut sym­bo­lin ⇔ tai sen ASCII-vas­ti­neen <=>. Si­tä kut­su­taan ni­mil­lä loo­gi­nen ek­vi­va­lens­si, päät­te­ly­ek­vi­va­lens­si tai ly­hyes­ti ek­vi­va­lens­si. Sa­na ”ek­vi­va­lens­si” tar­koit­taa mo­nia mui­ta­kin ma­te­maat­ti­sia kä­sit­tei­tä mu­kaan lu­kien ta­val­li­nen yh­tä­suu­ruus =, jo­ten voi syn­tyä se­kaan­nuk­sen vaa­ra. Se väl­te­tään käyt­tä­mäl­lä etu­lii­tet­tä ”loo­gi­nen” tai ”päät­te­ly”.

Etu­lii­te ”päät­te­ly” ko­ros­taa sym­bo­lin ⇔ eroa sym­bo­liin ↔: ↔ esiin­tyy väit­tei­den si­säl­lä, tuot­taa to­tuus­ar­von F tai T (kol­mi­ar­vo­lo­gii­kas­sa myös U), ei­kä rii­pu asia­yh­tey­des­tä vaan ai­noas­taan va­sem­man ja oi­kean puo­len­sa tuot­ta­mis­ta to­tuus­ar­vois­ta. Sym­bo­li ⇔ esiin­tyy väit­tei­den vä­lis­sä, ei tuo­ta to­tuus­ar­voa vaan tu­lok­sen ”pä­te­vä päät­te­ly­as­kel” tai ”ei pä­te­vä päät­te­ly­as­kel”, ja riip­puu asia­yh­tey­des­tä. Alam­me nyt kä­si­tel­lä tä­tä pe­rus­teel­li­ses­ti.

Va­sen ⇔ oi­kea tar­koit­taa, et­tä kai­kil­la niil­lä asia­yh­tey­den sal­li­mil­la muut­tu­jien ar­vo­yh­dis­tel­mil­lä, joil­la va­sen puo­li on to­si, myös oi­kea puo­li on to­si, ja päin­vas­toin.

Vas­ta­esi­merk­ki täl­le on sel­lai­nen muut­tu­jien ar­vo­yh­dis­tel­mä, jon­ka asia­yh­teys sal­lii ja jol­la toi­nen puo­li on to­si, mut­ta toi­nen puo­li ei ole to­si.

Ote­taan en­sin ta­pauk­sia, jois­sa asia­yh­teys sal­lii kaik­ki muut­tu­jien ar­vo­yh­dis­tel­mät. Kir­joi­ta vas­ta­esi­merk­ki tai va­lit­se ”ei vas­ta­esi­merk­ke­jä”.

Yk­si esi­merk­ki asia­yh­tey­des­tä on edel­lä ol­leet as­su­me-osat. Kun sie­ven­sim­me  |x − y| + x + y < 6  ⇔  x − y + x + y < 6 , niin Math­Check hy­väk­syi sen kun as­su­me x ≥ y oli pääl­lä, mut­ta an­toi vas­ta­esi­mer­kin kun se ei ol­lut pääl­lä.

Täs­sä esi­mer­kis­sä, kun as­su­me x ≥ y on pois pääl­tä, asia­yh­teys sal­li kaik­ki x:n ja y:n ar­vo­yh­dis­tel­mät. Sil­loin esi­mer­kik­si x = 2 ja y = 3 on pä­te­vä vas­ta­esi­merk­ki päät­te­ly­as­ke­leel­le  |x − y| + x + y < 6  ⇔  x − y + x + y < 6 . Va­sen puo­li tuot­taa 6 < 6 jo­ka ei ole to­si; ja oi­kea puo­li tuot­taa 4 < 6 jo­ka on to­si.

Täs­sä esi­mer­kis­sä, kun as­su­me x ≥ y on pääl­lä, asia­yh­teys ei sal­li vas­ta­esi­mer­kik­si x = 2 ja y = 3, kos­ka x ≥ y ei pä­de sil­le. It­se asias­sa sil­loin mi­kään ei ole pä­te­vä vas­ta­esi­merk­ki, kos­ka sil­loin it­seis­ar­von mää­ri­tel­män mu­kaan |x − y| = x − y, jo­ten va­sen ja oi­kea puo­li ovat sa­man­lai­set.

Asia­yh­teys voi koos­tua useas­ta osas­ta. Ma­te­maat­ti­sis­sa teks­teis­sä asia­yh­tey­den ker­to­mi­seen saa­te­taan käyt­tää se­kä sa­no­ja et­tä kaa­vo­ja, ja ne voi­vat ol­la ja­kaan­tu­neet useaan osaan jot­ka saat­ta­vat si­jai­ta kau­ka­na toi­sis­taan. Käy­tet­tä­vä lu­ku­tyyp­pi saa­te­taan sa­noa kir­jan alus­sa tai jät­tää ko­ko­naan sa­no­mat­ta. Kui­ten­kin sil­lä on tär­keä mer­ki­tys. Kum­mal­le­kin al­la ole­vis­ta vaih­to­eh­dois­ta, mie­ti en­sin it­se mi­ten asia on, ja sit­ten ko­kei­le mi­tä miel­tä Math­Check on asias­ta.

Har­joit­te­lem­me asia­yh­tey­den vai­ku­tus­ta.

Math­Checkin an­ta­mas­sa pa­laut­tees­sa on esiin­ty­nyt myös ⇐. Olet saat­ta­nut näh­dä sym­bo­lin ⇒, jo­ka tun­ne­taan ni­mel­lä imp­li­kaa­tio tai päät­te­ly­imp­li­kaa­tio. Nyt on ai­ka ker­toa, mi­tä ne tar­koit­ta­vat.

Va­sen ⇒ oi­kea tar­koit­taa, et­tä kai­kil­la niil­lä asia­yh­tey­den sal­li­mil­la muut­tu­jien ar­vo­yh­dis­tel­mil­lä, joil­la va­sen puo­li on to­si, myös oi­kea puo­li on to­si.

Vas­ta­esi­merk­ki imp­li­kaa­tiol­le on sel­lai­nen muut­tu­jien ar­vo­yh­dis­tel­mä, jon­ka asia­yh­teys sal­lii ja jol­la va­sen puo­li on to­si, mut­ta oi­kea puo­li ei ole to­si.

Sym­bo­lin ⇐ mer­ki­tys on help­po ar­va­ta: se on ⇒ ta­ka­pe­rin.

Va­sen ⇐ oi­kea tar­koit­taa sa­maa kuin oi­kea ⇒ va­sen.

Käy­kääm­me lä­pi kaik­ki edel­lä ol­leet ta­pauk­set, jois­sa on vas­ta­esi­merk­ke­jä, ja sel­vit­tä­kääm­me, kum­min päin nii­hin on vas­ta­esi­merk­ke­jä (tai jo­pa mo­lem­min päin). Kaik­ki lu­vut ovat reaa­li­lu­ku­ja.

Päät­te­ly­ope­raat­to­rei­den käyt­tö lue­taan usein sa­nal­li­ses­ti seu­raa­vas­ti:

il­maus	voi­daan lu­kea
va­sen ⇔ oi­kea	va­sen jos ja vain jos oi­kea
va­sen ⇒ oi­kea	jos va­sen niin oi­kea
va­sen ⇐ oi­kea	vain jos va­sen niin oi­kea

Toi­sin­päin, nä­mä sa­nal­li­set il­mauk­set tar­koit­ta­vat yleen­sä sa­maa kuin vas­taa­vat päät­te­ly­ope­raat­to­rit, so­vel­let­tu­na sii­hen kä­si­te­maail­maan jos­ta kul­loin­kin on pu­he. Sa­nal­li­sis­sa il­mauk­sis­sa myös va­sen ja oi­kea voi­vat ol­la sa­nal­li­sia. Ne voi­vat pu­hua pait­si koh­de­maail­mas­ta myös esi­mer­kik­si lo­gii­kan käyt­töön liit­ty­vis­tä asiois­ta, ku­ten esi­mer­kis­sä ”päät­te­ly­as­kel on epä­pä­te­vä jos ja vain jos sil­le on vas­ta­esi­merk­ki”.

Ma­te­ma­tii­kas­sa käy­te­tään toi­si­naan myös seu­raa­via il­mauk­sia vas­ta­ten päät­te­ly­ope­raat­to­rei­ta, ne­kin so­vel­let­tu­na sii­hen kä­si­te­maail­maan jos­ta on pu­he:

il­maus	voi­daan lu­kea
va­sen ⇔ oi­kea	va­sen on vält­tä­mä­tön ja riit­tä­vä eh­to oi­kea:lle
va­sen ⇒ oi­kea	va­sen on riit­tä­vä eh­to oi­kea:lle
va­sen ⇐ oi­kea	va­sen on vält­tä­mä­tön eh­to oi­kea:lle

Alim­mai­sen ta­ka­na ole­va aja­tus on, et­tä on mah­do­ton­ta et­tä oi­kea pä­tee mut­ta va­sen ei pä­de, sik­si va­sen on vält­tä­mä­tön eh­to. Kes­kim­mäi­ses­sä va­sen riit­tää ta­kaa­maan et­tä oi­kea pä­tee, mut­ta oi­kea voi pä­teä myös vaik­ka va­sen ei pä­ti­si, jo­ten va­sen ei ole vält­tä­mä­tön.

Päät­te­ly­as­kel ja päät­te­ly­ket­ju

Il­mauk­set muo­toa va­sen ⇒ oi­kea, va­sen ⇐ oi­kea ja va­sen ⇔ oi­kea ovat päät­te­ly­as­ke­lia. Päät­te­ly­as­kel ei tuo­ta to­tuus­ar­voa, vaan on pä­te­vä tai epä­pä­te­vä. Se on epä­pä­te­vä jos ja vain jos sil­le on vas­ta­esi­merk­ki.

Päät­te­ly­as­ke­leen pä­te­vyys ei siis mää­räy­dy sii­tä, on­ko se pe­rus­tel­ta­vis­sa jol­la­kin ma­te­maat­ti­sel­la sään­nöl­lä. Päät­te­ly­as­ke­leen pä­te­vyys mää­räy­tyy vain ja ai­noas­taan sii­tä, on­ko sil­le vas­ta­esi­merk­kiä.

Toi­saal­ta hy­vin usein on vai­kea sel­vit­tää, on­ko päät­te­ly­as­ke­leel­le vas­ta­esi­merk­kiä. Sik­si yleen­sä käy­tän­nös­sä vaa­di­taan, et­tä ku­kin päät­te­ly­as­kel pi­tää voi­da pe­rus­tel­la jol­la­kin ma­te­maat­ti­sel­la sään­nöl­lä, jos­ta tie­de­tään, et­tä se tuot­taa vain pä­te­viä päät­te­ly­as­ke­lia. Niin­pä ma­te­maat­ti­set sään­nöt ovat käy­tän­nös­sä vält­tä­mät­tö­miä päät­te­lyl­le, vaik­ka ne ei­vät poh­jim­mil­taan ole­kaan pä­te­vyy­den kri­tee­ri.

Jos al­la va­sen ⇐ oi­kea on pä­te­vä, niin va­lit­se va­sem­man­puo­lei­nen ruu­tu. Jos va­sen ⇔ oi­kea on pä­te­vä, niin va­lit­se kes­kim­mäi­nen ruu­tu. Jos va­sen ⇒ oi­kea on pä­te­vä, niin va­lit­se oi­kean­puo­lei­nen ruu­tu.

Vii­mei­sin edel­lä ol­leis­ta koh­dis­ta tuo esiin sen, et­tä päät­te­ly­ti­lan­teis­sa voi esiin­tyä mää­rit­te­le­mät­tö­miä väit­tei­tä. Päät­te­ly­as­kel ei kui­ten­kaan voi ol­la mää­rit­te­le­mä­tön. Jos teh­tä­vä­nä on sel­vit­tää, mit­kä lu­vut to­teut­ta­vat yh­tä­lön 3 √x + 2 = x + 4, niin ei ole epä­sel­vää ei­kä mää­rit­te­le­mä­tön­tä, to­teut­taa­ko x = −3 sen: ei to­teu­ta. Päät­te­ly­as­kel

3 √x + 2 = x + 4  ⇔  x = −1 ∨ x = 2

on pä­te­vä sii­tä huo­li­mat­ta, et­tä kun x = −3, niin sen va­sen puo­li on mää­rit­te­le­mä­tön. (Toi­si­naan esiin­ty­vä nä­ke­mys, et­tä ym. päät­te­ly­as­ke­lees­sa tar­kas­tel­laan vain nii­tä lu­ku­ja joil­la mo­lem­mat puo­let on mää­ri­tel­ty, kaa­tuu mm. sii­hen, et­tä teh­tä­vän­an­to ei tyy­pil­li­ses­ti ole muo­toa ”rat­kai­se tä­mä yh­tä­lö olet­taen, et­tä x ≥ −2” vaan ”rat­kai­se tä­mä yh­tä­lö”.)

Siis väi­te voi saa­da kol­me eri to­tuus­ar­voa: to­si, epä­to­si ja mää­rit­te­le­mä­tön, mut­ta päät­te­ly­as­ke­leel­la on vain kak­si mah­dol­li­suut­ta: se on tai ei ole pä­te­vä. Har­joit­te­lem­me tä­tä seu­raa­val­la esi­mer­kil­lä:

x > 0  ⇔ 

1

x

> 0

On­ko esi­mer­kin päät­te­ly­as­kel pä­te­vä? Vas­tausKun olet saa­nut tau­lu­kon täy­tet­tyä oi­kein, niin sii­nä ei ole yh­tään ri­viä, jos­sa toi­sel­la puo­lel­la on T mut­ta toi­sel­la puo­lel­la on F tai U. Toi­sin sa­noen, kai­kil­la niil­lä asia­yh­tey­den sal­li­mil­la muut­tu­jien ar­vo­yh­dis­tel­mil­lä, joil­la va­sen puo­li on to­si, myös oi­kea puo­li on to­si, ja päin­vas­toin. Se täs­mää sym­bo­lil­le ⇔ edel­lä an­net­tuun mää­ri­tel­mään. Esi­mer­kin päät­te­ly­as­kel on siis pä­te­vä.

Eh­kä huo­ma­sit Math­Checkin pa­laut­tees­sa sym­bo­lin ≡. Se ei kuu­lu tä­män teh­tä­vän op­pi­mis­ta­voit­tei­siin, mut­ta sil­tä va­ral­ta et­tä asia kiin­nos­taa: se on Math­Checkin oma päät­te­ly­ope­raat­to­ri, jol­le va­sen ≡ oi­kea on pä­te­vä jos ja vain jos jo­kai­sel­la asia­yh­tey­den sal­li­mal­la muut­tu­jien ar­vo­yh­dis­tel­mäl­lä va­sen ja oi­kea puo­li tuot­ta­vat sa­man to­tuus­ar­von. Niin­pä F ≡ U ei ole pä­te­vä, vaik­ka F ⇔ U on pä­te­vä. Sa­maa sym­bo­lia käy­te­tään ma­te­ma­tii­kas­sa mo­nes­sa muus­sa­kin mer­ki­tyk­ses­sä, mut­ta Math­Checkis­sä si­tä käy­te­tään näin.

Päät­te­ly­as­ke­lis­ta voi muo­dos­taa päät­te­ly­ket­ju­ja. Päät­te­ly­ket­ju va­sen ⇒ kes­kim­mäi­nen ⇒ oi­kea on pä­te­vä jos ja vain jos se­kä va­sen ⇒ kes­kim­mäi­nen on pä­te­vä et­tä kes­kim­mäi­nen ⇒ oi­kea on pä­te­vä.

On­ko seu­raa­va päät­te­ly­ket­ju pä­te­vä? Mik­si?

x = −2  ⇒  x ≤ 3  ⇒  x² ≤ 9

Vas­tausEi ole, kos­ka jäl­kim­mäi­nen päät­te­ly­as­kel ei ole pä­te­vä. Esi­mer­kik­si x = −4 on sil­le vas­ta­esi­merk­ki.

On­ko seu­raa­va päät­te­ly­ket­ju pä­te­vä? Mik­si?

x = −2  ⇒  x = 3 ∨ x = −2  ⇒  x² ≤ 9

Vas­tausOn pä­te­vä. En­sim­mäi­sen imp­li­kaa­tion va­sen puo­li on to­si ai­noas­taan sil­loin kun x = −2. Sil­loin oi­kea puo­li eli x = 3 ∨ x = −2 tuot­taa F ∨ T, jo­ka on T. Toi­sen imp­li­kaa­tion va­sen puo­li on to­si ai­noas­taan sil­loin kun x = −2 tai x = 3. Sil­loin x² = 4 tai x² = 9. Mo­lem­mis­sa ta­pauk­sis­sa x² ≤ 9, jo­ten oi­kea puo­li on to­si.

Seu­raa­va päät­te­ly­ket­ju on klas­sik­ko. Mi­kä sen päät­te­ly­as­ke­lis­ta ei ole pä­te­vä? Mik­si? Vih­jeVa­lit­se jot­kin hel­pot lu­vut a:ksi ja b:ksi, ja ko­kei­le väi­te ker­ral­laan on­ko se to­si.

Jos ole­te­taan a = b ≠ 0, niin  a = b  ⇒  a² = ab  ⇒  a² − b² = ab − b²  ⇒  (a + b)(a − b) = b(a − b)  ⇒  a + b = b  ⇒  2b = b  ⇒  2 = 1 .

Vas­taus(a + b)(a − b) = b(a − b)  ⇒  a + b = b  ei ole pä­te­vä, kos­ka jos esi­mer­kik­si a = b = 1, niin sen va­sen puo­li tuot­taa 0 = 0 jo­ka on to­si, mut­ta oi­kea puo­li tuot­taa 2 = 1 jo­ka on epä­to­si. Vir­he voi­daan tul­ki­ta kou­lu­ma­te­ma­tii­kan las­ku­sään­tö­jen kan­nal­ta seu­raa­vas­ti: päät­te­ly­as­ke­lees­sa mo­lem­mat puo­let jae­taan lu­vul­la a − b, jo­ka on 0 kos­ka a = b. Mut­ta nol­lal­la­han ei saa ja­kaa.

On­ko seu­raa­va päät­te­ly­ket­ju pä­te­vä? Mik­si?

√x = x − 2  ⇔  (√x)² = (x − 2)²  ⇔  x = x² − 4x + 4  ⇔  0 = (x − 4)x − (x − 4)  ⇔  (x − 4)(x − 1) = 0  ⇔  x = 4 ∨ x = 1

Vas­tausEi ole, kos­ka en­sim­mäi­nen päät­te­ly­as­kel ei ole pä­te­vä. Kun x = 1, niin sen va­sen puo­li on 1 = −1 jo­ka ei ole to­si, mut­ta oi­kea puo­li on 1 = 1 jo­ka on to­si.

On­ko seu­raa­va päät­te­ly­ket­ju pä­te­vä? Mik­si?

√x = x − 2  ⇒  (√x)² = (x − 2)²  ⇔  x = x² − 4x + 4  ⇔  0 = (x − 4)x − (x − 4)  ⇔  (x − 4)(x − 1) = 0  ⇔  x = 4 ∨ x = 1

Vas­tausOn pä­te­vä.

En­sim­mäi­nen as­kel on pä­te­vä sik­si, et­tä ai­na kun yh­tä­suu­ril­le olen­noil­le teh­dään sa­ma, mää­ri­tel­ty asia, niin myös lop­pu­tu­lok­set ovat yh­tä­suu­ret. Ne­liöön ko­rot­ta­mi­nen on ai­na mää­ri­tel­ty. Vas­tak­kai­sen suun­nan ei tar­vit­se pä­teä, kos­ka en­sim­mäi­nen as­kel käyt­tää ⇒ ei­kä ⇔.

Lop­pu pe­rus­tuu tut­tui­hin ja tur­val­li­siin kou­lu­ma­te­ma­tii­kan sään­töi­hin lu­kuun ot­ta­mat­ta si­tä, mi­tä ta­pah­tuu toi­ses­sa as­ke­lees­sa kun x < 0. Sil­loin toi­nen väi­te tuot­taa U ja kol­mas väi­te tuot­taa F, kos­ka sen va­sen puo­li on ne­ga­tii­vi­nen mut­ta, ku­ten koh­ta näh­dään, oi­kea puo­li ei ole: x² − 4x + 4 = (x − 2)² ≥ 0, kos­ka jo­kai­sen reaa­li­lu­vun ne­liö on vä­hin­tään 0.

Huo­maam­me, et­tä ei pel­käs­tään ⇔, vaan myös ⇒ on käyt­tö­kel­poi­nen yh­tä­löi­den rat­kai­se­mi­ses­sa. Sen käyt­tö voi tuot­taa yli­mää­räi­siä vas­taus­kan­di­daat­te­ja, mut­ta ne voi kar­sia ko­kei­le­mal­la kaik­ki saa­dut kan­di­daa­tit al­ku­pe­räi­ses­sä yh­tä­lös­sä.

On­ko seu­raa­va päät­te­ly­ket­ju pä­te­vä? Mik­si?

x + 1 + 2√x = 0  ⇔  x + 1 = −2√x  ⇒  (x + 1)² = (−2√x)²  ⇔  x² + 2x + 1 = 4x  ⇔  x² − 2x + 1 = 0  ⇔  (x − 1)² = 0  ⇔  x = 1

Vas­tausOn pä­te­vä. Toi­ses­sa as­ke­lees­sa mo­lem­mat puo­let ko­ro­te­taan ne­liöön, ja ne­liöin­ti on ai­na mää­ri­tel­ty. Vas­tak­kai­sen suun­nan ei tar­vit­se pä­teä, kos­ka toi­nen as­kel käyt­tää ⇒ ei­kä ⇔. Kol­man­nes­sa as­ke­lees­sa ne­ga­tii­vi­set lu­vut tuot­ta­vat va­sem­mal­la puo­len U ja oi­keal­la puo­len F, kos­ka niil­lä 4x < 0 mut­ta x² + 2x + 1 = (x + 1)² ≥ 0. Muu on tut­tua ja tur­val­lis­ta kou­lu­ma­te­ma­tiik­kaa.

Huo­maam­me, et­tä äs­kei­nen yh­tä­lö on mah­do­ton. Sen oli­si voi­nut huo­ma­ta myös si­ten, et­tä jot­ta se voi­si to­teu­tua, √x:n täy­tyy ol­la mää­ri­tel­ty. Sii­tä seu­raa x ≥ 0. Kos­ka ne­liö­juu­ret ovat ai­na ei-ne­ga­tii­vi­sia, sii­tä seu­raa et­tä x + 1 + 2√x ≥ 0 + 1 + 2 ⋅ 0 = 1 > 0.

Joh­dim­me siis äs­ken  mah­do­ton  ⇒  x = 1  käyt­täen vain pä­te­viä ma­te­ma­tii­kan sään­tö­jä, ja käyt­täen nii­tä oi­kein. Kui­ten­kin pe­rim­mäi­nen kri­tee­ri sil­le, on­ko päät­te­ly­as­kel epä­pä­te­vä, on on­ko sil­le vas­ta­esi­merk­kiä. On­ko täl­le päät­te­ly­as­ke­leel­le vas­ta­esi­merk­kiä? Jos ei, niin mik­si ei ole? Vas­tausVas­ta­esi­merk­ki imp­li­kaa­tiol­le on muut­tu­jien ar­vo­yh­dis­tel­mä, jol­la va­sen puo­li pä­tee mut­ta oi­kea puo­li ei pä­de. Täs­sä ta­pauk­ses­sa va­sen puo­li ei pä­de mil­lään muut­tu­jien ar­vo­yh­dis­tel­mäl­lä, jo­ten vas­ta­esi­merk­ke­jä ei ole.

It­se asias­sa jo­kai­nen ⇒-päät­te­ly­as­kel, jon­ka va­sen puo­li on mah­do­ton, on pä­te­vä. Oi­kea puo­li saa ol­la ihan mi­tä ta­han­sa. Mil­le­kään niis­tä ei ole vas­ta­esi­merk­kiä, kos­ka min­kään niis­tä va­sen puo­li ei to­teu­du mil­loin­kaan. Näin täy­tyy ol­la mo­nes­ta syys­tä, muun muas­sa sik­si, et­tä päät­te­lyä aloi­tet­taes­sa ei vält­tä­mät­tä tie­de­tä on­ko läh­tö­koh­ta mah­do­ton, mut­ta sil­ti täy­tyy voi­da pää­tel­lä. Ti­lan­ne oli juu­ri tä­mä yh­tä­lön x + 1 + 2√x = 0 ta­pauk­ses­sa (pait­si jos näit jo alus­sa, et­tä se on mah­do­ton yh­tä­lö).

Ih­mis­ten in­tui­tio on toi­si­naan vää­räs­sä. Ma­te­maat­tis­ten päät­te­ly­jen ta­pauk­ses­sa, jos jo­kin asia epäi­lyt­tää, kan­nat­taa miet­tiä mil­tä se näyt­tää vas­ta­esi­merk­kien nä­kö­kul­mas­ta. Jos päät­te­lyl­le on vas­ta­esi­merk­ki, niin se on epä­pä­te­vä. Jos on var­maa et­tä vas­ta­esi­merk­ke­jä ei ole, niin päät­te­ly on pä­te­vä vaik­ka se tun­tui­si kuin­ka hul­lul­ta.

Jää­kie­kon maail­man­mes­ta­ruus­ki­sois­sa oli 4.6.2021 jäl­jel­lä nel­jä jouk­kuet­ta. Myös ot­te­lui­ta oli jäl­jel­lä nel­jä: 5.6. Yh­dys­val­lat–Ka­na­da ja Suo­mi–Sak­sa se­kä 6.6. prons­si­ot­te­lu ja lop­pu­ot­te­lu. Jo­kai­ses­sa ot­te­lus­sa on voit­ta­ja ja hä­viä­jä (ta­sa­pe­le­jä ei ole). Lop­pu­ot­te­lus­sa pe­laa­vat 5.6. ot­te­lu­jen voit­ta­jat. Lop­pu­ot­te­lun voit­ta­ja saa kul­ta­mi­ta­lin ja hä­viä­jä ho­pea­mi­ta­lin. Prons­si­ot­te­lus­sa pe­laa­vat 5.6. ot­te­lu­jen hä­viä­jät. Prons­si­ot­te­lun voit­ta­ja saa prons­si­mi­ta­lin ja hä­viä­jä ei saa mi­tään mi­ta­lia. Olem­me var­maan kaik­ki sa­maa miel­tä, et­tä ti­lan­ne oli sel­lai­nen, et­tä jos Suo­mi voit­taa vie­lä yh­den­kin ot­te­lun, niin Suo­mi saa mi­ta­lin.

Mut­ta ot­ta­kaam­me tar­kas­tel­ta­vak­si ti­lan­ne 6.6. klo 20. Sil­loin prons­si­ot­te­lu oli pe­lat­tu, mut­ta lop­pu­ot­te­lua ei vie­lä. Prons­si­ot­te­lun voit­ti Yh­dys­val­lat ja hä­vi­si Sak­sa. Pä­ti­kö sil­lä het­kel­lä, et­tä jos Suo­mi voit­taa vie­lä yh­den­kin ot­te­lun, niin Suo­mi saa mi­ta­lin? Vas­tausKyl­lä pä­ti. Suo­mel­la oli jäl­jel­lä enää yk­si ot­te­lu eli lop­pu­ot­te­lu. Jos Suo­mi oli­si voit­ta­nut sen niin Suo­mi oli­si saa­nut kul­taa. (Suo­mi hä­vi­si sen ja sai ho­peaa.)

Pä­ti­kö sil­lä het­kel­lä, et­tä jos Sak­sa voit­taa vie­lä yh­den­kin ot­te­lun, niin Sak­sa saa mi­ta­lin? Mie­ti tark­kaan! Älä an­na vais­to­si joh­dat­taa si­nua har­haan! Vas­tausKyl­lä pä­ti. Vas­ta­esi­merk­ki väit­teel­le oli­si tuol­la het­kel­lä mah­dol­li­nen tu­le­vai­suus, jos­sa Sak­sa voit­taa vie­lä jon­kin ot­te­lun mut­ta jää sil­ti il­man mi­ta­lia. Sak­sa ei kui­ten­kaan enää voi­nut voit­taa yh­tään ot­te­lua, kos­ka sil­lä ei ol­lut jäl­jel­lä enää yh­tään ot­te­lua. Niin­pä vas­ta­esi­merk­ke­jä ei voi­nut ol­la, jo­ten väi­te pä­ti.

”Sak­sa voit­taa vie­lä jon­kin ot­te­lun” oli tuo­na het­ke­nä mah­do­ton, ja mah­dot­to­mas­ta seu­raa mi­tä ta­han­sa. ”Mi­tä ta­han­sa” voi ol­la vaik­ka ”1 + 1 = 3”, ja se voi ol­la ”Sak­sa saa mi­ta­lin”. Tuo­na het­ke­nä pä­ti siis se­kä ”jos Sak­sa voit­taa vie­lä yh­den­kin ot­te­lun, niin 1 + 1 = 3” et­tä ”jos Sak­sa voit­taa vie­lä yh­den­kin ot­te­lun, niin Sak­sa saa mi­ta­lin”.

Erääs­sä teh­tä­väs­sä opis­ke­li­joi­ta pyy­det­tiin kir­joit­ta­maan kaa­va, jo­ka esit­tää ohei­sen ku­van sa­vu­piip­pua. Jo­kai­nen sel­lai­nen sa­vu­piip­pu kel­paa, jo­ta ra­joit­taa nel­jä suo­raa vii­vaa, ja jo­ka yl­tää al­haal­la niin pit­käl­le et­tä sen ja ka­ton vä­liin ei jää pie­nin­tä­kään ra­koa, mut­ta ei niin pit­käl­le et­tä sen ala­reu­na al­kaa nä­kyä ik­ku­nas­ta. Kaik­ki reu­na­vii­vat ovat mu­ka­na vih­reäs­sä aluees­sa.

Nyt si­nua ei pyy­de­tä kir­joit­ta­maan sa­vu­pii­pun kaa­vaa, vaan kaa­vat, joi­den avul­la voi tar­kas­taa, on­ko an­net­tu sa­vu­pii­pun kaa­va oi­kein. Kir­joi­ta sel­lai­set kaa­vat va­sen ja oi­kea, et­tä sa­vu­piip­pu on oi­kea vas­taus jos ja vain jos va­sen ⇒ sa­vu­piip­pu ⇒ oi­kea. Vih­je 1Mi­kä on mah­dol­li­sim­man suu­ri sel­lai­nen alue ai­na­kin, et­tä lail­li­sen sa­vu­pii­pun pi­tää peit­tää ai­na­kin se? Vih­je 2Mi­ten sym­bo­lin ⇒ ja kaa­vo­jen sa­vu­piip­pu ja ai­na­kin avul­la il­mais­taan, et­tä sa­vu­pii­pun pi­tää peit­tää ai­na­kin kaa­van ai­na­kin il­mai­se­ma alue? Vihje 3Mi­kä on mah­dol­li­sim­man pie­ni sel­lai­nen alue enin­tään, et­tä lail­li­nen sa­vu­piip­pu ei saa peit­tää yh­tään enem­pää? Mi­ten sym­bo­lin ⇒ ja kaa­vo­jen sa­vu­piip­pu ja enin­tään avul­la il­mais­taan, et­tä sa­vu­piip­pu ei saa peit­tää lii­kaa? Vih­je 4Lail­li­nen sa­vu­piip­pu peit­tää ai­na­kin ku­vas­sa nä­ky­vän tum­man­vih­reän alueen ja enin­tään tum­man- ja vaa­lean­vih­reät alueet. Ku­vaan on pu­nai­sel­la piir­ret­ty erään lail­li­sen sa­vu­pii­pun reu­na.

Päät­te­ly­esi­merk­ki: al­go­rit­mi pa­rin sum­mal­le

Ma­te­ma­tii­kas­sa ja tie­to­jen­kä­sit­te­ly­tie­tees­sä jou­du­taan usein pe­rus­te­le­maan, et­tä jo­kin väi­te pä­tee jos ja vain jos jo­kin toi­nen väi­te pä­tee. Jos mer­kit­sem­me näi­tä väit­tei­tä va­sen ja oi­kea, niin on pe­rus­tel­ta­va, et­tä va­sen ⇔ oi­kea. Toi­si­naan täl­lai­sen päät­te­lyn voi vie­dä lä­pi pel­käs­tään ⇔-as­ke­lil­la. Usein kui­ten­kin jou­du­taan päät­te­le­mään erik­seen va­sen ⇒ oi­kea ja erik­seen oi­kea ⇒ va­sen. Käym­me nyt lä­pi esi­mer­kin täs­tä.

Esi­mer­kis­sä tar­kas­tel­laan vä­hä­töis­tä kei­noa sel­vit­tää, on­ko an­ne­tuis­sa lu­vuis­sa kak­si, joi­den sum­ma on 100. Sa­nom­me täl­lai­sia lu­ku­ja sa­ta­pa­rik­si. Esi­mer­kik­si 36 ja 64 on lu­ku­jen 80 36 50 64 12 sa­ta­pa­ri, mut­ta 36 ja 50 ei ole, kos­ka 36 + 50 ≠ 100, ja 20 ja 80 ei ole, kos­ka 20 ei ole niis­sä lu­vuis­sa mu­ka­na. Sa­ma lu­ku saa ol­la sa­ta­pa­rin mo­lem­pi lu­ku jos ja vain jos se esiin­tyy syöt­tees­sä ai­na­kin kah­des­ti. Sik­si 50 ja 50 ei ole lu­ku­jen 80 36 50 64 12 sa­ta­pa­ri, mut­ta on lu­ku­jen 50 36 50 64 12 sa­ta­pa­ri.

Ko­kei­le het­ken ai­kaa, löy­dät­kö näis­tä lu­vuis­ta sa­ta­pa­rin, mut­ta jos et löy­dä, niin älä jat­ka kauaa:

75 82 96 45 66 85 87 43 75 60 80 78 81 54 82 87 53 28 52 47 42 87 82 42 26

Ko­kei­le het­ken ai­kaa, löy­dät­kö näis­tä lu­vuis­ta sa­ta­pa­rin, mut­ta jos et löy­dä, niin älä jat­ka kauaa:

67 31 12 53 72 90 42 31 70 97 18 91 45 99 42 74 62 99 86 35 98 91 40 68 29

Ole­te­taan, et­tä lu­ku­jo­nos­sa ei ole sa­ta­pa­ria. Jos teh­tä­vä rat­kais­taan ko­kei­le­mal­la kaik­ki pa­rit, jot­ka lu­ku­jo­non lu­vuis­ta voi muo­dos­taa, niin kuin­ka mon­ta pa­ria pi­tää ko­keil­la, jos lu­ku­ja on ri­vin alus­sa il­moi­tet­tu mää­rä? Sa­maa pa­ria (esim. 75 ja 82) ei ko­keil­la mo­lem­piin suun­tiin (siis las­ke­taan jo­ko 75 + 82 tai 82 + 75, mut­ta ei mo­lem­pia). Vih­je: jos et kek­si yleis­tä lau­se­ket­ta, tee muu­ta­ma en­sim­mäi­nen koh­ta täs­tä teh­tä­väs­tä.

Teh­tä­vän voi rat­kais­ta pal­jon vä­hem­mäl­lä työl­lä seu­raa­vas­ti. Kut­sum­me tä­tä ta­paa päis­tä kes­kel­le -al­go­rit­mik­si. En­sin lu­vut jär­jes­te­tään kas­va­vaan suu­ruus­jär­jes­tyk­seen (se on­nis­tuu pal­jon vä­hem­mäl­lä työl­lä kuin kaik­kien pa­rien ko­kei­lu):

26 28 42 42 43 45 47 52 53 54 60 66 75 75 78 80 81 82 82 82 85 87 87 87 96

12 18 29 31 31 35 40 42 42 45 53 62 67 68 70 72 74 86 90 91 91 97 98 99 99

Sit­ten toi­mi­taan seu­raa­vas­ti:

1. Lai­ta va­sen etu­sor­mi en­sim­mäi­sen ja oi­kea etu­sor­mi vii­mei­sen lu­vun koh­dal­le.
2. Jos etu­sor­met ovat sa­mas­sa koh­das­sa, niin lo­pe­ta. Sa­ta­pa­ria ei ole ole­mas­sa. Muu­toin jat­ka koh­taan 3.
3. Las­ke etu­sor­mien osoit­ta­mien lu­ku­jen sum­ma.

   3.1 Jos se on pie­nem­pi kuin 100, niin siir­rä va­sen­ta etu­sor­mea yh­den lu­vun ver­ran oi­keal­le ja pa­laa koh­taan 2.

   3.2 Jos se on suu­rem­pi kuin 100, niin siir­rä oi­keaa etu­sor­mea yh­den lu­vun ver­ran va­sem­mal­le ja pa­laa koh­taan 2.

   3.3 Jos se on ta­san 100, niin lo­pe­ta. Sa­ta­pa­ri on löy­ty­nyt.

Yl­lä ole­va al­go­rit­mi avau­tuu toi­seen vä­li­leh­teen tai ik­ku­naan täs­tä.

Ole­te­taan, et­tä lu­ku­jo­nos­sa ei ole sa­ta­pa­ria. Jos teh­tä­vä rat­kais­taan päis­tä kes­kel­le -al­go­rit­mil­la, niin kuin­ka mon­ta pa­ria pi­tää ko­keil­la, jos lu­ku­ja on ri­vin alus­sa il­moi­tet­tu mää­rä?

Seu­raa­vak­si pe­rus­te­lem­me, et­tä päis­tä kes­kel­le -al­go­rit­mi tuot­taa oi­kean vas­tauk­sen. On to­dis­tet­ta­va seu­raa­va:

Lu­ku­jo­nos­sa on sa­ta­pa­ri  ⇔  päis­tä kes­kel­le -al­go­rit­mi löy­tää sa­ta­pa­rin

Suun­ta oi­kea ⇒ va­sen on täl­lä ker­taa jo läh­tö­koh­tai­ses­ti sel­vä: jos al­go­rit­mi on löy­tä­nyt lu­ku­jo­nos­ta sa­ta­pa­rin, niin tot­ta kai lu­ku­jo­nos­sa on ai­na­kin se sa­ta­pa­ri, jon­ka al­go­rit­mi löy­si. Ma­te­maa­ti­kot sa­no­vat läh­tö­koh­tai­ses­ti sel­viä ta­pauk­sia tri­viaa­leik­si.

Suun­ta va­sen ⇒ oi­kea vaa­tii enem­män työ­tä. Kut­sum­me seu­raa­vaa väi­tet­tä ni­mel­lä in­va­riant­ti. Osoi­tam­me, et­tä se on to­si päis­tä kes­kel­le -al­go­rit­min koh­dan 1 jäl­keen, al­go­rit­min lop­puun saak­ka:

Mi­kään lu­ku va­sem­man etu­sor­men va­sem­mal­la puo­lel­la ei ole sa­ta­pa­rin osa­puo­li. Mi­kään lu­ku oi­kean etu­sor­men oi­keal­la puo­lel­la ei ole sa­ta­pa­rin osa­puo­li.

Mik­si se on to­si kun koh­ta 1 on suo­ri­tet­tu mut­ta koh­taa 2 ei ole vie­lä aloi­tet­tu? Vas­tausKoh­dan 1 jäl­jil­tä va­sen etu­sor­mi on en­sim­mäi­sen lu­vun koh­dal­la, jo­ten sen va­sem­mal­la puo­lel­la ei ole lu­ku­ja. Sik­si mi­kään lu­ku va­sem­man etu­sor­men va­sem­mal­la puo­lel­la ei ole sa­ta­pa­rin osa­puo­li. Vas­taa­vas­ti oi­kea etu­sor­mi on oi­kean­puo­lim­mai­sim­man lu­vun koh­dal­la. Sen oi­keal­la puo­lel­la ei ole mi­tään lu­ku­ja, ei­kä niin ol­len myös­kään sa­ta­pa­rin osa­puo­le­na ole­via lu­ku­ja. Asiaa voi aja­tel­la myös vas­ta­esi­merk­kien kaut­ta näinJos väi­te ei pä­de, niin sil­le on ole­mas­sa vas­ta­esi­merk­ki. Vas­ta­esi­mer­kik­si in­va­rian­til­lem­me kel­paa vain sa­ta­pa­rin osa­puo­li, jo­ka on va­sem­man etu­sor­men va­sem­mal­la puo­lel­la tai oi­kean etu­sor­men oi­keal­la puo­lel­la. Mut­ta niis­sä pai­kois­sa ei vie­lä ole lu­ku­ja lain­kaan. Sik­si vas­ta­esi­merk­ke­jä ei ole, eli in­va­riant­ti pä­tee..

Seu­raa­vak­si on osoi­tet­ta­va, et­tä mi­kään, mi­kä teh­dään koh­das­sa 2 tai 3, ei voi saat­taa in­va­riant­tia pois voi­mas­ta. Koh­dat 2 ja 3 ei­vät muu­ta lu­ku­ja ei­vät­kä nii­den si­jain­te­ja. Mi­kä on ai­noa in­va­rian­tin kan­nal­ta olen­nai­nen asia, mi­tä koh­dat 2 ja 3 muut­ta­vat? Vas­tausEtu­sor­mien si­jain­nit.

Sik­si tut­kim­me jo­kai­sen toi­men­pi­teen koh­dis­sa 2 ja 3, jo­ka muut­taa etu­sor­men paik­kaa. Voim­me kes­kit­tyä sii­hen kun in­va­riant­ti en­sim­mäi­sen ker­ran lak­kaa ole­mas­ta voi­mas­sa, sil­lä jos on­nis­tum­me osoit­ta­maan et­tä en­sim­mäis­tä ker­taa ei ole, niin ei voi ol­la tois­ta ei­kä kol­mat­ta­kaan ker­taa. En­nen kuin in­va­riant­ti rik­kou­tuu en­sim­mäi­sen ker­ran, se on voi­mas­sa. Sik­si voim­me olet­taa, et­tä in­va­riant­ti oli voi­mas­sa juu­ri en­nen toi­men­pi­det­tä. Teh­tä­väm­me on osoit­taa, et­tä se on voi­mas­sa myös vä­lit­tö­mäs­ti toi­men­pi­teen jäl­keen.

Kun va­sen­ta etu­sor­mea siir­re­tään, niin sen va­sem­mal­le puo­lel­le jää lu­ku v, jo­ka ei ai­kai­sem­min ol­lut sen va­sem­mal­la puo­lel­la. Mei­dän on osoi­tet­ta­va, et­tä v ei voi ol­la sa­ta­pa­rin osa­puo­li. Jaam­me tä­män päät­te­lyn kol­meen ta­pauk­seen.

• Mik­si v ei voi muo­dos­taa sa­ta­pa­ria oi­kean etu­sor­men koh­dal­la ole­van lu­vun o kans­sa? Vas­tausVa­sen­ta etu­sor­mea siir­re­tään koh­das­sa 3.1 (ei­kä mis­sään muual­la). Juu­ri en­nen siir­toa va­sen etu­sor­mi oli v:n koh­dal­la. Sil­loin to­det­tiin, et­tä sen ja oi­kean etu­sor­men koh­dal­la ole­vien lu­ku­jen sum­ma on al­le 100. Siis v + o < 100, jo­ten ei voi pä­teä v + o = 100.
• Mik­si v ei voi muo­dos­taa sa­ta­pa­ria min­kään oi­keas­ta etu­sor­mes­ta va­sem­mal­le ole­van lu­vun kans­sa? Vas­tausOl­koon x mi­kä ta­han­sa lu­ku oi­keas­ta etu­sor­mes­ta va­sem­mal­le. Kos­ka lu­vut ovat kas­va­vas­sa suu­ruus­jär­jes­tyk­ses­sä, x ≤ o. Sik­si v + x ≤ v + o. Edel­lä näh­tiin et­tä v + o < 100, jo­ten v + x < 100.
• Mik­si v ei voi muo­dos­taa sa­ta­pa­ria min­kään oi­keas­ta etu­sor­mes­ta oi­keal­le ole­van lu­vun kans­sa? Vas­tausEdel­lä pe­rus­tel­tiin, et­tä voim­me olet­taa, et­tä in­va­riant­ti oli voi­mas­sa juu­ri en­nen va­sem­man etu­sor­men siir­tä­mis­tä. In­va­rian­tin mu­kaan mi­kään oi­keas­ta etu­sor­mes­ta oi­keal­le ole­vis­ta lu­vuis­ta ei voi muo­dos­taa sa­ta­pa­ria min­kään lu­vun kans­sa. Niin­pä v ei voi muo­dos­taa sa­ta­pa­ria min­kään niis­tä kans­sa.

Nyt kaik­ki lu­vut on tut­kit­tu ja to­det­tu, et­tä v ei voi muo­dos­taa sa­ta­pa­ria min­kään niis­tä kans­sa.

Myös on osoi­tet­ta­va, et­tä kun oi­keaa etu­sor­mea siir­re­tään, niin sen koh­dal­la juu­ri en­nen siir­toa ol­lut lu­ku o ei voi ol­la min­kään sa­ta­pa­rin osa­puo­li. Ma­te­maa­tik­ko saat­tai­si tyy­tyä to­tea­maan, et­tä ti­lan­ne on sym­met­ri­nen, jo­ten sa­man­lai­nen päät­te­ly toi­mii kuin va­sem­man etu­sor­men ta­pauk­ses­sa.

On kui­ten­kin hy­vää har­joi­tus­ta teh­dä päät­te­ly uu­del­leen so­vel­let­tu­na oi­keaan etu­sor­meen. Tee se! Kiin­ni­tä eri­tyis­tä huo­mio­ta nii­hin koh­tiin, jot­ka ovat eri­lai­set kuin äs­ken. Voit tii­vis­tää vas­taus­ta ver­rat­tu­na va­sem­man etu­sor­men päät­te­lyyn, kun­han säi­ly­tät olen­nai­set syyt, mik­si in­va­riant­ti säi­lyy voi­mas­sa. Osa 1Lu­ku o ei voi muo­dos­taa sa­ta­pa­ria va­sem­man etu­sor­men koh­dal­la ole­van lu­vun v kans­sa, kos­ka juu­ri en­nen siir­toa to­det­tiin, et­tä v + o > 100, jo­ten v + o ≠ 100. Osa 2Lu­ku o ei voi muo­dos­taa sa­ta­pa­ria min­kään va­sem­mas­ta etu­sor­mes­ta oi­keal­le ole­van lu­vun x kans­sa, kos­ka lu­vut ovat kas­va­vas­sa suu­ruus­jär­jes­tyk­ses­sä, jo­ten x ≥ v ja sik­si x + o ≥ v + o > 100, jo­ten x + o ≠ 100. Osa 3Lu­ku o ei voi muo­dos­taa sa­ta­pa­ria min­kään va­sem­mas­ta etu­sor­mes­ta va­sem­mal­le ole­van lu­vun kans­sa, kos­ka in­va­riant­ti oli voi­mas­sa juu­ri en­nen oi­kean etu­sor­men siir­tä­mis­tä, ja in­va­rian­tin mu­kaan mi­kään va­sem­mas­ta etu­sor­mes­ta va­sem­mal­le ole­vis­ta lu­vuis­ta ei voi muo­dos­taa sa­ta­pa­ria min­kään lu­vun kans­sa. Osa 4Nyt kaik­ki lu­vut on tut­kit­tu ja to­det­tu, et­tä o ei voi muo­dos­taa sa­ta­pa­ria min­kään niis­tä kans­sa.

Olem­me osoit­ta­neet, et­tä mi­kään etu­sor­men siir­to ei voi saa­da in­va­riant­tia pois voi­mas­ta. To­te­sim­me jo aiem­min, et­tä mi­kään muu­kaan, mi­tä al­go­rit­mi te­kee, ei voi saa­da in­va­riant­tia pois voi­mas­ta. Sik­si in­va­riant­ti on voi­mas­sa al­go­rit­min lo­pus­sa.

Voim­me nyt vii­meis­tel­lä suun­nan va­sen ⇒ oi­kea to­dis­tuk­sen. Pa­lau­ta mie­lee­si, mi­tä kai­ken kaik­kiaan olem­me to­dis­ta­mas­sa, lait­ta­mal­la sym­bo­lien va­sen ja oi­kea pai­kal­le oi­keat väit­teet. Vas­tausLu­ku­jo­nos­sa on sa­ta­pa­ri  ⇒  päis­tä kes­kel­le -al­go­rit­mi löy­tää sa­ta­pa­rin.

Mis­sä koh­dis­sa al­go­rit­mi voi lo­pet­taa? Vas­tausKoh­das­sa 2 ”Jos etu­sor­met ovat sa­mas­sa koh­das­sa” se­kä koh­das­sa 3.3 ”Jos se on ta­san 100”.

Mik­si päät­te­ly­as­kel pä­tee en­sim­mäi­ses­sä lo­pe­tus­koh­das­sa? Vas­tausKun etu­sor­met ovat sa­mas­sa koh­das­sa, niin yh­tä vail­le kaik­ki lu­vut ovat va­sem­man etu­sor­men va­sem­mal­la puo­lel­la tai oi­kean etu­sor­men oi­keal­la puo­lel­la. In­va­rian­tin mu­kaan ne ei­vät voi ol­la sa­ta­pa­rin osa­puo­lia. Sik­si on vain yk­si lu­ku, jo­ka voi ol­la sa­ta­pa­rin osa­puo­li (ni­mit­täin etu­sor­mien koh­dal­la ole­va lu­ku). Sa­ta­pa­riin tar­vi­taan kui­ten­kin kak­si lu­kua, jo­ten sa­ta­pa­re­ja ei ole.

Sym­bo­lin ⇒ va­sen puo­li ei siis pä­de (lu­ku­jo­nos­sa ei siis ole sa­ta­pa­ria), jo­ten oi­kean­kaan puo­len ei tar­vit­se pä­teä (al­go­rit­min ei tar­vit­se löy­tää sa­ta­pa­ria). Vas­ta­esi­merk­kien avul­la il­mais­tu­na: ei ole ole­mas­sa ti­lan­net­ta jos­sa va­sen puo­li pä­tee, jo­ten ei voi ol­la ole­mas­sa ti­lan­net­ta jos­sa va­sen puo­li pä­tee ja oi­kea puo­li ei pä­de.

Mik­si päät­te­ly­as­kel pä­tee jäl­kim­mäi­ses­sä lo­pe­tus­koh­das­sa? Vas­tausAl­go­rit­mi on löy­tä­nyt sa­ta­pa­rin, jo­ten sym­bo­lin ⇒ oi­kea puo­li pä­tee. Kun imp­li­kaa­tion oi­kea puo­li pä­tee, ei ole vä­liä pä­tee­kö va­sen puo­li. Vas­ta­esi­merk­kien avul­la il­mais­tu­na: ei ole ole­mas­sa ti­lan­net­ta jos­sa oi­kea puo­li ei pä­de, jo­ten ei voi ol­la ole­mas­sa ti­lan­net­ta jos­sa va­sen puo­li pä­tee ja oi­kea puo­li ei pä­de.

Olem­me nyt saa­neet val­miik­si suun­nan va­sen ⇒ oi­kea to­dis­tuk­sen. Kos­ka vas­tak­kai­nen suun­ta ⇐ to­dis­tet­tiin jo ai­kai­sem­min, on ko­ko to­dis­tus va­sen ⇔ oi­kea val­mis.

Täs­sä ta­pauk­ses­sa toi­nen suun­ta oli pal­jon hel­pom­pi kuin toi­nen suun­ta, ja eri suun­tien to­dis­ta­mi­ses­sa käy­tet­tiin ai­van eri­lai­sia päät­te­lyi­tä. Se on var­sin ta­val­lis­ta ma­te­ma­tii­kas­sa ja tie­to­jen­kä­sit­te­ly­tie­tees­sä.

Olem­me teh­neet pal­jon työ­tä ym­mär­tääk­sem­me, mis­tä ma­te­maat­ti­ses­sa päät­te­lys­sä on ky­se, ja hie­man myös mi­ten si­tä voi käyt­tää oh­jel­moin­nin apu­na. Ei­kö­hän nyt ole hy­vin an­sai­tun tauon paik­ka! Lo­puk­si vie­lä muu­ta­ma vas­ta­esi­merk­ki:

Ku­van läh­de: kal­ler­na, CC BY-SA 3.0, via Wi­ki­me­dia Com­mons