Diskreetti matematiikka I [lecture notes] [PDF]

Zitiervorschau

Diskreetti matematiikka I Vesa Halava

Luentomoniste

Turun yliopisto Matematiikan laitos 20014 Turku

2009

Sisältö 1 Matematiikan merkinnöistä 1.1

1

Kreikkalaiset aakkoset

. . . . . . . . . . . . . . . . . . . . . .

1.2

Logiikan merkinnöistä

. . . . . . . . . . . . . . . . . . . . . .

1.3

Summa- ja tulomerkinnät

. . . . . . . . . . . . . . . . . . . .

2 Logiikan alkeita 2.1

1 1 1

4

Matematiikan perusteista

. . . . . . . . . . . . . . . . . . . .

4

2.2

Loogisesta päättelystä

. . . . . . . . . . . . . . . . . . . . . .

6

2.3

Propositio- eli lauselogiikkaa . . . . . . . . . . . . . . . . . . .

9

2.4

Disjunktiiviset ja konjunktiiviset normaalimuodot . . . . . . .

14

2.5

Predikaattilogiikkaa

18

. . . . . . . . . . . . . . . . . . . . . . .

3 Induktio 3.1

21

Induktiotodistuksia . . . . . . . . . . . . . . . . . . . . . . . .

4 Joukko-oppia

21

25

4.1

Joukko käsitteenä . . . . . . . . . . . . . . . . . . . . . . . . .

25

4.2

Tärkeimmät lukujoukot

26

. . . . . . . . . . . . . . . . . . . . .

4.3

Joukkojen väliset suhteet ja operaatiot . . . . . . . . . . . . .

27

4.4

Perusjoukko ja komplementti

. . . . . . . . . . . . . . . . . .

30

4.5

Osittelulait ja De Morganin lait . . . . . . . . . . . . . . . . .

31

5 Relaatiot ja funktiot

32

5.1

Relaatio, relaatioiden yhdistäminen, käänteisrelaatio

. . . . .

33

5.2

Funktion määritelmä . . . . . . . . . . . . . . . . . . . . . . .

37

5.3

Funktioiden ominaisuuksia . . . . . . . . . . . . . . . . . . . .

37

5.4

Reaalifunktiot . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

6 Graateoriaa

42

6.1

Graat ja niiden esitykset

. . . . . . . . . . . . . . . . . . . .

42

6.2

Isomorset graat

. . . . . . . . . . . . . . . . . . . . . . . .

43

6.3

Pisteen aste . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

6.4

Aligraa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

6.5

Polut ja yhdistetyt graat . . . . . . . . . . . . . . . . . . . .

46

Alkusanat Diskreettiä matematiikkaa on vaikea määritellä. Yleensä diskreetiksi matematiikaksi kutsutaan matematiikka jossa tarkastellaan erillisiä, diskreettejä, epäjatkuvia objekteja. Diskreettiä matematiikkaa löytyy siis monilta matematiikan eri aloilta kuten algebrasta, lukuteoriasta, kombinatoriikasta, logiikasta jne. Tämä kurssi on tarkoitettu ensisijaisesti tietojenkäsittelytieteen opiskelijoille. Kurssilla käsitellään (diskreetin) matematiikan perusteita; joukkooppia, logiikkaa, relaatioita ja funktioita. Luentomoniste perustuu Mika Hirvensalon luentomonisteeseen Insinöörimatematiikka IA Lisälukemistoa: A. Arnold and I. Guessarian,

Mathemati s for omputer s ien e, Pren-

ti e Hall, 1996. N.L. Biggs, J. Truss,

Dis rete Mathemati s,

Oxford S ien e Publ., 1989.

Dis rete Mathemati s for Computer S ientists,

Addison-Wesley, 1999.

2nd edition,

1

1 Matematiikan merkinnöistä 1.1 Kreikkalaiset aakkoset Matematiikan ohella useilla luonnontieteen aloilla käytetään kreikkalaisia aakkosia. Joistakin pienistä kirjaimista käytetään kahta eri muotoa.

A B Γ ∆ E Z H Θ

alfa beta gamma delta epsilon zeeta eeta theeta

α β γ δ ǫ, ε ζ η θ, ϑ

ioota kappa lambda myy nyy ksii omikron pii

I K Λ M N Ξ O Π

ι κ, κ λ µ ν ξ o π, ̟

rhoo sigma tau ypsilon i khii psii oomega

P Σ T Υ Φ X Ψ Ω

ρ σ, ς τ υ φ, ϕ χ ψ ω

1.2 Logiikan merkinnöistä Yleisimmät logiikan merkinnät ovat

• ∧

(ja)

• ∨

(tai)

• ¬

(ei)

• ∀

(universaalikvanttori)

• ∃

(eksistentiaalikvanttori)

Jos siis

P

ja

Q

ovat väitelauseita, merkitsee esimerkiksi

väitelausetta  P ja

Q,

kun taas

¬P

tarkoittaa

P :lle

P ∧Q

yhdistettyä

vastakkaista väitettä.

Logiikkaa käsittelevissä osioissa täsmennetään hieman ylläolevia merkintöjä. Kvanttorit pätee

P (x)

ja

∀ ja ∃ tulkitaan siten, että (∀x)P (x) tarkoittaa (∃x)P (x) on olemassa x jolle pätee P (x).

1.3 Summa- ja tulomerkinnät Summa voidaan merkitä lyhyemmin

a1 + a2 + . . . + an =

n X

ai

i=1

ja tulo

a1 · a2 · . . . · an =

n Y i=1

ai .

kaikille

x:ille

1.3 Summa- ja tulomerkinnät

2

Seuraavaksi käsitellään summamerkinnän manipulointia. Vastaavat käsittelysäännöt voidaan saada helposti myös tulolle.

Summausindeksin i

valinta ei ole tärkeä, yhtä hyvin yllä oleva summa

voitaisiin kirjoittaa muodossa

n X

ak , tärkeää

on ainoastaa, että summausin-

k=1

deksiä ei voi vahingossa sekoittaa johonkin toiseen lausekkeissa esiintyvään muuttujaan. Ideana on, että summausindeksi juoksee läpi esiintyvien lukujen

a 1 , . . ., an indeksoinnin luvusta 1 lukuun n, ja tämä ilmaistaan summamerkin X ala- ja yläpuolella olevilla rajoitteilla  i = 1 ja  n. Summamerkintää käyttäen voidaan vaikkapa n:n ensimmäisen kokonais-

luvun summa kirjoittaa lyhyempään muotoon:

1 + 2 + ... + n =

n X

i.

i=1

On kuitenkin huomattava, että kyseessä on vain merkintätapa. Tämä merkintä ei esimerkiksi anna mitään keinoa näyttää toteen, että

1 + 2 + ... + n =

n X

i=

i=1

n(n + 1) , 2

mikä kyllä pitää paikkansa. Summamerkinnän käsittelyyn liittyvät säännöt saadaan suoraan yleisistä summia koskevista säännöistä sekä summamerkinnän määrittelystä. Esimerkiksi tavanomainen osittelulain soveltaminen

c(a1 + a2 + . . . + an ) = ca1 + ca2 + . . . + can voidaan summamerkintää käyttäen kirjoittaa muotoon

c

n X

ai =

i=1

n X

cai .

i=1

Samoin summattavien jäsentely

