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

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


== Օրինակներ ==
Բանաձևերը ԴՆՁ-ում։

  
    
      
        A
        ∨
        B
      
    
    {\displaystyle A\lor B}
  

  
    
      
        (
        A
        ∧
        B
        )
        ∨
        ¬
        A
      
    
    {\displaystyle (A\land B)\lor \neg A}
  

  
    
      
        (
        A
        ∧
        B
        ∧
        ¬
        C
        )
        ∨
        (
        ¬
        D
        ∧
        E
        ∧
        F
        )
        ∨
        (
        C
        ∧
        D
        )
        ∨
        B
      
    
    {\displaystyle (A\land B\land \neg C)\lor (\neg D\land E\land F)\lor (C\land D)\lor B}
  Բանաձևերը ոչ ԴՆՁ-ում։

  
    
      
        ¬
        (
        A
        ∨
        B
        )
      
    
    {\displaystyle \neg (A\lor B)}
  

  
    
      
        A
        ∨
        (
        B
        ∧
        (
        C
        ∨
        D
        )
        )
      
    
    {\displaystyle A\lor (B\land (C\lor D))}
  


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


=== ԴՆՁ-ի կառուցման ալգորիթմը ===
1) Ազատվել բոլոր տրամաբանական գործողություններից, որ պարունակում է բանաձևը, փոխարինել դրան հիմնականներով՝ կոնյունկցիա, դիզյունկցիա, ժխտում; Դա կարելի է կատարել՝ օգտագործելով հավասարազոր բանաձևեր.

  
    
      
        A
        →
        B
        =
        ¬
        A
        ∨
        B
      
    
    {\displaystyle A\rightarrow B=\neg A\vee B}
  

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

  
    
      
        ¬
        (
        A
        ∨
        B
        )
        =
        ¬
        A
        ∧
        ¬
        B
      
    
    {\displaystyle \neg (A\vee B)=\neg A\wedge \neg B}
  

  
    
      
        ¬
        (
        A
        ∧
        B
        )
        =
        ¬
        A
        ∨
        ¬
        B
      
    
    {\displaystyle \neg (A\wedge B)=\neg A\vee \neg B}
  3) Ազատվել երկակի ժխտման նշաններից։
4) Կոնյուկցիայի և դիզյունկցիայի օպերացիաների ժամանակ, եթե անհրաժեշտ է, օգտագործել տարածման հատկություններ։


=== ԴՆՁ-ի կառուցման օրինակ ===
ԴՆՁ դարձնենք հետևյալ բանաձևը։
  
    
      
        F
        =
        (
        (
        X
        →
        Y
        )
        ↓
        ¬
        (
        Y
        →
        Z
        )
        )
      
    
    {\displaystyle F=((X\rightarrow Y)\downarrow \neg (Y\rightarrow Z))}
  
Արտահայտենք տրամաբանական օպերացիաները → և ↓ ։
  
    
      
        ∨
        ∧
        ¬
      
    
    {\displaystyle \vee \wedge \neg }
   միջոցով.

  
    
      
        F
        =
        (
        (
        ¬
        X
        ∨
        Y
        )
        ↓
        ¬
        (
        ¬
        Y
        ∨
        Z
        )
        )
        =
        ¬
        (
        (
        ¬
        X
        ∨
        Y
        )
        ∨
        ¬
        (
        ¬
        Y
        ∨
        Z
        )
        )
      
    
    {\displaystyle F=((\neg X\vee Y)\downarrow \neg (\neg Y\vee Z))=\neg ((\neg X\vee Y)\vee \neg (\neg Y\vee Z))}
  Ստացված բանաձևում փոխարինենք ժխտումը փոփոխականներով և կրճատենք երկակի ժխտումները.

  
    
      
        F
        =
        ¬
        (
        (
        ¬
        X
        ∨
        Y
        )
        ∨
        ¬
        (
        ¬
        Y
        ∨
        Z
        )
        )
        =
        (
        ¬
        ¬
        X
        ∧
        ¬
        Y
        )
        ∧
        (
        ¬
        Y
        ∨
        Z
        )
        =
        (
        X
        ∧
        ¬
        Y
        )
        ∧
        (
        Y
        ∨
        ¬
        Z
        )
      
    
    {\displaystyle 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
        ∧
        ¬
        Y
        ∧
        ¬
        Y
        )
        ∨
        (
        X
        ∧
        ¬
        Y
        ∧
        Z
        )
      
    
    {\displaystyle F=(X\wedge \neg Y\wedge \neg Y)\vee (X\wedge \neg Y\wedge Z)}
  Օգտագործելով կոնյուկցիայի իդեմպոտենտությունը՝ ստանում ենք ԴՆՁ-ն. 

  
    
      
        F
        =
        (
        X
        ∧
        ¬
        Y
        )
        ∨
        (
        X
        ∧
        ¬
        Y
        ∧
        Z
        )
      
    
    {\displaystyle F=(X\wedge \neg Y)\vee (X\wedge \neg Y\wedge Z)}
  


== k-դիզյունկտիվ նորմալ ձև ==
k-դիզյունկտիվ նորմալ ձև անվանում են դիզյունկտիվ նորմալ ձևը, որում յուրաքանչյուր կոնյունկցիա պարունակում է հավասարապես k լիթերալ։
Օրինակ, հետևյալ բանաձևը գրված է 2-ԴՆՁ-ում.

  
    
      
        (
        A
        ∧
        B
        )
        ∨
        (
        ¬
        B
        ∧
        C
        )
        ∨
        (
        B
        ∧
        ¬
        C
        )
      
    
    {\displaystyle (A\land B)\lor (\neg B\land C)\lor (B\land \neg C)}
  


== Անցում ԴՆՁ-ից ԿԴՆՁ ==
Եթե որևէ պարզ կոնյունկցիայում չի բավարարում փոփոխականը, օրինակ Z-ը, ապա այնտեղ տեղադրում ենք հետևյալ արտահայտությունը

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

  
    
      
        X
        ∨
        ¬
        Y
        ¬
        Z
        =
        X
        (
        Y
        ∨
        ¬
        Y
        )
        (
        Z
        ∨
        ¬
        Z
        )
        ∨
        (
        X
        ∨
        ¬
        X
        )
        ¬
        Y
        ¬
        Z
        =
      
    
    {\displaystyle X\vee \neg Y\neg Z=X(Y\vee \neg Y)(Z\vee \neg Z)\vee (X\vee \neg X)\neg Y\neg Z=}
  

  
    
      
        X
        Y
        Z
        ∨
        X
        ¬
        Y
        Z
        ∨
        X
        Y
        ¬
        Z
        ∨
        X
        ¬
        Y
        ¬
        Z
        ∨
        X
        ¬
        Y
        ¬
        Z
        ∨
        ¬
        X
        ¬
        Y
        ¬
        Z
        =
      
    
    {\displaystyle 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=}
  
  
    
      
        =
        X
        Y
        Z
        ∨
        X
        ¬
        Y
        Z
        ∨
        X
        Y
        ¬
        Z
        ∨
        X
        ¬
        Y
        ¬
        Z
        ∨
        ¬
        X
        ¬
        Y
        ¬
        Z
      
    
    {\displaystyle =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
Դիզյունկտիվ և կոնյունկտիվ նորմալ ձևեր
ԴՆՁ-ի և ԿՆՁ-ի սահմանումներ