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

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

Օրինակներ

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

$A\vee B$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$Z\vee \mathrm{\neg }Z=1$,

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

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

$XYZ\vee X\mathrm{\neg }YZ\vee XY\mathrm{\neg }Z\vee X\mathrm{\neg }Y\mathrm{\neg }Z\vee X\mathrm{\neg }Y\mathrm{\neg }Z\vee \mathrm{\neg }X\mathrm{\neg }Y\mathrm{\neg }Z=$

$=XYZ\vee X\mathrm{\neg }YZ\vee XY\mathrm{\neg }Z\vee X\mathrm{\neg }Y\mathrm{\neg }Z\vee \mathrm{\neg }X\mathrm{\neg }Y\mathrm{\neg }Z$

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

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

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

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

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

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

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

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

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

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

Տես նաև

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

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

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

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

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