Peatükk 2 Valikulaused

Vaid väga väike osa algoritmidest on kirjeldatavad alati täpselt samas järjekorras täidetavate operatsioonide järjendina. Käesolevas peatükis vaatleme valikulauseid, millega saab kirjeldada tegevuse suunamist vastavalt algoritmi täitmise ajal selguvatele tingimustele.

Kasutades näitena jälle kokaraamatut, kohtame retseptides sageli juhiseid, kuidas mõnd puuduvat komponenti teisega asendada (näiteks ``...kui veiniäädikat käepärast pole, võib selle asemel kasutada ka sidrunimahla...'') või võimaluse korral rooga mittekohustuslike lisanditega huvitavamaks teha (näiteks ``...kõige peale võib puistata veidi jahvatatud kaneeli...'').

Nii algoritme käsitlevas kirjanduses kui ka programmikeeltes kasutatakse tingimuste esitamiseks matemaatilisest loogikast laenatud vahendeid, sestap alustamegi peatükki loogika põhimõistete vaatlemisest.

2.1 Loogika alused

Loogika (ingl logic) on filosoofia, lingvistika ja matemaatika piiril asuv teadus, mis tegeleb arutluste ja tõestuste uurimisega, see tähendab eelduste ja nendest tehtavate järelduste tõelevastavuse uurimisega.

Õigupoolest ei ole formaalse loogika seisukohalt arutlusel ja tõestusel mingit vahet --- arutluseks nimetatakse üldiselt mõtlemist, järelduste tegemist, tõestuseks aga tehtud järelduste õigsuse demonstreerimist kellelegi teisele. Loogika seisukohalt pole oluline, kas järeldusi tehakse omaks tarbeks või teistele esitamiseks --- nende paikapidavust see ei muuda.

Võib öelda, et loogika peaeesmärk on leida sellised järelduste tegemise reeglid, et tõestest eeldustest tehtaks ainult tõeseid järeldusi. (See on muidugi üsna jäme lihtsustus, tegelikult on loogika uurimisvaldkond palju laiem ja probleemid mitmekesisemad.)

Analoogiliselt algoritmidele on ka loogikas väidete (ja ennekõike nendevaheliste seoste) täpsemaks esitamiseks kasutusel formaalsed tähistused.

2.1.1 Tõeväärtus

Loogilise arutluse elementaarosad on väited, mis võivad olla kas tõesed või väärad, näiteks ``2+2=4'' või ``Eesti pealinn on Tartu''.

Väidet nimetatakse tõeseks (ingl true), kui see vastab tegelikkusele ja vääraks (ingl false), kui see ei vasta tegelikkusele. Eelpool toodud väidetest on esimene tõene, teine aga väär.

Laused, mis midagi ei väida, ei saa olla ei tõesed ega väärad ning pole seetõttu ka loogika uurimisobjektid. Sellised on näiteks enamik küsi- ja hüüdlauseid.

2.1.2 Lausearvutus

Lausearvutus (ingl propositional calculus) on loogika osa, mis uurib keerulisemate väidete konstrueerimist lihtsamatest.

Lausearvutuse valemite koostamisel asendatakse lausetes olevad väited neid tähistavate muutujatega ja lausete omavahelised seosed loogiliste tehetega. Selleks jagatakse uuritav arutlus või tõestus lauseteks, need omakorda osalauseteks jne, kuni jõutakse väideteni, mida enam osadeks jagada ei saa. Saadud väiteid tähistatakse loogikas harilikult suurte ladina tähtedega ja iga sellise muutuja tõeväärtuseks loetakse loomulikult tema poolt tähistatava väite tõeväärtus.

Loogilised tehted, mille abil väited uuesti lauseteks seotakse, on eitus, konjunktsioon, disjunktsioon, implikatsioon ja ekvivalents. Mitmest seotud väitest koosnevaid avaldisi tähistatakse harilikult väikeste ladina tähtedega ja nende tõeväärtused defineerime järgnevates lõikudes.

Nagu aritmeetikas, võib ka lausearvutuses avaldise väärtus sõltuda tehete sooritamise järjekorrast. Nagu aritmeetikas, kasutatakse ka lausearvutuses tehete järjekorra märkimiseks sulge --- sulgudes olevad tehted sooritatakse alati enne.

Nagu aritmeetikas, oleks ka lausearvutuses tülikas kõigis avaldistes kõigi tehete järjekorda sulgudega näidata, seepärast määratakse tehetele prioriteedid: kõrgeima prioriteediga tehe on eitus (sarnane miinusmärgi kasutamisele aritmeetikas), järgmine konjunktsioon (sarnane korrutamisele), seejärel disjunktsioon (sarnane liitmisele), seejärel implikatsioon ja lõpuks ekvivalents (sarnane võrdusele).

Eitus

Eitus (ingl negation) on unaarne ehk üheoperandiline tehe ja avaldise Ø p (loetakse ``mitte p'') tõeväärtus on vastupidine muutuja või avaldise p tõeväärtusele.¹

Loogilise eituse abil esitatakse lausearvutuses konstruktsioone, mida loomulikus keeles väljendatakse sõnade ``ei'', ``mitte'' ja muude negatiivsete vormide abil. Lausearvutuse valemi Ø p tehniliselt kõige täpsem tõlge eesti keelde on väide ``pole õige, et p kehtib'' ehk lühemalt ``pole õige, et p''.

Näiteks, kui A tähistab väidet ``Kati läks eile koos Matiga välja'', siis Ø A tähistab väidet ``pole õige, et Kati läks eile koos Matiga välja''. Oluline on tähele panna, et eitav väide ei täpsusta, kas Kati ei läinud üldse välja või läks ta välja küll, aga ilma Matita; samuti ei ütle eitav väide midagi Mati tegemiste kohta.