(a1 + a2 + . . . + an ) + (b1 + b2 + . . . + bn ) = (a1 + b1 ) + (a2 + b2 ) + . . . + (an + bn ) saa muodon

n X i=1

ai +

n X

bi =

i=1

n X (ai + bi ). i=1

Edelleen, summamerkintä voidaan aina katkaista halutusta kohdasta: jos

1 < m < n,

voidaan tietysti kirjoittaa

a1 + . . . + an = a1 + . . . + am + am+1 + . . . + an ,

1.3 Summa- ja tulomerkinnät

3

mikä voidaan edelleen lyhentää muotoon

n X

ai =

i=1

Summausindeksin muutos

m X

ai +

i=1

n X

ai .

i=m+1

on suora seuraus merkintätavasta:

n X

ai =

i=1

n+1 X

ai−1 =

i=2

n−1 X

ai+1 .

i=0

Yleisenä sääntönä pätee, että summausmerkinnän ylä- ja alarajaa voidaan nostaa yhdellä, jos summalausekkeessa esiintyvästä indeksistä vähennetään yksi. Samoin summausmerkinnän rajoja voidaan laskea yhdellä, jos summalausekkeen indeksiin lisätään ykkönen. Tarvittaessa summamerkinnän rajan nostoa tai laskua voidaan tietenkin soveltaa useamman kerran peräkkäin.

Huomautus 1.1.

Joskus summaus suoritetaan jonkin joukon alkioille tai ti-

ettyyn joukkoon kuuluvien indeksien yli. Esimerkiksi, jos eli

X

on lukujen

x1 , x2 , . . . , xk

X = {x1 , x2 , . . . , xk }

muodostama joukko, voidaan käyttää merk-

intää

x1 + x2 + · · · + xk = missä merkintä

x ∈ X tarkoittaa  x X alkiot.

X

x,

x∈X

kuuluu joukkoon

X .

Tässä siis sum-

mataan kaikki joukon

Jos taas halutaan summata vain tietty indeksien, jotka muodostavat joukon

I,

mukaiset alkiot, voidaan kirjoittaa

X

xi .

i∈I

Tässä siis summataan yli niiden indeksien, jotka kuuluvat joukkoon

I.

4

2 Logiikan alkeita 2.1 Matematiikan perusteista Matematiikka eroaa luonnontieteistä ja yhteiskuntatieteistä oleellisesti siinä,

verioida) tai kumota (falsioida) empiirisesti, siis havaintojen perusteella. Tämä voidaan ilmaista myös siten, että matematiikan käsitteitä ei ole operationaalisesti sidottu mihinkään että matematiikan väitteitä ei voida todentaa (

reaalimaailman olioihin. Matemaattisessa teoriassa tosin sen peruskäsitteet, perusobjektit, -ominaisuudet ja -suhteet yleensä muodostetaan teoriaa kehitettäessä reaalimaailman objekteista pitkälle menevällä abstraktiolla; muut kuin peruskäsitteet

määritellään näitä käyttäen. Vastaavasti muut kuin teorian perusominaisuaksioomat) johdetaan eli dedusoidaan aksioomista ja aiemmin dedusoiduista ominaisuuksista eli lauseista (eli teoreemoista). Totuuden kannalta matemaattinen teoria voidaan aina muotoilla ns. aksiomaattis-deduktiivisen teorian muotoon, jossa lauseiden totuus palautuu udet (eli

tällöin aksioomien totuuteen ja deduktiossa käytettyjen päättelysääntöjen pätevyyteen. Päättelysääntöjen pätevyys on yleensä melko ongelmaton ja helposti todennettavissa oleva asia. Melko yllättävältä saattaa tuntua, että

yleensä aksioomien totuusarvo on matematiikan kannalta täysin yhdentekevä seikka. Yleensä sanotaan että lause on tosi, mikäli se on johdettavissa aksioomista, sen enempää kiinnittämättä huomiota aksioomien totuusarvoon.

Esimerkki 2.1.

Shakkipeliä voidaan verrata matemaattiseen teoriaan:

1. aksioomajoukkoa vastaa pelin alkuasetelma, 2. sääntöjen mukaiset siirot päteviä päättelysääntöjä. Matemaattisen teorian yhteydessä usein esiintyvä kysymys onko tämä lause tosi? vastaa shakkipelissä kysymystä voidaanko tällainen asetelma saada pelisääntöjä noudattamalla alkuasetelmasta? Kukin säännönmukaisilla siirroilla saatu asetelma vastaa siis matemaattisen teorian lausetta. Shakkipelissä ei oteta kantaa siihen kysymykseen, onko pelin alkuasetelma jollakin tavalla tosi, ja sama pätee myös matemaattiseen teoriaan. Aksioomien totuusarvo on itse teorian kannalta yleensä merkityksetön. Sen sijaan mielenkiintoista on, mitä aksioomista voidaan johtaa. On tosin huomattava, että matemaattisen teorian aksioomia ei yleensä valita mielivaltaisesti, vaan niiden toivotaan kuvaavan mahdollisimman hyvin teorian objektien perusominaisuuksia. Jos esimerkiksi halutaan teorian kuvaavan luonnollisia lukuja, on syytä valita aksioomat siten, että ne eivät ainakaan ole ristiriidassa luonnollisia lukuja koskevan intuition kanssa. Aksioomien ristiriidattomuus puolestaan on matemaattisen teorian kannalta erittäin merkittävä kysymys. Teoriaa ei voida pitää hyväksyttävänä (tai

2.1 Matematiikan perusteista

5

edes mielenkiintoisena), jos sen aksioomat ovat keskenään ristiriitaiset. Ristiriitaisesta aksioomajoukosta voidaan nimittäin pätevillä päättelysäännöillä johtaa

mikä tahansa teoriaa koskeva väittämä, erityisesti voidaan aina johtaa

väitelause ja sen kielto. Aksioomien ristiriidattomuus sen sijaan on erittäin hankalasti (jos lainkaan) todennettavissa: lähes kaikkien mielenkiintoisten matemaattisten teorioiden aksioomajoukkojen ristiriidattomuutta ei voida teorian puitteissa todentaa.

Esimerkki 2.2. Luonnollisten lukujen teorian peruskäsitteet ovat joukko N, luonnollinen luku

1∈N

ja luonnollisen luvun

n seuraaja s(n).

Luonnolliset

luvut voidaan aksiomatisoida ns. Peanon aksioomilla: 1. Jos

n 6= m,

niin

seuraaja).

2. Kaikille joukon

s(n) 6= s(m) N

alkioille

n

(kahdella eri luonnollisella luvulla on eri

pätee

luonnollisen luvun seuraaja). 3. Jos joukko niin silloin

s(n) 6= 1

