Teh­tä­vä:
Tau­luk­ko­väit­tei­tä, osa 1

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

Ky­ky muo­dos­taa täs­mäl­li­siä väit­tä­miä vaik­ka yk­si­tyis­koh­dat te­ke­vät kiu­saa on tär­keä se­kä oh­jel­moin­nis­sa et­tä asiak­kai­den vaa­ti­mus­ten ke­rää­mi­ses­sä. Kiu­saa te­ke­vät yk­si­tyis­koh­dat ovat usein juu­ri nii­tä, jot­ka ai­heut­ta­vat kal­lii­ta vir­hei­tä ja muu­tos­tar­pei­ta, jos nii­tä ei huo­ma­ta ajois­sa. Yk­si­tyis­koh­tien saa­mis­ta oi­kein voi har­joi­tel­la muo­dos­ta­mal­la tau­lu­koi­ta kos­ke­via väit­tä­miä pre­di­kaa­teil­la.

Täs­sä teh­tä­väs­sä kaik­ki väit­tä­mät kos­ke­vat tau­luk­koa ni­mel­tä A, jon­ka in­dek­se­jä ovat 1, …, n. ”Jo­kai­nen tau­lu­kon al­kio on 2” voi­daan il­mais­ta

∀ i; 1 ≤ i ≤ n: A[i] = 2 .

Math­Checkil­le sen voi kir­joit­taa ihan sa­mal­la ta­val­la, mut­ta kos­ka merk­ke­jä ∀ ja ≤ on han­ka­la syöt­tää näp­päi­mis­töl­tä, Math­Check huo­lii myös seu­raa­van:

AA i; 1 <= i <= n: A[i] = 2 .

Ole­mas­sa­olo­kvant­to­ri ∃ voi­daan kir­joit­taa Math­Checkil­le sel­lai­se­naan tai EE.

Kir­joi­ta seu­raa­vat väit­tä­mät.

Jo­kai­nen tau­lu­kon al­kio on vä­hem­män kuin 2.

tai

Ei ole niin, et­tä jo­kai­nen tau­lu­kon al­kio on vä­hem­män kuin 2.

tai

Jo­kin tau­lu­kon al­kio on vä­hin­tään 2. (So­vel­la edel­li­seen vas­tauk­seen de Mor­ga­nin kaa­vaa.)

tai

Väit­tä­mäs­sä voi esiin­tyä jo­kin muut­tu­ja va­paa­na. Sil­loin väit­tä­män to­tuus­ar­vo yleen­sä, mut­ta ei ai­na, riip­puu va­paan muut­tu­jan ar­vos­ta. ”Jo­kin tau­lu­kon al­kio on x” voi­daan il­mais­ta kaa­val­la ∃ i; 1 ≤ i ≤ n: A[i] = x. Sii­nä va­paa­na esiin­ty­vät x ja A. Jat­ka väit­tä­mien il­mai­se­mis­ta kaa­voi­na.

Jo­kin tau­lu­kon al­kio on enem­män kuin z2.

tai

Usein va­paa­ta muut­tu­jaa käy­te­tään va­lit­se­maan jo­kin paik­ka tau­lu­kos­ta. Sil­loin se täy­tyy ra­joit­taa lail­li­sel­le alueel­le, kos­ka muu­toin väit­tä­mä pu­hui­si myös ole­mat­to­mien al­kioi­den ar­vois­ta, mi­kä tyy­pil­li­ses­ti joh­taa mää­rit­te­le­mät­tö­mään to­tuus­ar­voon joil­la­kin tau­lu­kon si­säl­löil­lä. Ra­joi­te ei ai­na ole 1 ≤ i ≤ n, kos­ka jos kaa­vas­sa pu­hu­taan myös esim. edel­li­ses­tä (eli koh­das­sa i − 1 ole­vas­ta) al­kios­ta, niin sen­kin täy­tyy ol­la lail­li­sel­la alueel­la. ”Koh­das­sa i ole­va al­kio on x” voi­daan il­mais­ta kaa­val­la 1 ≤ i ≤ n ∧ A[i] = x. Täs­sä kaa­vas­sa ei tar­vit­tu kvant­to­rei­ta lain­kaan!

