Դիզյունկտիվ նորմալ ձև
Դիզյունկտիվ նորմալ ձև (ԴՆՁ) բուլյան տրամաբանության մեջ, նորմալ ձև, որում բուլյան բանաձևը ունի լիթերալների կոնյունկցիայի դիզյունկցիայի տեսք։ Ցանկացած բուլյան բանաձև կարող է արտահայտվել դիզյունկտիվ նորմալ ձևով։ Դրա համար կարելի է օգտագործել երկակի ժխտման օրենքը, Դե Մորգանի օրենքը, տարածման օրենքը։ Դիզյունկտիվ նորմալ ձևը հարմար է թեորեմի ավտոմատ ապացուցման համար։
Օրինակներ[խմբագրել | խմբագրել կոդը]
Բանաձևերը ԴՆՁ-ում։
Բանաձևերը ոչ ԴՆՁ-ում։
ԴՆՁ-ի կառուցումը[խմբագրել | խմբագրել կոդը]
ԴՆՁ-ի կառուցման ալգորիթմը[խմբագրել | խմբագրել կոդը]
1) Ազատվել բոլոր տրամաբանական գործողություններից, որ պարունակում է բանաձևը, փոխարինել դրան հիմնականներով՝ կոնյունկցիա, դիզյունկցիա, ժխտում; Դա կարելի է կատարել՝ օգտագործելով հավասարազոր բանաձևեր.
2) Ամբողջ արտահայտությանը վերաբերող ժխտման նշանը փոխարինել այն ժխտման նշաններով, որոնք վերաբերում են հիմնական բանաձևերի առանձին փոփոխական արտահայտություններին.
3) Ազատվել երկակի ժխտման նշաններից։
4) Կոնյուկցիայի և դիզյունկցիայի օպերացիաների ժամանակ, եթե անհրաժեշտ է, օգտագործել տարածման հատկություններ։
ԴՆՁ-ի կառուցման օրինակ[խմբագրել | խմբագրել կոդը]
ԴՆՁ դարձնենք հետևյալ բանաձևը։
Արտահայտենք տրամաբանական օպերացիաները → և ↓ ։ միջոցով.
Ստացված բանաձևում փոխարինենք ժխտումը փոփոխականներով և կրճատենք երկակի ժխտումները.
Օգտագործելով տարածման կանոնը՝ ստանում ենք.
Օգտագործելով կոնյուկցիայի իդեմպոտենտությունը՝ ստանում ենք ԴՆՁ-ն.
k-դիզյունկտիվ նորմալ ձև[խմբագրել | խմբագրել կոդը]
k-դիզյունկտիվ նորմալ ձև անվանում են դիզյունկտիվ նորմալ ձևը, որում յուրաքանչյուր կոնյունկցիա պարունակում է հավասարապես k լիթերալ։
Օրինակ, հետևյալ բանաձևը գրված է 2-ԴՆՁ-ում.
Անցում ԴՆՁ-ից ԿԴՆՁ[խմբագրել | խմբագրել կոդը]
Եթե որևէ պարզ կոնյունկցիայում չի բավարարում փոփոխականը, օրինակ Z-ը, ապա այնտեղ տեղադրում ենք հետևյալ արտահայտությունը
- ,
որից հետո բացում ենք փակագծերը (այդ դեպքում կրկնվող դիզյունկտիվ գումարելիները չենք գրում, որովհետև իդեմպոտենտության օրենքի համաձայն)։ Օրինակ.
Այսպիսով, ԴՆՁ-ից ստացանք ԿԴՆՁ (կատարյալ դիզյունկտիվ նորմալ ձև)
ԴՆՁ-ն բնութագրող ֆորմալ քերականություն[խմբագրել | խմբագրել կոդը]
Հետևյալ ֆորմալ քերականությունը բնութագրում է ԴՆՁ-ին վերաբերող բոլոր բանաձևերը.
- <ԴՆՁ> → <կոնյունկտ>
- <ԴՆՁ> → <ԴՆՁ> ∨ <կոնյունկտ>
- <կոնյունկտ> → <լիթերալ>
- <կոնյունկտ> → (<կոնյունկտ> ∧ <լիթերալ>)
- <լիթերալ> → <թերմ>
- <լիթերալ> → ¬<թերմ>,
որտեղ <թերմը> նշանակում է կամայական բուլյան փոփոխական։
Տե՛ս նաև[խմբագրել | խմբագրել կոդը]
- Կոնյունկտիվ նորմալ ձև
- Կատարյալ դիզյունկտիվ նորմալ ձև
- Կատարյալ կոնյունկտիվ նորմալ ձև
- Կոնյունկտիվ միանդամ
- Դիզյունկտիվ միանդամ
Գրականություն[խմբագրել | խմբագրել կոդը]
- Ю.И. Галушкина, А.Н. Марьямов։ Конспект лекций по дискретной математике - 2-е изд., испр. - М.։ Айрис-пресс, 2008. - 176 с. - (Высшее образование)