Algoritmi-Matematiikka [version 11 Oct 2011 ed.] [PDF]

Zitiervorschau

ALGORITMIMATEMATIIKKA Keijo Ruohonen

1993

Kirjallisuutta ANDERSON, I.: A First Course in Combinatorial Mathematics. Oxford University Press (1979) G RAHAM , R.L. & K NUTH , D.E. & P ATASHNIK , O.: Concrete Mathematics. A Foundation for Computer Science. Addison-Wesley (1989) GRAY, P.: Logic, Algebra and Databases. Ellis Horwood (1985) GREENE, D.H. & K NUTH , D.E.: Mathematics for the Analysis of Algorithms. Birkhäuser (1982) G RIMALDI, R.P.: Discrete and Combinatorial Mathematics. An Applied Introduction. Addison-Wesley (1994) K NUTH , D.E.: The Art of Computer Programming I. Fundamental Algorithms. Addison-Wesley (1975) MCELIECE, R.J. & ASH, R.B. & ASH, C.: Introduction to Discrete Mathematics. McGraw-Hill (1989) RICHARDS, T.: Clausal Form Logic. An Introduction to the Logic of Computer Reasoning. Addison-Wesley (1989) ROBINSON, J.A.: Logic: Form and Function. The Mechanization of Deductive Reasoning. Edinburgh University Press (1979) ROGERS, R.: Mathematical Logic and Formalized Theories. North-Holland (1974) SCHÖNING, U.: Logic for Computer Scientists. Birkhäuser (1989) SKIENA, S.: Implementing Discrete Mathematics. Addison-Wesley (1990) TRUSS, J.K.: Discrete Mathematics for Computer Scientists. Addison-Wesley (1991)

SISÄLTÖLUETTELO 1

I LAUSELOGIIKKA ELI PROPOSITIOLOGIIKKA

1 2 4 4 5 9 10 11 14 16

1. Perusoperaatiot ja totuustaulut 2. Laskulakeja 3. Normaalimuodot 4. Implikaatio-operaattori 5. Päättely. Tautologiat. Sijoitus 6. Päättelyn apuneuvoja: Premissiksi siirto 7. Päättelyn apuneuvoja: Reductio ad absurdum (RAA) 8. Päättelyn apuneuvoja: Resoluutio 9. Aksiomatisointi

II 1. KERTALUVUN PREDIKAATTILOGIIKKA

16 16 18 21 21 22 25 27 30 37 37 39 44 45 49 51 51 55 57 59 59 61 62

1. 2. 3. 4. 5. 6. 7. 8. 9.

III

Yleistä Kvanttorit Predikaattikalkyyliä Ekvivalenssi Päättely Normaalimuoto Resoluutio Päättelyn anatomiaa. Herbrandin universumi Resoluutio Hornin konjunkteille. PROLOG

KOMBINATORIIKKAA 1. 2. 3. 4. 5.

Kombinaatiot Binomikertoimet Dirichlet’n laatikkoperiaate. Inkluusio-ekskluusio-periaate Permutaatiot Stirlingin kaava

IV KOKONAISLUKUFUNKTIOT 1. Kertalukunotaatio 2. Katto ja pohja 3. Kongruenssilaskentaa

V REKURSIOKAAVAT 1. Yleistä 2. Ensimmäisen kertaluvun lineaarinen rekursiokaava 3. Vakiokertoiminen lineaarinen rekursiokaava

HAKEMISTO

1

I

L AUSELOGIIKKA ELI PROPOSITIOLOGIIKKA

1. Perusoperaatiot ja totuustaulut Lauselogiikka käsittelee ns. propositioita eli lauseita, joilla on ns. totuusarvo, "tosi" (T) tai "väärä" (V). Mitään muuta lauseen ominaisuutta ei oteta huomioon. Lauseita yhdistellään ns. loogisin operaatioin eli konnektiivein. Tuttuja konnektiiveja ovat "ja" (merkitään AND tai ∧, joskus &), "tai" (merkitään OR tai ∨) sekä "ei" (merkitään NOT tai ~, joskus ¬). Totuusarvot muodostuvat tällöin seuraavasti: A T T V V

B T V T V

~A V V T T

A∧B T V V V

A∨B T T T V

Yo. taulu on ns. totuustaulu. Huomaa, että A∨B on tosi silloinkin, kun sekä A että B on tosi (ehkä hieman toisin kuin tavallisessa kielenkäytössä). Konnektiivi, jolle näin ei ole, on ns. eksklusiivinen "tai" (merkitään XOR, joskus ⊕ tai +), jonka totuustaulu on A T T V V

B T V T V

A XOR B V T T V

Mahdollisia kahden lauseen A ja B konnektiiveja on ilmeisesti 24 = 16 kpl. Yllä on niistä kolme. Nämä voidaan kuitenkin kaikki ilmaista yo. operaatioiden ∧, ∨ ja ~ avulla. Esimerkiksi A XOR B = (A ∧ (~B)) ∨ ((~A) ∧ B), kuten voidaan totuustaulua käyttäen todeta. Huom! Itse asiassa yksi ainoa operaatiokin riittää. Tällainen on esimerkiksi "ei ... eikä" (merkitään NOR, joskus ↓), jonka totuustaulu on

2 A T T V V

B T V T V

A NOR B V V V T

Silloin ~A = A↓A, A∧B = (A↓A)↓(B↓B) ja A∨B = (A↓B)↓(A↓B). Jatkossa sovitaan, että operaatioiden suoritusjärjestys on ~, ∧, ∨ (eli sama kuin aritmeettisten operaatioiden -, ˘, +), jolloin sulkuja jätetään paljolti pois. Esimerkiksi edellä esiintyvä kaava on silloin A ∧ ~B ∨ ~A ∧ B. Ja-konnektiivia sanotaan usein konjunktioksi, tai-konnektiivia disjunktioksi ja eitä negaatioksi. Vastaavat operaatiot ovat konjungointi, disjungointi sekä negeeraus. Huom! Myös lauseista yo. operaatioin saatavat lausekkeet ovat itse asiassa lauseita, sillä niillä on totuusarvot. Sanaa lauseke käytetäänkin ilmaisemaan sitä, että lause on kirjoitettavissa muiden lauseiden avulla käyttäen loogisia operaatioita.

2. Laskulakeja Totuustauluja käyttäen voidaan todentaa seuraavat laskulait (jotka muuten tekevät lauselogiikasta ns. Boolen algebran): 1)

 A∧B = B∧A   A∨B = B∨A

2)

 (A∧B)∧C = A∧(B∧C)   (A∨B)∨C = A∨(B∨C)

3)

A∧T=A  A∨V=A

4)

A∧V=V  A∨T=T

(vaihdantalait)

(liitäntälait)

3 5)

 A ∧~A = V   A ∨~A = T

6)

 A∧(B∨C) = A∧B ∨ A∧C   A∨(B∧C) = (A∨B)∧(A∨C)

(osittelulait)

Pitkissä konjunktio- ja disjunktioketjuissa ei tarvitse käyttää sulkeita, sillä tulos on sulutuksesta riippumaton. Siis kirjoitetaan A1 ∧ A2 ∧˘˘˘∧ An (joka on tosi täsmälleen silloin, kun A1,A2,...,An ovat kaikki tosia) ja A1 ∨ A2 ∨˘˘˘∨ An (joka puolestaan on tosi täsmälleen silloin, kun ainakin yksi lauseista A1,A2,...,An on tosi). Asia on päätellen aika selvä*. Se voitaisiin todistaa formaalisestikin lähtien liitäntälaeista, mutta tämä ei ole aivan helppoa. Lähtien laeista 1) - 6) voitaisiin todistaa kaikki muut laskulait (helpommalla usein pääsee, kun käyttää totuustauluja). Tällaisia ovat esimerkiksi 7)

~~A = A

(komplementäärisyyslaki)

8)

 A∧A = A   A∨A = A

9)

 A∧(A∨B) = A   A∨(A∧B) = A

10)

 ~(A∧B) = ~A∨~B   ~(A∨B) = ~A∧~B

(idempotenssilait)

(absorptiolait)

(de Morganin lait)

Toistuvasti de Morganin lakeja käyttäen saadaan lisäksi lait  ~(A1 ∧ A2 ∧˘˘˘∧ An) = ~A1 ∨ ~A2 ∨˘˘˘∨ ~An   ~(A1 ∨ A2 ∨˘˘˘∨ An) = ~A1 ∧ ~A2 ∧˘˘˘∧ ~An Jos tehdään vaihdokset ∧

*

← →

∨

ja T

toisin kuin esimerkiksi matriisitulolle!

← →

V,

4 saadaan laskulaista aina toinen laskulaki (joskus sama). Tämä pätee yo. laskulaeille ja, koska kaikki lait saadaan laeista 1) - 6), kaikille laskulaeille. Tällä tavoin toisiinsa liittyvät lait ovat keskenään duaaliset.

3. Normaalimuodot Osittelulakeja käyttäen voidaan "kirjoittaa auki" lausekkeita, aivan kuten aritmetiikassakin. Kun lauseke kirjoitetaan auki käyttäen ensimmäistä osittelulakia ja de Morganin lakeja sekä sievennetään sitten niin pitkälle kuin mahdollista komplementäärisyyslakia käyttäen, saadaan se ns. disjunktiiviseen normaalimuotoon (DNF) D1 ∨˘˘˘∨ Dn, missä kukin ns. disjunkti Di on muotoa Di = Ai1 ∧˘˘˘∧ Aimi, missä puolestaan kukin ns. literaali Aij on lause tai lauseen negaatio. Vastaavasti, jos 1. osittelulain sijasta käytetään pelkästään toista osittelulakia (ja de Morganin lakeja ja sievennetään), saadaan lauseke ns. konjunktiiviseen normaalimuotoonsa (CNF) (C1) ∧˘˘˘∧ (Cn), missä konjunktit Ci ovat literaaliensa disjunktioita, ts. Ci = Ai1 ∨˘˘˘∨ Aimi. Huom! Disjunkteista ja konjunkteista käytetään usein yhteistä nimeä klausa (engl. clause).

4. Implikaatio-operaattori "Tavallisessa" päättelyssä esiintyy "jos ..., niin"-päätelmiä. Koska kyse on totuusarvoista, lauselogiikassa täytyy olla vastine eli "jos A, niin B"-päätelmä ja se on jokin niistä 16 mahdollisesta konnektiivista. Katsomalla todetaan, että ainoa valinta on ns. implikaatio (merkitään →), jonka totuustaulu on

5 A T T V V

B T V T V

A→B T V T T

Lausuttuna pykälän 1 operaatioiden avulla implikaatio on A→B = ~A∨B.

Huom! Usein päätelmä tehdään käänteisesti. Se on sallittua, sillä A→B = ~A∨B = B∨~A = ~~B∨~A = (~B)→(~A). Ekvivalenssi "jos ja vain jos" (merkitään ↔) on myös looginen operaatio. Se on luonnollisesti laskua

A↔B = (A→B)∧(B→A) = (~A∨B)∧(~B∨A)

