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

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

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

:\neg A \wedge (B \vee C)
:(A \vee B) \wedge (\neg B \vee C \vee \neg D) \wedge (D \vee \neg E)
:A \wedge B

Բանաձևերը **ոչ ԿՆՁ-ում**։

:\neg (B \vee C)
:(A \wedge B) \vee C
:A \wedge (B \vee (D \wedge E)).

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

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

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

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

:A \rightarrow B = \neg A \vee B
:A \leftrightarrow B = (\neg A \vee B) \wedge (A \vee \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 ) \wedge (( \neg Y \rightarrow Z ) \rightarrow \neg X ) 

Վերափոխենք F-ի այնպիսի բանաձևի, որը չի պարունակում → .

: 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 = ( \neg X \vee Y) \wedge ((\neg Y \wedge \neg Z) \vee \neg X)

Տարածման կանոնի համաձայն՝ ստանանք ԿՆՁ-ն.

:F = (\neg X \vee Y) \wedge (\neg X \vee \neg Y) \wedge (\neg X \vee \neg Z) 

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

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

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

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

:(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 էջ։

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

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