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

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

Օրինակներ

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

$\mathrm{\neg }A\wedge (B\vee C)$

$(A\vee B)\wedge (\mathrm{\neg }B\vee C\vee \mathrm{\neg }D)\wedge (D\vee \mathrm{\neg }E)$

$A\wedge B$

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

$\mathrm{\neg }(B\vee C)$

$(A\wedge B)\vee C$

$A\wedge (B\vee (D\wedge E)).$

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

$\mathrm{\neg }B\wedge \mathrm{\neg }C$

$(A\vee C)\wedge (B\vee C)$

$A\wedge (B\vee D)\wedge (B\vee E).$

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

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

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

$A\to B=\mathrm{\neg }A\vee B$

$A\leftrightarrow B=(\mathrm{\neg }A\vee B)\wedge (A\vee \mathrm{\neg }B)$

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

$\mathrm{\neg }(A\vee B)=\mathrm{\neg }A\wedge \mathrm{\neg }B$

$\mathrm{\neg }(A\wedge B)=\mathrm{\neg }A\vee \mathrm{\neg }B$

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

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

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

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

$F=(X\to Y)\wedge ((\mathrm{\neg }Y\to Z)\to \mathrm{\neg }X)$

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

$F=(\mathrm{\neg }X\vee Y)\wedge (\mathrm{\neg }(\mathrm{\neg }Y\to Z)\vee \mathrm{\neg }X)=(\mathrm{\neg }X\vee Y)\wedge (\mathrm{\neg }(\mathrm{\neg }\mathrm{\neg }Y\vee Z)\vee \mathrm{\neg }X)$

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

$F=(\mathrm{\neg }X\vee Y)\wedge ((\mathrm{\neg }Y\wedge \mathrm{\neg }Z)\vee \mathrm{\neg }X)$

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

$F=(\mathrm{\neg }X\vee Y)\wedge (\mathrm{\neg }X\vee \mathrm{\neg }Y)\wedge (\mathrm{\neg }X\vee \mathrm{\neg }Z)$

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

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

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

$(A\vee B)\wedge (\mathrm{\neg }B\vee C)\wedge (B\vee \mathrm{\neg }C)$

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

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

$(X\vee Y)\wedge (X\vee \mathrm{\neg }Y\vee \mathrm{\neg }Z)=(X\vee Y\vee (Z\wedge \mathrm{\neg }Z))\wedge (X\vee \mathrm{\neg }Y\vee \mathrm{\neg }Z)=(X\vee Y\vee Z)\wedge (X\vee Y\vee \mathrm{\neg }Z)\wedge (X\vee \mathrm{\neg }Y\vee \mathrm{\neg }Z)$

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

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

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

<ԿՆՁ> → <դիզյունկտ>

<ԿՆՁ> → <ԿՆՁ> ∧ <դիզյունկտ>

<դիզյունկտ> → <լիթերալ>;

<դիզյունկտ> → (<դիզյունկտ> ∨ <լիթերալ>)

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

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

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

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

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

Տես նաև

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

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

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

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

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