= (A∧B) ∨(~A∧~B).

Huomaa, että → ei ole vaihdannainen, ts. A→B ≠ B→A, eikä myöskään liitännäinen, ts. (A→B)→C ≠ A→(B→C). Suoritusjärjestyksessä → tulee operaatioiden ~, ∧ ja ∨ jälkeen ja ↔ vielä sen jälkeen.

5. Päättely. Tautologiat. Sijoitus Laskulakeja käyttäen voidaan muokata loogisia lausekkeita. Toisaalta logiikan semanttiseen olemukseen kuuluu päättely: "Jos lausekkeet A1,...,An ovat tosia, niin myös lauseke B on tosi." Päättelyn on oltava pitävä, ts. se on voitava todistaa oikeaksi. Tätä varten sallitaan päättely vain tietyillä ns. päättelysäännöillä, joita kylläkin voi käytössä olla paljon. Käytettyjen päättelysääntöjen tulee olla kyllin vahvat, jotta päästään haluttuun johtopäätökseen B. Klassiset päättelysäännöt ovat modus ponens (MP):

sekä

Jos A on tosi ja A→B on tosi, niin myös B on tosi.

6 ketjusääntö (KS): Jos A→B on tosi ja B→C on tosi, niin myös A→C on tosi. Nämä ovat, paitsi varsin luonnollisia, myös perusteltavissa "laskien", sillä A∧(A→B) → B = T ja (A→B)∧(B→C) → (A→C) = T. Päättely etenee päättelyketjuna: Lähdetään annetuista oletuksista A1,…, An (ns. premissit), siis siitä että A1,…,An ovat tosia, ja päätellään uusia tosia lausekkeita käyttäen päättelysääntöjä. Lausekkeita, jotka voidaan olettaa tosiksi, tulee näin koko ajan lisää. Jatketaan kunnes haluttu johtopäätös B on näin saatu pääteltyä. Merkitään A1,…,An |= B (tarkemmin sanoen tämä merkintä tarkoittaa, että vastaava päättely on oikea; toisinaan merkitään myös A1,…,An |- B). Huom! Toinen tapa todistaa päättely oikeaksi olisi totuustaulujen käyttö, mutta se on yleensä tavattoman työlästä, sillä A1,…,An ja B ovat useinkin hyvin mutkikkaita lausekkeita tai sitten n on suuri (eli premissejä on paljon). Yo. tavalla päättely voidaan suorittaa täysin formaalisesti käyttäen symboleja ∧ , ∨ , ~ , → , ↔ , ( ja ) sekä tarvittavaa määrää symboleja niille propositioille, jotka eivät ole lausekkeita (ts. eivät ole ilmaistavissa toisten propositioiden lausekkeina), ns. atomeille. Syntaksi BNF-notaatiolla*: 〈lauseke〉 ::= 〈propositio〉 | ~〈propositio〉 | 〈propositio〉 〈operaatio〉 〈propositio〉 〈operaatio〉 ::= ∧ | ∨ | → | ↔ 〈propositio〉 ::= 〈atomi〉 | (〈lauseke〉) (huomaa, miten tämä syntaksi tuottaa "liikaa" sulkuja). Päättelysääntöjä voidaan nyt käyttää täysin mekaanisena symbolimanipulaationa. Vaikeutena on tietysti löytää oikea päättelyketju.

*

"BNF" = Backus-Naur form

7 Lauseke, joka on tosi riippumatta siinä esiintyvien atomien totuusarvoista, on ns. tautologia. Jos A on tautologia, on se pääteltävissä tavallaan mistä tahansa premisseistä, A:han on joka tapauksessa tosi. Tätä merkitään |= A (toisinaan myös |- A). Päättelyketjun missä tahansa vaiheessa, erityisesti sen alussa, voi siis ottaa käyttöön tautologian. Luonnollisesti, jos tautologian jonkin atomin tilalle kirjoitetaan joka paikkaan sama lauseke, niin tulos on edelleen tautologia. Lausekkeen todistaminen tautologiaksi käy jollain seuraavista tavoista: 1 ) muodostetaan lausekkeen totuustaulu (useimmiten työlästä); 2 ) kirjoitetaan lauseke jompaankumpaan normaalimuotoonsa ja sievennetään niin pitkälle kuin mahdollista käyttäen laskulakeja; tulokseksi pitää saada T (toisinaan sievennys on helppoa suoraankin ilman normaalimuotoa); tai 3 ) todistetaan lauseke formaalisesti tautologiaksi lähtien annetuista aksiomista ja käyttäen päättelysääntöjä (ks. pykälä 9). Tautologiat ovat lauselogiikan teoreemoja, siis loogisia totuuksia. Hyödyllisiä tautologioita ovat mm. edellä olleet MP ja KS A∧(A→B) → B (A→B)∧(B→C) → (A→C) sekä esimerkiksi ~B∧(A→B) → ~A ja (A→B) → (A∨C → B∨C). MP:n ja KS:n lisäksi myös kaksi vm. tautologiaa ovat tulkittavissa päättelysäännöiksi. Itse asiassa pätee yleisempikin tulos: LAUSE 1. A |= B täsmälleen silloin, kun A→B on tautologia (eli |= A→B). Todistus. Jos A |= B, niin saadaan totuustaulu A T V V

B T T V

A→B T T T

8 joten tällöin A→B on aina tosi. (Huomaa, että oletus A |= B sulkee pois tapauksen, jossa A:n totuusarvo on T ja B:n V.) Jos taas A→B on tautologia, niin implikaation totuustaulun mukaan A:n totuudesta seuraa B:n totuus, jolloin A |= B. ■ SEURAUS. A1,…,An |= B täsmälleen silloin, kun |= A1 ∧˘˘˘∧ An → B. Todistus. A1,…,An ovat kaikki yhtaikaa tosia täsmälleen silloin, kun A1∧˘˘˘∧ A n on tosi. ■ Eräs päättelyn apuväline on sijoitus: Jos lausekkeessa A1 esiintyy osana lauseke B ja A2 saadaan A1:stä sijoittamalla B:n paikalle lauseke C (ei välttämättä joka paikkaan), niin A1, B↔C |= A2. Ts. ekvivalentteja lausekkeita voidaan päättelyn aikana mielin määrin korvata toisillaan. Erityisesti, jos B↔C on tautologia, niin tällöin A1 |= A2. Sijoituksen pätevyys seuraa suoraan totuustaulujen perusteella, sillä jos B↔C on tosi, niin B:n ja C:n totuusarvot ovat samat. Jos |= B↔C, niin B=C on (Boolen algebran) laskulaki. Tässä tapauksessa si-joitus onkin siis laskulain käyttöä. Toisaalta, jos B=C on laskulaki, niin sel-västi |= B↔C ja tätä voidaan käyttää yo. päättelyssä A1 |= A2 . Laskulain käyttö klassisessa päättelyssä onkin siis "naamioitunut" sijoitukseksi. Kun tämä tiedetään, voidaan laskulakeja tietysti käyttää "suoraankin" päättelyketjun välitulosten muokkaamisessa. MP ja KS ovat "luonnollisia" päättelysääntöjä. Kumpikin riittää yksinäänkin, jos "apuna" käytetään sopivia tautologioita. MP:n käyttö voidaan korva-ta KS:n käytöllä, sillä päättely A, A→B |= B

(MP)

voidaan laskulakeja A = A∨~A → A

ja

A∨~A → B = B

A ↔ A∨~A → A

ja

A∨~A → B ↔ B

eli tautologioita

käyttäen (sijoitus!) pukea KS-päättelyksi A∨~A → A , A→B |= A∨~A → B. Vastaavasti voidaan KS korvata MP:llä, jos KS otetaan käyttöön tautologiana (A→B)∧(B→C) → (A→C).

9 Tällöin päättely A→B, B→C |= A→C

(KS)

voidaan pukea MP-päättelyksi (A→B)∧(B→C) , (A→B)∧(B→C) → (A→C) |= A→C. Tautologioiden käyttö päättelyssä ei yleisesti ole aivan niin mutkatonta kuin yllä, sillä on tiedettävä mitä tautologioita käyttää ja että kyseessä todella ovat tautologiat. On huomattava, että useinkaan ei itse asiassa kiinnosta päättelyn A1,…,An |= B oikeellisuus, vaan miten se tehdään tehokkaasti askel askeleelta. Seuraavassa kolmessa pykälässä on esitetty apuneuvoja, joilla päättely voidaan tehdä tehokkaaksi.

6. Päättelyn apuneuvoja: Premissiksi siirto Menettely esiintyy jo Lauseessa 1 ja sen Seurauksessa. Yleisemmin voidaan esittää LAUSE 2. Päättelyn A1,…,An |= B→C kanssa ekvivalentti päättely on A1,…, An,B |= C (ts. siirretään B premissiksi). Todistus. Otetaan käyttöön laskulaki X → (Y→Z) = X∧Y → Z (eli tautologia X → (Y→Z) ↔ X∧Y → Z sijoituksen kautta). Silloin A1,…,An,B |= C Lauseen 1

⇔*

|= A1 ∧˘˘˘∧ An ∧ B → C

Seuraus laskulaki

⇔

|= A1 ∧˘˘˘∧ An → (B → C)

Lauseen 1

⇔

A1,…,An |= B→C. ■

Seuraus *

Tämä ⇔ on metakielen ekvivalenssi, kun ↔ taas on looginen operaatio.

10 7. Päättelyn apuneuvoja: Reductio ad absurdum (RAA) LAUSE 3. Päättelyn A1,…,An |= B→C kanssa ekvivalentti päättely on A1,…, An,~C |= ~B. Todistus. Otetaan käyttöön laskulaki X→Y = ~Y→~X (ks. sivu 5). Silloin A1,…,An,~C |= ~B Lause 2

⇔

A1,…,An |= ~C→~B

laskulaki

⇔

A1,…,An |= B→C. ■

SEURAUS (RAA). Päättelyn A1,…,An |= B→C kanssa ekvivalentti päättely on A1,…,An,B,~C |= V (yleensä V on muotoa D∧~D). Todistus. Otetaan käyttöön laskulaki ~B = B→V. Silloin A1,…,An |= B→C Lause 3

⇔

A1,…,An,~C |= ~B

laskulaki

⇔

A1,…,An,~C |= B→V

Lause 2

⇔

A1,…,An,~C,B |= V. ■

Huom! Mieti tarkasti, milloin muotoa A1,…,An |=V oleva päättely on oikea. Lause 3 on sellaisenaankin usein käyttökelpoinen. RAA on matematiikan vastaoletuksen käytön vastine lauselogiikassa. Sen etuna on tavoitteen

11 (=V) yksinkertaisuus. RAA on varsin vahva päättelystrategia, kun se sopii: pitkä ja vaikeasti löydettävä suora päättely korvautuu useinkin varsin lyhyellä ja helposti löydettävällä käänteisellä päättelyllä, kuten matematiikan todistuksista huomataan.