Koh­das­sa i ole­va al­kio on vä­hin­tään 2.

tai

Koh­das­sa i ole­va al­kio on yh­tä­suu­ri kuin seu­raa­va (siis koh­das­sa i + 1 ole­va) al­kio.

tai

Koh­das­sa i ole­va al­kio on vä­hin­tään yh­tä­suu­ri kuin en­sim­mäi­nen al­kio.

tai

Koh­das­sa i ole­va al­kio on vä­hin­tään yh­tä­suu­ri kuin toi­sek­si vii­mei­nen al­kio.

tai

Koh­das­sa i ole­va al­kio on x, mut­ta edel­li­nen al­kio ei ole x.

tai

Seu­raa­vas­sa tar­vi­taan se­kä va­paa i:n esiin­ty­mä et­tä kvant­to­ri. Kvant­to­rin luo­ma­na muut­tu­ja­na ei voi käyt­tää i:tä, kos­ka sil­lä on jo toi­nen teh­tä­vä. Pi­tää siis va­li­ta jo­kin toi­nen muut­tu­ja. Mi­kä ta­han­sa muut­tu­ja kel­paa, jol­la ei jo ole muu­ta teh­tä­vää.

Koh­das­sa i ole­va al­kio on suu­rem­pi kuin jo­kin al­kio.

tai

Seu­raa­va esi­merk­ki ha­vain­nol­lis­taa eräs­tä kaik­ki­kvant­to­riin liit­ty­vää il­miö­tä. Pai­na nap­pia ja yri­tä ym­mär­tää, mik­si Math­Check an­taa sel­lai­sen pa­laut­teen kuin an­taa. Sit­ten kat­so se­li­tys täs­täJos n = 0, niin ylem­pi ri­vi on muo­toa F ∧ … ja si­ten tuot­taa F, mut­ta alem­pi ri­vi on muo­toa ∀ i; 1 ≤ i ≤ 0: … eli ∀ i; F: … ja si­ten tuot­taa T. Se tuot­taa T, kos­ka sil­le ei ole vas­ta­esi­merk­kiä eli sel­lais­ta i, jol­le pä­te­vät se­kä 1 ≤ i ≤ 0 et­tä …, kos­ka mil­le­kään i ei pä­de 1 ≤ i ≤ 0. Kaik­ki väit­tä­mät muo­toa ”kai­kil­la x, jot­ka kuu­lu­vat tyh­jään jouk­koon, pä­tee …” ovat tot­ta. Vaa­ti­mus n ≥ 1 ei siis to­si­asias­sa ole mu­ka­na alem­mal­la ri­vil­lä, vaik­ka se näyt­tää­kin ole­van mu­ka­na, jos ri­vin lu­kee huo­li­mat­to­mas­ti..

tai

Kor­jaa al­la ole­va yri­tys sa­noa ”koh­das­sa i ole­va al­kio on vä­hin­tään yh­tä suu­ri kuin mi­kään tau­lu­kon al­kio”.

tai

Väit­tä­mä ”Koh­das­sa i ole­va al­kio on suu­rem­pi kuin mi­kään al­kio” ei kos­kaan pä­de. Jos i ei osu lail­li­sel­le alueel­le, niin väit­tä­mä on mää­rit­te­le­mä­tön tai epä­to­si riip­puen sii­tä, on­ko i ra­jat­tu väit­tä­mäs­sä lail­li­sel­le alueel­le. Jos i osuu lail­li­sel­le alueel­le, niin väit­tä­mä tuot­taa epä­to­si, kos­ka koh­das­sa i ole­va al­kio ei ole suu­rem­pi it­seään eli koh­das­sa i ole­vaa al­kio­ta. Suo­men­kie­les­sä on kä­te­vä pie­ni sa­na rat­kai­se­maan tä­mä on­gel­ma: ”koh­das­sa i ole­va al­kio on suu­rem­pi kuin mi­kään muu al­kio” on hyö­dyl­li­nen tau­luk­koa kos­ke­va väit­tä­mä, jo­ka pä­tee joil­le­kin tau­lu­kon si­säl­löil­le ja i:n ar­voil­le, ja toi­sil­le ei pä­de. Kaa­vois­sa tä­mä jou­du­taan sa­no­maan esi­mer­kik­si li­sää­mäl­lä ra­joit­tee­seen osa, jo­ka sa­noo et­tä kvan­ti­fioi­tu muut­tu­ja on eri­suu­ri kuin i.

