Մասնակից:7Vendetta7/Ավազարկղ

Ժեգալկինի բազմանդամ, բազմանդամ $\mathbb {Z} _{2}$ տիրույթում, այսինքն բազմանդամ 0 և 1 տեսքի գործակիցներով, որտեղ արտադրյալի դերը կատարում է կոնյունկցիան, իսկ գումարմանը՝ բացառող կամը: Բազմանդամը առաջարկվել է 1927 թվականին Իվան Իվանովիչ Ժեգալկինի կողմից՝ որպես բուլյան տրամաբանության ֆունկցիաների ներկայացման հարմար միջոց: Արտասահմանյան գրականության մեջ Ժեգալկինի բազմանդամը հանդես է գալիս հանրահաշվական նորմալ ձև (ՀՆՁ) անվանմամբ:

Ժեգալկինի թեորեմը հանդիսանում է ապացույց Ժեգալկինի բազմանդամի տեսքով կամայական բուլյան ֆունկցիայի գոյության և ներկայացման միակության համար:

Ժեգալկինի բազմանդամը ներկայացնում է իրենից գումարում ըստ մոդուլ երկուսի երկու զույգ առ զույգ տարբեր չփոխակերպված փոփոխականներով արտադրյալների, որտեղ ոչ մի արտադրյալում ոչ մի փոփոխական չի հանդիպում մեկ անգամից ավելի, ինչպես նաև (եթե անհրաժեշտ է) հաստատուն 1: Ձևականորեն Ժեգալկինի բազմանդամը կարելի է ներկայացնել այս տեսքով.

$P(X_{1}...X_{n})=a~\oplus ~a_{1}X_{1}~\oplus ~a_{2}X_{2}~\oplus ~...~\oplus ~a_{n}X_{n}~\oplus ~a_{12}X_{1}X_{2}~\oplus ~a_{13}X_{1}X_{3}~\oplus ~...~\oplus ~a_{1...n}X_{1}...X_{n},$

$a,\ldots ,a_{1\ldots n}\in \{0,1\}.$

կամ ավելի ձևականեցված տեսքով.

$P=a\oplus \bigoplus _{\begin{array}{c}1\leq i_{1}<\ldots <i_{k}\leq n\\k\in {\overline {1,n}}\end{array}}a_{i_{1},\ldots ,i_{k}}\wedge x_{i_{1}}\wedge \ldots \wedge x_{i_{k}},\quad a,a_{i_{1},\ldots ,i_{k}}\in \{0,1\}.$

Ժեգալկինի բազմանդամների օրինակներ՝

$P=B\oplus AB;$

$P=X\oplus YZ\oplus ABX\oplus ABDYZ;$

$P=1\oplus A\oplus ABD.$

Նախադրյալներ

Ըստ Պոստի թեորեմի, որպեսզի բուլյան ֆունկցիաների համակարգը լինի լրիվ անհրաժեշտ է, որ նրա մեջ գոյություն ունենա՝

1. գոնե մեկ ֆունկցիա, որը 0-ն պահպանող չէ:
2. գոնե մեկ ֆունկցիա, որը 1-ը պահպանող չէ:
3. գոնե մեկ ֆունկցիա, որը ոչ գծային է:
4. գոնե մեկ ֆունկցիա, որը ոչ մոնոտոն է:
5. գոնե մեկ ֆունկցիա, որը ոչ ինքնաերկակի է:

Այդ պահանջներին պատասխանում է մասնավորապես ${\bigl \langle }\wedge ,\oplus ,1{\bigr \rangle }$ ֆունկցիաների համակարգը (կոնյունկցիա, գումարում ըստ մոդուլ 2-ի, հաստատուն 1): Հենց այս համակարգի վրա էլ կառուցվում են Ժեգալկինի բազմանդամները:

Գոյություն և ներկայացման միակություն