8. Päättelyn apuneuvoja: Resoluutio KS yhdessä RAA:n kanssa muodostaa vahvan ja helposti mekanisoitavan päättelymenetelmän. (Kuten s. 8 todettiin, voidaan MP:n käyttö korvata KS:n käytöllä.) Tällöin KS kirjoitetaan seuraavaan muotoon: Jos ~A→B on tosi ja B→C on tosi, niin myös ~A→C on tosi. Koska toisaalta ~A→B = A∨B, B→C = C∨~B ja ~A→C = A∨C, saadaan KS edelleen muotoon resoluutiosääntö (RS):

Jos A∨B on tosi ja C∨~B on tosi, niin myös A∨C on tosi.

RAA saadaan käyttöön joko sellaisenaan tai muodossa LAUSE 4. Päättelyn A1,…,An |= B kanssa ekvivalentti päättely on A1,…,An, ~B |= V. Todistus. Otetaan käyttöön laskulaki B = T→B. Silloin A1,…,An |= B laskulaki

⇔

A1,…,An |= T→B

RAA

⇔

A1,…,An,T,~B |= V

Lause 2

⇔

A1,…,An,~B |= T→V

laskulaki

⇔

A1,…,An,~B |= V. ■

12 RAA:ia tai Lausetta 4 käyttäen voidaan rajoittua muotoa A1,…,An |= V oleviin päättelyihin.

Resoluutiomenettely 1 ) Kirjoitetaan kukin lausekkeista A1,…,An konjunktiiviseen normaalimuotoon, jonka literaalit ovat atomeja tai atomien negaatioita. (Ks. pykälä 3.) Kerätään yhteen kaikki näin saadut konjunktit: C1,…,Cm. Päättelyt A1,…,An |= V ja C1,…,Cm |= V ovat ilmeisesti ekvivalentit, sillä A1 ∧˘˘˘∧ An = C1 ∧˘˘˘∧ Cm ja päättelyt A1,…,An |= V ja A1 ∧˘˘˘∧ An |= V ovat samat, samoin päättelyt C1,…,Cm |= V ja C1 ∧˘˘˘∧ Cm |= V. 2 ) Siirrytään tutkimaan päättelyä C1,…,Cm |= V. 3 ) Jos konjunktien C1,…,Cm joukosta löytyy kaksi konjunktia, joista yhdessä on literaalina jokin atomi sellaisenaan ja toisessa sama atomi negeerattuna, niin sovelletaan RS:ä. Esimerkiksi, jos X∨Y∨Z∨~W ja Y∨W∨U ovat tällaiset konjunktit, niin niistä päätellään uusi konjunkti X∨Y∨Z∨U käyttäen RS:ä. (Huomaa myös toisen idempotenssilain käyttö literaalien toiston eliminoimiseksi uudessa konjunktissa.) Saatu uusi konjunkti lisätään konjunktilistaan C1,…,Cm. Jos toinen konjunkteista on yksiliteraalinen, mutta toinen taas ei, esimerkiksi X∨~Y∨Z ja Y,

13 voidaan RS:ä soveltaa, kun ajatellaan Y muodossa V∨Y. Uusi konjunkti on nyt X∨Z∨V eli X∨Z. Jos taas molemmat konjunktit ovat yksiliteraalisia, esimerkiksi X ja ~X, päätellään V ja lopetetaan. (Tämäkin voidaan katsoa RS:n soveltamiseksi: Kirjoitetaan vain X = X∨V ja ~X = ~X∨V ja päätellään V∨V = V.) 4 ) Kohtaa 3) toistetaan, kunnes V on saatu pääteltyä tai uusia konjunkteja ei enää synny RS:n avulla. (Äärellistä literaalimäärää käyttäen syntyy vain äärellinen määrä konjunkteja, joissa ei ole toistuvia literaaleja.) VÄITE. Jos menettely pysähtyy, mutta V:ä ei ole saatu pääteltyä, ei päättely ollut alunperinkään mahdollinen, ts. lausekkeiden A1,…,An (tai vastaavasti konjunktien C1,…,Cm) atomeille voidaan valita sellaiset totuusarvot, että A1,…,An (ja C1,…,Cm) saavat kaikki totuusarvon T. Matemaattinen todistus tälle tosiasialle on vähän konstikas: Todistus. Tarkastellaan niitä konjunkteja, jotka ovat käsillä prosessin pysähtyessä ilman, että V:ä olisi päätelty. Olkoot kaikki tällöin esiintyvät atomit (jossain järjestyksessä) X1 ,..., Xk . Konstruoidaan literaalijono Y1 ,…, Yk , missä Y i = Xi

tai

Yi = ~Xi ,

seuraavasti:  X1 , jos ~X1 ei ole konjunkti Y1 = ~X , jos ~X on konjunkti  1 1

ja jokaisessa konjunktissa esiintyy mui Xi , jos takin literaaleja kuin ~Y1,…,~Yi-1,~Xi Yi =  ~Xi , jos jossain konjunktissa esiintyy vain  literaaleja ~Y1,…,~Yi-1,~Xi . Valitaan sitten atomeille X1,…,Xk totuusarvot siten, että Y1,…,Yk ovat tosia. Tällöin kaikki konjunktit (ja erityisesti C1,…,Cm) ovat myös tosia, kuten voidaan todeta asettamalla vastaoletus*: Jokin konjunkteista saa totuusarvon V , ts. sen kaikki literaalit ovat joukossa ~Y1,…,~Yk (siis "vääriä"). *

Tässäkin vastaoletus (eli "metakielen" RAA) on tehokkaampi kuin suora todistus!

14 Näytetään, että vastaoletuksesta seuraa ristiriita. Valitaan pienin sellainen indeksin arvo j, että jonkin konjunktin, sanotaan C:n, kaikki literaalit ovat joukossa ~Y1,…,~Yj. Silloin Yj = ~X j (muutoin eo. Yj:n määrittely ei toteudu). Koska j on pienin mahdollinen, ~Y j (eli X j) esiintyy C:ssä. Edelleen Yj:n määrittelyn nojalla on toinen konjunkti, sanotaan C', jonka kaikki lite-raalit ovat joukossa ~Y1,…,~Yj-1,~Xj (eli joukossa ~Y1,…,~Yj-1,Yj). Nyt Y j (eli ~Xj) esiintyy C':ssa, muuten sen kaikki literaalit olisivat jo joukossa ~Y1,…,~Yj-1 ja j ei olisikaan pienin mahdollinen. Kun sovelletaan RS:ä C:hen ja C':uun, saadaan konjunkti C", jossa esiintyvät literaalit ovat joukossa ~Y1,…,~Yj-1. (Huomaa, että j > 2, sillä muuten C = Xj ja C' = ~X j ja V voitaisiin päätellä.) Nyt C" on myös tarkasteltujen konjunktien joukossa, (sillä j on pienin mahdollinen). ■ Resoluutioperiaatetta käyttäen voidaan näin ollen suorittaa kaikki päättelyt. Käytännössä päättelyn ollessa mahdollista, niiden konjunktien valinta, joihin RS:ä sovelletaan, on suoritettava "harkiten". (Asiaan palataan seuraavassa luvussa.) Usein merkitään V =

∞ ja puhutaan tyhjästä konjunktista.

9. Aksiomatisointi Tautologiat ovat yleispäteviä loogisia totuuksia, ts. lauselogiikan teoreemoja. Teorian aksiomatisoinnilla tarkoitetaan menettelyä, jossa tietyistä aksiomista voidaan sovittu(j)a päättelysääntö(j)ä käyttäen johtaa kaikki teorian teoreemat (tai ainakin "kyllin suuri osa" niistä). Lauselogiikan aksiomat ovat luonnollisesti tautologioita. Aksiomien valintoja tunnetaan lukuisia. Eräs valintakriteeri on "taloudellisuus": "turhia" aksiomia, ts. sellaisia, jotka voidaan johtaa muista aksiomista, ei oteta mukaan. "Taloudellinen" aksiomasysteemi voi kuitenkin olla vaikeakäyttöinen. "Turhia" aksiomia otetaankin joskus mukaan teoreemojen johtojen helpottamiseksi. Eräs lauselogiikan aksiomatisointi Annetaan ensin ns. aksiomakaaviot (kolme kpl): (I)

P → (Q→P)

(II)

(P → (Q→R) ) → ((P→Q) → (P→R) )

( I I I ) (~Q→~P) → (P→Q)

15 Varsinaiset aksiomat (äärettömän monta) saadaan sijoittamalla aksiomakaavioissa esiintyvien symbolien P, Q ja R paikalle kaikilla mahdollisilla tavoilla kulloinkin käsillä olevista atomeista muodostetut lausekkeet. Huom! Jos kaaviossa esiintyy sama symboli monta kertaa, on sen paikalle sijoitettava joka kohtaan sama lauseke. Koska aksiomakaaviot ovat tautologioita, ovat myös kaikki aksiomat tautologioita. Päättelysääntönä on MP, ts. "tyypillinen" johdon askel on A , A→B |- B. Huom! Syntaktisen johdon merkkinä käytetään merkkiä |sen) päättelyn merkkinä merkkiä |= .*

