Literal je iskazna formula oblika p ili -p gde je p iskazno slovo. Literal je atomična formula ili njena negacija.
Normalne forme su način zapisivanja logičke formule takav da navodimo sve kombinacije literala koje proizvode tačnu vrednost formule.
Razlikujemo dve normalne forme:
- konjuktivna normalna forma (KNF)
- disjunktivna normalna forma (DNF).
Uzmimo za primer formulu koja ima tri literala: p,q,r.
Konjuktivna normalna forma sadrži iskaze spojene konjukcijom. U svakom iskazu nalaze se sva tri literala, spojeni disjunkcijom, pri čemu su neki od njih negirani.
Disjunktina normalna forma sadrži iskaze spojene disjunkcijom. U svakom iskazu nalaze se sva tri literala spojeni konjukcijom, pri čemu su neki od njih negirani.
Primer KNF:
(p+q+r) * (-p+q+r) * (-p + -q + r)
Iskaz je tačan ako je (p,q ili r tačno) i (ne-p, q ili r tačno) i (ne-p, ne-q ili r) tačno. Dakle, sve ove situacije.
Primer DNF:
(p*q*r)+(-p*q*r)+(-p*-q*r)
Iskaz je tačan ako je (i p i q i r tačno) ili (ne-p i q i r) ili (ne-p i ne-q i r). Dakle, makar jedna od ovih situacija.
Može se reći i ovako: KNF je proizvod zbirova, DNF je zbir proizvoda.
Ili: KNF je AND OR-ova, DNF je OR AND-ova.