Koh­das­sa i ole­va al­kio on suu­rem­pi kuin mi­kään muu al­kio.

tai

Tau­lu­kon en­sim­mäi­nen al­kio on eri­suu­ri kuin mi­kään muu al­kio.

tai

Tau­lu­kon vii­mei­nen al­kio on jon­kin muun kans­sa yh­tä­suu­ri.

tai

x esiin­tyy tau­lu­kos­sa se­kä koh­das­sa i et­tä jos­sain muual­la.

tai

x esiin­tyy tau­lu­kos­sa ai­na­kin kah­des­ti.

tai

Tau­lu­kos­sa on ai­na­kin kak­si al­kio­ta. (Tä­män voi sa­noa hy­vin yk­sin­ker­tai­ses­ti.)

tai

Tau­lu­kos­sa on ai­na­kin kak­si eri­suur­ta al­kio­ta.

tai

Tau­lu­kon al­kio ja tau­lu­kon al­kion paik­ka ovat eri asioi­ta. Har­joi­tel­laan­pa tä­tä hie­man!

Tau­lu­kon suu­rin al­kio (tai jo­kin niis­tä, jos suu­rin esiin­tyy useas­ti) on koh­das­sa i.

tai

Tau­lu­kon suu­rin al­kio on i. (Se saa esiin­tyä useas­ti.)

tai

Koh­das­sa i ole­vaa al­kio­ta en­nen ovat koh­dis­sa 1, …, i − 1 si­jait­se­vat al­kiot. Koh­das­sa i ole­van al­kion jäl­keen ovat koh­dis­sa i + 1, …, n si­jait­se­vat al­kiot.

Koh­das­sa i ole­va al­kio on suu­rem­pi kuin mi­kään al­kio sen jäl­keen.

tai

Tau­luk­ko ja­kau­tuu al­ku­osaan ja lop­pu­osaan. Kum­pi ta­han­sa tai mo­lem­mat osat voi­vat ol­la tyh­jiä. Lop­pu­osa al­kaa koh­das­ta i. Jos lop­pu­osa on tyh­jä, niin tul­kit­se i jär­ke­väs­ti. Al­ku­osas­sa on vain yk­kö­siä.

tai

Tau­luk­ko ja­kau­tuu al­ku­osaan ja lop­pu­osaan. Kum­pi ta­han­sa tai mo­lem­mat osat voi­vat ol­la tyh­jiä. Lop­pu­osa al­kaa koh­das­ta i. Jos lop­pu­osa on tyh­jä, niin tul­kit­se i jär­ke­väs­ti. Lop­pu­osas­sa on vain kak­ko­sia.

tai

Koh­taa i en­nen on vain yk­kö­siä ja koh­das­ta i al­kaen on vain kak­ko­sia. Yk­kö­siä ei ole pak­ko ol­la ei­kä kak­ko­sia ole pak­ko ol­la. (Jos kak­ko­sia ei ole, niin i on tau­lu­kon vii­mei­sen koh­dan jäl­kei­nen koh­ta. Muu­toin i osuu tau­lu­kon alueel­le.)

tai

Tau­lu­kon jo­kai­nen al­kio on yh­tä­suu­ri en­sim­mäi­sen al­kion kans­sa.

tai

Tau­lu­kon kaik­ki al­kiot ovat kes­ke­nään yh­tä­suu­ret.

tai

Mit­kä seu­raa­vis­ta väit­tä­mis­tä tar­koit­ta­vat sa­maa? Mie­ti en­sin it­se ja kat­so sit­ten mi­tä miel­tä Math­Check on. Voit myös muun­nel­la väit­tä­miä, jos ha­luat ko­keil­la mui­ta­kin vaih­to­eh­to­ja.

tai

Eri ih­mi­set tul­kit­se­vat väit­tä­män ”vii­mei­sen yk­kö­sen jäl­keen on vain kak­ko­sia” eri ta­voin. Ryh­män (a) mie­les­tä väit­tä­mä vaa­tii, et­tä tau­lu­kos­sa on yk­kö­nen. Joi­den­kin mui­den mie­les­tä ei vaa­di.