, (semantti-

Aksiomakaavioissa esiintyy vain loogisia operaatioita ~ ja →. Näillä tultaisiin toimeen sellaisenaankin, sillä A∨B = ~A→B, A∧B = ~(A→~B) ja A↔B = (A→B) ∧ (B→A). Teoreeman (siis tautologian) (syntaktista) johtoa kutsutaan teoreeman todistukseksi. Voidaan osoittaa, että eo. aksiomista lähtien voidaan johtaa tarkalleen kaikki tautologiat. (Selvästi ei muita kuin tautologioita voida johtaa: Jos A ja A→B ovat tautologioita, niin samoin on B.) Jos A on aksiomien joukko, josta teoreema B voidaan johtaa, merkitään A |- B (tai vain |- B, jos A on sovittu). Lauselogiikassa |- B merkitsee, että B on tautologia eli samaa kuin |= B.

*

Joissain kirjoissa nämä ovat tosin vaihtaneet paikkaa!

16

II

1. KERTALUVUN PREDIKAATTILOGIIKKA

1. Yleistä Lauselogiikan propositiot (lausekkeet) ovat totuusarvomielessä atomiensa funktioita, ns. Boolen funktioita. Atomien totuusarvon määrittelyalue on tietysti {T,V}. Yleisemmin voitaisiin ottaa käyttöön yksi tai useampia muuttujia eli parametreja x,y,z,… , joiden määrittelyalueillaan saamista arvoista "lausekkeen" P(x,y,z,…) totuusarvo riippuu. Tällaisia "lausekkeita" kutsutaan (muuttujiensa) predikaateiksi. Koska predikaatit ovat totuusarvoisia, niitä voidaan yhdistellä ja muokata tavalliseen tapaan lauselogiikan operaatioin. Tapa, jolla predikaatti määritellään, riippuu usein sen muuttujien määrittelyalueista. Esimerkiksi, jos muuttujien määrittelyalue on reaalilukujen joukko Ä, voidaan predikaattien määrittelyssä käyttää tuttuja operaatioita, funktioita ja relaatioita +, -, ˘, /, ¢, =, > , jne.. Huom! Muuttujien määrittelyalueet voivat olla varsin mielivaltaisia. Kuitenkaan muuttujien arvot eivät saa olla joukkoja, jos ko. joukon alkioita on jonkin (toisen) muuttujan määrittelyalueessa. Muuttujien arvot eivät myöskään saa olla funktioita tai predikaatteja, jos näillä on yhteisiä muuttujia jonkin predikaatin kanssa. Muussa tapauksessa kyseessä on korkeamman kuin 1. kertaluvun logiikka, jollaisia ei tässä kurssissa käsitellä.

2. Kvanttorit Universaalikvanttori eli kaikkikvanttori ∀ Se, että predikaatti P(x) on tosi kaikilla x:n määrittelyalueen arvoilla, ilmaistaan predikaattilogiikassa käyttäen kaikkikvanttoria ∀: (∀x)P(x). Tulos voidaan tulkita propositioksi, joka on tosi tarkalleen silloin, kun P(x) on tosi kaikilla x:n arvoilla. Jos predikaatissa on x:n lisäksi muitakin muuttujia y,z,… , voidaan myös kirjoittaa (∀x)P(x,y,z,…). Tulos ei ole nyt propositio, vaan muuttujien y,z,… predikaatti.

17 Eksistentiaalikvanttori eli olemassaolokvanttori ∃ Se, että predikaatti P(x) on tosi jollakin x:n määrittelyalueen arvolla, ilmaistaan olemassaolokvanttorin ∃ avulla: (∃x)P(x). Jälleen tulos voidaan tulkita propositioksi, joka on tosi tarkalleen silloin, kun P(x) on tosi ainakin yhdellä x:n arvolla. Huom! (∃x)P(x) on siis tosi myös, jos P(x) toteutuu useammallakin x:n arvolla kuin vain yhdellä. Erityisesti, jos (∀ x)P(x), niin myös (∃x)P(x). Jos halutaan ilmaista, että P(x) on tosi tarkalleen yhdellä x:n arvolla, kirjoitetaan (∃| x) P(x).

Muotoa (∀x)P(x,y,z,…)

tai

(∃x)P(x,y,z,…)

olevissa ilmaisuissa muuttujan x sanotaan olevan sidottu ja muuttujien y,z,… sanotaan olevan vapaita. Sidottu muuttuja voidaan aina vaihtaa toiseksi, kunhan määrittelyalue pysyy samana: esimerkiksi propositiot (∀x)P(x)

ja

(∀t)P(t)

ja

(∃t)P(t,y,z,…),

ovat samat, samoin predikaatit (∃x)P(x,y,z,…)

olettaen, että x:n ja t:n määrittelyalueet ovat samat. Mutkikkaammissa ilmaisuissa sama muuttuja voi esiintyä sekä sidottuna että vapaana, esimerkiksi ilmaisussa

((∃x)P(x,y,z) ) ∨ Q(x,y) x esiintyy sekä vapaana että sidottuna (y ja z esiintyvät vain vapaina). Tällaisessa tapauksessa sidottu muuttujan esiintymä voidaan tarvittaessa korvata uuden muuttujan sidotulla esiintymällä, esimerkiksi yo. ilmaisu voitaisiin korvata ilmaisulla

((∃t)P(t,y,z) ) ∨ Q(x,y), jälleen olettaen, että x:n ja t:n määrittelyalueet ovat samat. Itse asiassa voi-taisiin olettaa, ettei ilmaisuissa esiinny samaa muuttujaa sekä sidottuna et-tä vapaana. Näin ei kuitenkaan aina tehdä.

18 Kvanttorien käyttöön voidaan liittää seuraava väljä nyrkkisääntö: Kaikkikvanttori liittyy yleensä implikaatioon (tai disjunktioon) ja olemassaolokvanttori konjunktioon, ts. esimerkiksi ilmaisut (∀x) ( P(x,y) → Q(x,y)) (eli (∀x) ( ~P(x,y) ∨ Q(x,y)) ) ja (∃x) ( P(x,y) ∧ Q(x,y)) sekä muut niiden kaltaiset ilmaisut ovat "tyypillisiä".

3. Predikaattikalkyyliä Väljästi sanoen predikaattikalkyyli tarkoittaa sellaisten ilmaisujen manipulaatiota ja tarkastelua, joissa esiintyy predikaatteja (sekä näiden yhteydessä funktioita, ks. s. 16), propositioita, kvanttoreita ja lauselogiikan operaatioita. Kvanttorien yhdistelmät Välittömästi toisiaan seuraavien samantyyppisten kvanttorien järjestys on yhdentekevä, ts. esimerkiksi (∀x) ( (∀y)P(x,y,z) )

ja

(∀y) ( (∀x)P(x,y,z) )

ovat samat, samoin (∃x) ( (∃y)P(x,y,z) )

ja

(∃y) ( (∃x)P(x,y,z) ) .

Peräkkäisten erityyppisten kvanttorien yhdente-kevä. Esimerkiksi (∀x) ( (∃y)P(x,y,z) )

ja

järjestys

sen

sijaan

ei

ole

(∃y) ( (∀x)P(x,y,z) )

eivät yleensä ole samat. Peräkkäiset kvanttorit kirjoitetaan usein yhteen tai ilman sulkeita, siis esimerkiksi (∀x,y)P(x,y,z)

ja

(∃y)(∀x)P(x,y,z).

Koska sidottuja muuttujia saa vaihtaa, voidaan tarvittaessa olettaa, että jokaisella kvanttorilla on oma sidottu muuttujansa ja että mikään näistä sidotuista muuttujista ei esiinny samassa ilmaisussa vapaana.

19 Kvantifioitujen lausekkeiden negeeraus Kvantifioiduille lausekkeille pätevät yleistetyt de Morganin lait:  ~ ( (∀x)P(x,y,z,…) ) = (∃x) ( ~P(x,y,z,…) )   ~ ( (∃x)P(x,y,z,…) ) = (∀x) ( ~P(x,y,z,…) ) Nämä kaavat ovat tosiaan de Morganin lakien yleistyksiä: Jos nimittäin x:n määrittelyalue on esimerkiksi {1,…,n}, niin (∀x)P(x) = P(1) ∧ ˘˘˘ ∧ P(n) ja ~( (∀x)P(x) ) = ~( P(1) ∧ ˘˘˘ ∧ P(n)) de Morgan

=

~P(1) ∨ ˘˘˘∨ ~P(n)

= (∃x) ( ~P(x) ) . Huom! Sulkeita jätetään usein pois ja kirjoitetaan esim. ~(∀x)P(x,y,z,…) = (∃x)~P(x,y,z,…) . Syntaksi BNF-notaatiota käyttäen saadaan määriteltyä syntaktisesti oikeat lausekkeet seuraavasti: 〈vakio〉 ::= 〈symboli〉 〈muuttuja〉 ::= 〈symboli〉 〈funktio〉 ::= 〈symboli〉 〈predikaatti〉 ::= 〈symboli〉 〈termi〉 ::= 〈vakio〉  〈muuttuja〉  〈funktio〉(〈termiluettelo〉) 〈termiluettelo〉 ::= 〈termi〉  〈termi〉,〈termiluettelo〉 〈atomi〉 ::= 〈predikaatti〉  〈predikaatti〉(〈termiluettelo〉) 〈literaali〉 ::= 〈atomi〉  ~〈atomi〉 〈operaatio〉 ::= ∧  ∨  →  ↔

20 〈muuttujaluettelo〉 ::= 〈muuttuja〉  〈muuttuja〉,〈muuttujaluettelo〉 〈kvanttori〉 ::= (∀〈muuttujaluettelo〉)  (∃〈muuttujaluettelo〉) 〈lauseke〉 ::= 〈literaali〉  ~(〈lauseke〉)  〈kvanttori〉(〈lauseke〉)  (〈lauseke〉)〈operaatio〉(〈lauseke〉)

(Huomaa, miten tämä syntaksi tuottaa "liikaa" sulkeita.) Näin määritellyt lausekkeet ovat ns. hyvin muodostetut lausekkeet (WFF = "well-formed formula"). Vakioita, muuttujia, funktioita ja predikaatteja merkitseviä symboleja varataan käyttöön tarpeen mukaan. Usein ne ovat "tuttuja": • • • •

vakioita: c, 0, 1, 2, π, ... muuttujia: x, y, z, … funktioita: f, g, sin, exp, ¢, +, -, predikaatteja: P, Q, =, > , …

˘,

/, …

Semanttisesti tulee mukaan lisävaatimuksia: • • • •

Vakioilla on oltava tietyt sovitut arvot. Muuttujien määrittelyalueet on sovittava. Kullakin funktiolla on oltava aina sama määrä muuttujapaikkoja ja sen on oltava määritelty muuttujiensa määrittelyalueilla. Kullakin predikaatilla on oltava aina sama määrä muuttujapaikkoja ja sen on oltava määritelty muuttujiensa määrittelyalueilla.

Huom! Syntaksissa määritellyn prefiksinotaation sijasta käytetään usein tuttua infiksinotaatiota, esimerkiksi x+y eikä +(x,y) tai x=y eikä =(x,y). Varsinainen infiksinotaatiota käyttävä syntaksi määritellään formaalisesti hieman eri tavalla. Huom! Syntaksi sallii myös "puhtaat propositiot": ne ovat predikaatteja, joilla on nolla kpl muuttujia. Merkinnän P() sijasta käytetään merkintää P. Huom! Semanttisesti muuttujan x määrittelyalueen A alijoukot voidaan samaistaa tiettyihin predikaatteihin P(x): Joukko B ⊆ A samaistetaan predikaattiin  T, jos x ∈ B P(x) =   V, jos x ∉ B.

21 4. Ekvivalenssi Predikaatit P(x,y,z,…) ja Q(x,y,z,…) ovat ekvivalentit, jos (∀x,y,z,…)(P(x,y,z,…) ↔ Q(x,y,z,…)) on tosi. Lauselogiikassa lausekkeiden ekvivalenssi voidaan aina todistaa laskulaeilla, päättelyllä, aksiomatisoinnilla tai totuustauluilla. Predikaattilogiikassa ekvivalenssi on algoritmisesti ratkeamaton (ks. 73117 Automaattiteoria). Semanttisesti tulee mukaan lisäksi se, että eri predikaatteja ja funktioita käyttäen voidaan ilmaista ekvivalentteja asioita. Syntaktisesti ei tällaista ekvivalenssia voida yleisesti ottaen todistaa. Näin ollen mitään laskulakikokoelmaa (vrt. pykälä I.2) ei predikaattilogiikassa ole algoritmisesti käytettävissä, paitsi tietysti lauselogiikan operaatioiden osalta.

5. Päättely Predikaattilogiikan päättelytehtävä on sama kuin lauselogiikassa: Selvitettävä onko päättely "Jos lausekkeet A1,...,An ovat tosia, niin myös lauseke B on tosi." oikea, merkitään A1,…,An |= B. Huomaa, että premissien A1,…,An totuus riippuu niissä esiintyvien vapaiden muuttujien arvoista ja samoja muuttujia voi olla vapaina myös B:ssä; sama koskee predikaatteja, vakioita ja funktioita. RAA on voimassa myös predikaattilogiikan päättelyssä. Näin ollen voidaan rajoittua muotoa A1,…,An |= V oleviin päättelyihin (ks. pykälät I.7-8). LAUSE 5. Jos lausekkeissa A1,…,An esiintyvät vapaat muuttujat ovat x1,…,xk, niin päättelyt A1,…,An |= V ja (∃x1,…,xk )(A1 ∧ ˘˘˘∧ An) |= V ovat ekvivalentit.

22 A1,…,An |= V

Todistus. ⇔

A1,…,An

eivät

ole

yhtaikaa

tosia

millään

muuttujien x1,…,xk arvoilla. ⇔

(∀x 1,…,x k)(~A1 ∨ ˘˘˘∨ ~An ) on tosi.

de Morgan

⇔

(∃x1,…,xk)(A1 ∧˘˘˘∧ An) on väärä.

⇔

(∃x 1,…,x k)(A1 ∧ ˘˘˘∧ An ) |= V ■

Näin ollen voitaisiin olettaa, että premisseissä ei ole vapaita muuttujia. Toisaalta näin on usein jo alunperin. Jatkossa oletetaankin, että vapaita muuttujia ei päättelyssä esiinny. Kätevä päättelyn apuneuvo, erityisesti resoluutiomenetelmää sovellettaessa, on ilmeinen sijoitussääntö (SS): Jos t on termi, jossa esiintyy vain muuttujia x1,…, xk ja jonka arvot ovat muuttujan x i määrittelyalueessa, niin (∀x 1 ,…,x k )P(x 1 ,…,x k ) |= (∀x 1 ,…,x k ) P(x1 ,…,x i-1,t,xi+1,…,x k ) (ks. termin syntaktinen määritelmä s.19). Usein sijoitettava termi on vakio, jonka on tällöin oltava x i:n määrittelyalueessa. Sijoitussäännön vaatima premissin muoto ei ole kovinkaan vaativa, kuten nähdään seuraavassa pykälässä.

6. Normaalimuoto Jatkamalla sivun 19 BNF-syntaksia säännöillä 〈normaalimuoto〉 ::= 〈CNF〉  〈kvanttori〉(〈normaalimuoto〉) 〈CNF〉 ::= (〈konjunkti〉)  (〈konjunkti〉)∧〈CNF〉 〈konjunkti〉 ::= 〈literaali〉  〈literaali〉∨〈konjunkti〉

23 saadaan syntaktinen määritelmä ns. prenex-normaalimuodolle. Lauseke on prenex-normaalimuodossa, jos kaikki sen kvanttorit ovat lausekkeen edessä ja loppuosa on konjunktiivisessa normaalimuodossa. Prenex-normaalimuotoinen lauseke on edelleen ns. Skolemin normaalimuodossa, jos siinä olemassaolokvanttorit edeltävät kaikkikvanttoreita, ts. lauseke on (muuttujien järjestystä ehkä lukuunottamatta) muotoa (∃x 1 )˘˘˘ (∃x m )(∀x m+1 )˘˘˘ (∀x k )P(x 1 ,…,x k ), missä P(x 1 ,…,x k ) ei sisällä kvanttoreita. (Tapauksilla m=0 ja m=k on ilmeiset tulkinnat.) Voidaan osoittaa, että jokainen lauseke voidaan korvata (vieläpä algoritmisesti!) ekvivalentilla Skolemin normaalimuodossa olevalla lausekkeella. Muotoa A1,…,An |= V eli A1 ∧˘˘˘∧ An |= V, missä premisseissä ei ole vapaita muuttujia, olevaa päättelyä ajatellen voidaan A1 ∧˘˘˘∧ An korvata eräällä ( e i välttämättä ekvivalentilla!) Skolemin normaalimuodossa olevalla lausekkeella B, kunhan (

*

)

B toteutuu ⇔ A1 ∧˘˘˘∧ An toteutuu.

B:n toteutuminen tarkoittaa sitä, että siinä esiintyvien vakioiden arvot voidaan valita ja predikaatit sekä funktiot määritellä siten, että B on tosi (vapaita muuttujiahan B:ssä ei ole); vastaavasti A1 ∧˘˘˘∧ An:n toteutuminen. Huomaa, ettei tällöin (

*

) merkitse B:n ja A1 ∧˘˘˘∧ An:n ekvivalenttisuutta.

Tällainen lauseke B saadaan seuraavalla menettelyllä, ns. Skolemin muunnoksella (engl. Skolemization): 1 ) Poistetaan ekvivalenssit: P↔Q korvataan (P→Q)∧(Q→P):llä. 2 ) Poistetaan implikaatiot: P→Q korvataan ~P∨Q:lla. 3 ) Siirretään negeeraus lausekkeen " sisään" (yleistetyillä) de Morganin laeilla. 4 ) Poistetaan peräkkäiset negeeraukset komplementäärisyyslailla. 5 ) Poistetaan olemassaolokvanttorit: Jos kvantifiointi (∃x) ei ole minkään kaikkikvanttorin vaikutusalueella, korvataan x ns. Skolemin vakiolla a jokaisessa esiintymässään ja kvantifiointi (∃x ) sulkeineen poistetaan. Skolemin vakio ei saa olla lausekkeessa ennestään esiintyvä vakio. Aina kun poistetaan eo. tavalla olemassaolokvanttori, pitää valita uusi Skolemin vakio. Skolemin vakio on määräämätön vakio, joka "edustaa" sellaista x:n arvoa, jolle tarkasteltava lausekkeen osa on tosi. Jos taas kvantifiointi (∃x) on yhden tai useamman kaikkivanttorin vaikutusalueella, sa-

