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

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


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

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

  
    
      
        (
        A
        ∨
        B
        )
        ∧
        (
        ¬
        B
        ∨
        C
        ∨
        ¬
        D
        )
        ∧
        (
        D
        ∨
        ¬
        E
        )
      
    
    {\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge (D\vee \neg E)}
  

  
    
      
        A
        ∧
        B
      
    
    {\displaystyle A\wedge B}
  Բանաձևերը ոչ ԿՆՁ-ում։

  
    
      
        ¬
        (
        B
        ∨
        C
        )
      
    
    {\displaystyle \neg (B\vee C)}
  

  
    
      
        (
        A
        ∧
        B
        )
        ∨
        C
      
    
    {\displaystyle (A\wedge B)\vee C}
  

  
    
      
        A
        ∧
        (
        B
        ∨
        (
        D
        ∧
        E
        )
        )
        .
      
    
    {\displaystyle A\wedge (B\vee (D\wedge E)).}
  Բայց վերը նշված 3 ոչ ԿՆՁ-ում բանաձևերը համարժեք են ԿՆՁ-ի հետևյալ բանաձևերին.

  
    
      
        ¬
        B
        ∧
        ¬
        C
      
    
    {\displaystyle \neg B\wedge \neg C}
  

  
    
      
        (
        A
        ∨
        C
        )
        ∧
        (
        B
        ∨
        C
        )
      
    
    {\displaystyle (A\vee C)\wedge (B\vee C)}
  

  
    
      
        A
        ∧
        (
        B
        ∨
        D
        )
        ∧
        (
        B
        ∨
        E
        )
        .
      
    
    {\displaystyle A\wedge (B\vee D)\wedge (B\vee E).}
  


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


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

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

  
    
      
        A
        ↔
        B
        =
        (
        ¬
        A
        ∨
        B
        )
        ∧
        (
        A
        ∨
        ¬
        B
        )
      
    
    {\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \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
        )
        →
        ¬
        X
        )
      
    
    {\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X)}
  Վերափոխենք F-ի այնպիսի բանաձևի, որը չի պարունակում → .

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

  
    
      
        F
        =
        (
        ¬
        X
        ∨
        Y
        )
        ∧
        (
        (
        ¬
        Y
        ∧
        ¬
        Z
        )
        ∨
        ¬
        X
        )
      
    
    {\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X)}
  Տարածման կանոնի համաձայն՝ ստանանք ԿՆՁ-ն.

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


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

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


== Անցում ԿՆՁ-ից ԿԿՆՁ ==
Եթե հասարակ դիզյունկցիայում չի բավարարում որևէ փոփոխականը (օրինակ՝ z-ը), ապա ավելացնում ենք հետևյալ արտահայտությունը. 
  
    
      
        Z
        ∧
        ¬
        Z
        =
        0
      
    
    {\displaystyle Z\wedge \neg Z=0}
   (այն չի փոխում դիզյունկցիան), որից հետո բացում ենք փակագծերը.

  
    
      
        (
        X
        ∨
        Y
        )
        ∧
        (
        X
        ∨
        ¬
        Y
        ∨
        ¬
        Z
        )
        =
        (
        X
        ∨
        Y
        ∨
        (
        Z
        ∧
        ¬
        Z
        )
        )
        ∧
        (
        X
        ∨
        ¬
        Y
        ∨
        ¬
        Z
        )
        =
        (
        X
        ∨
        Y
        ∨
        Z
        )
        ∧
        (
        X
        ∨
        Y
        ∨
        ¬
        Z
        )
        ∧
        (
        X
        ∨
        ¬
        Y
        ∨
        ¬
        Z
        )
      
    
    {\displaystyle (X\vee Y)\wedge (X\vee \neg Y\vee \neg Z)=(X\vee Y\vee (Z\wedge \neg Z))\wedge (X\vee \neg Y\vee \neg Z)=(X\vee Y\vee Z)\wedge (X\vee Y\vee \neg Z)\wedge (X\vee \neg Y\vee \neg Z)}
  Այսպիսով, ԿՆՁ-ից ստանում ենք ԿԿՆՁ։


== ԿՆՁ-ն բնութագրող ֆորմալ քերականություն ==
Հետևյալ ֆորմալ քերականությունը բնութագրում է կՆՁ դարձած բոլոր բանաձևերը. 

<ԿՆՁ> → <դիզյունկտ>
<ԿՆՁ> → <ԿՆՁ> ∧ <դիզյունկտ>
<դիզյունկտ> → <լիթերալ>;
<դիզյունկտ> → (<դիզյունկտ> ∨ <լիթերալ>)<լիթերալ> → <թերմ>
<լիթերալ> → ¬<թերմ>որտեղ <թերմը> նշանակում է կամայական բուլյան փոփոխական։


== ԿՆՁ-ի բանաձևի ստացման առաջադրանք ==
Հաշվողական բարդությունների տեսության մեջ կարևոր դեր է կատարում բուլյան բանաձևերի կատարման առաջադրանքը կոնյուկտիվ նորմալ ձևում։ Համաձայն Կուկի թեորեմի՝ այդ առաջադրանքը NP-ամբողջ է, և այն բերվում է 3-ԿՆՁ բանաձևերի կատարմանը, ինչին էլ բերվում են NP-ամբողջական առաջադրանքները։


== Տե՛ս նաև ==
Դիզյունկտիվ նորմալ ձև
Կատայալ դիզյունկտիվ նորմալ ձև
Կոնյունկտիվ միանդամ
Դիզյունկտիվ միանդամ


== Գրականություն ==
Յու. Ի. Գալուշկինա, Ա.Ն. Մարյամով. Դիսկրետ մաթեմատիկայի դասախոսությունների հակիրճ տարբերակ, 2-րդ հր., Այրիս պրես, 2008. - 176 էջ։


== Արտաքին հղումներ ==
Դիզյունկտիվ և կոնյունկտիվ նորմալ ձևեր