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

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

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

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

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

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

Բայց վերը նշված 3 ոչ ԿՆՁ-ում բանաձևերը համարժեք են ԿՆՁ-ի հետևյալ բանաձևերին.

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

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

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

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

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

4) Եթե հարկավոր է, կոնյունկցիայի և դիզյունկցիայի գործողությունների ժամանակ գործածել տարածման հատկությունները։

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

ԿՆՁ-ի բերենք հետևյալ բանաձևը.

Վերափոխենք F-ի այնպիսի բանաձևի, որը չի պարունակում → .

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

Տարածման կանոնի համաձայն՝ ստանանք ԿՆՁ-ն.

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

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

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

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

Եթե հասարակ դիզյունկցիայում չի բավարարում որևէ փոփոխականը (օրինակ՝ z-ը), ապա ավելացնում ենք հետևյալ արտահայտությունը. (այն չի փոխում դիզյունկցիան), որից հետո բացում ենք փակագծերը.

Այսպիսով, ԿՆՁ-ից ստանում ենք ԿԿՆՁ։

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

Հետևյալ ֆորմալ քերականությունը բնութագրում է կՆՁ դարձած բոլոր բանաձևերը.

<ԿՆՁ> → <դիզյունկտ>
<ԿՆՁ> → <ԿՆՁ> ∧ <դիզյունկտ>
<դիզյունկտ> → <լիթերալ>;
<դիզյունկտ> → (<դիզյունկտ> ∨ <լիթերալ>)
<լիթերալ> → <թերմ>
<լիթերալ> → ¬<թերմ>

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

ԿՆՁ-ի բանաձևի ստացման առաջադրանք[խմբագրել | խմբագրել կոդը]

Հաշվողական բարդությունների տեսության մեջ կարևոր դեր է կատարում բուլյան բանաձևերի կատարման առաջադրանքը կոնյուկտիվ նորմալ ձևում։ Համաձայն Կուկի թեորեմի՝ այդ առաջադրանքը NP-ամբողջ է, և այն բերվում է 3-ԿՆՁ բանաձևերի կատարմանը, ինչին էլ բերվում են NP-ամբողջական առաջադրանքները։

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

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

  • Յու. Ի. Գալուշկինա, Ա.Ն. Մարյամով. Դիսկրետ մաթեմատիկայի դասախոսությունների հակիրճ տարբերակ, 2-րդ հր., Այրիս պրես, 2008. - 176 էջ։

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