24 notaan kaikkikvanttorien (∀y 1 ),…,(∀y k ) vaikutusalueilla, tulisi Skolemin vakio riippumaan muuttujien y1,…,yk arvoista, ts. se olisi näiden funktio. Tällöin x:n paikalle kirjoitetaan jokaisessa esiintymässä ns. Skolemin funktio f(y1,…,yk) ja kvantifiointi (∃x ) sulkeineen poistetaan. Skolemin funktio ei saa olla mikään lausekkeessa aikaisemmin esiintyvä funktio. Jokaista olemassaolokvanttorin tällaista poistoa varten tarvitaan uusi Skolemin funktio. Skolemin funktio on määräämätön funktio, joka "antaa" kutakin muuttujien y1,…,yk arvoyhdelmää kohti sellaisen x:n arvon, jolla kyseinen lausekkeen osa toteutuu. Huom! Skolemin vakiot ja funktiot ovat formaalisesti vain uusia vakio- ja funktiosymboleja. Ne eivät saa olla sellaisia, joiden semanttinen merkitys on jo sovittu (esimerkiksi 1, π, sin, ¢ ). 6 ) Korvataan tarvittaessa jäljelle jääneitä sidottuja muuttujia uusilla, niin ettei sama muuttuja esiinny eri kvantifioinneissa. 7 ) Siirretään kaikkikvanttorit lausekkeen alkuun. 8 ) Kaikkikvanttorien jälkeen tuleva lausekkeen osa on nyt literaaleista, suluista ja propositiologiikan operaatioista ∧ ja ∨ muodostuva lauseke. Saatetaan se konjunktiiviseen normaalimuotoonsa (ks. pykälä I.3). Sovellettaessa Skolemin muunnosta lausekkeeseen, jossa ei ole vapaita muuttujia (kuten voimme olettaa, ks. s. 22), saadaan tuloksena lauseke, a ) jossa ei myöskään ole vapaita muuttujia, b ) jossa esiintyy vain kaikkikvanttoreita eikä lainkaan olemassaolokvanttoreita, c ) jonka kaikki kaikkikvanttorit sitovat eri muuttujia ja ovat lausekkeen edessä (jolloin ne voidaan yhdistää yhdeksi kvantifioinniksi, ks. s. 18) ja d ) jossa lausekkeen loppuosa on konjunktiivisessa normaalimuodossa. LAUSE 6. Jos lauseke B saadaan Skolemin muunnoksella lausekkeesta A, niin B on toteutuva tarkalleen, kun A on toteutuva. ( Huom! Jotta B saataisiin toteutumaan, on erityisesti siinä esiintyville Skolemin vakioille annettava arvot ja esiintyvät Skolemin funktiot on määriteltävä. A:ssa näitä vakioita ja funktioita ei ole.) Todistus. ⇐

Oletetaan, että A on toteutuva. Silloin A:n vakioille on an-

nettu sellaiset arvot ja A:n predikaatit sekä funktiot on määritelty siten, että A saadaan todeksi. Otetaan samat arvot ja määrittelyt käyttöön B:n predikaateille sekä muille vakioille ja funktioille kuin sen Skolemin vakioille ja Skolemin funktioille. Edelleen A:n olemassaolokvantifioinnit anta-

25 vat tällöin vastaaville A:n sidotuille muuttujille arvot. Otetaan nämä käyttöön B:n Skolemin vakioiden arvotuksessa ja sen Skolemin funktioiden määrittelyssä. Näin nähdään, että B saadaan todeksi, sillä Skolemin muunnoksen operaatiot 1-4) ja 6-8) säilyttävät toteutumisen*. ⇒

Oletetaan, että B toteutuu. Olkoon C lauseke, joka on saatu A:sta ope-

raatioiden 1-4) jälkeen, ja D lauseke, joka on saatu C:stä operaation 5) jälkeen. Koska operaatiot 6-8) säilyttävät toteutumisen myös käänteisinä * , myös D toteutuu. Skolemin vakioiden arvoista ja Skolemin funktioiden määrittelyistä saadaan nyt C:n olemassaolokvantifioiduille muuttujille arvot, joilla C toteutuu. Operaatiot 1-4) säilyttävät myös toteutumisen käänteisinäkin, joten A toteutuu. ■ Huom! Yo. todistus osoittaa, että B→A on aina tosi. Toisaalta A→B ei välttämättä ole tosi: Koska A:ssa ei esiinny Skolemin vakioita eikä Skolemin funktioita, niin näille voidaan valita sellaiset arvot ja määritelmät, että B ei ole tosi, vaikka A sitä olisikin. Yleisesti ekvivalenssi A↔B ei siis päde.

SEURAUS. Jos lauseke B saadaan Skolemin muunnoksella lausekkeesta A, niin päättelyt A |= V ja B |= V ovat ekvivalentit. A |= V

Todistus. ⇔

A ei toteudu.

Lause 6

⇔

B ei toteudu.

⇔

B |= V ■

Näin ollen voidaan rajoittua päättelyissä lausekkeisiin, jotka ovat Skolemin muunnoksen antamaa muotoa.

