Դիզյունկտիվ նորմալ ձև

**Դիզյունկտիվ նորմալ ձև** (**ԴՆՁ**) բուլյան տրամաբանության մեջ, նորմալ ձև, որում բուլյան բանաձևը ունի լիթերալների կոնյունկցիայի դիզյունկցիայի տեսք։ Ցանկացած բուլյան բանաձև կարող է արտահայտվել դիզյունկտիվ նորմալ ձևով։ Դրա համար կարելի է օգտագործել երկակի ժխտման օրենքը, Դե Մորգանի օրենքը, տարածման օրենքը։ Դիզյունկտիվ նորմալ ձևը հարմար է թեորեմի ավտոմատ ապացուցման համար։

## Օրինակներ

Բանաձևերը **ԴՆՁ-ում**։
:A \lor B
:(A \land B) \lor \neg A
:(A \land B \land \neg C) \lor (\neg D \land E \land F) \lor (C \land D) \lor B

Բանաձևերը **ոչ ԴՆՁ-ում**։
:\neg(A \lor B)
:A \lor (B \land (C \lor D))

## ԴՆՁ-ի կառուցումը

### ԴՆՁ-ի կառուցման ալգորիթմը

1) Ազատվել բոլոր տրամաբանական գործողություններից, որ պարունակում է բանաձևը, փոխարինել դրան հիմնականներով՝ կոնյունկցիա, դիզյունկցիա, ժխտում; Դա կարելի է կատարել՝ օգտագործելով հավասարազոր բանաձևեր.
:A \rightarrow B = \neg A \vee B
:A \leftrightarrow B = (A \wedge B) \vee (\neg A \wedge \neg B)

2) Ամբողջ արտահայտությանը վերաբերող ժխտման նշանը փոխարինել այն ժխտման նշաններով, որոնք վերաբերում են հիմնական բանաձևերի առանձին փոփոխական արտահայտություններին. 
:\neg (A \vee B) = \neg A \wedge \neg B
:\neg (A \wedge B) = \neg A \vee \neg B

3) Ազատվել երկակի ժխտման նշաններից։

4) Կոնյուկցիայի և դիզյունկցիայի օպերացիաների ժամանակ, եթե անհրաժեշտ է, օգտագործել տարածման հատկություններ։

### ԴՆՁ-ի կառուցման օրինակ

ԴՆՁ դարձնենք հետևյալ բանաձևը։F = ((X \rightarrow Y) \downarrow \neg (Y \rightarrow Z))

Արտահայտենք տրամաբանական օպերացիաները → և ↓ ։\vee \wedge \neg միջոցով.
:F = ((\neg X \vee Y) \downarrow \neg(\neg Y \vee Z)) = \neg ((\neg X \vee Y) \vee \neg (\neg Y \vee Z))

Ստացված բանաձևում փոխարինենք ժխտումը փոփոխականներով և կրճատենք երկակի ժխտումները.
:F = \neg ((\neg X \vee Y) \vee \neg (\neg Y \vee Z)) = (\neg \neg X \wedge \neg Y) \wedge (\neg Y \vee Z) = (X \wedge \neg Y) \wedge (Y \vee\neg  Z)

Օգտագործելով տարածման կանոնը՝ ստանում ենք. 
:F = (X \wedge \neg Y \wedge \neg Y) \vee (X \wedge \neg Y \wedge Z)

Օգտագործելով կոնյուկցիայի իդեմպոտենտությունը՝ ստանում ենք ԴՆՁ-ն. 
:F = (X \wedge \neg Y ) \vee (X \wedge \neg Y \wedge Z)

## ''k''-դիզյունկտիվ նորմալ ձև
*k*-դիզյունկտիվ նորմալ ձև անվանում են դիզյունկտիվ նորմալ ձևը, որում յուրաքանչյուր կոնյունկցիա պարունակում է հավասարապես *k* լիթերալ։

Օրինակ, հետևյալ բանաձևը գրված է 2-ԴՆՁ-ում.
: (A \land B) \lor (\neg B \land C) \lor (B \land \neg C)

## Անցում ԴՆՁ-ից ԿԴՆՁ

Եթե որևէ պարզ կոնյունկցիայում չի բավարարում փոփոխականը, օրինակ Z-ը, ապա այնտեղ տեղադրում ենք հետևյալ արտահայտությունը
:Z \vee \neg Z = 1,
որից հետո բացում ենք փակագծերը (այդ դեպքում կրկնվող դիզյունկտիվ գումարելիները չենք գրում, որովհետև Z \vee Z = Z իդեմպոտենտության օրենքի համաձայն)։ Օրինակ.

:X \vee \neg Y \neg Z = X(Y \vee \neg Y)(Z \vee \neg Z) \vee (X \vee \neg X)\neg Y \neg Z =
:
 XYZ \vee X \neg YZ \vee XY \neg Z \vee X \neg Y \neg Z \vee X \neg Y \neg Z \vee \neg X \neg Y \neg Z = 

: = XYZ \vee X \neg YZ \vee XY \neg Z \vee X \neg Y \neg Z \vee \neg X \neg Y \neg Z

Այսպիսով, ԴՆՁ-ից ստացանք ԿԴՆՁ (կատարյալ դիզյունկտիվ նորմալ ձև)

## ԴՆՁ-ն բնութագրող ֆորմալ քերականություն

Հետևյալ ֆորմալ քերականությունը բնութագրում է ԴՆՁ-ին վերաբերող բոլոր բանաձևերը. 
:  → 
:  →  ∨ 
:  →  → ( ∧ )
:  → 
:  → ¬,

որտեղ  նշանակում է կամայական բուլյան փոփոխական։

## Տես նաև

* Կոնյունկտիվ նորմալ ձև
* Կատարյալ դիզյունկտիվ նորմալ ձև
* Կատարյալ կոնյունկտիվ նորմալ ձև
* Կոնյունկտիվ միանդամ
* Դիզյունկտիվ միանդամ

## Գրականություն

* Ю.И. Галушкина, А.Н. Марьямов։ Конспект лекций по дискретной математике - 2-е изд., испр. - М.։ Айрис-пресс, 2008. - 176 с. - (Высшее образование)

## Արտաքին հղումներ
* Disjunctive Normal Form
* Դիզյունկտիվ և կոնյունկտիվ նորմալ ձևեր
* ԴՆՁ-ի և ԿՆՁ-ի սահմանումներ

Կատեգորիա:Բուլյան հանրահաշիվ