Loomuliku keele väidet ``Kati ei läinud eile koos Matiga välja'' mõistavad paljud inimesed selliselt, et Kati ei läinud üldse välja; sageli tehakse sellisest sõnastusest koguni järeldus, et Mati läks välja ja Kati jäi koju.

Juba sellest näitest selgub, et loomuliku keele väidete lausearvutuse valemiteks teisendamine ei tarvitse alati lihtne ülesanne olla. Eituse puhul on oluline selgeks teha, millisele esialgse väite osale eitus rakendub (seda osa nimetatakse eituse fookuseks) ja ka lausearvutuse valemis eitust just samale osale rakendada, vastasel korral muudame lause valemiks teisendamisel selle mõtet ja võime kergesti valedele järeldustele jõuda.

Konjunktsioon

Konjunktsioon (ingl conjunction) ehk loogiline ``ja'' (ingl boolean and) on binaarne ehk kaheoperandiline tehe. Avaldis p Ù q (loetakse ``p ja q'') on tõene, kui nii p kui ka q on mõlemad tõesed, ning väär igal muul juhul.²

Konjunktsiooni abil esitatakse lausearvutuses kahe väite samaaegset kehtimist. Loomulikus keeles vastab sellele enamasti sidesõna ``ja'' kasutamine või lihtsalt väidete järjest esitamine.

Näiteks, kui A tähistab väidet ``Kati õpib'' ja B tähistab väidet ``Mati õpib'', siis A Ù B võib eesti keeles üles kirjutada nii kujul ``Kati õpib. Mati õpib.'' kui ka kujul ``Kati õpib ja Mati õpib'' kui ka kujul ``Kati ja Mati õpivad''.

Üldiselt on konjunktsiooni p Ù q abil võimalik esitada väiteid, mille saab sõnastada kujul ``kehtivad nii p kui ka q'' ehk lühemalt ``nii p kui ka q''. Näiteks väidet ``1 ja 1 on kokku 2'' ei saa konjunktsioonina esitada, kuigi ka selles väites esineb sidesõna ``ja''.

Disjunktsioon

Disjunktsioon (ingl disjunction) ehk loogiline ``või'' (ingl boolean or) on samuti binaarne tehe. Avaldis p Ú q (loetakse ``p või q'') on tõene, kui vähemalt üks väidetest p ja q on tõene, ning väär, kui kumbki neist ei kehti.

Loomulikus keeles vastab disjunktsioonile enamasti sidesõnade ``või'' või ``ehk'' kasutamine.

Näiteks, kui A tähistab väidet ``Kati koristab tuba'' ja B tähistab väidet ``Kati laulab'', siis A Ú B võib eesti keeles üles kirjutada kujul ``Kati koristab tuba või laulab''.

Loomulikus keeles kasutatakse väidet ``p või q'' sageli tähenduses ``kehtib kas p või q, kuid mitte mõlemad korraga''. Näiteks väidet ``Kati koristab oma toa ära või saab karistada'' mõistetakse enamasti tähendavat, et Kati ei saa karistada, kui ta oma toa korda teeb. Sõna ``või'' sellise tõlgenduse nimi on loogikas välistav ``või'' (ingl exclusive or).

Implikatsioon

Implikatsioon (ingl implication) on samuti binaarne tehe. Avaldis p É q (loetakse ``kui p, siis q'') on väär ainult siis, kui p kehtib, aga q ei kehti.³

Implikatsiooni p É q nimetatakse ka järeldusseoseks, selles sõnastuses on p implikatsiooni eeldus ja q selle järeldus. Kuna implikatsioonitehte tulemus sõltub ainult avaldiste p ja q tõeväärtustest, mitte aga sisulisest põhjuslikust seosest nende väidete kehtivuse vahel, ei saa seda tehet päriselt samastada arutluse ja tõestuse mõistetega, millest oli juttu peatüki alguses.⁴

Loomulikus keeles kasutatakse implikatsiooni p É q esitamiseks tavaliselt väljendeid ``q, sest p'' või ``kui p, siis q'' (vahel ka lühemalt ``kui p, q''), kuid siis peetakse silmas ikka põhjuslikku seost. Seetõttu nimetatakse loomulikus keeles sageli implikatsiooni eeldust põhjuseks ja järeldust tagajärjeks.

Näiteks, kui A tähistab väidet ``Kati ei korista oma tuba'' ja B tähistab väidet ``Kati saab karistada'', siis A É B võib eesti keeles esitada kujul ``kui Kati ei korista oma tuba, saab ta karistada'' ja sellisel juhul eeldatakse ikka põhjuslikku seost --- Kati saab karistada just oma kohustuste täitmatajätmise eest, mitte lihtsalt niisama.

Levinuim viga nii implikatsioonitehte kui ka põhjusliku seose kasutamisel on implikatsiooni eelduse mittekehtimisest selle järelduse mittekehtimise tuletamine. See tähendab, kui kehtib p É q ja p on väär, tehakse sellest eksijäreldus, et ka q peab olema väär. See pole aga õige ei formaalselt (kui p on väär, siis p É q on tõene sõltumata q väärtusest) ega ka sisuliselt (ühel tagajärjel võib olla mitu erinevat põhjust, näiteks Kati võib oma toa ära koristada, kuid saada karistuse väikevenna kiusamise eest).

Ekvivalents

Ekvivalents (ingl equivalence) on samuti binaarne tehe. Avaldis p º q (loetakse ``p parajasti siis, kui q'') on tõene, kui p ja q tõeväärtused on samad, ning väär, kui p ja q tõeväärtused on erinevad.⁵

