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

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

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

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

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

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

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

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

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

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

Այդ պահանջներին պատասխանում է մասնավորապես ֆունկցիաների համակարգը (կոնյունկցիա, գումարում ըստ մոդուլ 2-ի, հաստատուն 1): Հենց այս համակարգի վրա էլ կառուցվում են Ժեգալկինի բազմանդամները:

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

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

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

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

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

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

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

ԿԴՆՁ-ի համարժեքային փոխակերպումների օգնությամբ[խմբագրել | խմբագրել կոդը]

  1. 1,0 1,1 Капитонова Ю. В., Кривой С. Л., Летичевский А. А. Лекции по дискретной математике. — СПб., БХВ-Петербург, 2004. — isbn 5-94157-546-7, с 110-111