7. Resoluutio Kuten edellisissä pykälissä näytetty, voidaan rajoittua muotoa A |= V oleviin päättelyihin, missä A on Skolemin muunnoksen antamaa muotoa eikä sisällä vapaita muuttujia. Tällöin A on muotoa (∀x1,…,xk)(C1 ∧˘˘˘∧ Cm ),

*

7):n osalta tämä ei ole aivan helppo nähdä. Idea selvinnee esimerkin avulla.

26 missä konjunktit C1,…,Cm eivät sisällä kvanttoreita. Ilmeisesti A ja

((∀x1,…,xk)C1) ∧˘˘˘∧ ((∀x1,…,xk)Cm ) ovat ekvivalentit, joten voidaan siirtyä muotoa (∀x1,…,xk)C1 ,…, (∀x1,…,xk)Cm |= V oleviin päättelyihin. Silloin 1 ) kuhunkin premissiin (∀x 1 ,…,x k )C i voidaan soveltaa sijoitussääntöä (ks. s. 22) ja, 2 ) jos kahdessa konjunktissa Ci ja Cj esiintyy sama atomi, toisessa negeerattuna ja toisessa sellaisenaan, voidaan soveltaa resoluutiosääntöä. Resoluutiosääntö tulee nyt käyttöön muodossa "Jos (∀x 1 ,…,x k )(P(x 1 ,…,x k ) ∨ Q(x1 ,…,x k )) on tosi ja (∀x 1 ,…,x k )(R(x 1 ,…,x k ) ∨ ~Q(x 1 ,…,x k )) on tosi, niin myös (∀x 1 ,…,x k )(P(x 1 ,…,x k ) ∨ R(x 1 ,…,x k )) on tosi." Ideana on luoda sijoitussäännöllä tilanteita, joihin RS soveltuu, muutoin resoluutiomenettely on samanlainen kuin pykälässä I.8. Valitettavasti predikaattilogiikassa resoluutiomenettely ei aina johda tulokseen, sillä se voi johtaa päättymättömään päättelyketjuun, toisin kuin propositiologiikassa. Predikaattilogiikassahan päättely on yleisesti ottaen algoritmisesti ratkeamaton tehtävä. Käytännössä voidaan kuitenkin rajoittua päättelytilanteisiin, joista resoluutiomenettely selviytyy sopivin apuneuvoin ja "nyrkkisäännöin". Tärkein näistä apuneuvoista on ns. yhdennys eli unifikaatio, jota käyttäen löytyvät resoluutiomenettelyn soveltamiseksi tarvittavat sijoitukset. Yhdennys Jos kahdessa konjunktissa C ja C' (voivat olla samakin) esiintyvät muotoa P(˘˘˘) ja ~P(---) (tai P(---)) olevat literaalit, missä ˘˘˘ ja --- eivät ole valmiiksi samat, niin pyritään saamaan ne samoiksi sopivalla sijoitusketjulla t1/xi1 , t2/xi2 ,…, tm/xim , missä termi tj sijoitetaan muuttujan xij paikalle. Samalla syntyy konjunktijono C , C' , D1 ,…, Dm , missä Dj saadaan sijoituksella t j/x ij jostakin sitä jonossa edeltävästä konjunktista. Lopulta Dm:ssä ja jossakin sitä jonossa edeltävässä konjunktissa

27 atomit P(˘˘˘) ja P(---) ovat muuntuneet samoiksi ja resoluutiota voidaan soveltaa. Yhdennyksellä voidaan myös saada idempotenssilaki käyttöön ja näin vähentää literaaleja konjunkteissa. Mikäli konjunkteissa C ja C' esiintyvät muuttujat ovat x1,…,xk, voidaan yo. sijoitusten ketju ajatella yhtenä, ts. muuttujien x1,…,xk paikalle sijoitetaan kummassakin konjunktissa yhtaikaa tietyt termit, molemmille omansa. (Erityisesti voidaan muuttujan paikalle sijoittaa terminä se itse.) Tämä on ns. P( ˘˘˘):n ja P(---):n yhdentäjä. Voidaan osoittaa, että jos P( ˘˘˘ ) ja P(---) yleensä ottaen voidaan yhdentää, niin niille on olemassa ns. yleisin yhdentäjä, ts. yhdentäjä, josta kaikki muut P( ˘˘˘):n ja P(---):n yhdentäjät saadaan sijoituksella (ks. ROBINSON tai RICHARDS). Heuristiikkaa 1 ) Pyritään soveltamaan resoluutiosääntöä yksiliteraalisiin konjunkteihin, sillä tällöin saadaan tuloksena "lyhyempiä" konjunkteja. 2 ) Usein lähtötietoina annetaan yleisiä kulloiseenkiin tilanteeseen liittyviä periaatteita eli ns. aksiomia (tietysti predikaattilogiikan lausekkeina) ja ratkaistavaan tehtävään liittyviä erityistietoja, sekä tietysti itse tehtävä. Päättelyssä on käytettävä eo. erityistietoja sekä tehtävän määrittelyä, ei pelkkiä aksiomia. Muussa tapauksessa resoluutiomenettely tuottaa vain tilanteeseen liittyviä yleisiä totuuksia, joiden joukossa V ei varmaankaan ole. 3 ) Pyritään valitsemaan resoluutiota varten "vähän esiintyviä" literaaleja, koska valinnan varaa on näiden osalta vähän, jos ollenkaan. 4 ) Toistuvissa päättelytilanteissa valiutuvat usein jotkin aksiomat ja sijoitukset, samoin tietynlaiset päättelyketjun osat. Näistä voidaan kerätä tietoa, jota voidaan käyttää apuna. 5 ) Jos ei ole tarkkaa kuvaa siitä mitä "reittiä" päättelyketju on nopeimmin toteutettavissa, on syytä käyttää varovaisuussyistä mahdollisimman yleisiä yhdentäjiä.

8. Päättelyn anatomiaa. Herbrandin universumi Edellä käsitelty päättely on puhtaan symbolista. Mitään semanttista tietoa muuttujien määrittelyalueista, vakioiden aiotuista arvoista, funktioiden ja predikaattien määrittelyistä tms. ei käytetä. Jos tällaista tietoa halutaan käyttää, on se ilmaistava premisseissä, ts. tilanteeseen liittyvinä aksiomina. Näin ollen, jos resoluutiomenettely toteaa päättelyn A1,…,An |= B oikeaksi, se on sitä kaikissa semanttisissa tilanteissa. Toisaalta, vaikka päättely

28 olisikin yleisesti ottaen väärä, se voi olla oikea tietyissä semanttisissa tilanteissa. Resoluutiomenettely ei voi tätä todeta, ellei ko. semanttista tilannetta ilmaista aksiomien kautta. Jos päättely A1,…,An |= B on yleisesti (siis kaikissa semanttisissa tilanteissa) oikea, niin tämä on mahdollista todeta resoluutiota käyttäen. Kuten edellä on todettu, voidaan rajoittua muotoa (∀x1,…,xk)(C1 ∧˘˘˘∧ Cm ) |= V oleviin päättelyihin, jossa ei ole vapaita muuttujia ja jossa konjunktit C1,…, Cm eivät sisällä kvantifiointeja. Näytetään tulos vain tapauksessa, jossa konjunktit C1,…,Cm eivät sisällä lainkaan funktiosymboleja (eivätkä siis erityisesti Skolemin funktioita). Menettely on seuraavanlainen: 1 ) Vakioiden arvot ovat aina jonkin muuttujan määrittelyalueessa (niiden muuttujien, joiden "paikalla" vakio esiintyy lausekkeessa). Valitaan kullekin muuttujalle x i määrittelyalue A i seuraavasti: a) Jos jotkin vakiot kuuluvat xi:n määrittelyalueeseen, niin A i muodostuu näistä vakioista. b) Jos mikään vakio ei kuulu x i:n määrittelyalueeseen, niin A i ={ci}, missä ci on uusi symboli. Nämä määrittelyalueet A i (i=1,…,k) muodostavat ns. Herbrandin universumin. Huomaa, että alueet Ai ovat äärellisiä. 2 ) Sijoitetaan nyt kaikilla mahdollisilla tavoilla muuttujien määrittelyalueiden A i alkiot muuttujien paikoille konjunkteissa C1,…, Cm. Näin saadaan konjunktit C'1 ,…,C's , joissa ei esiinny lainkaan muuttujia. 3 ) Annetaan konjunkteissa C'1 ,…,C's esiintyville atomeille jotkut totuusarvot. Nämä atomit ovat itse asiassa propositioita! 4 ) Jos konjunktit C'1 ,…,C's ovat näillä totuusarvoilla kaikki tosia, on löydetty tilanne (Herbrandin universumi), jossa päättely (∀x1,…,xk)(C1 ∧˘˘˘∧ Cm ) |= V on väärä. Näin ollen se ei voi olla yleisesti ottaen oikea. Lähtötilanne olikin siis väärä. 5 ) Jos taas kaikki konjunktit C'1 ,…,C's eivät ole näillä totuusarvoilla tosia, annetaan niissä esiintyville atomeille jotkut toiset totuusarvot ja palataan kohtaan 4). 6 ) Jatketaan kunnes kaikki konjunkteissa C'1 ,…,C's esiintyvien atomien totuusarvoyhdelmät on käyty läpi. Ellei menettely ole pysähtynyt kohtaan 4), niin konjunktit C1,…,Cm eivät voi olla yhtai-

29 kaa tosia Herbrandin universumissa. Silloin ne eivät voi olla yhtaikaa tosia missään semanttisessa tilanteessa. Muussa tapauksessa tällaisessa tilanteessa (∀x 1 ,…,x k )(C1 ∧˘˘˘∧ C m ) olisi tosi ja käytetyistä predikaattien määrittelyistä saataisiin juuri sellaiset totuusarvot konjunktien C'1 ,…,C's atomeille, että esitetty prosessi pysähtyisikin kohtaan 4). Koska kyse itse asiassa on siitä, että propositiologiikan mielessä C'1 ,…, C's |= V, voidaan päättelyn (∀x 1 ,…,x k )(C1 ∧˘˘˘∧ C m ) |= V oikeellisuus todentaa resoluutiomenettelyllä. Konjunktit C'1 ,…,C's saadaan nimittäin sijoitussäännöllä konjunkteista C1,…,Cm, arvon ci tilalla voidaan käyttää muuttujaa xi itseään. Yo. menettely on ns. Herbrandin algoritmi. Näin ollen muotoa (∀x1,…,xk)(C1 ∧˘˘˘∧ Cm ) |= V olevien päättelyiden, joissa ei ole vapaita muuttujia ja joissa konjunktit C1, …,Cm eivät sisällä kvantifiointeja eivätkä funktioita, oikeellisuuden toteaminen on algoritmisesti ratkeava tehtävä. Predikaattilogiikan päättelytehtävän algoritminen ratkeamattomuus johtuukin nimenomaan funktiosymboleista ja erityisesti Skolemin funktioista (eli kaikkikvanttorien vaikutusalueiden sisäisistä olemassaolokvantifioinneista). Jos konjunkteissa C1,…,Cm on funktioita, voidaan määritellä Herbrandin universumi, mutta se on jonkin verran mutkikkaampi kuin yllä oleva. Erityisesti määrittelyalueet A i voivat olla äärettömiä*. Tästä johtuen vastaava Herbrandin algoritmi ei aina pysähdy (kuten yllä esitetty algoritmi pysähtyy kohdassa 4)), jos päättely (∀x 1 ,…,x k )(C1 ∧˘˘˘∧ C m ) |= V onkin väärä. Sen sijaan se pysähtyy, jos päättely on oikea, ja näyttää, että päättelyn oikeellisuus voidaan myös todeta resoluutiolla. (Ks. RICHARDS tai ROBINSON.)