Loomulikus keeles kasutatakse ekvivalentsi harva, enamasti matemaatilistes tekstides, kus p º q sõnastatakse kujul ``p parajasti siis, kui q'' või ``p siis ja ainult siis, kui q''.

Koondtabel

Lõpetuseks lausearvutuse põhitehete tõeväärtused ühtse koondtabelina.

A B Ø A A Ù B A Ú B A É B A º B

väär väär tõene väär väär tõene tõene

väär tõene tõene väär tõene tõene väär

tõene väär väär väär tõene väär väär

tõene tõene väär tõene tõene tõene tõene

Table 2.1: Lausearvutuse tehted

2.1.3 Predikaatarvutus

Predikaatarvutus (ingl predicate calculus) on lausearvutuse laiendus, kus lausemuutujate asemel kasutatakse predikaate. Predikaatarvutus võimaldab esitada mitmeid praktikas olulisi seoseid ja järeldusi, milleks lausearvutuse vahenditest ei piisa.

Predikaat

Esimeses peatükis programmi elementidest rääkides oli juttu sellest, et primitiividel võivad olla ka parameetrid. Osutub, et ka loogikas on sageli kasulik üksikute lausemuutujate asemel vaadelda parametriseeritud väiteid.

Vaadeldes väiteid A = ``Kati õpib'' ja B = ``Mati õpib'', märkame, et nad on sama struktuuriga. Tähistades nende väidete ühise osa ``x õpib'' sümboliga Q(x), saamegi predikaadi (ingl predicate), millest x asendamisel konkreetsete väärtustega võime tekitada erinevaid väiteid. Kui tähistame k = ``Kati'' ja m = ``Mati'', saame väite A esitada kujul Q(k) ja väite B kujul Q(m).

Ka matemaatikast tuntud võrdus- ja võrratusmärgid (=, <, >, £, ³) on predikaadid, kuigi ``<(2,4)'' asemel kirjutatakse ``2<4''.⁶

Sageli seab predikaadi esitatava väite olemus piiranguid objektidele, millele seda predikaati rakendada võib (näiteks ei ole ju mõistlik rääkida õppimisest elutute esemete puhul). Hulka, mille elementidele võib predikaati rakendada, nimetatakse universumiks (ingl universe).

Nagu primitiivide puhul, pole ka predikaatide defineerimisel alati selge, millised väite osad peaks jätma fikseerituks ja millised eraldama parameetritena. Näiteks väite C = ``Kati meeldib Matile'' üldistusteks sobivad

R₁(x)	=	``x meeldib Matile'';
R₂(y)	=	``Kati meeldib y'le'';
R(x,y)	=	``x meeldib y'le''.

Esialgse väite saab siis esitada kujul R₁(k) või R₂(m) või R(k,m).

Võrreldes parameetriteta lausemuutujate kasutamisega võimaldavad predikaadid esitada rohkem infot erinevate väidete omavaheliste seoste kohta. Näiteks väited ``Kati ja Mati õpivad ning Kati meeldib Matile'' saame lausearvutuse valemina esitada kujul

A Ù B Ù C,

predikaatarvutuse valemina aga kujul

Q(k) Ù Q(m) Ù R(k,m).

Predikaatarvutuse valemist on kohe näha, et meil on tegemist korduvate väidete ja korduvate isikutega, lausearvutuse seisukohalt on tegu lihtsalt kolme samaaegselt kehtiva väitega.

Üldisuskvantor

Üldisuskvantor (ingl universal quantifier) on tehe, mida võib rakendada predikaatloogika avaldisele. Avaldis " x : p (loetakse ``iga x korral kehtib p'') on tõene, kui väide p kehtib iga universumisse kuuluva objekti x jaoks.

Sageli on vaja märkida, et väide p kehtib ainult teatud hulga H (mitte terve universumi) elementide kohta. Seda saaks kirjeldada valemiga

" x : x Î H É p

(loetakse ``iga x korral kehtib: kui x on hulga H element, siis kehtib p''), kuid sagedase kasutamise tõttu on lepitud kokku lühemas ja ülevaatlikumas kirjaviisis

" x Î H : p

(loetakse ``iga x korral hulgast H kehtib p''). Näiteks väite ``naturaalarvude hulga N kõik elemendid on mittenegatiivsed'' võib esitada kujul

" n Î N : n ³ 0.

Olemasolukvantor

Olemasolu- ehk eksistentsikvantor (ingl existential quantifier) on teine levinud kvantor. Avaldis $ x : p (loetakse ``leidub x, mille korral kehtib p'') on tõene, kui väide p kehtib vähemalt ühe (aga võimalik, et ka enam kui ühe) universumisse kuuluva objekti x jaoks.

Analoogiliselt üldisuskvantoriga võib ka olemasolukvantori kasutamisel näidata, millise hulga elemente me vaatleme. Näiteks väite ``täisarvude hulgas Z leidub negatiivseid elemente'' võib esitada kujul:

$ x Î Z : x < 0.

2.1.4 Loogiline samaväärsus

Loogikas on tähtsal kohale valemite loogilise samaväärsuse (ingl logically equivalent) mõiste.

Lausearvutuse valemeid p ja q nimetatakse loogiliselt samaväärseteks ja kirjutatakse p = q, kui nende tõeväärtused on samad nendes esinevate lausemuutujate kõigi võimalike tõeväärtuste korral.

Loogilist samaväärsust ei tohi segamini ajada ekvivalentsitehtega. Näiteks valemite p = A Ù B É A ja q = A Ù (B É A) tõeväärtused on samad, kui A ja B on mõlemad tõesed, seega sellisel juhul väide p º q kehtib. Siiski pole need valemid loogiliselt samaväärsed, sest kui A ja B on mõlemad väärad, pole p ja q tõeväärtused samad, seega ei saa me väita, et p = q.

