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

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

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

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

 
 
 

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

 
 

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

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

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

 
 

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

 
 

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

4) Կոնյուկցիայի և դիզյունկցիայի օպերացիաների ժամանակ, եթե անհրաժեշտ է, օգտագործել տարածման հատկություններ։

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

ԴՆՁ դարձնենք հետևյալ բանաձևը։ 

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

 

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

 

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

 

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

 

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

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

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

 

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

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

 ,

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

 
 
 

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

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

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

<ԴՆՁ> → <կոնյունկտ>
<ԴՆՁ> → <ԴՆՁ> ∨ <կոնյունկտ>
<կոնյունկտ> → <լիթերալ>
<կոնյունկտ> → (<կոնյունկտ> ∧ <լիթերալ>)
<լիթերալ> → <թերմ>
<լիթերալ> → ¬<թերմ>,

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

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

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

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

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