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

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

Օրինակներ

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

$\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 էջ։

Արտաքին հղումներ

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