Kõige lihtsam (kuigi sageli töömahukas) viis lausearvutuse valemite loogilise samaväärsuse kontrollimiseks on koostada nende valemite tõeväärtustabelid. Valemi tõeväärtustabelis on üks rida iga võimaliku selles valemis esinevate muutujate väärtustuse kohta.⁷ Näiteks võib tuua eelmises lõigus vaadeldud valemite tõeväärtustabelid.⁸

Predikaatarvutuse valemite jaoks üldjuhul selliseid tabeleid koostada ei saa, sest predikaatide võimalike tõeväärtuste komplektide leidmiseks tuleb enne kokku leppida, millisest universumist pärit objektidega me tegeleme ja milline on iga predikaadi sisuline tähendus. Ilma neid kahte parameetrit fikseerimata pole võimalik antud predikaadi P(x) jaoks kindlaks teha, kas leiduvad x väärtused, mille korral P(x) on vastavalt tõene või väär, seega me ei tea, kas tabelisse tuleb lisada read vastavate juhtude jaoks.

Näiteks täisarvude hulgal Z võib predikaat P(x) = (x < 0) olla (sõltuvalt x valikust) nii tõene kui ka väär, kuid naturaalarvude hulgal N saab ta olla ainult väär.

Siiski on olemas ka predikaatarvutuse valemite paare, mis on samaväärsed igas interpretatsioonis (universumihulga ja predikaatide tähenduste fikseerimist nimetatakse valemi interpretatsiooniks). Järgmised samaväärused kehtivad alati:

