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

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search

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

Օրինակներ[խմբագրել | խմբագրել կոդը]

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

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

ԴՆՁ-ի կառուցումը[խմբագրել | խմբագրել կոդը]

ԴՆՁ-ի կառուցման ալգորիթմը[խմբագրել | խմբագրել կոդը]

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

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

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

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

ԴՆՁ-ի կառուցման օրինակ[խմբագրել | խմբագրել կոդը]

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

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

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

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

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

k-դիզյունկտիվ նորմալ ձև[խմբագրել | խմբագրել կոդը]

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

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

Անցում ԴՆՁ-ից ԿԴՆՁ[խմբագրել | խմբագրել կոդը]

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

,

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

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

ԴՆՁ-ն բնութագրող ֆորմալ քերականություն[խմբագրել | խմբագրել կոդը]

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

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

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

Տե՛ս նաև[խմբագրել | խմբագրել կոդը]

Գրականություն[խմբագրել | խմբագրել կոդը]

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

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]