Konjunktiivinen normaalimuoto

Konjunktiivinen normaalimuoto on propositiologiikassa loogisten lauseiden muoto. Lause on konjunktiivisessa normaalimuodossa, mikäli:

• lause on konjunktio,
• jokainen sen termi (konjunkti) on disjunktio, ja
• jokaisen tällaisen disjunktion termi (disjunkti) on literaali, joka on joko yksittäinen propositiomuuttuja tai sen negaatio.

Toisin sanottuna lauseessa saa olla EI-konnektiiveja ainoastaan TAI-konnektiivien sisällä, TAI-konnektiiveja ainoastaan lauseen ainoan JA-konnektiivin sisällä (jos sellaista on), eikä siinä saa olla muita konnektiiveja. Esimerkiksi lause $(p_{0}\lor p_{1})\land \neg p_{2}\land (p_{0}\lor \neg p_{3})$ on konjunktiivisessa normaalimuodossa.

Muuntaminen normaalimuotoon

Mikä tahansa totuusfunktio voidaan esittää konjunktiivisessa normaalimuodossa olevana lauseena. Näin ollen minkä tahansa loogisen lauseen voi muuntaa normaalimuodossa olevaksi lauseeksi, joka on loogisesti ekvivalentti alkuperäisen lauseen kanssa.

Konjunktiivista normaalimuotoa olevaan lauseen voi muun muassa johtaa disjunktiivisen normaalimuodon kautta niin, että lauseella $\alpha$ muunnetaan lause $\neg \alpha$ disjunktiivisen normaalimuotoon, josta voidaan De Morganin lakeja soveltamalla johtaa lauseen $\alpha$ konjunktiivinen normaalimuoto.

Tällä tavalla aikaan saatu lause normaalimuodossa saattaa olla kuitenkin eksponentiaalisen kokoinen alkuperäiseen lauseeseen verrattuna. Jos lauseen ei tarvitse olla ekvivalentti, vaan riittää että se on yhtä toteutuva kuin alkuperäinen lause (esimerkiksi lauseen toteutuvuutta määritettäessä), voidaan soveltaa Tseitin-muunnosta, jolla tuloslauseen koko on lineaarinen alkuperäisen lauseen kokoon nähden.