(ykkönen ei ole minkään

A sisältää luvun 1 ja jokaisen sisältämänsä luvun seuraajan, A sisältää kaikki luonnolliset luvut (induktioaksiooma).

Näistä peruskäsitteistä ja aksioomista lähtien johdetaan kaikki luonnollisten lukujen ominaisuudet. Esimerkiksi yhteenlaskun määrittely voidaan

1 + n = n + 1 = s(n)

aloittaa määrittelemällä kaikkia summia

n + m.

Samoin käsitteet

ja laajentaa tästä koskemaan

suurempi kuin

ja

pienempi kuin

voidaan määritellä käyttäen pelkästään mainittuja peruskäsitteitä. Luonnollisten lukujen teoriaa voidaan laajentaa kokonaislukujen teoriaksi uusia käsitteitä määrittelemällä. Samoin voidaan kokonaisluvuista päästä rationaalilukuihin ja edelleen reaalilukuihin. Toisaalta määritelmät voivat olla varsin monimutkaisia, ja toisinaan on perusteltua käyttää omaa aksiomatisointa esimerkiksi reaalilukuihin.

Esimerkki 2.3.

Reaalilukujen teorian peruskäsitteet ovat joukko

0 ∈ R,

1 ∈ R,

ykkönen

yhteenlasku

+

ja kertolasku

sioomat on tapana jaotella kolmeen ryhmään:

·.

R,

nolla

Reaalilukujen ak-

A) Kunta-aksioomat: 1. Kaikille reaaliluvuille

a, b

ja

c

pätee

a + (b + c) = (a + b) + c

ja

a · (b · c) = (a · b) · c. 2. Jokaiselle reaaliluvulle

a

pätee

0+a=a

ja

1 · a = a.

a kohti on olemassa a:n vastaluku −a, joka toteuta kohti on −1 −1 käänteisluku a , joka toteuttaa a · a = 1.

3. Jokaista reaalilukua taa

a + (−a) = 0

olemassa

ja jokaista nollasta eroavaa reaalilukua

2.2 Loogisesta päättelystä 4. Kaikille reaaliluvuille 5. kaikille reaaliluvuille

B) Järjestysaksioomat:

a

ja

a, b,

b ja

pätee

c

a+b=b+a

pätee

raavat ehdot:

R+ , a = 0 2. Jos

tai

a kohti −a ∈ R+ .

a, b ∈ R+ ,

niin

ja

a · b = b · a.

a · (b + c) = a · b + a · c.

On olemassa osajoukko

1. Jokaista reaalilukua

6

R+ ⊆ R,

joka toteuttaa seu-

pätee tarkalleen yksi vaihtoehdoista

a∈

a + b, a · b ∈ R+ .

C) Täydellisyysaksiooma: Jokaisella epätyhjällä, ylhäältä rajoitetulla reaalilukujoukolla on pienin yläraja. Edellä mainittuihin käsitteisiin perustuen voidaan määritellä kaikki yleensä tarvittavat reaalilukuja koskevat käsitteet ja aksioomista johdetaan reaalilukujen ominaisuudet. Esimerkiksi järjestysaksioomassa mainittua osajoukkoa kutsutaan yleensä lään

a>b

positiivisten reaalilukujen joukoksi ja tämän avulla määritel-

tarkalleen silloin, kun

a − b ∈ R+ .

Aksioomista lähtien voidaan

muun muuassa johtaa kaikki yhtälöiden ja epäyhtälöiden käsittelysäännöt, esimerkiksi että kerrottaessa epäyhtälö negatiivisella luvulla sen epäyhtälömerkki kääntyy.

Esimerkki 2.4. Tarkastellaan esimerkin vuoksi, miten ylläolevista aksioomista seuraa se tunnettu asia, että nollalla kertominen tuottaa aina nollan. Ensin-

0 = 0 + 0 kunta-aksiooman 2 perusteella, joten a · 0 = a · (0 + 0) = a · 0 + a · 0 kunta-aksiooman 5 perusteella. Edelleen kunta-aksiooman 3 perusteella reaaliluvulla a · 0 on vastaluku −a · 0, joka lisäämällä yhtälön kumpaankin puoleen saadaan a · 0 + (−a · 0) = (a · 0 + a · 0) + (−a · 0). näkin

Soveltamalla kunta-aksioomia 3 ja 1 saadaan tämä sievenemään muotoon

0 = a · 0.

Huomautus 2.5.

Kummassakin yllä olevassa esimerkissä käytetään

oppia taustateoriana.

joukko-

Joukko-oppiin perehdytään tarkemmin myöhemmin.

2.2 Loogisesta päättelystä Esimerkissä 2.4 sivuttiin lopuksi hieman loogista päättelyä: Reaalilukujen aksioomista pääteltiin, että

a·0 = 0. Seuraavaksi perehdytään loogisen päät-

telyn muotoihin hieman yksityiskohtaisemmin.

deduktiivinen, induktiivinen ja abduktiivinen päättely. Deduktiivisessa päättelyssä oletuksista saadaan johtopäätös käyttämällä päättelysääntöjä. Induktiivisessa päättelyssä johdePäättelyn eri muodoista voidaan mainita ainakin

taan joukosta tapauksia yleinen sääntö, ja abduktiossa taas tyypillisesti tunnetuista säännönmukaisuuksista ja seurauksesta päätellään

tunut.

mitä on tapah-

2.2 Loogisesta päättelystä

7

Matemaattisten lauseiden todistamiseen käytetään ainoastaan loogisesti sitovaa deduktiivista päättelyä ja siksi siihen perehdytään jatkossa tarkem-

Syllogismi on deduktion muoto, jossa kahdesta premissistä (pääpremissi ja alipremissi) päätellään johtopäätös. min.

Esimerkki 2.6.

Klassinen esimerkki syllogismista:

Jokainen ihminen on kuolevainen

Sokrates on ihminen

(pääpremissi)

(alipremissi)

Sokrates on kuolevainen

(johtopäätös)

Määritelmä 2.7.

Päättely

htopäätökseen Q on pätevä

premisseistä eli oletuksista P1 , P2 , . . ., Pn joloogisesti sitova, jos Q on tosi aina silloin kun

eli

premissit P1 , P2 , . . ., Pn ovat yhtä aikaa tosia. Tällöin merkitään P1 , P2 , . . ., Pn |= Q ja sanotaan, että Q on looginen johtopäätös premisseistä P1 , P2 , . . ., Pn . Päättely on siis epäpätevää, mikäli voi esiintyä sellainen tulkinta, jossa premissit ovat kaikki tosia, mutta johtopäätös epätosi.

Määritelmä 2.8.

P |= Q P =⇒ Q

Jos premissejä on vain yksi, merkitään tavallisesti

ja sanotaan, että P implikoi Q:n. Päättelyä implikaatioksi. Jos P =⇒ Q ja Q =⇒ P , sanotaan, että P ja Q ovat ekvivalentit (merkitään P ⇐⇒ Q). sijaan

P =⇒ Q

sanotaan

Huomautus 2.9.

lauseet

Kuten luvun alussa mainittiin, matemaattisen lauseen

A1 , . . ., Ak . Täten siis seuraussuhteen A1 , . . ., Ak |= L

todistaminen merkitsee sen johtamista aksioomista matemaattisen lauseen

L

todistaminen on

toteen näyttämistä.

Jos esimerkiksi tulee näyttää toteen, että luonnollisille luvuille pätee

L, tapahtuu tämä periaatteessa siten, että valitaan esimerkin 2.2 Peanon aksioomat oletusjoukoksi P1 , P2 , P3 , ja tämän jälkeen näytetään toteen, että P1 , P2 , P3 |= L. Käytännössä uuden matemaattisen väittämän todistuklause

sessa ei kuitenkaan tarvitse yleensä nojautua aksioomiin asti, vaan yleensä voidaan käyttää premisseinä jo todistettuja lauseita (joiden siis jo tiedetään seuraavan aksioomista). Tavallisimmat tavat matemaattisen lauseen

