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

Од Википедија — слободната енциклопедија
Прејди на: содржини, барај

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

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

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

 
 

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

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

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

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

Следново е формална граматика за ДНФ:

  1. дисјункт → (конјунктдисјункт)
  2. дисјунктконјункт
  3. конјункт → (литералконјункт)
  4. конјунктлитерал
  5. литерал → ¬променлива
  6. литералпроменлива

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

Надворешни линкови[уреди | уреди извор]