Дисјунктивен нормален облик

Во Буловата логика, дисјунктивниот нормален облик (ДНО) претставува стандардизација (или нормализација) на логичка формула која е дисјункција на конјуктивни клаузи; таа може исто така да биде опишана како ИЛИ од И, збир на производи, или (во филозофската логика) како концепт на кластери. Како нормален облик, корисен во автоматското докажување на теореми. Една логичка формула се смета дека е во ДНО, ако и само ако, таа е дисјункција од една или повеќе конјункции на еден или повеќе литерали. ДНО формула е во целосна дисјунктивен нормален облик ако секоја од нејзините променливи се појавува само еднаш во секој минтерм. Како и кај конјуктивниот нормален облик (КНО), единствените дозволени оператори во ДНО се И, ИЛИ и НЕГАЦИЈА. Операторот НЕГАЦИЈА може да се користи единствено како дел од литерал, што значи дека тој може да претходи единствено на пропозициска променлива.На пример, сите овие формули се во ДНО: 


но,и исто така



Како и да е, следните формули не се во ДНО:


Претворањето на една формула во ДНО вклучува логички еквиваленции, како што е елиминација на двојна негација,Де Морганови закони и законот за дистрибутивност. 

Сите логички формули можат да се претворат во дисјунктивен нормален облик. Сепак, во некои случаи, претворањето во ДНО може да доведе до експоненцијално проширување на формулата. На пример, во ДНО, логичките формули од следниот облик имаат 2n клауза:

Секоја посебна Булова функција може да се претстави со една и само една целосна дисјунктивен нормален облик, една од двете канонични форми. 

Важна варијација што се користи во проучувањето на компјутерската комплексност е k-ДНО. Една формула е во k-ДНО ако е во ДНО и секоја клауза содржи најмногу k литерали. За разлика од соодветните суб-клаузи на конјуктивниот нормален облик за k>=3, не постои лесен алгоритам за претворање на произволен пример на формула од ДНО во k-ДНО. 

Следново е формална граматика за ДНО:
 дисјункт → (конјункт ∨ дисјункт)
 дисјункт → конјункт
 конјункт → (литерал ∧ конјункт)
 конјункт → литерал
 литерал → ¬променлива
 литерал → променлива

Каде што променлива е било која променлива

 Надворешни врски 

 Java applet for converting boolean logic expressions to CNF and DNF, showing the laws used  [dead link]

Категорија:Нормални облици (логика)