P

=⇒ Q

todistamiseen

ovat 1.

Suora todistus. Suorassa todistuksessa pyritään löytämään helposti todistuva osaimplikaatioiden ketju

P =⇒ P1 , P1 =⇒ P2 , . . ., Pn−1 =⇒

Pn , Pn =⇒ Q 2.

Epäsuora todistus.

Epäsuorassa todistuksessa implikaation

sijasta todistetaan väite

¬Q =⇒ ¬P .

P =⇒ Q

2.2 Loogisesta päättelystä

8

Epäsuora todistus perustuu seuraavaan hyvin yksinkertaiseen ajatuk-

¬Q =⇒ ¬P , merkitsee tämä sitä, että aina ¬Q on tosi, on myös ¬P tosi. Nyt alkuperäinen väite P =⇒ Q on myös oikea, sillä jos P on tosi, on ¬P epätosi, eikä tällöin ¬Q voi olla tosi. Täten Q on tosi. Epäsuorassa todistuksessa väitettä ¬Q kutsutaan vastaoletukseksi. Jos ¬P on osoitettu epätodeksi, sanotaan epäsuoran todistuksen johtaneen ristiriitaan. Tällöin siis päätellään Q:n pitävän paikkansa. Implikaatiota ¬Q =⇒ ¬P kutsutaan implikaation P =⇒ Q kontrapositioksi. seen: Jos on todistettu, että kun

a2 + b2 ≥ 2

Esimerkki 2.10. Osoitetaan, että kaikille reaaliluvuille a ja b pätee ab.

Oletetaan tätä varten tunnetuksi että reaalilukujen aksioomista (kutsu-

taan niitä kollektiivisesti nimellä

R)

V1 : (∀x)(x2 ≥ 0),

seuraa väite

siis että

kaikkien reaalilukujen neliöt ovat ei-negatiivisia. Todistus voidaan kirjoittaa osaimplikaatioiden ketjuksi seuraavasti: 1.

R |= V1

2.

V1 =⇒ (a − b)2 ≥ 0.

3.

(a − b)2 ≥ 0 =⇒ a2 − 2ab + b2 ≥ 0

4.

a2 − 2ab + b2 ≥ 0 =⇒ a2 + b2 ≥ 2ab

5.

a2 + b2 ≥ 2ab =⇒

a2 + b2 ≥ ab. 2

Kukin osaimplikaatio puolestaan on kirjoitettavissa edelleen yksinkertaisempien osaimplikaatioden ketjuksi, joista kukin voidaan perustella reaalilukujen aksioomilla tai loogisilla päättelysäännöillä. Käytännössä todistuksia ei kuitenkaan kirjoiteta näin yksityiskohtaisesti, mutta väljemmästä esitysasusta huolimatta jokainen suora matemaattinen todistus on periaatteessa purettavissa jonoksi yksinkertaisia osaimplikaatioita.

Esimerkki 2.11. Osoitetaan, että jos reaaliluvut a ja b eivät kuulu joukkoon R+ ,

niin myöskään

a+b

seuraavasti (merkitään reaalilukujen

R =⇒

R+ . Väite aksioomia R:llä)

ei kuulu joukkoon

Jos

a, b ∈ / R+ , ,

niin

voidaan esittää siis

a+b∈ / R+ .

Todistetaan väite epäsuorasti.

Vastaoletus: On olemassa reaaliluvut a, b ∈/ R+ , joille a + b ∈ R+. Järjestysaksiooman 1 mukaan, koska

R+ .

Samoin joko

1. Jos

b=0

a = b = 0,

tai

niin

−b ∈ R+ .

a∈ / R+ ,

niin joko

a=0

tai

Käydään läpi kaikki vaihtoehdot:

a + b = 0 ∈ R+ .

−a ∈

2.3 Propositio- eli lauselogiikkaa

9

a = 0 ja −b ∈ R+ , niin järjestysaksiooman 2 mukaan a+b+(−b) = 0 + b − b = 0 ∈ R+ .

2. Jos

b = 0 ja −a ∈ R+ , niin järjestysaksiooman 2 mukaan a+b+(−a) = a + 0 − a = 0 ∈ R+ .

3. Jos

−a ∈ R+ ja −b ∈ R+ , (−a) + (−b) = 0 ∈ R+ .

4. Jos

niin järjestysaksiooman 2 mukaan

a+b+

Kaikissa tapauksissa päädyttiin siis ristiriitaan järjestysaksiooman 1 kanssa, sillä sen mukaan 0 ei kuulu joukkoon

R+ .

Näin ollen vastaoletus on väärä ja

väite on tosi. Jos on osoitettava, että jokin väite ei pidä yleisesti paikkansa, riittää usein

falsiomiseksi eli vääräksi todistamiseksi löytää yksikin vastaesimerkki. Toisaalta, väitettä ei voi todistaa oikeaksi käymällä läpi joitakin esväitteen

imerkkitapauksia. Näyttää pitävän paikkaansa, ainakin näille, joita kokeilin, ei siis ole todistus.

Esimerkki 2.12.

Jos on osoitettava, että väite

x2 + 2x ≥ 0 ei päde

kaikille

reaaliluvuille, riittää löytää vastaesimerkki, jollaiseksi kelpaa vaikkapa

x=

−1. Yksi tapa todistaa matemaattinen väittämä oikeaksi äärettömän monen tapauksen kohdalla on ns.

täydellinen induktio, joka nimestään huolimatta ei

ole induktiivista päättelyä, vaan yksi deduktion alalaji. Induktioon palataan myöhemmin.

2.3 Propositio- eli lauselogiikkaa Yksinkertaisin tapa esittää väitteitä ja päättelyitä on

propositio-

eli lausel-

ogiikka. Propositiologiikassa lauseilla ei oleteta olevan sisäistä rakennetta, mutta lauseita voidaan yhdistellä loogisilla

konnektiiveilla.

Määritelmä 2.13.

Propositiologiikan peruskäsitteet ovat propositiomuuttujat eli atomaariset propositiot p1 , p2 , p3 , . . . sekä näitä yhdistävät loogiset konnektiivit negaatio ¬, konjunktio ∧, disjunktio ∨, implikaatio → (luetaan jos . . ., niin . . .) ja ekvivalenssi ↔ (luetaan  . . . jos ja vain jos . . . ). Propositiot eli lauseet ovat joko propositiomuuttujia tai saatu loogisten konnektiivien avulla yhdistämällä.

Huomautus 2.14.

P =⇒ Q eroaa ylläolevan määritelmän implikaatiosta p → q siten, että P =⇒ Q on kahden lauseen P ja Q välinen asiantila: Jos P on tosi, on myös Q tosi. Sen sijaan p → q on vain uusi lause, joka on saatu yhdistämällä lauseet (propositiot) p ja q . Myöhemmin nähdään kuitenkin, että näillä kahdella implikaation käsitAiemmin määritelty implikaatio

teillä on vahva yhteys.

2.3 Propositio- eli lauselogiikkaa Yhdistetyn proposition

10

päämuoto määräytyy viimeksi käytetyn konnekti-

ivin mukaan, esimerkiksi proposition

((p1 ∨p2 ) → p3 )∧(¬p1 → p3 ) päämuoto

