Disjunktiivinen normaalimuoto

Wikipedia
Loikkaa: valikkoon, hakuun

Disjunktiivinen normaalimuoto tarkoittaa sellaista lauseketta, joka on koottu propositiologiikan propositiomuuttujista sekä TAI-, JA- ja EI-konnektiiveista (merkitään \or, \and ja \neg) tietyllä tavalla, joka kuvataan alla tarkemmin. Tämän menetelmän mukainen esitys on olemassa jokaiselle totuusfunktiolle, mikä osoittaa kyseisen konnektiivi-joukon täydelliseksi ja näin tekee propositiologiikan "peruskonnektiiveista" ja itse disjunktiivisen normaalimuodon menetelmästä perustavan välineen niin kaksiarvo-logiikan tutkimiselle kuin sen sovelluksillekin esimerkiksi loogisissa piireissä.

Normaalimuodon rakenne[muokkaa | muokkaa wikitekstiä]

Puuesitys-kuva yllä mainitusta disjunktiivisesta normaalimuodosta. Kuvassa käytetty merkintää, jossa \land (vastaavasti \lor ) kattaa senkin tilanteen, jossa kyseistä konnektiivia ei todella tarvittaisi silloin, kun sillä yhdistettäviä on vain yksi kappale. (Kuvassa tämä tilanne toteutuu \mathbf{} x_{10} -alkeiskonjunktion kohdalla.)

Totuusfunktiota esittävän lausekkeen sanotaan olevan disjunktiivisessa normaalimuodossa, kun se on seuraavaa muotoa:

  • Lauseke on yhden tai useamman alkeiskonjunktion disjunktio.
  • Kukin alkeiskonjunktio on yhden tai useamman literaalin konjunktio.
  • Kukin literaali on joko yksittäinen propositiomuuttuja tai sellaisen negaatio.

Esimerkiksi lauseke

\mathbf{}(\neg x_{10}\land x_{7}\land x_{9}\land \neg x_{2}\land \neg x_{6})\lor (x_{10})\lor (\neg x_{4}\land x_{12}\land x_{4}\land \neg x_{4})

on disjunktiivisessa normaalimuodossa. Se koostuu kolmesta alkeiskonjunktiosta, joissa on viisi, yksi ja neljä literaalia.

On huomattava, ettei mikä tahansa TAI-, JA- ja EI-konnektiiveja yhdistelemällä muodostettu lauseke ole disjunktiivisessa normaalimuodossa. Normaalimuoto edellyttää "3-tasoisuutta", jossa TAI-konnektiivit ovat uloimpana, JA-konnektiivit seuraavalla tasolla, ja EI-konnektiivit sisimpänä suoraan propositiomuuttujien edessä.

Normaalimuodon käyttö halutun totuusfunktion esittämisessä[muokkaa | muokkaa wikitekstiä]

Mielivaltainen totuusfunktio \mathbf{}f voidaan esittää disjunktiivisessa normaalimuodossa olevalla lausekkeella, jonka muodostamisen tapa kuvataan tässä.

Monipaikkainen yhdistely TAI- tai JA-konnektiivilla[muokkaa | muokkaa wikitekstiä]

Alipropositioiden monipaikkainen TAI-yhdistelmä \mathbf{} P_{1} \lor \dots \lor P_{n} antaa TAI-konnektiivien sulutuksesta huolimatta arvon \mathbf{} 1 tarkalleen silloin jos edes yksi \mathbf{} P-alipropositio saa arvon \mathbf{} 1, sillä TAI:n määritelmän perusteella se nousee "sulkuja avattaessa" aina ylemmäs päätyen lopulta koko lausekkeen arvoksi. Esimerkiksi

\mathbf{} (0\lor 1)\lor (0\lor 0)=1\lor (0\lor 0)=1\lor 0=1=1\lor 0 =(0\lor 1)\lor 0=(0\lor (1\lor 0))\lor 0.

Erityisesti TAI-konnektiivi on siis liitännäinen. Sama päättely pätee JA-konnektiivilla arvon \mathbf{} 0 suhteen, joten on nähty miten TAI- tai JA-konnektiivin yhdistelmä on tulkittavissa monipaikkaiseksi totuusfunktioiksi yksinkertaisella tavalla. Esimerkiksi monipaikkainen JA-konnektiivi antaa arvon \mathbf{} 1 vain silloin, kun kaikki siinä yhdistettävät arvot ovat \mathbf{} 1.

Käytettävien alkeiskonjunktioiden muodostaminen[muokkaa | muokkaa wikitekstiä]

Muodostetaan sellaisia alkeiskonjuntioita, jotka saavat arvon \mathbf{} 1 tarkalleen yhdellä totuusjakaumalla, ja nämä totuusjakaumat ovat tarkalleen samat kuin ne, joilla haluttu totuusfunktio \mathbf{} f saa arvon \mathbf{} 1. Tämä onnistuu niin, että kussakin muodostettavassa alkeiskonjunktiossa on kaikki \mathbf{} f:n käyttämät propositiomuuttujat, joista EI-konnektiivilla varustetaan ne, joiden arvo on \mathbf{} 0 alkeiskonjunktioon liittyvässä totuusjakaumassa, jotta kaikista literaaleista saataisiin sillä arvo \mathbf{} 1 alkeiskonjunktion JA-yhdistelyyn ja täten \mathbf{} 1 alkeiskonjunktiosta saatavaksi arvoksi. Jos esimerkiksi \mathbf{} f saa arvon \mathbf{} 1 totuusjakaumalla \mathbf{}x_{1}x_{2}x_{3}x_{4}=0110, tähän totuusjakaumaan liitetään alkeiskonjunktio \mathbf{} (\neg x_{1}\land x_{2}\land x_{3}\land \neg x_{4}).

