Disjunktiivinen normaalimuoto

Disjunktiivinen normaalimuoto tarkoittaa sellaista lauseketta, joka on koottu propositiologiikan propositiomuuttujista sekä TAI-, JA- ja EI-konnektiiveista (merkitään formula_1, formula_2 ja formula_3) tietyllä tavalla, joka kuvataan alla tarkemmin. Tämän menetelmän mukainen esitys on olemassa jokaiselle totuusfunktiolle, mikä osoittaa kyseisen konnektiivijoukon täydelliseksi ja näin tekee propositiologiikan "peruskonnektiiveista" ja itse disjunktiivisen normaalimuodon menetelmästä perustavan välineen niin kaksiarvologiikan tutkimiselle kuin sen sovelluksillekin esimerkiksi loogisissa piireissä.
Normaalimuodon rakenne.
Totuusfunktiota esittävän lausekkeen sanotaan olevan disjunktiivisessa normaalimuodossa, kun se on seuraavaa muotoa:
Esimerkiksi lauseke
formula_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ä.
Mielivaltainen totuusfunktio formula_5 voidaan esittää disjunktiivisessa normaalimuodossa olevalla lausekkeella, jonka muodostamisen tapa kuvataan tässä.
Monipaikkainen yhdistely TAI- tai JA-konnektiivilla.
Alipropositioiden monipaikkainen TAI-yhdistelmä formula_6 antaa TAI-konnektiivien sulutuksesta huolimatta arvon formula_7 tarkalleen silloin jos edes yksi formula_8-alipropositio saa arvon formula_7, sillä TAI:n määritelmän perusteella se nousee "sulkuja avattaessa" aina ylemmäs päätyen lopulta koko lausekkeen arvoksi. Esimerkiksi
formula_10.
Erityisesti TAI-konnektiivi on siis liitännäinen. Sama päättely pätee JA-konnektiivilla arvon formula_11 suhteen, joten on nähty miten TAI- tai JA-konnektiivin yhdistelmä on tulkittavissa monipaikkaiseksi totuusfunktioiksi yksinkertaisella tavalla. Esimerkiksi monipaikkainen JA-konnektiivi antaa arvon formula_7 vain silloin, kun kaikki siinä yhdistettävät arvot ovat formula_7.
Käytettävien alkeiskonjunktioiden muodostaminen.
Muodostetaan sellaisia alkeiskonjunktioita, jotka saavat arvon formula_7 tarkalleen yhdellä totuusjakaumalla, ja nämä totuusjakaumat ovat tarkalleen samat kuin ne, joilla haluttu totuusfunktio formula_15 saa arvon formula_7. Tämä onnistuu niin, että kussakin muodostettavassa alkeiskonjunktiossa on kaikki formula_15:n käyttämät propositiomuuttujat, joista EI-konnektiivilla varustetaan ne, joiden arvo on formula_11 alkeiskonjunktioon liittyvässä totuusjakaumassa, jotta kaikista literaaleista saataisiin sillä arvo formula_7 alkeiskonjunktion JA-yhdistelyyn ja täten formula_7 alkeiskonjunktiosta saatavaksi arvoksi. Jos esimerkiksi formula_15 saa arvon formula_7 totuusjakaumalla formula_23, tähän totuusjakaumaan liitetään alkeiskonjunktio formula_24.
Lopullisen normaalimuoto-esityksen kokoaminen ja sen vastaavuus totuusfunktion kanssa.
Yhdistetään yllä kuvatulla tavalla muodostetut alkeiskonjunktiot TAI-konnektiiveilla, jolloin halutun totuusfunktion formula_15 normaalimuotoesitys on valmis. Näin koottu lauseke esittää todella haluttua totuusfunktiota, sillä siitä saadaan arvo formula_7 tarkalleen silloin, kun joku TAI-yhdistelyssä olevista alkeiskonjunktioista antaa arvon formula_7, mikä taas käytettyjen alkeiskonjunktioiden muodostamistavan perusteella tarkoittaa sitä, että totuusjakaumana on nyt jokin niistä totuusjakaumista, joilla haluttu totuusfunktio formula_15 saa arvon formula_7. Toisaalta jokaista formula_15:ssä arvon formula_7 antavaa totuusjakaumaa kohti koottu esitys sisältää alkeiskonjunktion, joka antaa arvon formula_7 tällä totuusjakaumalla, jolloin formula_7 päätyy TAI-yhdistelyn kautta myös kootusta esityksestä saatavaksi totuusarvoksi. On siis nähty, että formula_15 ja koottu normaalimuoto antavat arvon formula_7 tarkalleen samoilla totuusjakaumilla.
Erikoistapauksena esityksen kokoamisessa on se tilanne, jossa haluttu totuusfunktio on formula_36-funktio, joka saa arvon formula_36 kaikilla totuusjakaumilla. Yllä kuvatulla tavalla normaalimuodoksi tulisi nyt tyhjä lauseke. Tämän välttämiseksi voidaan esitykseksi valita nyt aina formula_11-arvoinen lauseke formula_39, joka on disjunktiivisessa normaalimuodossa sallittua muotoa.
Esimerkki totuusfunktion esityksen kokoamisesta.
Totuusfunktion esittäminen disjunktiivisessa normaalimuodossa hahmottunee parhaiten esimerkin kautta. Olkoon haluttu totuusfunktio formula_40 se formula_41-kokoinen totuusfunktio, joka on kuvattu alla olevassa totuustaulussa.
Kyseinen totuusfunktio saa arvon formula_42, kun totuusjakaumana on formula_43 tai formula_44, mistä seuraa, että menetelmän mukaiset käytettävät alkeiskonjunktiot ovat nyt formula_45 ja formula_46. (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 formula_47
Tämä lauseke esittää totuusfunktiota formula_40, mitä voidaan "testata" vaikka totuusjakaumalla formula_49, jolloin lauseke antaa arvon formula_50
, tai totuusjakaumalla formula_51, jolloin lauseke saa arvon formula_52