Ըստ Ժեգալկինի թեորեմի կամայական բուլյան ֆունկցիա կարող է ներկայացվել Ժեգալկինի բազմանդամի տեսքով միայն մեկ ձևով: Թեորեմը ապացուցվում է հետևյալ կերպ: Նկատենք, որ n փոփոխականներից կազմված բուլյան ֆունկցիաները $2^{2^{n}}$ հատ են: Ընդ որում $x_{i_{1}}\ldots x_{i_{k}}$ տեսքի կոնյունկցիաների քանակը հավասար է 2ⁿ, քանի որ n հնարավոր արտադրյալներից յուրաքանչյուրը կամ մտնում է կոնյունկցիայի մեջ կամ՝ ոչ: Բազմանդամի մեջ կամայական այդպիսի կոնյունկցիան ընդունում է կամ 1 կամ էլ 0 արժեք, այսինքն գոյություն ունեն $2^{2^{n}}$ հատ տարբեր Ժեգալկինի բազմանդամներ կախված n-ից: Այժմ մնում է միայն ապացուցել, որ տարբեր բազմանդամներ պատասխանատու են տարբեր ֆունկցիաների համար: Ենթադրենք հակառակը: Այդ դեպքում հավասարեցնելով երկու տարբեր Ժեգալկինի բազմանդամներ և տեղափոխելով նրանցից մեկի անդամները հավասարություն մյուս մաս, կստանանք բազմանդամ, որը հավասար է 0-ի և ունի ոչ զրոյական գործակիցներ: Այդ դեպքում կդիտարկենք ամենակարճ երկարություն ունեցող մեկ արժեքով գործակից ունեցող գումարելին, այսինքն ամենաքիչ թվով փոփոխականներ ունեցողը, որը մտնում է նրա մեջ: Այդ փոփոխականների փոխարեն մեկերը դնելով և մնացածի փոխարեն զրոներ դնելով՝ կստանանք, որ այս հավաքածուի մեջ միայն այդ գումարելին է ընդունում մեկ արժեք, այսինքն զրոյական ֆունկցիան հավաքածուներից որևիցե մեկի վրա ընդունում է մեկ արժեք: Հակասություն: Նշանակում է, որ ցանկացած բուլյան ֆունկցիա ներկայացվում է Ժեգալկինի բազմանդամի տեսքով միայն և միայն մեկ ձևով:

Ֆունկցիայի ներկայացում Ժեգալկինի բազմանդամի տեսքով

ԴՆՁ-ի համարժեքային փոխակերպումների օգնությամբ

ԴՆՁ-ի համեմատությամբ Ժեգալկինի բազմանդամի մեջ բացակայում են ԿԱՄ և ՈՉ գործողությունները: Այդպիսով, Ժեգալկինի բազմանդամը կարելի է ստանալ ԴՆՁ-ի միջոցով, ԿԱՄ և ՉԷ գործողությունները արտահայտելով գումարում ըստ մոդուլ 2-ի գործողության և մեկ հաստատունի միջոցով: Դրա համար կիրառվում են հետևյալ հարաբերությունները.

$A\vee B=A\oplus B\oplus AB;$

${\overline {A}}=A\oplus 1.$

Ներքևում ներկայացվում է ԴՆՁ-ի փոխակերպումը Ժեգալկինի բազմանդամի.

$XY\vee {\overline {X}}\,{\overline {Y}}=XY\oplus {\overline {X}}\,{\overline {Y}}\oplus XY{\overline {X}}\,{\overline {Y}}=XY\oplus {\overline {X}}\,{\overline {Y}}=XY\oplus (X\oplus 1)(Y\oplus 1)=$

$=XY\oplus XY\oplus X\oplus Y\oplus 1=X\oplus Y\oplus 1.$

Փոխակերպումներում օգտագործված են հետևյալ հարաբերությունները.

$A\oplus A=0;$

$(A\oplus B)C=AC\oplus BC.$