on konjunktio. Sulkeita vähennetään sopimalla että negaatio sitoo vahvemmin kuin muut konnektiivit, toisin sanoen

(¬p1 ) → p2

eikä propositiota

¬(p1 → p2 ).

¬p1 → p2

tarkoittaa propositiota

Propositiot itsessään ovat vain merkkijonoja, mutta niihin voidaan liittää

semantiikka (merkitysoppi) seuraavan määritelmän mukaisesti.

Määritelmä 2.15. tai

0

Propositiomuuttujiin voidaan liittää totuusarvo

1 (tosi)

(epätosi). Yhdistettyjen lausekkeiden totuusarvo määritellään seuraa-

van taulukon mukaan:

p 0 0 1 1

q 0 1 0 1

¬p 1 1 0 0

p∧q 0 0 0 1

p∨q 0 1 1 1

p→q 1 1 0 1

p↔q 1 0 0 1

Edellisen määritelmän mukaista taulukkoa sanotaan

totuustaulukoksi.

Valintaa, jossa kaikille propositiomuuttujille annetaan jokin totuusarvo kutsutaan

totuusarvotukseksi.

Totuustaulukon vaakarivi vastaa siis yhtä to-

tuusarvotusta. Toisaalta, totuustaulukossa käydään läpi tarkasteltavan propo-

υ on totuusarvotus, propop totuusarvoa totuusarvoituksessa υ merkitään υ(p):llä. Vastaavasti, jos P on propositio, niin P :n totuusarvoa totuusarvotuksessa υ merkitään υ(P ).

sition totuusarvo kaikissa totuusarvotuksissa. Jos sitiomuuttujan

Esimerkki 2.16.

Selvitetään proposition

P = (p ∧ ¬q) ∨ (((r ∧ ¬q) ∧ ¬r) ∨ (p ∧ q)) α(p) = 0, α(q) = 1 ja α(r) = 1. Ensiksi voidaan todeta, että ¬q :n totuusarvo on 0, joten p ∧ ¬q :n totuusarvo on 0. Koska myös proposition ∧r totuusarvo on 0, on tällöin proposition (r ∧ ¬q) ∧ ¬r totuusarvo on 0. Seuraavaksi todetaan, että p ∧ q :n totuusarvo on 0, mistä seuraa, että päämuodon toisen sulkulausekkeen ja täten myös koko proposition totuusarvo on 0. Siis α(P ) = 0. totuusarvo totuusarvotuksessa

Esimerkki 2.17. q) ∧ r

α,

jolle

On helppo todeta, että propositioilla

p ∧ (q ∧ r)

ja

(p ∧

on aina samat totuusarvot, joten näistä propositioista voidaan käyttää

sulkeita vähentävää merkintää

p ∧ q ∧ r . Merkintä yleistyy myös disjunktiolle

ja useammalle kuin kolmelle propositiomuuttujalle.

Totuustaulukkoa käyttämällä voidaan selvittää propositiologiikan väittämien välisiä loogisia seuraussuhteita.

Esimerkki 2.18. propositiosta

Selvitetään, onko propositio

p → q.

¬p → ¬q

looginen seuraus

Kirjoitetaan tätä varten totuustaulukko:

2.3 Propositio- eli lauselogiikkaa p 0 0 1 1

¬p 1 1 0 0

q 0 1 0 1

¬q 1 0 1 0

p→q 1 1 0 1

¬p → ¬q 1 0 1 1 p → q

Nähdään, että taulukon toisella rivillä premissi htopäätös

¬q → ¬q

Esimerkki 2.19. sitioista

p

ja

11

on tosi, mutta jo-

ei. Täten johtopäätös ei seuraa premissistä loogisesti. Selvitetään, onko propositio

p → q,

q

looginen seuraus propo-

toisin sanoen, onko päättely

Kirjoitetaan tätä varten totuustaulukko:

p 0 0 1 1

p

pätevä.

p→q 1 1 0 1

q 0 1 0 1

Taulukosta nähdään, että premissit

p, p → q |= q

ja

p → q ovat yhtäaikaisesti tosia vain q on tosi. Näin ollen päättely on

neljännellä rivillä, jolloin myös johtopäätös loogisesti sitovaa.

Esimerkki 2.20.

Kirjoitetaan lausetta Siitä että jos matematiikka on help-

poa niin logiikka on helppoa, seuraa että jos logiikka ei ole helppoa, niin ei matematiikka ole helppoa vastaava propositio ja laaditaan sille totuustaulukko. Valitaan propositiomuuttujiksi

q =logiikka

p=matematiikka

on helppoa ja

on helppoa. Tällöin propositio jos matematiikka on helppoa

niin logiikka on helppoa kirjoitetaan

p → q

ja jos logiikka ei ole help-

¬q → ¬p. Alkuperäisen P = (p → q) → (¬q → ¬p).

poa, niin matematiikka ei ole helppoa saa muodon lauseen muotoilu propositiologiikalla on täten

Laaditaan tälle totuustaulukko laatimalla ensin totuustaulukot propositioille

p→q

ja

¬q → ¬p p 0 0 1 1

q 0 1 0 1

p→q 1 1 0 1

¬q → ¬p 1 1 0 1

Totuustaulukosta voidaan huomata, että tiomuuttujien

p

ja

q

Määritelmä 2.21. 1.

Toteutuva

2.

Kumoutuva

P

P 1 1 1 1

on tosi riippumatta proposi-

totuusarvoista. Propositio on

jos se on tosi ainakin yhdessä arvotuksessa. jos se on epätosi ainakin yhdessä arvotuksessa.

2.3 Propositio- eli lauselogiikkaa 3.

Tautologia

12

eli loogisesti tosi lause, jos se on tosi riippumatta siinä esi-

intyvien propositiomuuttujien totuusarvoista. 4.

Kontradiktio

eli loogisesti epätosi, jos se on epätosi riippumatta siinä

esiintyvien propositiomuuttujien totuusarvoista. 5.

Kontingentti, jos se ei ole

tautologia eikä kontradiktio

Loogisen seurauksen ja implikaatio-konnektiivin välillä vallitsee seuraavanlainen yhteys:

Lause 2.22.

P =⇒ Q pätee tarkalleen silloin kun P → Q on tautologia.

Todistus. Jos P =⇒ Q, on Q tosi aina kun P on. Tällöin konnektiivin → määritelmän mukaan P → Q in tautologia, sillä P :n ollessa epätosi on P → Q aina tosi. Oletetaan sitten, että P → Q on tautologia. Tällöin konnektiivin → määritelmän mukaan P :n ollessa tosi on välttämättä myös Q:n oltava tosi, joten P =⇒ Q. P1 , . . ., Pn |= Q selvitP1 ∧ . . . ∧ Pn → Q tautologia.

Edellisen lauseen mukaan loogisen seurauksen tämiseksi voidaan yhtä hyvin selvittää, onko

Esimerkki 2.23.

Tautologioita ovat esimerkiksi

• P ∨ ¬P (tertium non datur) • ¬(P ∧ ¬P ) (ristiriidan laki) • (P ∧ (P → Q)) → Q (modus ponens) • (P → Q) ↔ (¬Q → ¬P ) (kontrapositio) Huomaa, että yllä luetellut tautologiat formalisoivat loogisesti päteviä päättelysääntöjä: Esimerkiksi tertium non datur (kolmannen poissuljetun

P tai ¬P jompikumpi on tosi, kun taas ¬P eivät molemmat voi olla tosia. Modus päättelyketju: Propositiosta P ja P → Q yhdessä

laki) ilmaisee, että propositioista ristiriidan laki ilmaisee, että ponens on tyypillinen voidaan päätellä

Q,

P

ja

ja kontrapositio on tyypillinen tapa todistaa propositio

P → Q todistamalla ¬Q → ¬P sen sijaan. Esimerkissä ei ole välttämätöntä, että P ja Q olisivat atomaarisia propositioita. Määritelmän 2.21 ominaisuudet (toteutuvuus, kumoutuvuus, tautologisuus, kontradiktivisyys tai kontingenssi) ovat siis kutakin propositiota kohti aina todennettavissa totuustaulukon avulla. Toisaalta taas totuustaulukon laatiminen käy työlääksi propositiomuuttujien määrän kasvaessa. Teoreettisen tietojenkäsittelytieteen suurin ratkaisematon ongelma, ns.

P

vs.

NP

-ongelma voidaan muotoilla seuraavasti: onko proposition toteutuvuuden selvittämiseksi olemassa (oleellisesti) parempaa menetelmää kuin kaikkien totuusarvotusten läpikäynti? Jos esimerkiksi kaikki propositiot

P1 , . . ., Pn

2.3 Propositio- eli lauselogiikkaa ovat muotoa

p1 ∧ . . . ∧ pk → q , tunnetaan tehokas P1 ∧ . . . ∧ Pn toteutuva. Kyseinen

tämiseksi, onko

13

menetelmä sen selvitmenetelmä on tärkeä

logiikkaohjelmoinnin kannalta (esim. Prolog-kieli), mutta yleistä tehokasta menetelmää toteutuvuudenen selvittämiseksi ei tunneta. Ainakin joissakin tapauksissa proposition ominaisuuksia voidaan pyrkiä selvittämään siirtymällä

loogisesti ekvivalentteihin

propositioihin.

Määritelmä 2.24. Propositiot P ja Q ovat loogisesti ekvivalentit, merkitään P ≡ Q, jos P |= Q ja Q |= P . ja Q ovat yhtäaikaa tosia.

Esimerkki 2.25.

Toisin sanoen,

Helposti todetaan, että

P ≡Q

tarkalleen silloin kun

P ∧Q ≡ Q∧P

ja että

P

¬(¬P ) ≡ P .

Loogiselle ekvivalenssille saadaan monia muitakin helposti todennettavissa olevia identiteettejä.

Esimerkki 2.26.

⊥ (falsum) joka on ⊤ (verum) joka on aina tosi (1). Muun muuassa seuraavat

Otetaan käyttöön propositiomuuttujat

aina epätosi (0) ja

loogiset ekvivalenssit pätevät: 1.

P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R

ja

assosiatiivilait)