*

Tämä johtuu siitä, että funktioiden arvot ovat muuttujien määrittelyalueissa. Jos esimerkiksi funktion f(xi) arvot ovat muuttujan xi määrittelyalueessa ja samoin vakion a arvo on xi:n määrittelyalueessa, pitää Ai:ssä olla a, f(a), f(f(a)), f(f(f(a))),….

30 9. Resoluutio Hornin konjunkteille.

PROLOG

Hornin konjunkti on konjunkti, jossa on enintään yksi negeeraamaton literaali. Tästä seuraa välittömästi, että jos sovelletaan resoluutiosääntöä Hornin konjunkteihin, tuloksena on jälleen Hornin konjunkti (tai ∞ ). LAUSE 7. Muotoa A→B oleva propositiolauseke, missä A on mielivaltainen operaatioita ∧ ja ∨ käyttäen atomeista muodostettu lauseke ja B on mielivaltainen operaatiota ∧ käyttäen literaaleista muodostettu lauseke, voidaan kirjoittaa konjunktiiviseen normaalimuotoon, jonka konjunktit ovat Hornin konjunkteja (HCNF ). Todistus. Soveltamalla toistuvasti laskulakia A→P∧Q = (A→P)∧(A→Q) voidaan rajoittua tapaukseen, jossa B:ssä on vain yksi literaali, sanotaan Q. Kirjoitetaan A→Q muotoon ~A∨Q ja viedään ~A konjunktiiviseen normaalimuotoon. Tässä normaalimuodossa on vain negeerattuja literaaleja (miksi?). Lopuksi ositellaan Q sisään tähän CNF-lausekkeeseen, jolloin tulos on HCNF-lauseke. ■ Lauseessa mainittu HCNF-muoto saadaan aikaan myös seuraavalla tavalla. Voidaan rajoittua tapaukseen, jossa B:ssä on vain yksi literaali, sanotaan Q. Jos nyt A:ssakin on vain yksi atomi, sanotaan P, on asia selvä: P→Q = ~P∨Q. Muuten A on joko muotoa P∧R tai P∨R. Jos A on muotoa P∧R, käytetään laskulakia P∧R→Q = P → (R→Q). Jos nyt tiedetään, että muotoa P→S ja R→Q olevat lausekkeet, missä S on atomi, saadaan HCNF-muotoon, niin samoin saadaan P∧R→Q. Ajattele vain, mitä tapahtuu, jos S:n tilalle kirjoitetaan R→Q:n HCNF. (Tässä S on sitä sisältävien Hornin konjunktien ainoa negeeraamaton atomi.) Jos taas A on muotoa P∨R, käytetäänkin laskulakia P∨R→Q = (P→Q)∧(R→Q). Mikäli nyt P→Q ja R→Q saadaan HCNF-muotoon, niin samoin ilmeisesti saadaan P∨R→Q. Toistetaan yo. menettelyä "atomitasolle" asti. Huom! Lause pätee erityisesti, jos B=V, jolloin A→B = ~A, tai jos A=T, jolloin A→B = B. Hornin CNF ei siis ole erityisen vaativa. Hornin konjunkti on positiivinen, jos siinä on tarkalleen yksi negeeraamaton literaali, ja negatiivinen, jos siinä ei ole negeeraamattomia literaaleja. Resoluutiosäännön soveltaminen Hornin konjunkteihin on "rajatumpaa" kuin yleisesti, sillä negeeraamattomia literaaleja on vain yksi per konjunkti. Eräs menettely on suurinpiirtein esitettynä seuraava:

31 ( 1 ) Etsi konjunktilistasta ensimmäinen konjunkti, sanotaan Ci, jossa on negeerattuja literaaleja, ja aseta C←Ci. Ellei tällaisia ole, päättely on väärä ja lopetetaan. (2) Etsi C:n ensimmäinen negeerattu literaali ~P. (3) Etsi konjunktilistasta ensimmäinen konjunkti, sanotaan Cj, jonka (ainoa) negeeraamaton literaali Q yhdentyy P:n kanssa. Ellei tällaista ole, ota ~P:n tilalle seuraava C:n negeerattu literaali ja yritä uudelleen, jne.. Ellei tämäkään onnistu, aseta C:ksi konjunktilistassa ensimmäinen Ci:tä seuraava konjunkti, jossa on negeerattuja literaaleja ja palaa kohtaan (2). Jne.. (4) Ellei lopultakaan yhdennys onnistu, päättely on väärä ja lopetetaan. Muussa tapauksessa suoritetaan yhdennys heti, kun se on mahdollista, tehdään tarvittavat sijoitukset ja sovelletaan resoluutiosääntöä. Tuloksena on uusi konjunkti C'. ( 5 ) Jos C' on tyhjä, päättely on oikea ja lopetetaan. Jos taas C':ssa on negeerattuja literaaleja, lisätään se konjunktilistaan, asetetaan C←C' ja mennään kohtaan (2). Jäljelle jääneessä tapauksessa C':ssä on yksi literaali ja se on negeeraamaton. Tällöin lisätään C' konjunktilistaan ja palataan kohtaan (3), missä etsitään konjunktilistassa ensimmäinen Cj:tä seuraava konjunkti, jonka (ainoa) negeeraamaton literaali R yhdentyy P:n kanssa, jne.. Onnistuvien yhdennysmahdollisuuksien etsintä kannattaa depth-first-etsinnän muotoon, ks. 73119 Graafiteoria.

pukea

ns.

PROLOG PROLOG on yleinen ohjelmointikieli, jonka toiminta perustuu resoluution, yhdennyksen ja depth-first-etsinnän tehokkaaseen käyttöön. PROLOG-ohjelma on itse asiassa aksiomakokoelma (tietokanta) eli kokoelma loogisia lausekkeita ja syöttönä on ns. kysely eli eräs looginen lauseke. Jotta ohjelma toimisi nopeasti, on asetettava rajoituksia. Puhtaimmillaan ne merkitsevät sitä, että PROLOG-ohjelma + kysely testaa Skolemin muunnoksen jälkeen muotoa (∀x1,…,xk)(C1 ∧˘˘˘∧ Cn-1 ∧ Cn) |= V olevan päättelyn oikeellisuuden, missä C1,…,Cn-1 ovat positiivisia Hornin konjunkteja ja Cn negatiivinen Hornin konjunkti. PROLOG ei itse tee Skolemin muunnosta, vaan se jää käyttäjän tehtäväksi. Toisaalta PROLOG ei myöskään ota tehtävää vastaan yo. muodossa. Sen sijaan se ottaa vastaan konjunktit C1,…,Cn-1 ohjelmanaan (tietokanta) ja ~Cn:n kyselynä. Itse asiassa kysely on (∃x 1,…,x k)D, missä D saadaan, kun kirjoitetaan D = ~Cn ja viedään negaatio konjunktin sisään. Koska Cn on negatiivinen Hornin

32 konjunkti, ei D:ssä ole negeerattuja literaaleja. PROLOG tulostaa kaikki löytämänsä muuttujien x1,…,xn arvoyhdelmät, joille D on tosi, tai ilmoittaa, ettei sellaisia löytynyt. Jos esimerkiksi annetaan "perheaksiomat" C1:

(∀x,y) ( Isä(x,y) → Mies(x))

C2:

(∀x,y,z)(Isä(x,y) ∧ Isä(x,z) → Sisarukset(y,z))

C3:

(∀x,y) (Sisarukset(x,y) ∧ Mies(x) → Veli(x,y))

C4:

Isä(Jussi,Harri)

C5:

Isä(Jussi,Simo) (∃y)Isä(Simo,y)

ja halutaan tietää, voidaanko näistä päätellä (∃z)Veli(z,Harri), niin RAA:n ja Skolemin muunnoksen jälkeen tehtävä on muodossa: onko C 1 ,…, C5 , Isä(Simo,Rauni) , (∀z)~Veli(z,Harri) |= V ? Tässä Rauni on Skolemin vakio (voi olla mies tai nainen). Vastaava ohjelma on

mies(X):-isa(X,Y). sisarukset(Y,Z):-isa(X,Y),isa(X,Z). veli(X,Y):-sisarukset(X,Y),mies(X). isa(jussi,harri). isa(jussi,simo). isa(simo,rauni). ja vastaava kysely on

?- veli(Z, harri). PROLOG tulostaa:

PROLOG-

33

?- veli(Z, harri) Nº1

Z=simo

No more solutions Jos kysely onkin

?- sisarukset(X, Y). saadaan tulostus

?- sisarukset(X, Y) Nº1

X=harri,Y=harri

Nº2

X=harri,Y=simo

Nº3

X=simo,Y=harri

Nº4

X=simo,Y=simo

Nº5

X=rauni,Y=rauni

No more solutions Haluttaessa PROLOG antaa tietoja käyttämästään päättelyketjusta. Edellinen yo. kyselyistä johtaa seuraavanlaiseen ketjuun, joka saadaan trace-komennoilla:

………… call veli(_835, harri) ………… call sisarukset(_835, harri) ………… call isa(_1576, _835) exit isa(jussi, harri)

34

………… call isa(jussi, harri) exit isa(jussi, harri) exit sisarukset(harri, harri) ………… call mies(harri) ………… call isa(harri, _2208) fail isa(harri, _2208) fail mies(harri) redo sisarukset(harri, harri) redo isa(jussi, harri) fail isa(jussi, harri) redo isa(jussi, harri) exit isa(jussi, simo) ………… call isa(jussi, harri) exit isa(jussi, harri) exit sisarukset(simo, harri) ………… call mies(simo) ………… call isa(simo, _2208)

35

exit isa(simo, rauni) exit mies(simo) exit veli(simo, harri) redo veli(simo, harri) redo mies(simo) redo isa(simo, rauni) fail isa(simo, _2208) fail mies(simo) redo sisarukset(simo, harri) redo isa(jussi, harri) fail isa(jussi, harri) redo isa(jussi, simo) exit isa(simo, rauni) ………… call isa(simo, harri) fail isa(simo, harri) redo isa(simo, rauni) fail isa(_1576, _835) fail sisarukset(_835, harri) fail veli(_835, harri) Jokainen positiivinen Hornin konjunkti ~A1∨˘˘˘∨~Ak∨Ak+1, missä A1,…, Ak+1 ovat atomeja, voidaan kirjoittaa muotoon A1 ∧˘˘˘∧ Ak → Ak+1 ,

