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 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ä.
Totuusfunktiota esittävän lausekkeen sanotaan olevan disjunktiivisessa normaalimuodossa, kun se on seuraavaa muotoa:
Esimerkiksi lauseke
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ä.
Mielivaltainen totuusfunktio formula_5 voidaan esittää disjunktiivisessa normaalimuodossa olevalla lausekkeella, jonka muodostamisen tapa kuvataan tässä.
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.
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.
Yhdistetään yllä kuvatulla tavalla muodostetut alkeiskonjunktiot TAI-konnektiiveilla, jolloin halutun totuusfunktion formula_15 normaalimuoto-esitys 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.
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