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

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

Օրինակներ

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

$A\lor B$

$(A\land B)\lor \neg A$

$(A\land B\land \neg C)\lor (\neg D\land E\land F)\lor (C\land D)\lor B$

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

$\neg (A\lor B)$

$A\lor (B\land (C\lor D))$

ԴՆՁ-ի կառուցումը

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

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

$A\rightarrow B=\neg A\vee B$

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

Արտահայտենք տրամաբանական օպերացիաները → և ↓ ։$\vee \wedge \neg$ միջոցով.

$F=((\neg X\vee Y)\downarrow \neg (\neg Y\vee Z))=\neg ((\neg X\vee Y)\vee \neg (\neg Y\vee Z))$

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

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

Օգտագործելով տարածման կանոնը՝ ստանում ենք.

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

Օգտագործելով կոնյուկցիայի իդեմպոտենտությունը՝ ստանում ենք ԴՆՁ-ն.

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

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

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

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

$(A\land B)\lor (\neg B\land C)\lor (B\land \neg C)$

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

Եթե որևէ պարզ կոնյունկցիայում չի բավարարում փոփոխականը, օրինակ Z-ը, ապա այնտեղ տեղադրում ենք հետևյալ արտահայտությունը

$Z\vee \neg Z=1$,

որից հետո բացում ենք փակագծերը (այդ դեպքում կրկնվող դիզյունկտիվ գումարելիները չենք գրում, որովհետև $Z\vee Z=Z$ իդեմպոտենտության օրենքի համաձայն)։ Օրինակ.

$X\vee \neg Y\neg Z=X(Y\vee \neg Y)(Z\vee \neg Z)\vee (X\vee \neg X)\neg Y\neg Z=$

$XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z=$

$=XYZ\vee X\neg YZ\vee XY\neg Z\vee X\neg Y\neg Z\vee \neg X\neg Y\neg Z$

Այսպիսով, ԴՆՁ-ից ստացանք ԿԴՆՁ (կատարյալ դիզյունկտիվ նորմալ ձև)

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

Հետևյալ ֆորմալ քերականությունը բնութագրում է ԴՆՁ-ին վերաբերող բոլոր բանաձևերը.

<ԴՆՁ> → <կոնյունկտ>

<ԴՆՁ> → <ԴՆՁ> ∨ <կոնյունկտ>

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

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

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

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

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

Տես նաև

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

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

• Ю.И. Галушкина, А.Н. Марьямов։ Конспект лекций по дискретной математике - 2-е изд., испр. - М.։ Айрис-пресс, 2008. - 176 с. - (Высшее образование)

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

• Disjunctive Normal Form
• Դիզյունկտիվ և կոնյունկտիվ նորմալ ձևեր
• ԴՆՁ-ի և ԿՆՁ-ի սահմանումներ