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

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

ՕրինակներԽմբագրել

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

 
 
 

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

 
 
 

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

 
 
 

ԿՆՁ-ի կառուցումԽմբագրել

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

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

 
 

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

 
 

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

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

ԿՆՁ-ի կառուցման օրինակԽմբագրել

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

 

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

 

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

 

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

 

k- կոնյունկտիվ նորմալ ձևԽմբագրել

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

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

 

Անցում ԿՆՁ-ից ԿԿՆՁԽմբագրել

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

 

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

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

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

<ԿՆՁ> → <դիզյունկտ>
<ԿՆՁ> → <ԿՆՁ> ∧ <դիզյունկտ>
<դիզյունկտ> → <լիթերալ>;
<դիզյունկտ> → (<դիզյունկտ> ∨ <լիթերալ>)
<լիթերալ> → <թերմ>
<լիթերալ> → ¬<թերմ>

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

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

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

Տե՛ս նաևԽմբագրել

ԳրականությունԽմբագրել

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

Արտաքին հղումներԽմբագրել