Disjunktiivinen normaalimuoto

Disjunktiivinen normaalimuoto tarkoittaa sellaista lauseketta, joka on koottu propositiologiikan propositiomuuttujista sekä TAI-, JA- ja EI-konnektiiveista (merkitään ${\displaystyle \lor }$, ${\displaystyle \land }$ ja ${\displaystyle \neg }$) 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ä.

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

${\displaystyle \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ä.

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

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

${\displaystyle \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 ${\displaystyle \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 ${\displaystyle \mathbf {} 1}$ vain silloin, kun kaikki siinä yhdistettävät arvot ovat ${\displaystyle \mathbf {} 1}$.

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

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

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

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

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

Kyseinen totuusfunktio saa arvon ${\displaystyle 1_{\mathbf {} }}$, kun totuusjakaumana on ${\displaystyle x_{1}x_{2}x_{3}=000,001,101_{\mathbf {} }}$ tai ${\displaystyle 111_{\mathbf {} }}$, mistä seuraa, että menetelmän mukaiset käytettävät alkeiskonjunktiot ovat nyt ${\displaystyle \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 ${\displaystyle 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

${\displaystyle \neg x_{1}\neg x_{2}\neg x_{3}\lor \neg x_{1}\neg x_{2}x_{3}\lor x_{1}\neg x_{2}x_{3}\lor x_{1}x_{2}x_{3}.}$

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

${\displaystyle \neg 1\neg 0\neg 0\lor \neg 1\neg 00\lor 1\neg 00\lor 100=011\lor 010\lor 110\lor 100=0\lor 0\lor 0\lor 0=0=f(100)}$

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

${\displaystyle \neg 0\neg 0\neg 1\lor \neg 0\neg 01\lor 0\neg 01\lor 001=110\lor 111\lor 011\lor 001=0\lor 1\lor 0\lor 0=1=f(001).}$