36 kuten yllä onkin tehty. Edelleen ym. lauseke D on muotoa B1∧˘˘˘∧Bm, missä B1,…,Bm ovat atomeja. PROLOG-ohjelmat ja kyselyt voidaan näin ollen kirjoittaa ilman negaatiota tai disjunktiota. PROLOGissa on toki operaatiot not ja or, mutta ne eivät ole samat kuin vastaavat loogiset operaatiot. Esimerkiksi not on itse asiassa ns. negaatio äärellisen tuloksettoman haun kautta, ts. jos PROLOG ei pysty päättelemään atomia A tietokannasta, niin se katsoo not(A):n oikeaksi. Jotta tämä not olisi sama kuin NOT, pitäisi tietokannan sisältää kaikki tieto tarkasteltavasta tilanteesta ja päättelyn tietokanta |= A pätemättömyyden pitäisi olla PROLOGin selvitettävissä äärellisessä määrässä askelia, ns. äärellisen maailman* oletus. Koska näin ei aina ole, voi not-operaation käyttö johtaa virheelliseen tulokseen. Ks. RICHARDS tai jokin PROLOGia käsittelevä kirja, esim. STERLING, L. & SHAPIRO, E.: The Art of Prolog. MIT Press (1986).

*

"Maailma" tässä on oleellisesti Herbrandin universumi.

37

III

KOMBINATORIIKKAA

1. Kombinaatiot n eri alkion eri järjestyksiä eli permutaatioita on n! = 1˘2˘3˘˘˘n kpl. (Sovitaan, että 0! = 1 ja 1! = 1.) n:stä alkiosta voidaan valita järjestyksessä k alkiota n(n-1)

˘˘˘

n! (n-k+1) = (n-k)!

eri tavalla, ns. k:n alkion variaatiot. Ellei järjestystä oteta lukuun, voidaan n:stä alkiosta valita k alkiota merk.

n! k!(n-k)!

=

 n k 

 n eri tavalla, ns. k:n alkion kombinaatiot. k  on ns. binomikerroin*. Jos sallitaan, että sama joukon alkio voidaan valita (rajattoman) monta kertaa, saadaan ns. toistovariaatiot ja toistokombinaatiot. k:n alkion toistovariaatioita (n:stä alkiosta) on n ˘n

˘˘˘

n = nk

k kpl kpl. (Sovitaan, että n0 = 1, erityisesti 00 = 1.) Huom! Usein ajatellaan, että mainitut n alkiota muodostavat ns. aakkoston ja k:n alkion toistovariaatiot ovat ns. k:n pituisia sanoja. 0:n pituinen sana on ns. tyhjä sana, joita on yksi. Ks. 73117 Automaattiteoria ja/tai 73118 Formaaliset kielet. LAUSE 8. k:n alkion toistokombinaatioita (n:stä alkiosta) on  n+k-1  k 

merk.

=

〈nk 〉

kpl (k> 1) ** .

* **

Luetaan “n yli k:n”. GRAHAM & KNUTH & P ATASHNIK käyttää kulmasulkeita merkitsemään ns. Eulerin lukuja.

38 Todistus. Voidaan ilmeisesti ajatella, että ko. alkiot ovat luvut 1,2,…,n. Jos jaetaan toistokombinaatiot kahteen eri luokkaan sen mukaan onko mukana luku 1 vaiko ei, saadaan yhtälö (rekursiokaava) n 〈nk 〉 = 〈k-1 〉 + 〈n-1 k 〉

( k> 2, n> 2).

n Tämä yhtälö määrittää 〈 k 〉:n täysin, kun annetaan ilmeiset “reunaehdot”

〈n1 〉 = n

ja

〈k1 〉 = 1.

 n+k-1 Mutta  k  toteuttaa sekä mainitun rekursiokaavan että annetut reun naehdot, joten se on 〈 k 〉. Yhtälö  n+k-2  n+k-2  n+k-1  k  =  k-1  +  k  voidaan todeta suoraan laskien, mutta se on erikoistapaus eräästä seuraavassa pykälässä (s. 40) esitetystä binomiaali-identiteetistä. ■ n Sovitaan, että 〈0 〉 = 1 (tämä on sopusoinnussa Lauseen 8 kanssa). Lauseen todistuksessa tarvitun identiteetin (1)

n 〈nk 〉 = 〈k-1 〉 + 〈n-1 k 〉

n lisäksi 〈k

〉 toteuttaa identiteetit

(2)

〈nk 〉 = kn 〈n+1 k-1 〉 ,

(3)

n 〈nk 〉 = n+k-1 〈 〉 k-1 k

(4)

n n n 〈n+1 k 〉 = 〈0 〉 + 〈1 〉 +˘˘˘+ 〈k 〉 .

ja

Identiteetit ( 2 ) ja ( 3 ) seuraavat Lauseesta 8 suoralla laskulla. ( 4 ) saadaan (1):stä soveltamalla sitä toistuvasti:

〈n+1 〉 = 〈n+1 k k-1 n+1 = 〈 k-2

〉 + 〈kn 〉 n 〉 + 〈k-1 〉 + 〈nk 〉 = ˘˘˘

39 n n 〈n+1 1 〉 + 〈2 〉 +˘˘˘+ 〈k 〉 n n = n + 1 + 〈 2 〉 +˘˘˘+ 〈k 〉 n n n n = 〈 0 〉 + 〈1 〉 + 〈2 〉 +˘˘˘+ 〈k 〉 =

Jotta myös tapaus n=0 saataisiin mukaan, sovitaan, että 0 (katso (2)). Edelleen sovitaan, että 〈0

〈k0 〉 =

0, kun k > 1

〉 = 1 (katso (4)).

2. Binomikertoimet Binomikerroin voidaan määritellä yleisestikin* kaavalla x(x-1) ˘˘˘ (x-k+1) x  , k  = k! missä x on mielivaltainen reaali- tai kompleksiluku ja k on ei-negatiivinen kokonaisluku. Tapauksessa k=0 osoittajaan tulee ns. “tyhjä tulo”, jonka arvoksi sovitaan 1. Siis aina x   0  = 1. x  Toisaalta, jos x on kokonaisluku ja 0 < x0)

n

∑

(V)

 m+n+1  m+k   k  = n

(alla olevasta kuvasta)

k=0

m

( m+k k )

k

n

m+1 n

(VI)

∑

 n+1  k m  = m+1

(seuraa (III):sta ja (V):stä; m< n )

k=m

 n  n-k   n  m  ( V I I )  m   k  = k  m-k

(suoraan laskien; n> m > k )

42 m-n

(VIII)

∑

 l   m   l +m k  n+k = l+n  (alla olevasta kuviosta; l> m-n> 0)

k=0

l-k

n+k

( lk ) m-n

k

m ( n+k ) m-n-k

m-n

n

l l-m

(IX)

∑

 l-k  p+k  l +p+1   m   n  =m+n+1

(alla olevasta kuviosta, jako-

k=n-p

viiva on keskellä ruutua;

l-m> n-p> 0 ) m+n+1

( p+k n ) l+p-m-n

p-n+k

( lm-k)

l-m-k

m Identiteetin (II) sekä reunaehtojen

n

43  n 0  = 1

 n  n = 1

ja

avulla voidaan binomikertoimet saada ns. Pascalin kolmiosta, jossa alkio on aina välittömästi sen yläpuolella olevien alkioiden summa (reuna-alkioita lukuunottamatta): 1 1 1 1 1 1 1

2

1

3 4

5 6

1

3 6

10 15

1 4

10 20

1 5

15

1 6

1

......................... Identiteetit (VIII) ja (IX) ovat ns. Vandermonden konvoluutiokaavat. N e voidaan kirjoittaa “kauniimpaan” (mutta ei välttämättä käyttökelpoisempaan!) muotoon: (VIII) voidaan kirjoittaa muotoon n

(VIII')

l   m 

∑ k  n-k

 l +m = n 

k=0

(ilmeinen) ja (IX) muotoon n

(IX')

l m l+m ∑ 〈k 〉〈n-k 〉 = 〈 n 〉 k=0

(totea!). Kätevä apuväline binomiaali-identiteettien etsimisessä reittianalogiaa (ja ylös oikealle 45° kulmassa olevia jakoviivoja) ajatellen on HEIJASTUSPERIAATE. Alla olevassa kuviossa niiden P:stä Q:hun (ylös tai oikealle) kulkevien reittien lukumäärä, jotka sivuavat tai leikkaavat suoraa d, on sama kuin P:stä d:n suhteen peilaamalla saadusta pisteestä P' pisteeseen Q kulkevien reittien lukumäärä. ■

44 d Q

P

P'

Heijastusperiaatteen avulla voidaan esimerkiksi rajoittua reitteihin, jotka eivät leikkaa tai sivua suoraa d. Huom! Binomiaali-identiteettien (ja muidenkin summausidentiteettien) todentamiseen ja generointiin on yleinenkin työkalu, ns. Gosperin algoritmi, joka löytyy useista symbolisen laskennan ohjelmistoista (MACSYMA, Mathematica, Maple). Ks. myös GRAHAM & KNUTH & P ATASHNIK . Äskettäin algoritmia on saatu vielä huomattavasti terästettyä.

3. Dirichlet’n laatikkoperiaate. Inkluusio-ekskluusio-periaate Yksinkertaiset asiat ovat joskus erittäin arvokkaita. Eräs tällainen asia on ns. laatikkoperiaate, jota usein käyttää huomaamattaan. DIRICHLET’N LAATIKKOPERIAATE. Jos n eri kohdetta sijoitetaan m n

laatikkoon, niin johonkin laatikkoon tulee vähintään m

kohdetta ja toi-

n

saalta johonkin laatikkoon tulee enintään m kohdetta. Todistus. Asetetaan vastaoletus: Jokaisessa laatikossa on vähemmän kuin n m

n

kohdetta tai jokaisessa laatikossa on enemmän kuin m kohdetta. Siln ) ja toiloin ensimmäisessä tapauksessa kohteita on < m ˘ m = n kpl ( n sessa tapauksessa > m˘ m = n kpl ( ). ■ Kutakuinkin ilmeinen joukko-opin kaava on #(A∪B) = #A + #B - #(A∩B),

45 missä A ja B ovat äärellisiä joukkoja ja #X merkitsee joukon X alkioiden lu-kumäärää eli kardinaliteettia. Tämä on erikoistapaus ns. inkluusio-ekskluusio-periaatteesta. INKLUUSIO-EKSKLUUSIO-PERIAATE. Kullakin n:stä kohteesta voi olla yksi tai useampia ominaisuuksista O1,…,Om. Merkitään N i:llä niiden kohteiden lukumäärää, joilla on ainakin ominaisuus Oi, N ij:llä niiden kohteiden lukumäärää, joilla on ainakin ominaisuudet i ja j, jne.. Silloin niiden kohteiden lukumäärä, joilla on ainakin yksi ominaisuuksista O1,…,Om, on m

∑

m

Ni -

i=1

m

∑

∑

Nij +

i,j=1 i