Ø Ø p	=	p;
Ø (p Ù q)	=	Ø p Ú Ø q;
Ø (p Ú q)	=	Ø p Ù Ø q;
p É q	=	Ø p Ú q;
p É q	=	Ø (p Ù Ø q);
p º q	=	(p Ù q) Ú (Ø p Ù Ø q);
p º q	=	(p É q) Ù (q É p);
Ø (" x : p)	=	$ x : Ø p;
Ø ($ x : p)	=	" x : Ø p.

2.2 Loogilised avaldised

Siiani rääkisime loogika teooriast, nüüd pöördume taas programmeerimise poole ja vaatame, kuidas seda teooriat algoritmide kirjeldamisel rakendada.

2.2.1 Predikaadid

Igas programmikeeles on olemas terve hulk predikaate kontrollimaks mitmesuguseid tingimusi, mida erinevad andmeobjektid võivad rahuldada või mitte rahuldada.

Arvud

Kõigis levinud programmikeeltes on olemas predikaadid arvutüüpi väärtuste võrdlemiseks: =, <, >, £, ³. Kuna märke £ ja ³ arvuti klaviatuuril ega programmikeelte lubatud sümbolite hulgas tavaliselt pole, kasutatakse nende predikaatide esitamiseks mingeid muid kombinatsioone, levinuimad on ``<='' ja ``=>''; võrdusmärgi asemel kasutatakse mitmetes keeltes ``==''.

Ettevaatlik peab olema reaalarvude võrdlemisel. Reaalarve hoitakse arvuti mälus ligikaudsete suurustena ja ümardamisvigade tõttu võib sageli saada ootamatuid tulemusi.

Harjutuseks võiks uurida, kui palju nulle peab avaldises 1 + 0,00001 teises arvus koma ja ühe vahele panema, et arvuti arvaks, et summa on ikka 1. Siis võiks võtta selle väikese arvu ja võrrelda teda nulliga. Kes varem pole selliste asjade peale mõelnud, võib üllatuse osaliseks saada...Vähimat arvu x, mille korral 1 + x pole veel 1, nimetatakse selle arvutüübi ``epsiloniks''.

Võimalikud on ka vastupidised vead. Näiteks võib juhtuda, et 0,44 ja 0,11 + 0,33 võrdlemine annab negatiivse tulemuse. Seda tüüpi vigade vältimiseks võib absoluutselt täpse võrdumise asemel nõuda, et arvude erinevus oleks väiksem mingist piisavalt pisikesest suurusest või piisavalt palju väiksem võrreldavatest suurustest. (Kes on matemaatikatunnis õppinud absoluutse ja suhtelise vea mõisteid, peaks märkama, et eelnimetatud asendustest esimene kontrollib absoluutse ja teine suhtelise vea suurust.)

Lisaks võrdlemispredikaatidele võib programmikeel pakkuda ka muid, aga need on üldiselt igal keelel erinevad.

Tekstid

Samuti on kõigis (või vähemalt peaaegu kõigis) programmikeeltes olemas predikaadid sümboli- ja tekstitüüpi väärtuste võrdlemiseks.⁹

Tavaliselt võrdlevad programmikeelte standardsed predikaadid tekstitüüpi väärtusi leksikograafiliselt (ingl lexicographical order) --- võrdlemisel jäetakse vahele need sümbolid kummagi teksti algusest, mis on omavahel võrdsed ja otsus langetatakse esimese erineva sümboli põhjal; kui üks tekstidest otsa saab, loetakse tema väiksemaks. Samasugust järjestust kasutavad sõnaraamatud ja entsüklopeediad --- leksikograafilisel võrdlemisel loetakse väiksemaks tekst, mis oleks sõnaraamatus eespool.

Erinevus on selles, et sõnaraamatutes tavaliselt suuri ja väikesi tähti ei eristata, aga enamikus programmikeeltes on sümbolite võrdlemine tõstutundlik (ingl case-sensitive). Kas suuremaks loetakse suuri või väikseid tähti, pole üldiselt määratud ning sõltub kasutatavast programmeerimissüsteemist ja arvuti seadetest.

Eesti täpitähti ei pea enamiku programmikeelte võrdlemispredikaadid üldse tähtedeks ja need satuvad sorteerimisel kuhu juhtub (ühe süsteemi piires ikka ühte kohta, aga üldiselt mitte sinna, kuhu nad eesti tähestiku järgi käima peaks). Kui on vaja korralikku eestikeelset järjestamist, tuleb selleks eraldi vaeva näha.

Lisaks võrdlemispredikaatidele on programmikeeltes sageli olemas predikaadid, mis kontrollivad, kas antud sümbol on number, täht (nagu juba öeldud, ``täpilisi'' üldiselt tähtedeks ei peeta) või mõnd muud liiki sümbol.

Mõnes programmikeeles on ka eraldi predikaadid kontrollimaks, kas antud teksti on võimalik tõlgendada arvu, kuupäeva või kellaajana. Milliseid arvude, kuupäevade ja aegade vorminguid need funktsioonid ``tunnistavad'', tuleb igal konkreetsel juhul eraldi uurida.

2.2.2 Loogilised tehted

Tavaliselt on programmikeeltes lausearvutuse tehetest olemas eitus, loogiline ``ja'', nii loogiline kui ka välistav ``või'' ja ekvivalents. Implikatsiooni eraldi tehtena enamasti realiseeritud ei ole, sest seda ei lähe programmeerimisel kuigi sageli vaja.

Kvantoreid üldotstarbelistes programmikeeltes tavaliselt ei ole, kuigi mõnes süsteemis olemasolevaid primitiive massiivist või muust andmekogust antud tingimustele vastavate elementide leidmiseks ja loendamiseks võib mingil määral kvantoritega võrrelda, samuti saab vajaduse korral nende abil (või päris ise) kvantorid realiseerida.

Loogikatehete kasutamisel peab tähelepanu pöörama sellele, et lisaks tavalistele loogikatehetele, mis opereerivad tõeväärtustega, on paljudes keeltes olemas ka bitiloogika (ingl bitwise logic) tehted, mis opereerivad täisarvudega.

Bititehted tõlgendavad täisarvu kahendkuju¹⁰ iga numbrit 0 väära ja numbrit 1 tõese tõeväärtusena, sooritavad loogilise tehte oma operandide samades positsioonides olevate bittide vahel ja tagastavad tulemusena saadud bittidest moodustatud arvu.

2.2.3 Loogilised muutujad

Peaaegu kõigis tänapäevastes programmikeeltes on olemas eraldi andmetüüp tõeväärtuste esitamiseks. Seda tüüpi muutujale on võimalik omistada loogilise avaldise väärtus ja seejärel võib muutujasse salvestatud väärtust kasutada kõikjal, kus muidu oleks tulnud kasutada seda avaldist ennast.

Muutuja kasutamise üks eelis on see, et talle saab panna korraliku nime, seega on pärast programmi lugedes kergem aru saada, millist tingimust see avaldis esitab. Keerukamate avaldiste puhul ei tarvitse see avaldise enda lugemisest kohe selguda.

Teine eelis on see, et muutujasse salvestatud väärtust võib korduvalt kasutada ilma, et arvuti peaks kulutama aega avaldise väärtuse uuesti arvutamisele. Sellest saadav võit on muidugi tühine, kui avaldis koosneb ainult paari arvu võrdlemisest, kuid keerukate predikaatide kasutamisel võib vahe olla märgatav.

2.3 Valikulausete liigid

2.3.1 Ühene valik

Ühene valik (ingl conditional statement) on lihtsaim võimalik valikulause, kus mingi tegevus kas sooritatakse või jäetakse sooritamata vastavalt antud tingimuse kehtivusele.

Peatüki alguses toodud kokaraamatu näide kaneeli kasutamisest oli just ühese valiku näide --- kui kokal oli kaneel käepärast, lisas ta seda toidule, vastasel korral ei teinud midagi.

Ühese valikulause üldkuju on

kui t
käsud
lõppkui

Kui tingimus t kehtib, täidetakse käsud ja jätkatakse algoritmi täitmist võtmesõnale lõppkui järgnevast lausest. Kui tingimus t ei kehti, jäetakse käsud vahele ja jätkatakse kohe võtmesõnale lõppkui järgnevast lausest.

Oluline on tähele panna, kuidas mõjub valikulause kasutamine algoritmi vahetingimustele. Oletame, et valikulause eel kehtis vahetingimus p.

Kui tingimus t kehtib, on valikulause sees oleva käsujada eeltingimus p Ù t --- kehtib kõik, mida me teadsime enne tingimuse t kontrollimist, lisaks saime teada, et ka t kehtib. Kui me sellest seisust valikulause sees olevaid käske täites jõuame tingimuseni q, siis, kuna lõppkui pole tegelikult käsk, vaid ainult valikulause lõpu näitaja, ei muuda see enam midagi ja seega jääb valikulause täitmise lõpuks kehtima vahetingimus q.

Kui tingimus t valikulause alguses selle kontrollimisel ei kehti, tähendab see, et me liigume kohe valikulause lõppu, kusjuures nüüd me teame, et kehtib p Ù Ø t.

Võttes kokku need kaks ainuvõimalikku varianti valikulause läbimiseks, saame, et valikulause järel peab kehtima vahetingimus q Ú p Ù Ø t.

Näiteks, kasutades eelmise peatüki lõpus toodud algoritmi kahe muutuja väärtuste vahetamiseks, võime koostada algoritmi kahe arvu järjestamiseks suuruse järjekorda.

Algoritm 1 Järjestab kahe muutuja väärtused suuruse järjekorda
Sisend: a, b --- järjestatavad väärtused
Väljund: a, b --- väärtused vahetatud nii, et a £ b
Abimuutujad: c

kui a > b
c¬a
a¬b
b¬c
lõppkui

Algoritmi õigsuses veendumiseks tähistame muutujate a ja b algväärtused vastavalt a₀ ja b₀ ning c puuduva algväärtuse ^. Siis saame algoritmi eeltingimuseks

a = a₀ Ù b = b₀ Ù c = ^.

Kui valikulause tingimus kehtib (see tähendab, kui a₀ > b₀), vahetavad selle sees olevad käsud muutujate a ja b väärtused ning valikulause lõppu jõuame vahetingimusega

a₀ > b₀ Ù a = b₀ Ù b = a₀ Ù c = a₀.

Kui valikulause tingimus ei kehti (see tähendab, kui a₀ £ b₀), jõuame valikulause lõppu vahetingimusega

a₀ £ b₀ Ù a = a₀ Ù b = b₀ Ù c = ^.

Võttes need tingimused kokku ja jättes kõrvale abimuutuja c, mille väärtusest me niikuinii ei hooli, saame

(a₀ > b₀ Ù a = b₀ Ù b = a₀) Ú (a₀ £ b₀ Ù a = a₀ Ù b = b₀),

millest ongi näha, et muutuja a lõppväärtus on kahest algväärtusest just väiksem ja muutuja b lõppväärtus neist kahest just suurem.¹¹

Paljude programmikeelte süntaks lubab valikulauses tingimuse kehtimisel täidetavate käskude jada asemel ainult üht käsku või lauset. Sellistes keeltes on tavaliselt olemas vahendid mitme lause ühendamiseks üheks liitlauseks --- tavaliselt tuleb liitlause moodustamiseks selle osad grupeerida võtmesõnade begin ja end või mingit liiki sulgude vahele.

Kui keeles on liitlause moodustamise võimalus, siis võib selliselt moodustatud liitlauset harilikult kasutada igal pool, kus on lubatud lihtlause kasutamine --- muuhulgas ka järgnevalt vaadeldavates valikulausetes.

2.3.2 Kahene valik

Kahene ehk alternatiivne valik (ingl alternative statement) erineb ühesest selle poolest, et algoritmis määratakse mingi tegevus ka juhtumiks, kui kontrollitav tingimus ei kehti. Seega kahese valikulause täitmisel sooritatakse üks tegevus, kui tingimus kehtib ja mingi teine tegevus, kui tingimus ei kehti.

Peatüki alguses toodud näide sidrunimahla kasutamisest veiniäädika asemel oli kahese valiku näide --- kui kokal oli veiniäädikat, kasutas ta seda; kui ei olnud, kasutas selle asemel sidrunimahla. (Mida teha siis, kui kumbagi pole, see retsept ei kirjeldanud. Algoritmi õigsuse seisukohalt on selline ühe võimaliku variandi vaatluse alt välja jätmine viga, kui kahest komponendist vähemalt ühe olemasolu pole algoritmi eeltingimus.)

Kahese valikulause üldkuju on

kui t
tõene-käsud
muidu
väär-käsud
lõppkui

Kui tingimus t kehtib, täidetakse tõene-käsud ja jätkatakse algoritmi täitmist võtmesõnale lõppkui järgnevast lausest. Kui tingimus t ei kehti, täidetakse väär-käsud ja jätkatakse võtmesõnale lõppkui järgnevast lausest.

Selle valikulause vahetingimuste uurimiseks oletame jälle, et valikulause eel kehtis vahetingimus p.

Siis jõuame tingimuse t kehtimise korral käsujada tõene-käsud täitmisele eeltingimusega p Ù t. Kui tõene-käsud täitmise järel kehtib vahetingimus q₁, jõuame sel juhul valikulause lõppu vahetingimusega q₁.

Tingimuse t mittekehtimise korral jõuame käsujada väär-käsud täitmisele eeltingimusega p Ù Ø t. Kui väär-käsud täitmise järel kehtib vahetingimus q₂, jõuame sel juhul valikulause lõppu vahetingimusega q₂.

Kokkuvõttes peab valikulause täitmise järel kehtima vahetingimus q₁ Ú q₂.

Algoritm 2 Lahendab lineaarvõrrandi
Sisend: a, b --- võrrandi ax + b = 0 kordajad
Väljund: x₀ --- võrrandi lahend, kui see on üheselt määratud

sisesta a, b
kui a = 0
väljasta `Pole ühest lahendit'
muidu
x₀¬-b / a
väljasta `Lahend on ', x₀
lõppkui

Kindlasti tasub tähele panna, et kahene valikulause ei tarvitse olla samaväärne kahest ühesest valikulausest koosneva järjendiga

kui t
tõene-käsud
lõppkui
kui Ø t
väär-käsud
lõppkui

Kui tingimus t kehtib, võib tõene-käsud täitmine muuta programmi olekut nii, et esimesest valikulausest väljumise järel tingimus t enam ei kehti. Siis aga on Ø t tõene ja vastavalt täidetakse ka väär-käsud.

Kui mingil põhjusel on siiski vaja alternatiivse valikulause asemel just üheseid valikulauseid kasutada, võib eelmises lõigus kirjeldatud viga vältida tõeväärtusmuutuja t₀ kasutamise abil:

t₀¬t
kui t₀
tõene-käsud
lõppkui
kui Ø t₀
väär-käsud
lõppkui

Selles versioonis salvestatakse tingimuse t esialgne tõeväärtus muutujasse t₀, kus see (eeldusel, et tõene-käsud sellele muutujale uut väärtust ei omista) säilib ka teise valikulause jaoks.

Veidi keerulisema näitena vaatleme kahte erinevat algoritmi kolmest arvust maksimaalse leidmiseks.

Algoritm 3 Leiab kolmest arvust maksimaalse
Sisend: a, b, c --- uuritavad arvud
Väljund: x = max(a, b, c)

kui a ³ b Ù b ³ c
x¬a
lõppkui
kui a ³ c Ù c ³ b
x¬a
lõppkui
kui b ³ a Ù a ³ c
x¬b
lõppkui
kui b ³ c Ù c ³ a
x¬b
lõppkui
kui c ³ a Ù a ³ b
x¬c
lõppkui
kui c ³ b Ù b ³ a
x¬c
lõppkui

Algoritm 4 Leiab kolmest arvust maksimaalse
Sisend: a, b, c --- uuritavad arvud
Väljund: x = max(a, b, c)

x¬a
kui b > x
x¬b
lõppkui
kui c > x
x¬c
lõppkui

Kuigi mõlemad algoritmid saavutavad lõpuks sama tulemuse, kasutab algoritm 3 võrdluspredikaati 12, algoritm 4 aga vaid 2 korda, seega on nende algoritmide efektiivsuse vahe 6-kordne.

2.3.3 Mitmene valik

Paljudes programmikeeltes on olemas ka mitmene valik ehk lüliti (ingl switch), mis võimaldab mingi avaldise väärtuse järgi valida ühe paljudest tegevustest.

Mitmese valikulause üldkuju on

valik a
    variant v₁
       käsud-1
    variant v₂
       käsud-2
    ...
    variant v_n
       käsud-n
    muidu
       muidu-käsud
lõppvalik

Kui avaldise a väärtus on v₁, täidetakse käsud-1 ja jätkatakse algoritmi täitmist võtmesõnale lõppvalik järgnevast lausest, kui avaldise a väärtus on v₂, täidetakse käsud-2 ja jätkatakse võtmesõnale lõppvalik järgnevast lausest jne. Kui avaldise a väärtus ei ole ükski v_i väärtustest, täidetakse muidu-käsud ja jätkatakse siis valikukäsu järelt.

Sageli seavad programmikeeled realisatsiooni efektiivsuse huvides piiranguid sellele, millist tüüpi avaldisi ja väärtusi võib mitmeses valikus kasutada. Kui on vaja teha mitmene valik mingit muud tüüpi avaldise põhjal või keeles, kus sellist konstruktsiooni üldse pole, võib selle asemel kasutada korduvaid kaheseid valikuid. Programmi parema loetavuse huvides tuleks võimalusel siiski kasutada mitmest valikut, mitte seda muude vahenditega imiteerida.

2.4 Lausete pesastamine

Struktuursete programmikeelte oluline ja praktikas väga kasulik omadus on võimalus juhtkonstruktsioone üksteise sisse asetada ehk pesastada (ingl nest). See tähendab seda, et igale poole, kuhu võib kirjutada primitiivi, võib selle asemel panna ka keerulisema konstruktsiooni --- näiteks liitlause või valikulause.

Tegelikult oleme eelnevates näidetes pesastamist juba kasutanud, pannes valikulause sisse mitmest käsust koosneva järjendi (mis mäletatavasti oli ka üks juhtkonstruktsioonidest), samuti koostades järjendeid mitmetest valikulausetest.

Osutub, et järjend pole selles suhtes mingi erand, täpselt sama hästi võib ühe valikulause sisse panna ka teise valikulause, nagu näiteks järgnevas algoritmis, mis kontrollib, kas antud kolm arvu võivad olla mingi kolmnurga küljepikkused.

Algoritm 5 Kontrollib, kas antud arvud on kolmnurga küljepikkused
Sisend: a, b, c --- uuritavad arvud
Väljund: diagnoos tekstina ekraanil

kui a > 0 Ù b > 0 Ù c > 0
--- a, b, c sobivad pikkusteks
kui a + b > c Ù a + c > b Ù b + c > a
--- sobivad kolmnurga küljepikkusteks
väljasta `Jah'
muidu
--- ei sobi kolmnurga küljepikkusteks
väljasta `Ei'
lõppkui
muidu
--- ei sobi üldse pikkusteks
väljasta `Ei'
lõppkui

Lõigus 2.3.3 märgitud mitmese valiku realiseerimine kaheste valikute abil tuleb üsna loomulikult välja just pesastamise teel:

kui a = v₁
    käsud-1
muidu
    kui a = v₂
       käsud-2
    muidu
    ...
       kui a = v_n
          käsud-n
       muidu
          muidu-käsud
       lõppkui
    ...
    lõppkui
lõppkui

Ülesanded

Ülesanne 1 Kasutades tähistusi A = ``sajab vihma'', B = ``sajab lund'', C = ``on suvi'', D = ``on talv'', esitada lausearvutuse valemitena väited
kui sajab vihma, siis on suvi;
kui on talv, sajab lund;
suvel lund ei saja;
pole suvi ega talv.
Millised neist väidetest on tõesed?

Ülesanne 2 Kasutades eelmise ülesande tähistusi, sõnastada eesti keeles väited, mida esitavad valemid
A Ù B;
B É Ø C;
Ø(C Ù D).
Millised neist väidetest on tõesed?

Ülesanne 3 Kasutades tavalisi matemaatilisi tähistusi, esitada predikaatarvutuse valemitena väited
täisarvude hulgas leidub nullist suuremaid;
kõik naturaalarvud on negatiivsed;
kõik naturaalarvud kuuluvad täisarvude hulka.
Millised neist väidetest on tõesed?

Ülesanne 4 Sõnastada eesti keeles väited, mida esitavad valemid
" x Î Z : x Î R;
($ x Î Z : x < 0) Ù ($ x Î Z : x > 0);
$ x Î Z : (x < 0 Ù x > 0).
Millised neist väidetest on tõesed?

Ülesanne 5 Koostada tehte välistav ``või'' ja valemi

(p Ú q) Ù Ø (p Ù q)

tõeväärtustabelid ning veenduda, et nad on loogiliselt samaväärsed.

Ülesanne 6 Shefferi kriips on binaarne loogiline tehe, mille tulemus p | q on väär parajasti siis, kui p ja q on mõlemad tõesed. Shefferi kriips on universaalne tehe --- tema abil on võimalik avaldada kõik teised tehted; näiteks eituse võib avaldada kujul
Ø p = p | p.
Avaldada Shefferi kriipsu abil kõik lõigus 2.1.2 vaadeldud tehted.

Ülesanne 7 Kirjutada programm, mis sisestab kolm arvu a, b ja c ning väljastab need mittekahanevas järjekorras. Kontrollida, et programm töötab õigesti ka siis, kui mõned arvudest on omavahel võrdsed.

Ülesanne 8 Kirjutada programm, mis sisestab neli arvu a, b, c ja d ning väljastab need mittekahanevas järjekorras.

Ülesanne 9 Kirjutada programm, mis sisestab ruutvõrrandi
ax² + bx + c = 0
kordajad ja leiab selle reaalarvulised lahendid (kui need on olemas) või väljastab korrektse teate (kui võrrandil reaalarvulised lahendid puuduvad).

Ülesanne 10 Antud kahe kolmnurga küljepikkused a₁, b₁, c₁ ja a₂, b₂, c₂. Kirjutada programm, mis kontrollib, kas need kolmnurgad on kongruentsed, sarnased või erinevad.

Ülesanne 11 Antud kolm naturaalarvu i, j, k, mis rahuldavad tingimust 1 £ i < j < k £ 9. Kirjutada programm, mis kontrollib, kas nende arvudega märgitud ruudud asuvad allolevas tabelis samas reas, veerus või diagonaalis.

1	2	3
4	5	6
7	8	9

Ülesanne 12 Kirjutada programm, mis kontrollib, kas antud positiivne täisarv on liig- või lihtaasta number. (Aasta on liigaasta, kui tema number jagub neljaga, välja arvatud need aastad, mille number jagub sajaga, kuid ei jagu neljasajaga.)

Kirjandus

Tõnu Tamme, Tanel Tammet, Rein Prank. Loogika. Mõtlemisest tõestamiseni. Tartu Ülikool, 1997.: Kõige mahukam seni eesti keeles ilmunud formaalse loogika õpik, mis sobib nii lause- ja predikaatarvutuse põhjalikumaks tundmaõppimiseks kui ka muude loogikavaldkondadega tutvumiseks. 424 lk.
Ene Grauberg. Loogika ja vaidluskunst. Olion, 1989.: Põhiliselt loogikale kui väitluse ja veenmise aparaadile keskenduv õpik, matemaatilisi formalisme on vähem. 95 lk.
A. Kolman, O. Zich. Huvitav loogika. Valgus, 1970.: Populaarne sissejuhatus formaalse loogika alustesse. 118 lk.
David Gries. The Science of Programming. Springer, 1981.: Programmeerimise põhitõdede ja -meetodite formaalne käsitlus. Väga sobiv neile, kes tahaks rohkem ja põhjalikumaid näiteid loogika rakendamisest programmeerimisel. 382 lk.

1: Eituse tähistamiseks kasutatakse Ø p asemel sageli ka kirjaviise ~ p või p.
2: Konjunktsiooni tähistamiseks kasutatakse p Ù q asemel sageli ka kirjaviisi p & q.
3: Implikatsiooni tähistamiseks kasutatakse p É q asemel sageli ka kirjaviise p ® q või p Þ q.
4: Olukord on sarnane eelmises peatükis vaadeldud Greeri kolmanda seaduse mõttega --- formaalne loogika on abiks arutluste täpsel üleskirjutamisel, kuid ei asenda mõtlemist.
5: Ekvivalentsi tähistamiseks kasutatakse p º q asemel sageli ka kirjaviise p ~ q, p « q või p Û q.
6: Kirjaviisi ``<(2,4)'' nimetatakse prefiks-, ``2<4'' aga infikskujuks. Põhimõtteliselt pole põhjust, miks ka muid predikaate ei võiks P(x,y) asemel kirjutada kujul xPy.
7: Kokku on n erineva muutujaga valemi tõeväärtustabelis 2ⁿ rida.
8: Tõeväärtustabeli kirjalikul koostamisel kantakse sellesse iga tehte tulemus vastava tehtemärgi alla tehete sooritamise järjekorras, nagu näidatud valemite kohal olevate numbritega.
9: Hoiatuseks C ja Java kasutajatele --- kuigi tekstitüüpi muutujate võrdlemine tavalise võrdlusoperaatori == abil on mõlemas keeles süntaktiliselt korrektne, pole tulemus sageli sugugi ootuspärane. Tekstitüüpi väärtuste võrdlemiseks tuleb C's kasutada funktsioone strcmp() ja strncmp(), Javas aga klassi String meetodeid equals() ja compareTo().
10: Kahendsüsteemi kirjeldus on olemas peaaegu kõigis arvutiõpikutes ja ka paljudes matemaatikaõpikutes.
11: Lisaks on näha, et täielikud vahetingimused kasvavad tõesti väga ruttu suurteks ja kohmakateks avaldisteks, mistõttu järgnevas kasutame enamasti osalisi vahetingimusi.

A	B	Ø A	A Ù B	A Ú B	A É B	A º B
väär	väär	tõene	väär	väär	tõene	tõene
väär	tõene	tõene	väär	tõene	tõene	väär
tõene	väär	väär	väär	tõene	väär	väär
tõene	tõene	väär	tõene	tõene	tõene	tõene