P ∨ (Q ∨ R) ≡ (P ∨ Q) ∨ R

2.

P ∧Q≡Q∧P

3.

P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)

ja

P ∨Q≡Q∨P

(vaihdanta- eli kommutointilait) ja

(osittelu- eli distribuutiolait) 4.

P ∧⊤≡P

5.

P ∧ ¬P ≡ ⊥

6.

¬(P ∧ Q) ≡ (¬P ) ∨ (¬Q)

ja

lait)

7.

¬(¬P ) ≡ P

P ∨⊥≡P

ja

(liitäntä- eli

P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)

(rajoituslait)

P ∨ ¬P ≡ ⊤ ja

(täydellisyyslait)

¬(P ∨ Q) ≡ (¬P ) ∧ (¬Q)

(De Morganin

(kaksoisnegaation laki)

Näistä säännöistä ainakin 1-5 ovat muistamisen arvoiset. Ne ilmaisevat, että propositiot muodostavat ekvivalenssin

albegran.

≡

suhteen niin sanotun

Boolen

Esimerkki 2.27. (p ∧ ¬q) ∨ (r ∧ ¬q ∧ ¬r) ∨ (p ∧ q) ≡ (p ∧ ¬q) ∨ ((r ∧ ¬r) ∧ ¬q) ∨ (p ∧ q)

≡ (p ∧ ¬q) ∨ (⊥ ∧ q) ∨ (p ∧ q) ≡ (p ∧ ¬q) ∨ ⊥ ∨ (p ∧ q)

≡ (p ∧ ¬q) ∨ (p ∧ q) ≡ p ∧ (¬q ∨ q)p ∧ ⊤ ≡ p.

2.4 Disjunktiiviset ja konjunktiiviset normaalimuodot

14

2.4 Disjunktiiviset ja konjunktiiviset normaalimuodot Määrittelemme nyt eräitä propositioiden normaalimuotoja sekä osoitamme, että jokainen propositio voidaan efektiivisesti saattaa näihin normaalimuotoihin.

Määritelmä 2.28. Literaali

positiivinen literaali ) tai propositiomuuttujan negaatio (¬p, negatiivinen literaali ). Jos n ≥ 1 ja L1 , . . . , Ln ovat literaaleja, on L1 ∧ · · · ∧ Ln alkeiskonjunktio ja L1 ∨ · · · ∨ Ln alkeisdisjunktio. on joko propositiomuuttuja (p,

Esimerkki 2.29. p2 ja ¬p1 ovat literaaleja. Jokainen literaali on sekä alkeiskonjunktio, että alkeisdisjunktio.

on alkeisdisjunktio.

Määritelmä 2.30.

p2 ∧ ¬p3 ∧ p1

Propositio

on alkeiskonjunktio ja

K1 ∨ · · · ∨ Kn ,

missä kukin

Ki

¬p2 ∨ ¬p4

on alkeiskon-

disjunktiivisessa normaalimuodossa (DN-muodossa ). Propositio missä kukin Di on alkeisdisjunktio, on konjunktiivisessa normaalimuodossa (KN-muodossa ). Erityisesti sovitaan, että K1 ∨ · · · ∨ Kn = ⊥ junktio, on

D1 ∧ · · · ∧ Dn , ja

D1 ∧ · · · ∧ Dn = ⊤,

Esimerkki 2.31.

kun

n = 0.

Alkeiskonjunkiot ja alkeisdisjunktiot ovat sekä DN- että

(p ∧ ¬q) ∨ r on DN-muodossa, mutta se ei ole KN(p ∧ ¬q) ∨ r voidaan muuntaa ekvivalentiksi proposi-

KN-muodossa. Propositio muodossa. Propositio

tioksi, joka on KN-muodossa, käyttämällä tunnettuja loogisia ekvivalenssejä:

(p ∧ ¬q) ∨ r ≡ (p ∨ r) ∧ (¬q ∨ r). Selvästi jälkimmäinen propositio on KN-muodossa Propositioden muuntamisessa haluttuun normaalimuotoon tarvitaan erityisesti osittelu- eli distributiivilakia ja De Morganin lakeja, jotka yleistetään seuraavissa lemmoissa.

Lemma 2.32. ( Yleistetyt distributiivilait) Jos P1 , . . . , Pm , Q1 , . . . , Qn ovat propositoita (m, n ≥ 0), niin (P1 ∨· · ·∨Pm )∧(Q1 ∨· · ·∨Qn ) ≡ (P1 ∧Q1 )∨· · ·∨(P1 ∧Qn )∨· · ·∨(Pm ∧Qn )

ja (P1 ∧· · ·∧Pm )∨(Q1 ∧· · ·∧Qn ) ≡ (P1 ∨Q1 )∧· · ·∧(P1 ∨Qn )∧· · ·∧(Pm ∨Qn ).

Lemma 2.33. ( Yleistetyt De Morganin lait)

Jos P1 , . . . , Pn ovat propositioita (n ≥ 0), niin ¬(P1 ∨ · · · ∨ Pn ) ≡ ¬P1 ∧ · · · ∧ ¬Pn

ja ¬(P1 ∧ · · · ∧ Pn ) ≡ ¬P1 ∨ · · · ∨ ¬Pn .

2.4 Disjunktiiviset ja konjunktiiviset normaalimuodot

15

Molemmat lemmat voidaan todistaa induktiolla. Näiden lakien sekä ekvivalenssin

¬¬P ≡ P

avulla jokainen propositio voidaan saattaa sekä DN-

että KN-muotoon.

Lause 2.34. Jokainen propositio on ekvivalentti disjunktiivisessa normaal-

imuodossa olevan proposition sekä konjunktiivisessa normaalimuodossa olevan proposition kanssa. Tällaiset normaalimuodot voidaan aina määrätä efektiivisesti. Todistus.

Sivuutetaan.

Esimerkki 2.35.

Propositiolle

¬(p ∨ ¬q) ∧ (¬r ∨ (p ∧ ¬q) ∨ ¬s)

saadaan

DN-muoto esimerkiksi seuraavasti:

¬(p ∨ ¬q) ∧ (¬r ∨ (p ∧ ¬q) ∨ ¬s) ≡ ¬p ∧ ¬¬q ∧ (¬r ∨ (p ∧ ¬q) ∨ ¬s) ≡ ¬p ∧ q ∧ (¬r ∨ (p ∧ ¬q) ∨ ¬s)

≡ (¬p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ p ∧ ¬q) ∨ (¬p ∧ q ∧ ¬s)

≡ (¬p ∧ q ∧ ¬r) ∨ ⊥ ∨ (¬p ∧ q ∧ s) ≡ (¬p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ ¬s).

Propositioiden DN- ja KN-muodot eivät ole yksikäsitteisiä ja niitä voidaan usein sieventää käyttäen tunnettuja loogisia ekvivalensseja ja laskulakeja.

Määritelmä 2.36.

Jos

p

on propositiomuuttuja, on merkitään

p1 = p

ja

0

p = ¬p. Jokainen literaali voidaan esittää siis muodossa Jos

α

on tulkinta ja

α(p) = 1,

niin selvästi

( 1, α(p ) = 0, a

Toisaalta, jos

α(p) = 0,

pa , missä a = 1 tai a = 0.

kun kun

a = 1, a = 0.

ja

a = 1, a = 0.

ja

niin

( 0, α(p ) = 1, a

kun kun

Saadaan siis tulos

α(pa ) = 1 ⇐⇒ α(p) = a. Kiinnitetään nyt jokin mielivaltainen

n ≥ 1

ja tarkastellaan vain niitä

propositioita, joiden propositiomuuttujienjoukko on

Määritelmä 2.37. junktio

Jos

0 ≤ k ≤ 2n − 1,

niin

a

(1)

{p0 , p1 , . . . , pn−1 }.

k's mintermi mk

n−1 pa00 ∧ pa11 ∧ · · · ∧ pn−1 ,

on alkeiskon-

2.4 Disjunktiiviset ja konjunktiiviset normaalimuodot missä

k.

ai :t

on valittu siten, että

Vastaava

k's maxtermi Mk

a0 a1 . . . an−1

16

esittää 2-järjestelmässä lukua

on alkeisdisjunktio

0 1 n p1−a ∨ p1−a ∨ · · · ∨ p1−a 0 1 n−1 .

Esimerkki 2.38. Jos n = 3, on mintermejä ja maxtermejä kumpiakin 8 = 23 kappaletta. Esimerkiksi

m3 = p00 ∧ p11 ∧ p12 = ¬p0 ∧ p1 ∧ p2 ja

M3 = p1−0 ∨ p1−1 ∨ p1−1 = p0 ∨ ¬p1 ∨ ¬p2 . 0 1 2 Jos taas

n = 4,

niin esimerkiksi

m3 = p00 ∧ p01 ∧ p12 ∧ p13 = ¬p0 ∧ ¬p1 ∧ p2 ∧ p3 . Nyt huomion (1) avulla saadaan seuraava lemma.

Lemma 2.39. Olkoon a0 a1 . . . an−1 luvun

k (0 ≤ k ≤ 2n − 1) n:n pituinen

2-järjestelmäesitys sekä α mielivaltainen tulkinta. Tällöin

α(mk ) = 1 ⇐⇒ α(p0 ) = a0 , . . . , α(pn−1 ) = an−1

ja α(Mk ) = 0 ⇐⇒ α(p0 ) = a0 , . . . , α(pn−1 ) = an−1 .

Määritelmä 2.40. ovat joukossa (1)

n ≥ 1. Propositio P , {p0 , p1 , . . . , pn−1 }, on Olkoon

jonka propositiomuuttujat

kanonisessa diskunktiivisessa normaalimuodossa (KDN), jos se on muotoa

mk 1 ∨ mk 2 ∨ · · · ∨ mk r , (jos (2)

r = 0,

missä

r≥0

ja

0 ≤ k1 < k2 < · · · kr ≤ 2n − 1

tulkitaan disjunktio propositioksi

⊥)

ja

kanonisessa konjunktiivisessa normaalimuodossa (KKN), jos se on muotoa

Mk1 ∧Mk2 ∧· · ·∧Mkr , (jos

r = 0,

missä

r≥0

ja

0 ≤ k1 < k2 < · · · < kr ≤ 2n −1

tulkitaan konjunktio propositioksi

⊤).

Lause 2.41. Propositio P , jonka propositiomuuttujat ovat joukossa {p0 , . . . , pn−1 },

on aina ekvivalentti yksikäsitteisen sellaisen KDN-muodossa olevan proposition Q kanssa, jonka propositiomuuttujienjoukko on {p0 , . . . , pn−1 }. Vastaavasti P on ekvivalentti yksikäsitteisen sellaisen KKN-muodossa olevan proposition R kanssa, jonka propositiomuuttujienjoukko on {p0 , . . . , pn−1 }. Molemmat normaalimuodot ovat efektiivisesti määrättävissä.

2.4 Disjunktiiviset ja konjunktiiviset normaalimuodot Todistus.

17

P ≡ ⊥, on ⊥ P:n KDN-esitys. Muutoin tämä saadaan muoQ, jossa esiintyvät numerojärjestyksessä kaikki mintermit mk , joille k :n n:n pituinen 2-järjestelmäesitys a0 a1 . . . an−1 on sellainen, että α(P ) = 1, kun α(pi ) = ai (i = 0, 1, . . . , n − 1). Nämä k :t nähdään P :n totuustaulusta. Se, että Q ≡ P sekä KDN-esityksen yksikäsitteisyys seuJos

dostamalla disjunktio

raavat siitä, että KND-muotoinen propositio saa totuusarvon 1 tarkalleen

silloin, kun jokin sen mintermeistä saa totuusarvon 1, ja Lemma 2.39 nojalla kaikki mintermit saavat arvon 1 eri tulkinnoissa. Proposition

P

KKN-esitys

saadaan vastaavasti muodostamalla konjunktio maxtermeistä, jotka vastaavat totuustaulun rivejä, joissa

Esimerkki 2.42.

P

saa arvon 0.

Määritetään proposition

P = ((p → q) → r)

KDN- ja

KKN-muodot. Tätä varten kirjoitetaan proposition totuustaulukko. Huomaa, että

n = 3. k 0 1 2 3 4 5 6 7

p 0 0 0 0 1 1 1 1

q 0 0 1 1 0 0 1 1

r 0 1 0 1 0 1 0 1

p→q 1 1 1 1 0 0 1 1

(p → q) → r 0 1 0 1 1 1 0 1

Nyt KDN-muotoa varten poimitaan niiden vaakarivien, joissa 1, indeksit

k; k = 1, 3, 4, 5, 7.

P

saa arvon

Nyt siis

P ≡ m1 ∨ m3 ∨ m4 ∨ m5 ∨ m7

≡ (¬p ∧ ¬q ∧ r) ∨ (¬p ∧ q ∧ r) ∨ (p ∧ ¬q ∧ ¬r) ∨ (p ∧ ¬q ∧ r) ∨ (p ∧ q ∧ r)

Vastaavasti KKN-muoto saadaan etsimällä vaakariviindeksit, joille

P

saa

totuusarvon 0, ja muodostomalla niitä vastaavien maxtermien konjunktio. Siis

P ≡ M0 ∧ M2 ∧ M6

≡ (p ∨ q ∨ r) ∧ (p ∨ ¬q ∨ r) ∧ (¬p ∨ ¬q ∨ r).

DN- ja KN-muotojen etsimiseen on olemassa muitakin tapoja. Esimerkiksi ns. Karnaugh'n kartat soveltuvat KDN-muodon etsimiseen tietyissä tapauksissa. Usein tärkeää on löytää minimaalinen normaalimuoto.

2.5 Predikaattilogiikkaa

18

2.5 Predikaattilogiikkaa Klassinen syllogismi, jossa lauseista Jokainen ihminen on kuolevainen ja Sokrates on ihminen saadaan johtopäätös Sokrates on kuolevainen, on loogisesti pätevä, mutta sitä ei voida ilmaista propositiologiikan keinoilla. Propositiologiikan kieli on nimittäin liian köyhää ilmaisemaan

inaisuuksia tai suhteita.

Määritelmä 2.43.

Predikaattilogiikan peruskäsitteitä ovat

yksilöiden om-

yksilömuuttujat

¬, ∧, ∨, →, ↔, yhtäsuuruusmerkki =, universaalikvanttori ∀, eksistentiaalikvanttori ∃ sekä yksi-tai useampipaikkaiset predikaattisymbolit A, B , C , . . ., sekä vakiosymbolit a1 , a2 , a3 , . . .. x1 , x2 , x3 , . . . ,

konnektiivit

Yksipaikkaiset predikaatit tarkoittavat yksilöiden ominaisuuksia ja useampipaikkaiset predikaatit yksilöiden suhteita eli

relaatiota (relaatioita käsit-

A(x) merkitsee, että yksilöllä yksilö x on suhteessa R y :n kanssa

tellään tarkemmin myöhemmin). Esimerkiksi

x

A, ja R(x, y) sitä, että (merkitään myös xRy ). Muotoa A(x) ja R(x, y) olevat kirjoitelmat ovat totuusarvoltaan avoimia, on ominaisuus

kaavoiksi. Näistä saadaan totuusarvoltaan suljettuja kaavoja eli lauseita joko 1) sijoittamalla muuttujien paikalle vakiosymbolit tai 2) kvantioimalla (täsmennetään seuraavassa määritelmässä) muuttujien yli.

ja niitä kutsutaan

Määritelmä 2.44.

Olkoon P (x) kaava, jossa on yksi vapaa muuttuja x. (∀x)P (x) on lause, jonka merkitys on jokainen x toteuttaa kaavan P (x) ja (∃x)P (x) on lause, jonka merkitys on on olemassa (ainakin yksi) sellainen x joka toteuttaa kaavan P (x). Sanotaan, että lauseet (∀x)P (x) ja (∃x)P (x) on saatu kvantioimalla muuttujan x yli kaavassa P (x). Tällöin

Huomautus 2.45.

Oppikirjoissa kvantiointi kuitenkin jätetään toisinaan

pois. Esimerkiksi  (a

+ b)2 = a2 + 2ab + b2 

on muodollisesti ottaen kaava,

mutta sen esittäminen pitää yleensä sisällään ajatuksen, että kaava pätee kaikille luvuille

a

ja

b.

On myös melko tavallista, että kvanttorit esitetään

sanallisesti, käyttämättä symboleja

Esimerkki 2.46. nen ja

K(x)

∀

ja

∃.

Merkitköön predikaatti

I(x)

ominaisuutta  x on ihmi-

ominaisuutta  x on kuolevainen, sekä vakiosymboli

s

Sokrat-

esta. Tällöin lause Jokainen ihminen on kuolevainen voidaan formalisoida muodossa

(∀x)(I(x) → K(x)),

Sokrates on ihminen muodossa

ja Sokrates on kuolevainen muodossa

K(s).

I(s),

Tämän luvun alussa mainittu

päättely kokonaisuudessaan voidaan formalisoida predikaattilogiikan todeksi lauseeksi

((∀x)(I(x) → K(x)) ∧ I(s)) → K(s). Yhtä hyvin päättely voidaan esittää aiempia merkintöjä käyttäen muodossa

(∀x)(I(x)) → K(x)), I(s) |= K(s)