Lopullisen normaalimuoto-esityksen kokoaminen ja sen vastaavuus totuusfunktion kanssa[muokkaa | muokkaa wikitekstiä]

Yhdistetään yllä kuvatulla tavalla muodostetut alkeiskonjunktiot TAI-konnektiiveilla, jolloin halutun totuusfunktion \mathbf{} f normaalimuoto-esitys on valmis. Näin koottu lauseke esittää todella haluttua totuusfunktiota, sillä siitä saadaan arvo \mathbf{} 1 tarkalleen silloin, kun joku TAI-yhdistelyssä olevista alkeiskonjunktioista antaa arvon \mathbf{} 1, mikä taas käytettyjen alkeiskonjunktioiden muodostamistavan perusteella tarkoittaa sitä, että totuusjakaumana on nyt jokin niistä totuusjakaumista, joilla haluttu totuusfunktio \mathbf{} f saa arvon \mathbf{} 1. Toisaalta jokaista \mathbf{} f:ssä arvon \mathbf{} 1 antavaa totuusjakaumaa kohti koottu esitys sisältää alkeiskonjunktion, joka antaa arvon \mathbf{} 1 tällä totuusjakaumalla, jolloin \mathbf{} 1 päätyy TAI-yhdistelyn kautta myös kootusta esityksestä saatavaksi totuusarvoksi. On siis nähty, että \mathbf{} f ja koottu normaalimuoto antavat arvon \mathbf{} 1 tarkalleen samoilla totuusjakaumilla.

Erikoistapauksena esityksen kokoamisessa on se tilanne, jossa haluttu totuusfunktio on 0_\mathbf{}-funktio, joka saa arvon 0_\mathbf{} kaikilla totuusjakaumilla. Yllä kuvatulla tavalla normaalimuodoksi tulisi nyt tyhjä lauseke. Tämän välttämiseksi voidaan esitykseksi valita nyt aina \mathbf{} 0-arvoinen lauseke x_{1}\and \neg x_{1}, joka on disjunktiivisessa normaalimuodossa sallittua muotoa.

Esimerkki totuusfunktion esityksen kokoamisesta[muokkaa | muokkaa wikitekstiä]

Totuusfunktion esittäminen disjunktiivisessa normaalimuodossa hahmottunee parhaiten esimerkin kautta. Olkoon haluttu totuusfunktio f_\mathbf{} se 3_\mathbf{}-kokoinen totuusfunktio, joka on kuvattu alla olevassa totuustaulussa.

x_{1}x_{2}x_{3}\mathbf{} f(x_{1}x_{2}x_{3})_\mathbf{}
000_\mathbf{} 1_\mathbf{}
001_\mathbf{} 1_\mathbf{}
010_\mathbf{} 0_\mathbf{}
011_\mathbf{} 0_\mathbf{}
100_\mathbf{} 0_\mathbf{}
101_\mathbf{} 1_\mathbf{}
110_\mathbf{} 0_\mathbf{}
111_\mathbf{} 1_\mathbf{}

Kyseinen totuusfunktio saa arvon 1_\mathbf{}, kun totuusjakaumana on x_{1}x_{2}x_{3}=000, 001, 101_\mathbf{} tai 111_\mathbf{}, mistä seuraa, että menetelmän mukaiset käytettävät alkeiskonjunktiot ovat nyt \neg x_{1}\neg x_{2}\neg x_{3},\neg x_{1}\neg x_{2}x_{3},x_{1}\neg x_{2}x_{3}\mathbf{} ja x_{1}x_{2}x_{3}\mathbf{}. (Huomaa, että tässä esimerkissä JA-konnektiivit on jätetty kirjoittamatta, mikä on yleinen tapa kirjallisuudessa.)

Kun ne "disjunktoidaan" TAI-konnektiiveilla, normaalimuodon lausekkeeksi saadaan nyt

\neg x_{1}\neg x_{2}\neg x_{3}\or \neg x_{1}\neg x_{2}x_{3}\or x_{1}\neg x_{2}x_{3}\or x_{1}x_{2}x_{3}.

Tämä lauseke esittää totuusfunktiota f_\mathbf{}, mitä voidaan "testata" vaikka totuusjakaumalla x_{1}x_{2}x_{3}=100\mathbf{}, jolloin lauseke antaa arvon

\neg 1\neg 0\neg 0\or \neg 1 \neg 00\or 1\neg 00\or 100=011\or 010\or 110\or 100=0\or 0\or 0\or 0=0=f(100)

, tai totuusjakaumalla x_{1}x_{2}x_{3}=001\mathbf{}, jolloin lauseke saa arvon

\neg 0\neg 0\neg 1\or \neg 0 \neg 01\or 0\neg 01\or 001=110\or 111\or 011\or 001=0\or 1\or 0\or 0=1=f(001).