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

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

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

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

Բայց վերը նշված 3 ոչ ԿՆՁ-ում բանաձևերը համարժեք են ԿՆՁ-ի հետևյալ բանաձևերին.

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

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

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

2) Փոխարինել ողջ արտահայտությանը վերաբերող ժխտման նշանը հիմնական բանաձևերի առանձին փոփոխականներին վերաբերող ժխտման նշաններով։

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

4) Եթե հարկավոր է, կոնյունկցիայի և դիզյունկցիայի գործողությունների ժամանակ գործածել տարածման հատկությունները։

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

ԿՆՁ-ի բերենք հետևյալ բանաձևը.

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

Ստացված բանաձևում տեղափոխենք ժխտումը փոփոխականների վրա և կրճատենք երկակի ժխտումները.

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

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

Օրինակ, հետևյալ բանաձևը գրառված է 2-ԿՆՁ-ով.

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

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

Այսպիսով, ԿՆՁ-ից ստանում ենք ԿԿՆՁ։

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

Հետևյալ ֆորմալ քերականությունը բնութագրում է կՆՁ դարձած բոլոր բանաձևերը. 
 <ԿՆՁ> → <դիզյունկտ>
 <ԿՆՁ> → <ԿՆՁ> ∧ <դիզյունկտ>
 <դիզյունկտ> → <լիթերալ>;
 <դիզյունկտ> → (<դիզյունկտ> ∨ <լիթերալ>)

 <լիթերալ> → <թերմ>
 <լիթերալ> → ¬<թերմ>

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

ԿՆՁ-ի բանաձևի ստացման առաջադրանք 

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

Տե՛ս նաև 

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

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

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

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

Բուլյան հանրահաշիվ