2.5 Predikaattilogiikkaa Esimerkki 2.47.

Merkitköön

< (x, y)

19

tavallista järjestystä positiivisten

x < y ). Tällöin siis < on < (1, 2) ja < (2, 1) ovat lauseita

kokonaislukujen joukossa (merkitään yleisemmin kaksipaikkainen predikaattisymboli. Nyt siis

(niissä ei esiinny vapaata muuttujaa), ensimmäinen on tosi ja jälkimmäinen

< (1, x) on kaava, siinä nimittäin on vapaa muuttuja x. (∀x)(x = 1∨ < (1, x)) taas on lause, jonka tulkinta on kaikille x = 1 tai 1 < x. Kyseinen lause on siis tosi, jos x tulkitaan

epätosi. Sen sijaan Kirjoitelma

x:ille

pätee

positiiviseksi kokonaisluvuksi.

Huomautus 2.48. Predikaattilogiikan merkitysoppi eli semantiikka on mutkikkaampaa kuin propositiologiikan. Propositiologiikassa kukin propositiomuuttuja

tulkitaan joko todeksi tai epätodeksi, ja tällainen

tulkinta määrää yksikäsit-

teisesti kaikkien propositioden totuusarvon. Predikaattilogiikassa on sen sijaan annettava tulkinta myös muuttujille, predikaattisymboleille ja vakiosymboleille: esimerkiksi lause

(1, x))

on tosi, mikäli

x:n

(∀x)(x = 1∨