Jäl­kim­mäi­nen jouk­ko ja­kau­tuu kah­tia sen mu­kaan, mi­tä tau­lu­kos­sa saa ol­la jos sii­nä ei ole lain­kaan yk­kö­siä. Ryh­män (b) mie­les­tä siel­lä saa ol­la mi­tä vain (pait­si tie­ten­kin yk­kö­siä), kos­ka väit­tä­mä ei vel­voi­ta mi­tään kun vii­meis­tä yk­kös­tä ei ole. Vaih­to­eh­toi­sen tul­kin­nan (c) mu­kaan sii­nä saa ol­la vain kak­ko­sia. Tä­män tul­kin­nan mu­kaan väit­tä­mä tar­koit­taa sa­maa kuin ”en­nen en­sim­mäis­tä yk­kös­tä saa ol­la vain kak­ko­sia” so­vel­let­tu­na tau­luk­koon ta­ka­pe­rin eli lo­pus­ta al­kuun.

(Sii­tä­kin voi­daan ol­la eri miel­tä, et­tä jos tau­lu­kos­sa on yk­kö­nen, on­ko tau­lu­kos­sa pak­ko ol­la lo­pus­sa ai­na­kin yk­si kak­ko­nen. Nou­da­tam­me kan­taa, jon­ka mu­kaan ei ole pak­ko.)

Il­mai­se tul­kin­ta (a). Vih­je 1Riit­tää sa­noa, et­tä tau­lu­kos­sa on jo­kin yk­kö­nen, jon­ka jäl­keen on vain kak­ko­sia. Ei tar­vit­se sa­noa, et­tä se on vii­mei­nen yk­kö­nen. Jos saa­daan sa­no­tuk­si et­tä sen jäl­keen on vain kak­ko­sia, niin se on vä­ki­sin vii­mei­nen yk­kö­nen. Vih­je 2Edel­lä on har­joi­tel­tu sen sa­no­mis­ta, et­tä tau­lu­kos­sa on jo­kin tiet­ty ar­vo. Vih­je 3Edel­lä on har­joi­tel­tu sen sa­no­mis­ta, et­tä jo­kin al­kio on jol­lain tie­tyl­lä ta­val­la eri­lai­nen kuin kaik­ki sen jäl­keen.

tai

Il­mai­se tul­kin­ta (b). Vih­je 1Täl­lä kan­nal­la oli­jat ovat sa­maa miel­tä edel­li­sen koh­dan kans­sa sil­loin, kun tau­lu­kos­sa on yk­kö­nen. Li­säk­si heil­le kel­paa, et­tä tau­lu­kos­sa on mi­tä ta­han­sa pait­si yk­kö­siä. Näis­tä saa tai-muo­toi­sen kaa­van. Vih­je 2Pi­dä huo­li, et­tä ∀:n tai ∃:n vai­ku­tus ei va­hin­gos­sa ulo­tu liian pit­käl­le. Tar­vit­taes­sa ra­jaa vai­ku­tus­alue su­luil­la.

tai

Il­mai­se tul­kin­ta (c). Vih­je 1Ajat­te­le, et­tä tau­luk­koa käy­dään lä­pi lo­pus­ta al­kuun. Luo ∃:lla muut­tu­ja tar­koit­ta­maan si­tä koh­taa, jos­sa ta­ka­pe­roi­nen lä­pi­käyn­ti py­säh­tyy. Vih­je 2Py­säh­ty­mi­seen on kak­si vaih­to­eh­tois­ta syy­tä. Niis­tä tu­lee ly­hyt tai-muo­toi­nen kaa­va. Vih­je 3Kaa­va, jo­ka ker­too mi­tä py­säh­ty­mis­koh­dan jäl­keen pi­tää pä­teä, on ol­lut edel­lä.

tai

Mi­ten ään­täi­sit suo­mek­si seu­raa­van merk­ki­pa­rin: τ🔒 ? Vih­je: kuuk­laa erik­seen kum­pi­kin näis­tä mer­keis­tä.