ELIB – Էլեկտրոնային Գրադարան | Գրքեր, նյութեր, հոդվածներ

Հ. Ց. ՀԱԿՈԲՅԱՆ

Հ. Գ. ՄՈՎՍԵՍՅԱՆ

ԲՈՒԼՅԱՆ

ՖՈՒՆԿՑԻԱՆԵՐ

ԽՆԴԻՐՆԵՐԻ ԺՈՂՈՎԱԾՈՒ

ԵՐԵՎԱՆԻ ՊԵՏԱԿԱՆ ՀԱՄԱԼՍԱՐԱՆ

Հ. Ց. ՀԱԿՈԲՅԱՆ, Հ. Գ. ՄՈՎՍԵՍՅԱՆ

ԲՈՒԼՅԱՆ ՖՈՒՆԿՑԻԱՆԵՐ

ԽՆԴԻՐՆԵՐԻ ԺՈՂՈՎԱԾՈՒ

ՈՒՍՈՒՄՆԱՄԵԹՈԴԱԿԱՆ ՁԵՌՆԱՐԿ

ԵՐԵՎԱՆ

ԵՊՀ ՀՐԱՏԱՐԱԿՉՈՒԹՅՈՒՆ

ՀՏԴ 519.6(076.1) ԳՄԴ 22.176ց7 Հ 177

Հրատարակության է երաշխավորել ԵՊՀ ինֆորմատիկայի և կիրառական մաթեմատիկայի ֆակուլտետի գիտական խորհուրդը:

Հակոբյան Հ. Ց., Մովսեսյան Հ. Գ. Հ 177

Բուլյան ֆունկցիաներ: Խնդիրների ժողովածու: Ուսումնամեթոդական ձեռնարկ/ Հակոբյան Հ. Ց., Մովսեսյան Հ. Գ.: -Եր., ԵՊՀ հրատ., 2017, 80 էջ:

Խնդրագրքում ներկայացված է դիսկրետ մաթեմատիկայի հիմնական բաժիններից մեկի՝ բուլյան ֆունկցիաների տեսության վերաբերյալ խնդիրների բավական ընդգրկուն շրջանակ: ՀՏԴ 519.6(076.1) ԳՄԴ 22.176ց7

ISBN 978-5-8084-2263-6

ԲՈՎԱՆԴԱԿՈՒԹՅՈՒՆ

Ներածություն ......................................................................................... 5

I – ԲՈՒԼՅԱՆ ՖՈՒՆԿՑԻԱՆԵՐ ԵՎ ԴՐԱՆՑ ՏՐՄԱՆ

ԵՂԱՆԱԿՆԵՐԸ ...................................................................................... 6

Հիմնական սահմանումներ, գաղափարներ, նշանակումներ......... 6 1. Բուլյան վեկտորներ, n-չափանի միավոր խորանարդ ....................................................................................... 16 2. Բուլյան ֆունկցիաների աղյուսակային, վեկտորային և երկրաչափական ներկայացումները.......................................... 22 3. Տարրական ֆունկցիաներ: Տեղադրության գործողություն: Բանաձևային ներկայացումներ .................................................. 25 4. Էական և կեղծ փոփոխականներ ................................................ 29 5. Հատուկ տեսքի բանաձևային ներկայացումներ. դիզյունկտիվ նորմալ ձև (ԴՆՁ), կոնյունկտիվ նորմալ ձև (ԿՆՁ), Ժեգալկինի բազմանդամ .............................. 32

II – ԲՈՒԼՅԱՆ ՖՈՒՆԿՑԻԱՆԵՐԻ ԴԱՍԵՐ:

ՓԱԿՈՒԹՅՈՒՆ ԵՎ ԼՐԻՎՈՒԹՅՈՒՆ ..................................... 37

Հիմնական սահմանումներ, գաղափարներ, նշանակումներ....... 37 6.

Բուլյան ֆունկցիաների դասերի փակություն և լրիվություն ................................................................................... 7. Հաստատունները պահպանող ֆունկցիաներ ....................... 8. Ինքնաերկակի ֆունկցիաներ .................................................... 9. Գծային ֆունկցիաներ ................................................................. 10. Մոնոտոն ֆունկցիաներ ............................................................. 11. Լրիվ և նախալրիվ դասեր: Բազիս ...........................................

III – ԲՈՒԼՅԱՆ ՖՈՒՆԿՑԻԱՆԵՐԻ ԻՐԱՑՈՒՄԸ ՖՈՒՆԿՑԻՈՆԱԼ

ՏԱՐՐԵՐԻ ՍԽԵՄԱՆԵՐՈՎ ....................................................... 58

Հիմնական սահմանումներ, գաղափարներ, նշանակումներ....... 58 12. Ֆունկցիոնալ տարրերի սխեմաներ (ՖՏՍ): Սխեմայի բարդություն ................................................................................. 61

IV – ԴԻԶՅՈՒՆԿՏԻՎ ՆՈՐՄԱԼ ՁԵՎԵՐԻ

ՄԻՆԻՄԱՑՈՒՄ ........................................................................... 65

Հիմնական սահմանումներ, գաղափարներ, նշանակումներ....... 65 13. ԴՆՁ-երի մինիմացման խնդրի երկրաչափական մեկնաբանումը .................................................................................... 68 14. Կրճատված ԴՆՁ: Փակուղային ԴՆՁ-եր ................................. 71 15. Մինիմալ և կարճագույն ԴՆՁ-եր .............................................. 75 Գրականության ցանկ......................................................................... 76

ՆԵՐԱԾՈՒԹՅՈՒՆ

Ուսումնամեթոդական ձեռնարկում ներառված են խնդիրներ, որոնք առնչվում են Երևանի պետական համալսարանի «Ինֆորմատիկայի և կիրառական մաթեմատիկայի» (ԻԿՄ) ֆակուլտետի ուսումնական ծրագրերում, մասնավորապես, «Դիսկրետ մաթեմատիկա» և «Մաթեմատիկական կիբեռնետիկայի հիմունքներ» դասընթացների շրջանակներում ուսումնասիրվող թեմաներին: Մեր համոզմամբ, այն օգտակար կլինի ոչ միայն ԻԿՄ ֆակուլտետի,

այլև

դիսկրետ

մաթեմատիկայի

հարցերով

հե-

տաքրքրվող այլ ուսանողների, ասպիրանտների, հետազոտողների համար: Շնորհակալություն ենք հայտնում ԵՊՀ ԻԿՄ ֆակուլտետի «Դիսկրետ մաթեմատիկայի և տեսական ինֆորմատիկայի» ամբիոնի

ասիստենտ,

ֆիզ.-մաթ.

գիտությունների

թեկնածու

Պ. Պետրոսյանին խնդրագրքի խմբագրման աշխատանքներին ակտիվ

մասնակցության

արժեքավոր

դիտողությունների

համար:

Հ. Ց. Հակոբյան Հ. Գ. Մովսեսյան

I. ԲՈՒԼՅԱՆ ՖՈՒՆԿՑԻԱՆԵՐ ԵՎ ԴՐԱՆՑ

ՏՐՄԱՆ ԵՂԱՆԱԿՆԵՐԸ

Հիմնական սահմանումներ, գաղափարներ, նշանակումներ

~ n  (1 , 2 , 3 ,..., n ) հավաքածուն, որտեղ  i  {0,1}, 1  i  n կոչվում է n -չափանի երկուական կամ բուլյան վեկտոր: Երբեմն այն նշանակում են պարզապես ~ -ով: Հավաքածուի տարրերն անվանում են վեկտորի կոորդինատներ: n թիվը կոչվում է վեկտորի երկարություն: կում են

 n

-ով նշանա-

~ n -ի 1 կոորդինատների քանակը, որն անվանում են

վեկտորի կշիռ: Այլ կերպ ասած՝

    i : n

i 1

 (~ n ) -ով նշանակում են այն թիվը, որի համար ~ n վեկտորը

 (~ n ) 

նրա n

a 2 i

2-ական n i

ներկայացումն

 (~ n ) թիվը

է,

այսինքն՝

~n կոչվում է  վեկտորի հա-

i 1

մար:

B n  { n  i  {0,1}} բազմությունը, այսինքն՝ n -չափանի բոլոր բուլյան վեկտորների բազմությունը անվանում են n -չափանի միավոր խորանարդի գագաթների բազմություն, համապատասխանաբար՝ n -չափանի բուլյան վեկտորներն անվանում են նաև n -չափանի միավոր խորանարդի գագաթներ:

Bkn  { n  n  B n ;  n  k } բազմությունն անվանում են

n -չափանի միավոր խորանարդի k -րդ շերտ (0  k  n ) : ~  (~ ,  ) 

 i 1

  i կոչվում է ~ , ~ վեկտորների հե-

մինգյան հեռավորություն կամ պարզապես հեռավորություն: ~ ~ Երբ  (~ ,  )  1 , ~ ,  կոչվում են հարևան վեկտորներ: Երբ

 (~ ,  )  n , ~ ,  կոչվում են հակադիր վեկտորներ: ~ n  ( ,  ,..., )

վեկտորի հակադիր վեկտորը նշանակում

~n են   (1 ,  2 ,..., n ) :

~ Ասում են, որ ~ -ն նախորդում է  -ին և նշանակում են

   , եթե  i   i , 1  i  n : ~ ~ ~ Եթե ~   կամ   ~ , ապա ~ ,  վեկտորները կոչվում են համեմատելի վեկտորներ: Հակառակ դեպքում դրանց անվանում են անհամեմատելի վեկտորներ: Նախորդման  հարաբերությունը մասնակի կարգի հարաբերություն է

B n բազմության վրա:

n -չափանի միավոր խորանարդ անվանում են այն գրաֆը, որի գագաթների բազմությունը թյունը՝

B n -ն է, կողերի բազմու-

E n -ը, որը սահմանվում է հետևյալ կերպ. ~ ~ ~ E n  {(~ ,  ) ~ ,   B n ,  (~ ,  )  1} :

Նկար 1-ում պատկերված են

n -չափանի միավոր խորա-

նարդներ n =1, 2, 3, 4 դեպքերում: Նկար 1-ում (1 ,  2 ,...,  n ) հավաքածուները ներկայացված են 1 2 ... n տեսքով:

●

Նկար 1

f ( x1 , x 2 ,..., x n ) ֆունկցիան, որը որոշված է B n բազմության վրա և ընդունում է արժեքներ {0,1} բազմությունից, կոչվում է n փոփոխականներից կախված կամ n -տեղանի բուլ8

յան ֆունկցիա: Այն երբեմն նշանակում են նաև՝ f ( ~x n ) : Բոլոր բուլյան ֆունկցիաների բազմությունը նշանակում են

P2 -ով:

Բոլոր n -տեղանի բուլյան ֆունկցիաների բազմությունը նշանակում են

P2n -ով: 0 -տեղանի բուլյան ֆունկցիաները հաս-

տատուն 0 և հաստատուն 1 ֆունկցիաներն են: n -տեղանի բուլյան ֆունկցիան, երբ n  1 , կարելի է ներկայացնել

տո-

ղերով և 2 սյուներով աղյուսակով (տե՛ս նկար 2):

( x1 , x2 ,..., xn 1 , xn ) f ( x1 , x2 ,..., xn 1 , xn ) (0, 0,..., 0, 0) f (0, 0,..., 0, 0) (0, 0,..., 0, 1) f (0, 0,..., 0, 1)

(1, 1,..., 1, 0) (1, 1, ..., 1, 1)

f (1, 1,..., 1, 0) f (1, 1,..., 1, 1) Նկար 2

Այն դեպքում, երբ աղյուսակի ձախ սյունում բուլյան վեկտորները դասավորված են ըստ իրենց համարների աճման կարգի, աղյուսակի աջ սյունը կոչվում է բուլյան ֆունկցիայի

վեկտորային ներկայացում. f (~ x n )  ( f (0,0,..., 0,0), f (0,0,..., 0,1),..., f (1,1,...,1,1)) : Երկու n -տեղանի բուլյան ֆունկցիաներ, որոնք կախված են միևնույն

x1 , x2 ,..., xn փոփոխականներից, կոչվում են հա-

վասար, եթե նրանց աղյուսակները համընկնում են:

N f  {~ n f (~ n )  1, ~ n  B n } բազմությունը կոչվում է

f (~ x n ) բուլյան ֆունկցիայի 1-երի կետերի բազմություն: Ասում են, որ

f (~ x n ) բուլյան ֆունկցիան տրված է երկրաչափորեն,

եթե n -չափանի միավոր խորանարդի վրա նշված են բոլոր այն գագաթները, որոնք պատկանում են

N f բազմությանը:

0, 1 և 2 տեղանի բուլյան ֆունկցիաները կոչվում են տար-

րական բուլյան ֆունկցիաներ: Նկար 3-ում և 4-ում, համապատասխանաբար, ներկայացված է դրանց մի մասը:

Նկար 3

x1 x2

x1 & x 2 x1  x 2 x1  x2 x1  x2 x1  x 2 x1  x2 x1  x2

Նկար 4

Տարրական ֆունկցիաներն ունեն հետևյալ անվանումները.

x - նույնական x ֆունկցիա,

x - x -ի ժխտում,

x1 & x 2 - կոնյունկցիա,

x1  x2 - դիզյունկցիա, x1  x2 - իմպլիկացիա, x1  x2 - գումար ըստ մոդուլ 2-ի, x1  x2 - համարժեքություն, x1  x 2 - Շեֆֆերի ֆունկցիա, x1  x 2 - Պիրսի ֆունկցիա: Օգտագործված նշանները կոչվում են տրամաբանական

կապեր: Նշված տրամաբանական կապերն օգտագործվում են նաև բուլյան վեկտորների նկատմամբ գործողություններ սահմանելու համար: Մասնավորապես, սահմանվում են՝

~ n  

~ n & 

 ( 1   1 ,  2   2 ,...,  n   n ) ,  ( 1 &  1 ,  2 &  2 ,...,  n &  n ) ,

և այլ գործողություններ բուլյան վեկտորների միջև: Դիտարկենք փոփոխականների X  {x1 , x2 ,... xn ,...} բազմությունը: Փոփոխականների X բազմության և տարրական բուլյան ֆունկցիաների բազմության համար սահմանվում է «բանաձևի» գաղափարը մակածման եղանակով, այն է՝ 1. ցանկացած x i  X բանաձև է, hաստատուն 0, 1 բուլյան ֆունկցիաները բանաձևեր են,

2. եթե A -ն, B -ն բանաձևեր են, ապա հետևյալ արտահայտությունները նույնպես բանաձևեր են.

( A ) , ( A * B) , որտեղ * -ը վերը նշված տրամաբանական կապերից որևէ մեկն է, 3. այլ բանաձևեր չկան: Եթե

f ( x1 , x 2 ,..., x n ) ֆունկցիայի որևէ փոփոխականի

փոխարեն տեղադրվում է որևէ ֆունկցիա, ապա այդ գործողությունն անվանում են տեղադրություն կամ սուպերպոզիցիա: Դժվար չէ տեսնել, որ բանաձևի սահմանման մեջ 2-րդ՝ հիմնական կետը, որը բանաձևի կառուցման հիմնական եղանակն է, հենց տեղադրությունն է: Ասում են, որ բանաձևը իրացնում է բուլյան ֆունկցիա հետևյալ սկզբունքով. 1. Ցանկացած xi  X տեսքի բանաձև իրացնում է նույնական

xi ֆունկցիան:

2. Հաստատուն 0, 1-ը՝ որպես բանաձևեր, իրացնում են հենց համապատասխան հաստատուն բուլյան ֆունկցիաները: 3. Եթե A -ն և B -ն բանաձևեր են, որոնք իրացնում են համապատասխանաբար

f1 , f 2 ֆունկցիաները,

ապա

(A) ,

( A * B ) բանաձևերը իրացնում են, համապատասխանաբար

f1 f1 * f 2 ֆունկցիաները, որտեղ * -ը վերը նշված տրամաբանական կապերից որևէ մեկն է: Ասում են, որ * տրամաբանական կապն ունի. ա) իդեմպոտենտության հատկություն, եթե ( A * A)  A , բ) կոմուտատիվության հատկություն, եթե

( A * B )  ( B * A) , գ) ասոցիատիվության հատկություն, եթե

(( A * B) * C )  ( A * ( B * C )) : Բանաձևում փակագծերի առատությունից խուսափելու նպատակով մտցվում են որոշ պայմանավորվածություններ: Նախ, պայմանավորվում են բաց թողնել բանաձևի արտաքին փակագծերը: Երկրորդ, տրամաբանական կապերի միջև սահմանվում է առաջնահերթություն: Առաջնային է ժխտում կապը, այնուհետ՝ կոնյունկցիան, հետո՝ դիզյունկցիան, հետո՝ մյուսները: Փակագծերը բաց են թողնվում նաև այն դեպքերում, երբ բանաձևում ձախից աջ նույն առաջնահերթության կապեր են:

f ( x1 , x2 ,..., xn ) ֆունկցիայի x k փոփոխականը կոչվում է էական փոփոխական, եթե գոյություն ունեն ~ ~ n  (1 ,..., k 1 ,0, k 1 ,..., n ) և  n  ( 1 ,...,  k 1 ,1, k 1 ,...,  n ) վեկտորներ, այնպես, որ

~ f (~ n )  f (  n ) : Հակառակ դեպքում xk -ը կոչվում է կեղծ

(ոչ էական):

f (~ x n ) և g(~ y m ) ֆունկցիաները կոչվում են հա-

վասար, եթե դրանցից մեկը ստացվում է մյուսից կեղծ փոփոխականներ ավելացնելով կամ հեռացնելով: Սահմանենք մի քանի հայտնի բուլյան ֆունկցիաներ: f (~ x n ) -ը կանվանենք շղթայական ֆունկցիա, եթե N f  {~1 ,~2 ,..., ~m 1} , որտեղ  (~i , ~i 1 )  1 , i  1, m և  (~i ,~ j )  1 , երբ i  1  j :

f (~ x n ) -ը կանվանենք ցիկլիկ ֆունկցիա, եթե N f  {~1 ,~2 ,..., ~2 m } , որտեղ  (~i , ~i 1 )  1 , i  1, 2m  1 ,  (~1 , ~2 m )  1 և  (~i ,~ j )  1 մնացած i, j -երի համար:

f (~ xn)

-ը

գոտկային

կանվանենք

ֆունկցիա,

եթե

N f   Bin , և այն կնշանակենք S k ,m ( ~ x n ) -ով: ik

k ,k

(~ x n ) -ն կանվանենք տարրական սիմետրիկ ֆունկ-

ցիա: Ցանկացած

i1 , i2 ,..., il ոչ բացասական ամբողջ թվերի հա-

0  i1  i2  ...  il  n պայմաi ,i ~ n i ,i ~ n i ,i ~ n նին, S 1 1 ( x )  S 2 2 ( x )  ...  S l l ( x ) ֆունկցիան

մար, որոնք բավարարում են

կանվանենք սիմետրիկ ֆունկցիա: Ընդունված է հետևյալ նշանակումը.

 x, եթե   1 x    x , եթե   0 : Տեղի ունի հետևյալ հավասարությունը, որը կոչվում է բուլյան ֆունկցիայի վերլուծություն՝ ըստ առաջին k փոփոխականների.

f ( x1 ,..., x k , x k 1 ,..., x n ) 



( 1 , 2 ,..., k )B k

x11 & x 2 2 & ... x k k & f ( 1 ,... k , x k 1 ,... x n ) :

Երբ k  n , ունենում ենք՝

f (x1 ,..., x n ) 



( 1,  2 ,... n )N f

x11 & x 2 2 & ... & x n n :

Այս ներկայացումը կոչվում է բուլյան ֆունկցիայի կատարյալ դիզյունկտիվ նորմալ ձև (կատարյալ ԴՆՁ): Այս բանաձևով կարող է ներկայացվել ցանկացած բուլյան ֆունցիա, որը նույնաբար 0 չէ: Ցանկացած բուլյան ֆունցիա, որը հաստատուն 1 չէ, կարող է ներկայացվել

f ( x1 ,..., xn ) 

( x1  x2  ...  xn ) & ,... ) N

( 1, 2

բանաձևով, որը կոչվում է բուլյան ֆունկցիայի կատարյալ

կոնյունկտիվ նորմալ ձև (կատարյալ ԿՆՁ): Ցանկացած բուլյան ֆունցիա կարող է ներկայացվել նաև f ( x1 ,..., x n ) 



1 i1  i2 ... ik  n {i1 ,i2 ,..., ik }{1, 2 ,..., n}

բանաձևով, որտեղ

c i1i2 ...ik & x i & x i & ... & x i  c 0

c0 և ci1i2 ...ik գործակիցները {0,1} բազմու-

թյունից են: Այս բանաձևը կոչվում է Ժեգալկինի բազմանդամ: Առավելագույն k -ն, որի համար ci1i2 ...ik

կինի բազմանդամի աստիճան:

 1 կոչվում է Ժեգալ-

1. ԲՈՒԼՅԱՆ ՎԵԿՏՈՐՆԵՐ,

ԽՈՐԱՆԱՐԴ

n - ՉԱՓԱՆԻ ՄԻԱՎՈՐ

1.1 Գտնել՝ 1) (1010), (10101), (111000) վեկտորների համարները, 2) B բազմության 1, 11, 111 համարների վեկտորները,

n 3) B1 բազմության վեկտորների համարները, n 4) B k բազմության այն ~ վեկտորների քանակը, որոնց n 1   (~ )  2 n , n  1 : համար 2

1.2 Գտնել հետևյալ բազմությունների տարրերի քանակը. ~ ~ n 1) {   B } , 2) {

  B n ,   k, k  0,1,..., n} ,

3) {

  B n ,   k, k  0,1,..., n} ,

4) { 5) {

  B n , l    k} , որտեղ 0  l  k  n ,

  Bn , 1  2  ...  n } :

1.3 Ցույց տալ, որ B n բազմության ~ ,  վեկտորները հակա~ n դիր են միայն այն դեպքում, երբ  (~ )   (  )  2  1 :

~ n 1.4 Ցույց տալ, որ B բազմության կամայական ~ ,  և ~ վեկտորների համար՝ ~ 1) 0   (~ ,  )  n ,

~ ~ 2)  (~ ,  )  0 միայն այն դեպքում, երբ ~   , ~ ~ 3)  (~ ,  )  n միայն այն դեպքում, երբ ~ և  վեկտորները հակադիր են,

~ ~ 4)  (~ ,  )   (  , ~ ) , ~ ~ 5)  (~ , ~ )   (~ ,  )   (~ ,  ) , ~ ~ 6)  (~ ,  )   (~  ~ ,   ~ ) , ~ ~ 7)  (~ ,  )  ~   , ~ ~ ~ 8)  (~ ,  )  ~    2 ~ &  : 1.5 Գտնել n -չափանի միավոր խորանարդի` 1) բոլոր կողերի քանակը, 2) այն կողերի քանակը, որոնք միացնում են շերտերի վեկտորները

B kn և Bkn1

(k  0,1,..., n) :

1.6 Գտնել B բազմության հետևյալ ենթաբազմությունների տարրերի քանակը. ~ ~ ~ n ~ 1) {  ( ,  )  r} , որտեղ   B որևէ տրված վեկտոր է,

~ 2) {

~  (~ ,  )  r} , որտեղ ~  B n որևէ տրված վեկտոր

է,

~ ~  (~ , ~ )   (~ ,  )  m} , որտեղ ~  B n ,   B n

~ տրված վեկտորներ են, և  (~ ,  )  m , ~ ~ ~ ~ ~ ~ n n ~ 4) {  ( ,  )   ( ,  )  m  1} , որտեղ   B ,   B ~ տրված վեկտորներ են, և  (~ ,  )  m ,

~ 5) {

~ ~  (~ , ~ )   (~ ,  )  m  2} , որտեղ ~  B n ,   B n

~ տրված վեկտորներ են, և  (~ ,  )  m :

n ~ 1.7 Դիցուք,   Bk : Գտնել հետևյալ բազմությունների տար-

րերի քանակը. ~ ~ n 1) {   B k 1 , ~ ~ n 2) {   Bk 1 , ~ ~ n 3) {   B k 1 , ~ ~ n 4) {   Bk  2 , ~ ~ n 5) {   B k  2 ,

~ 1  k  n,  (~ ,  )  3} , ~ 0  k  n  1,  (~ ,  )  3} ~ 1  k  n,  (~ ,  )  3} , ~ 2  k  n,  (~ ,  )  4}

~ 0  k  n  2,  (~ ,  )  4} :

~ n n ~ 1.8 Դիցուք,   B ,   B տրված վեկտորներ են, այնպի~ սին, որ  (~ ,  )  m : Գտնել B n բազմության հետևյալ ենթաբազմությունների տարրերի քանակը. ~ ~ ~ ~ ~ 1) {  ( ,  )  r ,  ( ,  )  k } , ~ ~ ~ ~ ~ 2) {  ( ,  )  r ,  ( ,  )  k } , ~ ~ ~ ~ ~ 3) {  ( ,  )  r ,  ( ,  )  k } : 1.9 Գտնել B n բազմության զույգ առ զույգ հակադիր վեկտորների առավելագույն քանակը: n 1.10 Գտնել Bk բազմության զույգ առ զույգ ոչ հակադիր վեկտորների առավելագույն քանակը:

1.11

n -ի

և k -ի ինչպիսի՞ արժեքների դեպքում

թյունը չի պարունակի հակադիր վեկտորներ:

B kn բազմու-

~ n 1.12 Գտնել B բազմության ~ և  վեկտորներից կազմված ~ բոլոր չկարգավորված (~ ,  ) զույգերի քանակը, որոնց համար՝

~ 1)  (~ ,  )  r , ~ ~ 2)  (~ ,  )  1 և  (~ )   (  )  1 ,

~ ~ 3)  (~ ,  )  1 և  (~ )   (  )  2 : 1.13

Գտնել` 1) 2)

~ max  (~ ,  ) ~ ~ ,   Bkn ~ max  (~ ,  ) ~ ~  B n ,   B n k

k 1

~ min  (~,  ) ~ ~,   Bkn ~ min  (~ ,  ) ~ ~  Bkn ,   Bkn1

1.14 Գտնել B բազմության այն ենթաբազմությունների քանակը, որոնք՝ 1) չեն պարունակում միևնույն կշիռ ունեցող վեկտորներ; 2) չեն պարունակում հակադիր վեկտորներ; 3) պարունակում են ճիշտ k հատ հակադիր վեկտորների զույգեր:

~ ~ ~ 1.15 Դիցուք,    և  (~ ,  )  m : Գտնել այն

~ վեկտորների քանակը, որ    ~

B n բազմության

  :

1.16 Դիցուք,   Bk : Գտնել հետևյալ բազմությունների տարրերի քանակը. 1) {   B nm ,    } , որտեղ k  m ,

2) {

  B nm ,    } , որտեղ k  m ,

3) {

  B n ,    }  {

  B n ,    } :

1.17 Գտնել բոլոր ~0 , ~1 , ~2 ,..., ~n հաջորդականությունների քանակը, որտեղ ~  B n , k  0, n , և որոնց համար

~0  ~1  ~2  ...  ~n :

1.18 Գտնել 1.17 խնդրի հաջորդականություններից այնպիսինn ների քանակը, որոնք պարունակում են տրված ~  B վեկk

տորը:

~ n n 1.19 Դիցուք, ~  Bk ,   Bm տրված վեկտորներ են, (k  m) ~ n և  (~ ,  )  r : Գտնել B բազմության այն վեկտորների քանակը, որոնք՝ ~    ; 1) համեմատելի են ~ -ի և  -ի հետ, եթե  ~ ~ 2) համեմատելի են ~ -ի և  -ի հետ, եթե ~ -ն և  -ն անհամեմատելի են: ~ n n 1.20 Դիցուք, ~  Bk ,   Bm տրված վեկտորներ են և ~  (~ ,  )  r : Գտնել հետևյալ բազմությունների տարրերի քանակը. 1) {i  i   i  1} ,

2) {i  i   i  0} , 3) {i  i  0,  i  1} , 4) {i  i  1,  i  0} :

~ ~ 3m 1.21 Դիցուք, ~ ,   B և ρ( ~ ,  )=2m: Գտնել

B 3m -ի

այն ~

վեկտորների քանակը, որ  (~, ~ )   (~,  )  2m :

1.22

~ ~ 4m 4m Դիցուք, ~ ,   B և ρ( ~ ,  )=2m: Գտնել B -ի այն

~ ~ վեկտորների քանակը, որ  (~, ~ )   (~,  )  2m :

2. ԲՈՒԼՅԱՆ ՖՈՒՆԿՑԻԱՆԵՐԻ ԱՂՅՈՒՍԱԿԱՅԻՆ,

ՎԵԿՏՈՐԱՅԻՆ ԵՎ ԵՐԿՐԱՉԱՓԱԿԱՆ

ՆԵՐԿԱՅԱՑՈՒՄՆԵՐԸ

2.1 Պարզել՝ կարող են արդյոք հետևյալ վեկտորները լինել որևէ բուլյան ֆունկցիայի վեկտորային ներկայացում. 1) ~  (000000) ,

2) ~  ( 0000111100 00 ) :

x 3 ) ֆունկցիայի աղյուսակը, եթե հայտնի է, 2.2 Կառուցել f ( ~ որ այն 1 արժեք է ընդունում միայն այն դեպքում, երբ x1  1 կամ երբ x1  x2 և x2  x3 :

x 4 ) ֆունկցիայի աղյուսակը, եթե հայտնի է, 2.3 Կառուցել f ( ~ որ այն 0 արժեք է ընդունում միայն այն դեպքում, երբ 2 x1  x2  x3  2 x4 : 2.4 Գտնել n փոփոխականից կախված բուլյան ֆունկցիաների քանակը, որոնք. 1) ցանկացած հարևան վեկտորների վրա ընդունում են նույն արժեքը, 2) ցանկացած հարևան վեկտորների վրա ընդունում են տարբեր արժեքներ, 3) ոչ բոլոր հարևան վեկտորների վրա են ընդունում նույն արժեքը, 4) առնվազն երկու հարևան վեկտորների վրա ընդունում են նույն արժեքը, 5) ցանկացած հաջորդական համարներ ունեցող վեկտորների վրա ընդունում են նույն արժեքը,

6) ցանկացած հաջորդական համարներ ունեցող վեկտորների վրա ընդունում են տարբեր արժեքներ, 7) ոչ բոլոր հաջորդական համարներ ունեցող վեկտորների վրա են ընդունում նույն արժեքը, 8) ընդունում են նույն արժեքը առնվազն երկու հաջորդական համարներ ունեցող վեկտորների վրա: 2.5 Գտնել n փոփոխականից կախված բուլյան ֆունկցիաների քանակը, որոնք. 1) հակադիր վեկտորների վրա ընդունում են նույն արժեքը, 2) ճիշտ k հատ վեկտորների վրա ընդունում են 1 արժեք, 3) ընդունում են 1 արժեք k-ից ոչ ավել վեկտորների վրա, 4) ընդունում են 1 արժեք նույն կշիռն ունեցող վեկտորներից միայն մեկի վրա, 5) ընդունում են նույն արժեքը կենտ կշռով վեկտորների վրա, 6) ընդունում են նույն արժեքը նույն կշիռն ունեցող բոլոր վեկտորների վրա (սիմետրիկ են), 7) ընդունում են 1 արժեք բոլոր այն ~ վեկտորների վրա, ~ որոնց համար՝ k    s , որտեղ 0  k  s  n : 2.6 Գտնել n փոփոխականից կախված բուլյան ֆունկցիաների n քանակը, որոնք ցանկացած ~  ( ,  ,...,  )  B -ի համար

բավարարում են հետևյալ պայմաններին.

1) f (1 ,  2 ,  3 ,...,  n )  f ( 2 , 1 ,  3 ,...,  n ) , 2) f (1 ,  2 ,  3 ,...,  n )  f (1 ,  2 ,  3 ,...,  n ) , 3) f (1 , 2 , 3 ,..., n )  f (1   2 ,1   2 , 3 ,..., n ) :

2.7 Գտնել 2n փոփոխականից կախված բուլյան ֆունկցիաների քանակը, որոնք ցանկացած   ( 1 ,  2 ,...,  2 n )  B 2 n -ի համար բավարարում են հետևյալ պայմաններին. 1, եթե   n, f (1 ,  2 ,  3 ,...,  2 n )   ~ 0, եթե   n :

x ) բուլյան ֆունկցիաների քանակը, որոնց 12.8 Գտնել f ( ~ երի կետերը բավարարում են հետևյալ պայմաններին՝ 1) x1  x 2  ...  xn 1  xn  k , n

2) x1  x 2  x3  ...  (1) n x n  0 :

3 ՏԱՐՐԱԿԱՆ ՖՈՒՆԿՑԻԱՆԵՐ:

ՏԵՂԱԴՐՈՒԹՅԱՆ ԳՈՐԾՈՂՈՒԹՅՈՒՆ:

ԲԱՆԱՁԵՎԱՅԻՆ ՆԵՐԿԱՅԱՑՈՒՄՆԵՐ

3.1 Պարզել՝ հետևյալ տարրական ֆունկցիաներից որոնք ունեն կոմուտատիվության, ասոցիատիվության, իդեմպոտենտության հատկություններ.

x & y, x  y, x  y , x  y, x  y, x  y , x  y : 3.2 Համարժե՞ք են արդյոք հետևյալ բանաձևերը. 1) x1  x 2 և ( x1  x 2 )  x 2 , 2) x1  ( x2  x3 ) և ( x1  x2 )  ( x1  x3 ) , 3) ( x1  x 2 )  (( x 2  ( x1  x3 ))  x3 ) և

( x1  x2 )  ( x1  ( x2  ( x1 x3 ))) , 4) x1  (( x 2  x3 )  x 2 x3 ) և

( x1  ( x2  x3 ))( x1  x2 , 5) x1  x 2 )  ( x1  ( x 2  x3 ) և x2  ( x1  x3 ) : 3.3 Ապացուցել հետևյալ բանաձևերի համարժեքությունը՝ կիրառելով տարրական ֆունկցիաների համարժեք ձևափոխություններ . 1) x  y և ( x  y )( y  x ) , 2) 3) 4) 5) 6)

x  y և (( x  x)  ( y  y ))  ( x  x)  ( y  y)) , x  ( y  z) և ( x  y)  ( x  z) , x ( y  z ) և ( xy  xz )  x , x  ( y  z) և ( x  y)  ( x  z) , x  ( y  z) և ( x  y)  ( x  z) ,

7) x ( y  z ) և ( x  y )  xz , 8) x  ( y  z ) և ( x  y )  ( x  z ) , 9) x  yz և ( x  y )( x  z ) , 10) x  ( y  z ) և ( x  y )  ( x  z ) : 3.4 Փոփոխականների փոխարեն տեղադրելով {0, 1, x} բազմության ֆունկցիաներ, հետևյալ ֆունկցիաներից ստանալ x ֆունկցիան. 1) 2)

~ f  (0110 ) ,

~ f  (10110111) :

3.5 f ( x1, x2 )  (0100) և g ( x1 , x2 )  (1101) ֆունկցիաների վեկտորային ներկայացումների միջոցով կառուցել

h( x1, x2 )  f ( x1, g ( x2 , x1 )) ֆունկցիայի արժեքների վեկտորը: 3.6 Դիցուք,

~ f  (10111010)

~g  (01110010 )

~h  (11110101) : Կառուցել հետևյալ ֆունկցիաների արժեքների վեկտորները. 1) f ( x2 , x3 , x1 ) , 2) f ( x1 , g ( x1 , x 2 , x3 ), x3 ) , 3) f ( x3 , g ( x1 , x2 , x1 ), h( x1 , x2 , x3 )) , 4) g ( x2 , h( x1 , x1 , x1 ), f ( x1 , x2 , g ( x1 , x2 , x1 ))) : 3.7 Արտահայտել f ( x , y ) ֆունկցիան A դասի ֆունկցիաների միջոցով. 1) f ( x , y )  x  y , A  {,} , 2) f ( x , y )  x  y , A  {} , 3) f ( x , y )  x  y , A  {&, } ,

4) f ( x, y)  x  y , A  {} : 3.8 Ցույց տալ, որ f ( x )  x ֆունկցիան հնարավոր չէ արտահայտել {&,  , , } դասի ֆունկցիաների միջոցով: 3.9 Ցույց տալ, որ f ( x , y ) ֆունկցիան հնարավոր չէ արտահայտել A դասի ֆունկցիաների միջոցով. 1) f ( x , y )  x  y , A  {&} , 2) f ( x , y )  x  y , A  {} , 3) f ( x , y )  x & y , A  { , } , 4) f ( x , y )  x  y , A  {&,} : 3.10 Դիցուք, բուլյան ֆունկցիայի բանաձևը պարունակում է միայն համարժեքություն տարրական ֆունկցիան: Ապացուցել, որ այդ ֆունկցիան հաստատուն 1 է միայն այն դեպքում, երբ բանաձևում յուրաքանչյուր փոփոխական գրված է զույգ անգամ: 3.11 Դիցուք, բուլյան ֆունկցիայի բանաձևը պարունակում է միայն համարժեքություն և ժխտում տարրական ֆունկցիաները: Ապացուցել, որ այդ ֆունկցիան հաստատուն 1 է միայն այն դեպքում, երբ բանաձևում յուրաքանչյուր փոփոխական գրված է զույգ անգամ, և ժխտման նշանների քանակը զույգ է: 3.12 Գտնել հետևյալ ֆունկցիաների 1-երի քանակը. 1) f ( ~ x n )  x1  ( x 2  ( x3  ...  ( x n 1  x n )...)) , 2) f ( ~ x n )  (...(( x1  x 2 )  x3 )  ...)  x n ,

x n )  x1 x 2  x 2 x3  ...  x n 1 x n , 3) f ( ~

4) f ( ~ x n )  x1 x 2  x 2 x3  ...  x n 1 x n  x n x1 ,

5) f ( ~ x 2 k )  x1 x 2  x3 x 4  ...  x 2 k 1 x 2 k ,

6) f ( ~ x 2 k 1 )  x1 x 2  x3 x 4  ...  x 2 k 1 x 2 k  x 2 k 1 , 7) f ( ~ x n )  x1 x 2  x 2 x3  ...  x n 1 x n ,

8) f (x n )  x1x 2  x 2 x 3  ...  x n 1x n  x n x1 , 9) f ( ~ x 2 k )  x1 x 2  x3 x 4  ...  x 2 k 1 x 2 k ,

10) f ( ~ x 2 k )  ( x1  x 2 )( x3  x 4 )...( x 2 k 1  x 2 k ) ,

11) f ( ~ x 2 k 1 )  x1 x 2  x3 x 4  ...  x 2 k 1 x 2 k  x 2 k 1 , 12) f (x 2k )  (x1  x 3  ...  x 2k 1 )(x 2  x 4  ...  x 2k ), 13) f (x 2k )  (x1  x 3  ...  x 2k 1 )  (x 2  x 4  ...  x 2k ),

14) f (x 2k )  (x1  x 3  ...  x 2k 1 )  (x 2  x 4  ...  x 2k ), 15) f (x 2k )  (x1  x 2 )(x 3  x 4 )...(x 2k 1  x 2k ),

16) f ( ~ x 2 k )  ( x1  x 2 )  ( x3  x 4 )  ...  ( x 2 k 1  x 2 k ) , 17) f ( ~ x n )  ( x1  x 2 )( x 2  x3 )...( x n 1  x n ) ,

18) f ( ~ x n )  ( x1  x 2 )  ( x 2  x3 )  ...  ( x n 1  x n ) :

4 ԷԱԿԱՆ ԵՎ ԿԵՂԾ ՓՈՓՈԽԱԿԱՆՆԵՐ

4.1 Ապացուցել, որ x1 -ը կեղծ փոփոխական է f ֆունկցիայի համար՝ ներկայացնելով ֆունկցիան այնպիսի բանաձևով, որը x1 չի պարունակում.

x 2 )  ( x2  x1 )( x2  x2 ) , 1) f ( ~

x 3 )  (( x1  x2 )  x3 ) x3  x2 , 2) f ( ~

x 3 )  (( x1  x2 x3 )  ( x1  x2 x3 ))(x2  x3 ) , 3) f ( ~

x 4 )  ( x1  ((x2  x3 )  x4 ))  x1 ( x2  x3 ) x4 : 4) f ( ~

4.2 Պարզել՝ ստորև բերված ֆունկցիաների որ փոփոխականներն են էական, որոնք` կեղծ: Հեռացնելով կեղծ փոփոխականները՝ ստանալ միայն էական փոփոխականներից կախված համարժեք ֆունկցիաներ.

~ 1)  f  (1011101100 100010 ) ,

~ 2)  f  (0101101001 011010) : 4.3 Դիցուք, f ( x1 , x 2 )  (1010 ) : Գտնել հետևյալ ֆունկցիաների վեկտորային ներկայացումները. 1) g ( z, x1 , x2 )  f ( x1 , x2 ) , 2) g ( x1 , z, x2 )  f ( x1 , x2 ) , 3) g ( x1 , x2 , z )  f ( x1 , x2 ) : 4.4 Կեղծ փոփոխականների հեռացման միջոցով պարզել՝ հավասար են արդյոք հետևյալ ֆունկցիաները.  g  (11001011) , 1) ~ f  (1011) և  ~ 2) ~ f  (0110) և  g  (0110110111100011) :

x ) ֆունկցիան ունի k հատ ոչ էա4.5 Ապացուցել, որ եթե f ( ~ կան փոփոխական, ապա նրա 1-երի կետերի քանակը՝ |Nf| բաժանվում է 2k-ի: Ճի՞շտ է արդյոք հակառակ պնդումը: n

4.6 Գտնել ճիշտ k հատ ոչ էական փոփոխական ունեցող

f (~ x n ) ֆունկցիաների քանակը:

x ) ֆունկցիայի իսկության վեկտո4.7 Ապացուցել, որ եթե f ( ~ րի մեկ կոորդինատը 0 է, իսկ մնացածը՝ 1, կամ մի կոորդինատը` 1, իսկ մնացածը՝ 0, ապա այդ ֆունկցիան էապես է կախված իր բոլոր փոփոխականներից: n

x ) ֆունկցիաների քանակը, որոնց բոլոր 4.8 Գտնել բոլոր f ( ~ փոփոխականներն էական են: n

x ) ֆունկցիաների քանակը, որոնց բոլոր 4.9 Գտնել բոլոր f ( ~ փոփոխականները կեղծ են: n

x ) ֆունկցիաների քանակը, որոնք ու4.10 Գտնել բոլոր f ( ~ նեն ճիշտ մեկ կեղծ փոփոխական: n

4.11 Ապացուցել, որ ցանկացած հաստատունից տարբեր սիմետրիկ ֆունկցիա էապես կախված է իր բոլոր փոփոխականներից: 4.12 Պարզել՝ n -ի ( n  2) որ արժեքների դեպքում հետևյալ ֆունկցիաները էապես են կախված իրենց բոլոր փոփոխականներից. x n )  ( x1  ...  x n )  ( x1  x 2 )...( x n 1  x n )( x n  x1 ) , 1) f ( ~

x n )  ( x1 x2  ...  xn1 xn  xn x1 )  ( x1 x2  ...  xn1 xn  xn x1 ) , 2) f (~ x n )  ( x  x )  ( x  x )  ....  ( x  x )  ( x  x ) , 3) f ( ~

n 1

4) f (x ) (x1 (x2 ....(xn1 xn)...)) (x1 xn)(x2 xn)...(xn1 xn), n

5) f (xn) (x1 x2)(x2 x1)(x2 x3)(x3 x2)....(xn x1)(x1 xn),

6) f (~x n )  (x1 x2 )(x2 x3 )....(xn1 xn )(xn x1 ) (x1  x2 ... xn 1) :

5 ՀԱՏՈՒԿ ՏԵՍՔԻ ԲԱՆԱՁԵՎԱՅԻՆ ՆԵՐԿԱՅԱՑՈՒՄՆԵՐ.

ԴԻԶՅՈՒՆԿՏԻՎ ՆՈՐՄԱԼ ՁԵՎ (ԴՆՁ), ԿՈՆՅՈՒՆԿՏԻՎ

ՆՈՐՄԱՆ ՁԵՎ (ԿՆՁ), ԺԵԳԱԼԿԻՆԻ ԲԱԶՄԱՆԴԱՄ

5.1 Հետևյալ ֆունկցիաները վերլուծել ըստ x1 փոփոխականի.

x 2 )  x1  x2 , 1) f ( ~

2) f ( ~ x 3 )  ( x1  x 2 )( x 2  x3 ) , 3) f ( ~ x 3 )  x1  ( x 2  x3 ) ,

4) f ( ~ x 3 )  x1 x 2  x 2 x3  x1 x3 ,

x 4 )  ( x1  x 2  x3 ) x 4  x1 x 2 x3 : 5) f ( ~

5.2 5.1-ում բերված ֆունկցիաները վերլուծել ըստ x1 և x2 փոփոխականների: 5.3 Հիմնական տարրական ֆունկցիաները ներկայացնել կատարյալ ԴՆՁ և կատարյալ ԿՆՁ տեսքերով: 5.4 Հետևյալ ֆունկցիաները ներկայացնել կատարյալ ԴՆՁ և կատարյալ ԿՆՁ տեսքերով.

~ 1)  f  (0110 ) , ~ 2)  f  (00010111) ,

~ 3)  f  (0000111100100001) :

5.5 Ստանալ ԴՆՁ-ով ներկայացում հետևյալ ֆունկցիաների համար՝ կատարելով բանաձևերի համարժեք ձևափոխություններ. 1) f ( ~ x 3 )  ( x1  x 2  x3 )( x1 x3  x 2 ) ,

2) f ( ~ x 3 )  ( x1  x 2 )  ( x 2  x3 ) ,

x 3 )  ( x1  x2 x3 )  ( x1  ( x2  x3 )) , 3) f ( ~ x 3 )  ( x1  x 2 )( x 2  x 3 ) , 4) f ( ~ x 3 )  ( x1 x 2  x3 )( x1 x3  x 2 ) , 5) f ( ~ 6) f ( ~ x 4 )  ( x1  x3 )  ( x 2  x 4 ) , 7) f ( ~ x 4 )  ( x1  x 2 ) x3  ( x3  x 4 ) :

x ) ֆունկցիաների քանակը, որոնց համար 5.6 Գտնել այն f ( ~ կատարյալ ԿՆՁ-ն նաև ԴՆՁ է: n

5.7 Գտնել հետևյալ ֆունկցիաների կատարյալ ԴՆՁ-երի երկարությունը. 1) f ( ~ x n )  x1  x 2  ....  x n , 2) f ( ~ x n )  ( x1  x 2  ...  x n )( x1  x 2  ...  x n ) ,

x n )  (x1  x2  x3 )(x1  x2  x3 ).  x4  x5  ... xn : 3) f (~

x ) ֆունկցիաների քանակը, որոնց կատա5.8 Գտնել այն f ( ~ րյալ ԴՆՁ-ում՝ 1) յուրաքանչյուր տարրական կոնյունկցիա պարունակում է առնվազն 2 փոփոխականի ժխտում, 2) յուրաքանչյուր տարրական կոնյունկցիա պարունակում է զույգ թվով փոփոխականի ժխտումներ, 3) յուրաքանչյուր տարրական կոնյունկցիայում ժխտումով փոփոխականների քանակը չի գերազանցում առանց ժխտման փոփոխականների քանակը: n

5.9 Հիմնական տարրական Ժեգալկինի բազմանդամով:

ֆունկցիաները

ներկայացնել

5.10 Հետևյալ ֆունկցիաները ներկայացնել Ժեգալկինի բազմանդամով՝ կիրառելով անորոշ գործակիցների մեթոդը.

x 2 )  x1  x2 , 1) f ( ~

2) f ( ~ x 3 )  x1 ( x 2  x3 ) ,

x 3 )  x1  ( x 2  x3 ) , 3) f ( ~

x 3 )  (00000111) , 4) f ( ~

x 3 )  (01101010) , 5) f ( ~

x 4 )  (0000100010 010000 ) : 6) f ( ~ 5.11 Հետևյալ ֆունկցիաները ներկայացնել Ժեգալկինի բազմանդամով՝ օգտվելով դրանց կատարյալ ԴՆՁ-ից.

x 2 )  x1  x2 , 1) f ( ~

2) f ( ~ x 3 )  x1  ( x3  x 2 ) ,

3) f ( ~ x 3 )  x1  x 2  x3 ,

x 3 )  (11000011) , 4) f ( ~

x 4 )  (0100000000010001) , 5) f ( ~ x 4 )  (1010101010001000) : 6) f ( ~

5.12 Հետևյալ ֆունկցիաները ներկայացնել Ժեգալկինի բազմանդամով` կատարելով համարժեք ձևափոխություններ. 1) f (x 2 )  x1 (x 2  x1x 2 ), 2) f (x 3 )  (x1  (x 2  x 3 ))((x1  x 2 )  x 3 )), 3) f (x 3 )  (x1  x 2 )  (x 2  x 3 ), 4) f (x 3 )  (x1  x 2 )(x 2  x 3 ), 5) f (x 3 )  (x1  x 2 )  (x 2  x 3 ), 6) f (x 4 )  (x1  x 2 )  (x 3  x 3 x 4 ),

7) f (x 4 )  (x1  x 2  x 3 )x 4  x1x 2 x 3 : 5.13 Գտնել Ժեգալկինի բազմանդամով տրված հետևյալ ֆունկցիաների 1-երի քանակը. 1) f ( ~ x n )  x1 x 2  x1 x3  ...  x1 x n , ( n  2) , 2) f ( ~ x n )  x1 x 2  x3  ...  x n , ( n  3) ,

x n )  x1 x 2  x1 x3  x 4 ...  x n , ( n  4) , 3) f ( ~

4) f ( ~ x n )  x1 x 2 x3  x 4 ...  x n , ( n  4) ,

5) f ( ~ x n )  x1 ...x k  x k 1 ...x n , (1  k  n ) ,

x n )  1  x1  x1 x 2  ...x1 x 2 ....x n : 6) f ( ~

x n ) բուլյան ֆունկցիայի համար xi 5.14 Ապացուցել, որ f ( ~ փոփոխականը էական է միայն այն դեպքում, երբ այն ներկայացված է նրա Ժեգալկինի բազմանդամում:

x ) ֆունկցիաների քանակը ( n  3), 5.15 Գտնել բոլոր այն f ( ~ որոնց Ժեգալկինի բազմանդամի աստիճանը՝ 1) փոքր է կամ հավասար 3-ից, n

2) հավասար է 3-ի, 3) հավասար է r-ի:

x ) ֆունկցիաների քանակը, որոնց 5.16 Գտնել բոլոր այն f ( ~ Ժեգալկինի բազմանդամն ունի k երկարություն: n

x n ) ֆունկցիաների քանակը, որոնց 5.17 Գտնել բոլոր այն f ( ~ Ժեգալկինի բազմանդամն ունի k երկարություն, և f (00 ... 0)  f (11 ... 1)  1 :

x n ) ֆունկցիաների քանակը, որոնց 5.18 Գտնել բոլոր այն f ( ~ n

Ժեգալկինի բազմանդամի երկարությունը 2 անգամ մեծ է նրա կատարյալ ԴՆՁ-ի երկարությունից ( n  1) :

x ) ֆունկցիայի Ժեգալկինի բազ5.19 Ապացուցել, որ եթե f ( ~ մանդամն ունի k>0 երկարություն, ապա այն 1 արժեք է ընդունում առնվազն 2 n k վեկտորների վրա B n -ից: n

II. ԲՈՒԼՅԱՆ ՖՈՒՆԿՑԻԱՆԵՐԻ ԴԱՍԵՐ:

ՓԱԿՈՒԹՅՈՒՆ ԵՎ ԼՐԻՎՈՒԹՅՈՒՆ

Հիմնական սահմանումներ, գաղափարներ, նշանակումներ Բուլյան ֆունկցիաների

H դասի փակում [H ]

կոչվում է

այդ դասի ֆունկցիաներից բոլոր հնարավոր տեղադրությունների միջոցով ստացվող բուլյան ֆունկցիաների բազմությունը:

H  P2 դասը կոչվում է փակ, եթե [ H ]  H :

H  P2 դասը կոչվում է լրիվ, եթե [ H ]  P2 : H  P2 դասը կոչվում է նախալրիվ, եթե [ H ]  P2 , սակայն ցանկացած f  H բուլյան ֆունկցիայի համար

[ H  { f }]  P2 : H  P2 դասը կոչվում է բազիս P2 -ի համար, եթե [ H ]  P2 , սակայն ցանկացած f  H բուլյան ֆունկցիայի համար [ H

\ { f }]  P2 :

f ( x1 , x2 ,..., xn ) բուլյան ֆունկցիան կոչվում է 0-ն պահպանող, եթե f (0,0,..., 0)  0 : 0-ն պահպանող ֆունկցիաների դասը նշանակվում է

T0 -ով:

f ( x1 , x2 ,..., xn ) բուլյան ֆունկցիան կոչվում է 1-ը պահպանող, եթե f (1,1,...,1)  1 : 1-ը պահպանող ֆունկցիաների դասը նշանակվում է

T1 -ով:

f ( x1 , x2 ,..., xn ) բուլյան ֆունկցիայի երկակի ֆունկցիա կոչ* վում է f ( x1 , x2 ,..., xn )  f ( x1 , x2 ,..., xn ) ֆունկցիան:

f ( x1 , x2 ,..., xn ) բուլյան ֆունկցիան կոչվում է ինքնաերկակի, եթե f ( x1 , x2 ,..., xn )  f * ( x1 , x2 ,..., xn ) : Ինքնաերկակի ֆունկցիաների դասը նշանակվում է S -ով:

Երկակիության սկզբունքը. Ցանկացած f ( x1 , x 2 ,..., x n ) , g1 ( y1 , y 2 ,..., y k ) , g 2 ( y1 , y 2 ,... y k ) , …. g n ( y1 , y 2 ,..., y k ) բուլյան ֆունկցիաների համար, եթե՝

 ( y1 , y 2 ,..., y k )  f ( g1 ( y1 , y 2 ,..., y k ), g 2 ( y1 , y 2 ,... y k ),..., g n ( y1 , y 2 ,..., y k )),

ապա՝  * ( y 1 , y 2 ,..., y k )  f * ( g 1* ( y1 , y 2 ,..., y k ), g 2* ( y 1 , y 2 ,... y k ),..., g n* ( y 1 , y 2 ,..., y k )) :

f ( x1 , x2 ,..., xn ) բուլյան ֆունկցիան կոչվում է գծային, եթե նրան համապատասխանող Ժեգալկինի բազմանդամը ունի

f (~ x n )  c0  c1 x1  c2 x2    cn xn տեսքը: Գծային ֆունկցիա-

ների դասը նշանակվում է L -ով:

f ( x1 , x2 ,..., xn ) բուլյան ֆունկցիան կոչվում է մոնոտոն, ~

եթե ցանկացած ~ ,   B n հավաքածուների համար ~  ~ պայ~ մանից հետևում է, որ f (~ )  f (  ) : Մոնոտոն ֆունկցիաների դասը նշանակվում է M -ով:

Պոստի թեորեմը (լրիվության հայտանիշը).

H  P2 դասը լրիվ է միայն այն դեպքում, եթե այն T0 , T1 , S , L , M դասերից ոչ մեկի ենթաբազմությունը չէ:

6 ԲՈՒԼՅԱՆ ՖՈՒՆԿՑԻԱՆԵՐԻ ԴԱՍԵՐԻ ՓԱԿՈՒԹՅՈՒՆ ԵՎ

ԼՐԻՎՈՒԹՅՈՒՆ

6.1 Ապացուցել, որ բուլյան ֆունկցիաների ցանկացած A, B , C դասերի համար տեղի ունեն հետևյալ հատկությունները. 1) A  A , 2)

A  A ,

3) եթե A  B ապա

4) եթե B   A և A  C

A  B  , ապա

5) եթե A  A և B  B  ապա 6) եթե A  A և B  B  ապա

7)  A  B    A  B  :

B  C  ,

A  B  A  B ,

A  B  A  B ,

6.2 Ապացուցել, որ P2-ի ցանկացած փակ դաս, որը պարունակում է հաստատունից տարբեր ֆունկցիա, պարունակում է նաև նույնական ֆունկցիան: 6.3 Դիցուք, *  { , ,\, } : Պարզել, թե* գործողության որ արժեքների դեպքում T0 * S դասը կլինի փակ: 6.4 Դիցուք, A  B  S և [ A  {1}]  [ B  {1}] : Ապացուցել, որ այդ դեպքում՝ [ A]  [ B ] : 6.5 Պարզել՝ փակ են արդյոք բուլյան ֆունկցիաների հետևյալ դասերը. 1) մեկ փոփոխականի բոլոր բուլյան ֆունկցիաների բազմությունը,

2) երկու փոփոխականի բոլոր բուլյան ֆունկցիաների բազմությունը, 3) բոլոր սիմետրիկ ֆունկցիաների բազմությունը, 4) բոլոր այն n փոփոխականի ֆունկցիաների բազմությունը, որոնց Ժեգալկինի բազմանդամի աստիճանը չի գերազանցում 1-ը, 5) բոլոր այն n փոփոխականների ֆունկցիաների բազմությունը, որոնց Ժեգալկինի բազմանդամի աստիճանը չի գերազանցում 2-ը: 6.6 Ցույց տալ, որ f  [ A] , արտահայտելով՝ f -ը A -ի բանաձևերով. 1) f  x , A  {0, x  y} ,

 x  y , A  {x  y} ,  x , A  { x  y} ,  x  y  z , A  { x  y} ,  0 , A  { xy  z} ,  x , A  {xy } ,  x  y , A  { x  y} ,  x , A  { xy  yz  zx} ,  xy , A  { xy  z} , f  xyz  t ( x  y  z ) , A  { xy  yz  zx} , f  x  y  z , A  { x , xy  yz  zx} , f  x  y  z , A  { xy  yz  z x} , 13) f  x  y , A  { xy , x  y} , 14) f  x  y , A  { x  y} , 15) f  xy , A  { x  y , x  y} : 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12)

f f f f f f f f

6.7 Պարզել՝ արդյոք f  [ A] . 1) f  x  y , A  { x , x  y , x  y  z ,0,1} ,

2) 3) 4) 5)

f f f f

 x  y , A  { x , x  y  z , xy  yz  xz } ,  x  y , A  { x  y  z , x  y  z} ,  xy , A  { x  y , x  y} ,  ( 01010111 ) , A  {0,1, xy , x  y} :

6.8 Նկարագրել [ A] դասի ֆունկցիաները. 1) A  { x , xy } , 2) A  { x , x  y} , 3) A  { xy  yz  zx} , 4) A  {x  y} , 5) A  { x  y ,1} , 6) A  { x  y  z ,1} , 7) A  { x  y , xy ,1} , 8) A  { x  y , x  y} , 9) A  { x  y , x } , 10) A  { x  y , xyz } , 11) A  { x  y  z  1} , 12) A  { x  y , x  y} , 13) A  { x  y , xy} , ~

14) A  { f / f  P2 , f ( 0)  f ( 1 )} : 6.9 Գտնել n փոփոխականից կախված բուլյան ֆունկցիաների քանակը, որոնք պատկանում են հետևյալ դասերին. 1) { x1 } , 2) { x1 } , 3) { x1 & x 2 } , 4) { x1  x 2 } , 5) { x1  x 2 } ,





6) { x1  x 2 } ,

7) { x1  x 2 } ,





8) {x1  x 2 } : 6.10 Ապացուցել, որ. 1) { x1  x 2 }  { x1 & x 2 }  [{ x1 }] ,

2) [{ x1 }]  { x1  x 2 }  { x1  x 2 } ,

3) { x1 & x 2 }  [{ x1  x 2 }] ,

4) [{ x1  x 2 }]  { x1 & x 2 , x1  x 2 } :

7 ՀԱՍՏԱՏՈՒՆՆԵՐԸ ՊԱՀՊԱՆՈՂ ՖՈՒՆԿՑԻԱՆԵՐ

7.1 Ապացուցել, որ հաստատունը պահպանող ֆունկցիաների դասերը փակ են: 7.2 Պարզել՝ պատկանում են արդյոք հետևյալ ֆունկցիաները T0 \ T1 բազմությանը. 1) f ( ~ x 3 )  (x  x )  (x  x )  (x  x ) ,

2) f ( ~ x 3 )  x1 x 2 x3  x1  x 2  x1 : 7.3 Պարզել՝ որ n -երի դեպքում են հետևյալ ֆունկցիաները պատկանում T0 \ T1 բազմությանը. x n )  x  x  x , 1) f ( ~

xn)  2) f ( ~



1i  j  n

xi x j :

7.4 Ապացուցել, որ. 1) { x1 & x 2 }  T0 , 2) { x1 & x 2 }  T1 :

7.5 Ապացուցել, որ. 1) {x  y , x  y}  T0 ,

2) { xy  z  t}  T0  T1 :

8 ԻՆՔՆԱԵՐԿԱԿԻ ՖՈՒՆԿՑԻԱՆԵՐ

8.1 Ապացուցել, որ ցանկացած f բուլյան ֆունկցիայի համար ( f *)*  f : 8.2 Ապացուցել երկակիության սկզբունքը. y k )  f ( g1 ( ~ y k ),...g n ( ~ y k )) , ապա Եթե h( ~

h * (~ y k )  f * ( g1 * ( ~ y k ),...g n * ( ~ y k )) :

8.3 Ապացուցել, որ ինքնաերկակի ֆունկցիաների դասը փակ է: 8.4 Ապացուցել, որ եթե A  B  S և ապա A   B  ;

A  {1}  B  {1} ,

8.5 Օգտվելով երկակիության սկզբունքից՝ ներկայացնել f * -ը բանաձևային տեսքով, եթե f -ը ներկայացվում է՝

f (~ x 3 )  ( x1 x 2  x3 )( x 2  ( x1  x3 )) տեսքով:

8.6 Թվարկել երկու փոփոխականից կախված բոլոր ինքնաերկակի ֆունկցիաները: 8.7 Պարզել՝ ինքնաերկակի են արդյոք հետևյալ ֆունկցիաները. 1) f  xy  yz  zx , 2) f  x  y  z  1 , 3) f  ( x  y  z )t  x  y  z , 4) ~ f  (1010 ) , 5) ~  (10010110 ) , f

6) ~ f  (10110101 ) , 7) ~  (1100100101 101100 ) : f

8.8 * -ները փոխարինել 0-ներով կամ 1-երով այնպես, որ ստացվի ինքնաերկակի ֆունկցիայի իսկության վեկտոր. 1) (* 01*) , 2) (* * 01 * *11) , 3) (* 1 * 1 * 0 * 1) , 4) (1001 * * * *1111 * * * *) , 5) (* * * * * * 01 * *101100 ) : 8.9 Փոփոխականների փոխարեն տեղադրելով x կամ x ՝ հետևյալ ֆունկցիաներից ստանալ հաստատուն ֆունկցիա. 1) ~ f  (10110110 ) , 2) ~  (11011000 ) , f

3) ~ f  (11001110 ) , 4) ~ f  (1000110100 0101100 ) :

x ) ֆունկցիան ինքնաերկակի է, 8.10 Ապացուցել, որ եթե f ( ~ ապա նրա 1-երի կետերի քանակը՝ |Nf| = 2n-1: Ճի՞շտ է արդյոք հակառակ պնդումը: n

8.11 Պարզել՝ որ n-երի դեպքում ( n  2 ) հետևյալ ֆունկցիաները կլինեն ինքնաերկակի. x n )  x  x  x , 1) f ( ~

xn)  2) f ( ~

 

1i  j  n

3) f ( ~ xn) 

1 i  j  n

xi x j , xi x j :

8.12 Ապացուցել, որ գոյություն չունի ճիշտ երկու փոփոխականից էապես կախված ինքնաերկակի ֆունկցիա: 8.13 Ապացուցել, որ xi փոփոխականը էական է ֆունկցիայի համար միայն այն դեպքում, երբ այն էական է նրա երկակի ֆունկցիայի համար: 8.14 Գտնել n փոփոխականից ինքնաերկակի ֆունկցիաների քանակը, որոնց բոլոր փոփոխականներն էական են: 8.15 Թվարկել երեք փոփոխականից կախված բոլոր ինքնաերկակի ֆունկցիաները, որոնց երեք փոփոխականներն էլ էական են: 8.16 Ապացուցել, որ { x1  x 2 }  S  [{ x1 }] :

9 ԳԾԱՅԻՆ ՖՈՒՆԿՑԻԱՆԵՐ

9.1 Ապացուցել, որ գծային ֆունկցիաների դասը փակ է: 9.2 Թվարկել երկու փոփոխականից կախված բոլոր գծային ֆունկցիաները: 9.3 Պարզել՝ գծային են արդյոք հետևյալ ֆունկցիաները. 1) f  x  y  x  y , 2) f  xy  x  y  z , 3) f  ( x  y )  ( y  x)) ~ z , 4) ~  (1001) , f

5) ~ f  (1101) , 6) ~  (10110101 ) , f

7) ~ f  ( 0110100101 101001 ) : 9.4 * -ները փոխարինել 0-ներով կամ 1-երով այնպես, որ ստացվի գծային ֆունկցիայի իսկության վեկտոր. 1) (10 * 1) , 2) (* 0 * 1 * *00 ) , 3) (1 * *11 * 0*) , 4) (* 1 * * * * * *00 * 1 * 1 * *) , 5) (1 * * * * * * * * * *0 * 110 ) : 9.5 Ապացուցել, որ եթե f ( x1 , x2 ..., xn ) ֆունկցիան ցանկացած երկու հարևան վեկտորների վրա ընդունում է հակադիր արժեքներ, ապա այն գծային է: Ճի՞շտ է արդյոք հակառակ պնդումը:

9.6 Ապացուցել, որ եթե f ( x1 , x2 ..., xn ) գծային ֆունկցիան հաստատունից տարբեր է, ապա նրա 1-երի կետերի քանակը՝ |Nf| = 2n-1: Ճի՞շտ է արդյոք հակառակ պնդումը: 9.7 Փոփոխականների փոխարեն տեղադրելով {0, 1, x, y} բազմության ֆունկցիաներ` հետևյալ ֆունկցիաներից ստանալ

x & y, x & y, x & y ֆունկցիաներից որևէ մեկը. 1) ~ f  (01100111 ) , 2) ~  (11010101 ) , f

3) f ( ~ x 3 )  x1  x 2  x 2  x3  x3  x1 , 4) ~ f  (1101111111 001111 ) :

x n ) -ը գծային ֆունկցիա է, այնպի9.8 Ապացուցել, որ, եթե f ( ~

x n )  T1 , ապա նրա 1-երի կետերի քասին որ f ( ~ x n )  T0 և f ( ~

նակը՝ |Nf| = 2n-1: 9.9 Գտնել f ( ~ x n ) գծային ֆունկցիաների քանակը, որոնք. 1) ներկայացվում են ճիշտ k փոփոխականներով, ~ ~ 2) բավարարում են f ( 0 )  f ( 1 )  1 պայմանին:

x ) ֆունկցիաների քանակը, որոնք 9.10 Գտնել բոլոր այն f ( ~ գծային չեն, և որոնց 1-երի կետերի քանակը՝ |Nf| = 2n-1: Դրանցից քանի՞սն են ինքնաերկակի: n

9.11 Ապացուցել, որ { x1  x 2 }  L : 9.12 Ապացուցել, որ { x1 & x 2 }  L  [{ x1 }] :

10 ՄՈՆՈՏՈՆ ՖՈՒՆԿՑԻԱՆԵՐ

x ) -ը մոնոտոն չէ, ապա գոյու10.1 Ապացուցել, որ եթե f ( ~ ~n n ~ թյուն ունեն  ,  հարևան վեկտորներ, այնպիսիք, որ ~ ~ ~ n   n , բայց f (~ n )  f (  n ) : n

10.2 Ապացուցել, որ մոնոտոն ֆունկցիաների դասը փակ է: 10.3 Թվարկել երկու փոփոխականից կախված բոլոր մոնոտոն ֆունկցիաները: 10.4 Պարզել՝ մոնոտոն են արդյոք հետևյալ ֆունկցիաները. 1) f  ( x  y )  ( x ~ y ) , 2) f  xy  xz  zy , 3) f  x1  ( x 2  x 3 ) , 4) f  x1  ( x 2  x 3 )  x 4 , x 3)  x x x  x  x , 5) f ( ~ 1 2 3

x 3 )  x1  x 2  , 6) f ( ~ 7) f ( ~ x 4 )  x1 x3  x 2 x 4 ,

8) f ( ~ x 5 )  x1 x3  x 2 x 4 , 9) ~  ( 0110 ) , f

10) ~ f  (10110111 ) , 11) ~ f  ( 00010111 ) , 12) ~  ( 0010001101 11111 ) : f

10.5 Պարզել, ո՞ր n-երի դեպքում ( n  2 ) հետևյալ ֆունկցիաները կլինեն մոնոտոն. x n )  x  x  x , 1) f ( ~

2) f ( ~ xn) 



1i  j  n

xi x j :

10.6 Ապացուցել, որ { x1 & x 2 }  M : 10.7 Ապացուցել, որ { x1 & x 2 , x1  x 2 }  M : Ապացուցել, որ հաստատունից տարբեր f ֆունկցիայի մոնոտոնության համար անհրաժեշտ է և բավարար, որ այն ներկայացվի միայն կոնյունկցիա և դիզյունկցիա պարունակող բանաձևով: 10.8 Ապացուցել, որ եթե f  M , ապա f *  M : 10.9 Ապացուցել, որ ցանկացած մոնոտոն ֆունկցիա կարելի է ներկայացնել հետևյալ տեսքով.

f ( x1 , x2 ,..., xn )  xi f ( x1 ,..., xi 1 ,1, xi 1 ,  , xn )   f ( x1 ,..., x i 1 ,0, x i 1 ,  , x n ) , որտեղ 1  i  n :

10.10 Ապացուցել, որ մոնոտոն ֆունկցիաների քանակը [n / 2]

փոքր չէ

2 Cn

-ից:

10.11 Ցույց տալ, որ T0, T1, L, S, M դասերից ոչ մեկը ընկած չէ մյուսում: 10.12 Ցույց տալ, որ T0, T1, L, S, M դասերը իրարից տարբեր են և տարբեր են ամբողջ P2 -ից: 10.13 Ցույց տալ, որ T0, T1, L, S, M դասերից յուրաքանչյուրը պարունակում է ֆունկցիա, որի բոլոր փոփոխականներն էական են:

10.14 Պարզել՝ արդյոք T0, T1, L, S, M դասերից յուրաքանչյուրը պարունակում է ֆունկցիա, որի բոլոր փոփոխականները կեղծ են: 10.15 Պարզել՝ գոյություն ունի արդյոք բուլյան ֆունկցիա, որ f  T0 , f  T1 , f  L, f  S , f  M , որտեղ  -ը կարող է ընդունել կամայական արժեք {,} բազմությունից (օրինակ՝ պարզել՝ գոյություն ունի արդյոք f բուլյան ֆունկցիա, որ.

f  T0 , f  T1 , f  L, f  S , f  M ): 10.16 Գտնել n փոփոխականներից կախված բուլյան ֆունկցիաների քանակը, որոնք պատկանում են A բազմությանը. A  T0 \ T1 ,

1) 2)

A  T0  T1 ,

A  T0  T1 ,

4) 5) 6) 7) 8) 9)

A  T0  S , A  T1  S ,

10) 11) 12) 13) 14)

A  L  S  T0  T1 ,

A  L  S  T0 , A  ( L \ T0 )  S ,

A  ( L \ T0 )  S , A LM ,

A  L \ (S  M ) ,

A  S  T0  T1 ,

15)

A  T0  L ,

16) 17)

A  T0  T1  L  S  M ,

18)

A  T0  T1  L  S  M :

A  T1  L , A LS ,

A  ( L  (T1S )) \ M ,

11 ԼՐԻՎ ԵՎ ՆԱԽԱԼՐԻՎ ԴԱՍԵՐ: ԲԱԶԻՍ

11.1 Գտնել երկու փոփոխականից բոլոր այն ֆունկցիաները, որոնք առանձին վերցրած կազմում են լրիվ դաս: 11.2 Բերել լրիվ դասի օրինակ, որը կազմված է. 1) մեկ երեք փոփոխականի ֆունկցիայից, 2) մեկ n փոփոխականի ֆունկցիայից ( n  2 ): n 11.3 Դիցուք, A  P2 , ընդ որում՝ A  2 2

1

: Ապացուցել, որ

[ A]  P : n

11.4 Պարզել՝ լրիվ է արդյոք A դասը. 1) A  { f1  (0110), f 2  (11000011), f 3  (10010110)} , 2) A  { f1  (0111), f 2  (01011010), f 3  (01111110)} , 3) A  { x , x  y ,0} , 4) A  { x , x  y ,1} , 5) A  { x , x  y , xy} , 6) A  { x  y , x  y ,0} , 7) A  { x , xy  yz  zx} , 8) A  { x y  yz  zx } , 9) A  { xy , x  y , x  y , xy  yz  zx} , 10) A  { x , x  y  z} , 11) A  {xy, x  y, x  y  z  1} , 12) A  {( x  y )  z} , 13) A  {( x  y)  z} :

11.5 Պարզել՝ լրիվ է արդյոք A դասը. 1) A  ( S  M )  ( L \ M ) , 2) A  ( L  T1  T0 )  ( S \ (T1  T0 )) , 3) A  ( L  T1 )  ( S  M ) , 4) A  ( L  T1 )  ( S \ T0 ) , 5) A  ( M \ T0 )  ( L \ S ) , 6) A  ( M \ T0 )  ( S \ L) ,

7) A  ( L  M )  ( S \ T0 ) , 8) A  ((L  M ) \ T1 ))  (T1  S ) ,

9) A  ( M \ S )  ( L  S ) ,

10) A  ( M  S )  (T0 \ M )  (T1  S ) :

11.6 Պարզել, լրի՞վ է արդյոք A  { f1 , f 2 } դասը. 1) f1  S \ M , f 2  L  S , f1  f 2  1 , 2) f1  L  T0  T1 , f 2  M  L , f1  f 2  1 , 3) f1  L  T0 , f 2  S , f1  f 2  1 , 4) f1  ( S  L ) \ T0 , f 2  M \ (T1  L) , f1  f 2  1 : 11.7 Ապացուցել, որ եթե A  { f 1 , f 2 ,..., f k } դասը լրիվ է, ա*

պա լրիվ է նաև A*  { f 1* , f 2* ,..., f k* } դասը, որտեղ f i -ը f i -ի երկակի ֆունկցիան է (i  1, k ) : 11.8 Ստուգել՝ արդյոք A դասը բազիս է P2 -ի համար. 1) A  { x  y , x  y , x  y} , 2) A  {0,1, x  y , x  y  z} , 3) A  { x  y  1, x  y  yz } ,

4) A  { xy  z , xy  z , xy  z} , 5) A  { x  y  z , x  y  z  1, xy  xz  yz , x } , 6) A  { x  y  z , xy  xz  yz ,0,1} , 7) A  { x  y , x  yz } , 8) A  {0,1, x  y , xy  yz  zt } : 11.9 [ A] լրիվ դասից անջատել բոլոր հնարավոր բազիսները. 1) A  {0, 1, x } , 2) A  { x  y , x  y , 1} , 3) A  { x , x  y , x  y  z} , 4) A  { xy , x  y , xy  z} , 5) A  { x  y , x  y} , 6) A  { xy , xy} , 7) A  { x  y  z , x. y  y . z  z . x , x } , 8) A  { xy , xy  x . z} , 9) A  { x , x  y , x  y  z , xy  z} , 10) A  {1, x  y , x  y  z  1} : 11.10 Ցույց տալ, որ P2 -ի ցանկացած բազիս պարունակում է չորսից ոչ ավել ֆունկցիաներ: 11.11 Բերել P2 -ի բազիսների օրինակներ, որոնք կազմված են մեկ, երկու, երեք և չորս ֆունկցիաներից: 11.12 Ցույց տալ, որ [{ f }]  P2 միայն այն դեպքում, երբ

f  T0 , f  T1 , f  S :

f  P22 ֆունկցիաները, որտեղ [{ f }]  P2 : Գտնել բոլոր այն f  P2n ֆունկցիաների քանակը, n որտեղ [{ f }]  P2 :

11.13 Գտնել

բոլոր

այն

11.14 Դիցուք, f  M և f -ը էապես կախված է առնվազն երկու փոփոխականից: Ապացուցել, որ այդ դեպքում՝

[{0, f }]  P2 : Ո՞ր դեպքերում է [{ f }]  P2 : 11.15 Ապացուցել, որ P2-ում ցանկացած նախալրիվ դաս պարունակում է նույնական ֆունկցիա: 11.16 Ապացուցել, որ T0, T1, L, S, M դասերը նախալրիվ դասեր են: 11.17 Ապացուցել, որ P2-ում փակ ցանկացած դաս, որը տարբեր է P2-ից, ընկած է որևէ նախալրիվ դասի մեջ: 11.18 Ապացուցել, որ T0, T1, L, S, M դասերից տարբեր այլ նախալրիվ դասեր չկան: 11.19 Ցույց տալ, որ T0, T1, L, S, M դասերից յուրաքանչյուրը պարունակում է ֆունկցիա, որի բոլոր փոփոխականները էական են: 11.20 Պարունակու՞մ են արդյոք հետևյալ փակ դասերը ֆունկցիա, որի բոլոր փոփոխականները կեղծ են. T0, T1, L, S, M, [{ x  y}] , [{ x  y}] , [{ x  y}] :

11.21 Գոյությո՞ւն ունեն արդյոք այնպիսի f1 և f2 բուլյան ֆունկցիաներ, որոնք բավարարեն միաժամանակ հետևյալ երեք պայմաններին. 1) Գոյություն ունի նախալրիվ դաս, որը պարունակում է f1 -ը և չի պարունակում f2-ը: 2) Գոյություն ունի նախալրիվ դաս, որը չի պարունակում f1 -ը և պարունակում է f2-ը: 3) Գոյություն չունի P2-ի բազիս, որը միաժամանակ պարունակի և f1 -ը, և f2-ը:

III. ԲՈՒԼՅԱՆ ՖՈՒՆԿՑԻԱՆԵՐԻ ԻՐԱՑՈՒՄԸ

ՖՈՒՆԿՑԻՈՆԱԼ ՏԱՐՐԵՐԻ ՍԽԵՄԱՆԵՐՈՎ

Հիմնական սահմանումներ, գաղափարներ, նշանակումներ Ֆունկցիոնալ տարրերի սխեման (ՖՏՍ) բուլյան ֆունկցիաների իրացման եղանակներից է: ՖՏՍ սահմանելու համար ֆիքսվում է փոփոխականների

X  { x1 , x2 ,... xn } բազմու-

թյուն և բուլյան ֆունկցիաների որևէ լրիվ համակարգ: Կդիտարկենք,

այսպես

կոչված,

«ստանդարտ»

համակարգը՝

{&,  , } : Հետևյալ

պատկերներից

յուրաքանչյուրը

կանվանենք

ֆունկցիոնալ տարր.

a, b գագաթները կանվանենք ֆունկցիոնալ տարրի մուտքային գագաթներ, c գագաթը՝ ելքային գագաթ: Դիտարկվում են նաև առանձին n հատ գագաթներ, որոնց վերագրված են

համապատասխանաբար

x1 , x2 ,... xn փոփոխականները, և

որոնք կոչվում են մուտք – գագաթներ: ՖՏՍ-ի սահմանումը տրվում է մակածման եղանակով. 1) մուտք - գագաթների բազմությունը ՖՏՍ է, 2) եթե E -ն ՖՏՍ է, ապա ՖՏՍ է նաև այն պատկերը, որը ստացվում է E -ի ցանկացած երկու գագաթ նույնացնելով երկու մուտքերով որևէ ֆունկցիոնալ տարրի մուտքային գագաթների հետ և վերագրելով այդ ֆունկցիոնալ տարրի ելքային գագաթին

f1 & f 2 ( f1  f 2 ) ֆունկցիան, պայմանով, որ E ՖՏՍ-ի նույնացվող երկու գագաթներին վերագրված էին f1 և f 2 ֆունկցիաները, եթե E -ն ՖՏՍ է, ապա ՖՏՍ է նաև այն պատկերը, որը ստացվում է E -ի ցանկացած մեկ գագաթ նույնացնելով մեկ մուտքով ֆունկցիոնալ տարրի մուտքային գագաթի հետ և վերագրելով այդ ֆունկցիոնալ տարրի ելքային գագաթին

f ֆունկցիան,

պայմանով, որ E ՖՏՍ-ի նույնացվող գագաթին վերագրված էր f ֆունկցիան. 3) այլ ՖՏՍ-ներ չկան: Ինչպես տեսնում ենք, ՖՏՍ-ի յուրաքանչյուր գագաթին վերագրված է բուլյան ֆունկցիա: Կասենք, որ E ՖՏՍ-ն իրացնում է եթե նրա որևէ գագաթին վերագրված է

f f

բուլյան ֆունկցիան, -ը:

E ՖՏՍ-ի ֆունկցիոնալ տարրերի քանակը կոչվում է E -ի բարդություն և նշանակվում է l (E ) :

f  P2n բուլյան ֆունկցիայի բարդություն կոչվում է այդ ֆունկցիան իրացնող E f

ՖՏՍ-երից մինիմալ բարդության

ՖՏՍ-ի

բարդությունը:

Այն

նշանակվում

l( f )

l ( f )  min l ( E f ) , որտեղ min -ը վերցված է ըստ բոլոր E f Ef

ՖՏՍ-երի, որոնք իրացնում են

-ը:

P2n -ում «վատագույն»՝

ամենամեծ բարդությունն ունեցող ֆունկցիայի բարդությունն անվանում են Շենոնի ֆունկցիա: Այն նշանակվում է

L(n) .

L ( n )  max l ( f ) : f P2n

Շենոնի ֆունցիայի համար հայտնի է հետևյալ վերին գնահատականը (Շենոնի թեորեմ).

2 n 3  N ( n  N )( L ( n )  (1   )) , n ինչպես նաև հայտնի է հետևյալ ստորին գնահատականը.

 N ( n  N )( L ( n ) 

2 n 1 (1   )) : n

Նշված գնահատականները լավագույնը չեն: Հայտնի են, օրինակ, հետևյալ ստորին և վերին գնահատականները (Լուպանովի թեորեմ).

2n 2n   N ( n  N )((1   )  L ( n )  (1   ) ) : n n

12 ՖՈՒՆԿՑԻՈՆԱԼ ՏԱՐՐԵՐԻ ՍԽԵՄԱՆԵՐ (ՖՏՍ):

ՍԽԵՄԱՅԻ ԲԱՐԴՈՒԹՅՈՒՆ

12.1 Հետևյալ ֆունկցիաների համար կառուցել դրանք իրացնող ՖՏՍ-ներ, որոնց բարդությունը չի գերազանցում m-ը.

x )  x1  x2 , m  2 1) f (~

x 2 )  x1  x2 , m  4 2) f ( ~

~ 3) f ( x )  x1  x2  x2  x3  x1  x3 , m  4

x 5 )  ( x1  x2  x3 )(( x1  x2 )( x2  x4 )  ( x3  x4 )  4) f ( ~  ( x1  x2  x3  x4  x5 )) , m  6 x 3 )  (01111110) , m  6 5) f ( ~ x 3 )  (10001001) , m  6 6) f ( ~ x 3 )  (01111011) , m  6 7) f ( ~ x 3 )  (10111111) , m  3 8) f ( ~

x 3 )  (01011100) , m  5 9) f ( ~ 10) 11) 12) 13)

f (~ x 3 )  (00011111) , m  2 f (~ x 3 )  (10001101) , m  4 f (~ x 3 )  (01101001) , m  8 f (~ x 3 )  (01101000) , m  10 :

12.2 Հետևյալ ֆունկցիաների համար ստանալ լավագույն ԴՆՁ-եր և դրանց հիման վրա կառուցել այդ ֆունկցիաներն իրացնող մինիմալ ՖՏՍ-ներ.

x 2 )  ( x  y)  xy , 1) f ( ~ x 2 )  xy  ( x  y) , 2) f ( ~ x 3 )  x  ( y  z) , 3) f ( ~

x 3 )  x  ( y  z) , 4) f ( ~

x 3 )  ( x  y)  z , 5) f ( ~ x 3 )  x  ( y  z) , 6) f ( ~ x 3 )  x  ( y  z) , 7) f ( ~ x 3 )  x( y  z ) , 8) f ( ~

x 3 )  ( x  y)  z , 9) f ( ~

x 3 )  xy  z : 10) f ( ~

12.3 Հետևյալ ֆունկցիաների համար կառուցել դրանք իրացնող ՖՏՍ-ներ, որոնց բարդությունը չի գերազանցում m-ը.    ~n 1) f ( x )  x1 1 & x2 2 & ... & xn n , որտեղ

( 1 ,  2 ,...,  n )  B n , m  n , x n )  x1  x2  ...  xn , m  4(n  1) , 2) f ( ~ 3) f ( ~ x n )  x1  ( x2  ( x3  ...  ( xn 1  xn )...)), m  n , x n )  (...(( x  x )  x )  ...)  x , m  [3n / 2] , 4) f ( ~

5) f ( ~ x n )  x1  x1 x2  x1 x2 x3  ...  x1 x2 ...xn , m  [3n / 2] , 6) f ( ~ x n )  ( x  x )( x  x )...( x  x )( x  x ) ,

n 1

m  2n  1 , եթե n -ը զույգ է և m  2 , եթե n -ը կենտ է: 12.4 Հետևյալ ֆունկցիաների համար կառուցել դրանք իրացնող ՖՏՍ-ներ, կիրառելով՝ կասկադների մեթոդը.

~ 1) f ( x )  x1 x3 x4  ( x2  x3 )(x1  x4 ) ,

~ 2) f ( x )  x1 x2  x2 x3  x1 x3 ,

3) f ( ~ x 4 )  x1  x2  x3  x1 x4 ,

~ 4) f ( x )  ( x1  ( x2  x3 ))  x1x3 ,

~ 5) f ( x )  ( x1 x3  x2 x4 )(x2 x3 x4  x1x3 x4  x3 x4 ) ,

6) f ( ~ x 4 )  x1  x2  x3  x4  x1 x2  x1 x3  x1 x4 

 x2 x3  x2 x4  x3 x4 , 7) f ( ~ x n )  ( x2 k 1 )  ( x2 k ) : k

12.5 Հաշվել 1 և 2 փոփոխականներից կախված բոլոր ֆունկցիաների բարդությունները: Հաշվել L(1) և L(2) թվերը: 12.6 Կառուցել m  3 բարդության ՖՏՍ, որն իրացնում է մեկ փոփոխականից կախված բոլոր բուլյան ֆունկցիաների դասը: 12.7 Հետևյալ ֆունկցիաների դասի համար կառուցել այն իրացնող ՖՏՍ, որի բարդությունը չի գերազանցում m-ը. 1)   {x, x y, x y z, 1} , m  6 , 2)   {xy  yz  xz , x  y  z} , m  9 : 12.8 Հետևյալ ֆունկցիաների դասի համար կառուցել այն իրացնող ՖՏՍ-եր, հաշվել դրանց բարդությունը. 1)

{ xi1 & xi2 & ... & xik 1  i1  i2  ...ik  n} ,

{ xi1  xi2  ...  xik 1  i1  i2  ...ik  n} :

* n 12.9 Ապացուցել, որ եթե f -ը f  P2 ֆունկցիայի երկակի * ֆունկցիան է, ապա L( f )  L( f ) :

12.10 Ապացուցել, որ ցանկացած մոնոտոն ֆունկցիա կարելի է իրացնել ՖՏՍ -ով, որը չի պարունակում ոչ մի ժխտում:

(~ x ) գոտկային ֆունկ12.11 Ապացուցել, որ ցանկացած S ցիա կարելի է իրացնել ՖՏՍ -ով, որը պարունակում է 1-ից ոչ ավելի ժխտում: 12.12 Ապացուցել, որ ցանկացած սիմետրիկ ֆունցիա կարելի է իրացնել ՖՏՍ-ով, որը պարունակում է [n+1/2]-ից ոչ ավելի ժխտում: ( k ,m)

12.13 Ապացուցել, որ {S ( 0,0) ( ~ x 3 ), S (1,1) ( ~ x 3 ), S ( 2, 2) ( ~ x 3 ), S (3,3) ( ~ x 3 )} ֆունկցիաների դասը կարելի է իրացնել ՖՏՍ-ով, որը պարունակում է ճիշտ 2 ժխտում:

12.14 Ապացուցել, որ {x1 , x2 , x3} ֆունկցիաների դասը կարելի է իրացնել ՖՏՍ-ով, որը պարունակում է ճիշտ 2 ժխտում:

IV. ԴԻԶՅՈՒՆԿՏԻՎ ՆՈՐՄԱԼ ՁԵՎԵՐԻ

ՄԻՆԻՄԱՑՈՒՄ

Հիմնական սահմանումներ, գաղափարներ, նշանակումներ

K  xi11 & xi22 & ... & xirr

բանաձևը,

որտեղ

1  i1  i2  ...  ir  n , կոչվում է տարրական կոնյունկցիա: r թիվը կոչվում է տարրական կոնյունկցիայի երկարություն: Հաստատուն 1-ը կհամարենք 0 երկարության տարրական կոնյունկցիա:

NK  Bn

կանվանենք (n  k ) չափանի միջա-

կայք: n -չափանի միավոր խորանարդում այն գրաֆը, որի գագաթները

N K միջակայքի վեկտորներն են, կողերը՝ n -չա-

փանի միավոր խորանարդի բոլոր այն կողերը, որոնք միացնում են

-ի գագաթները, կանվանենք (n  k ) չափանի

ենթախորանարդ n -չափանի միավոր խորանարդում: D  K1  K 2  ...  K s բանաձևը, որտեղ K i  K j (i  j ) կոչ-

s թիվը կոչվում է ԴՆՁի երկարություն: s  0 դեպքում ընդունում ենք D  0 : Ակնհայտ է, որ եթե f բուլյան ֆունկցիան իրացվում է

վում է դիզյունկտիվ նորմալ ձև (ԴՆՁ):

N Ki : D ԴՆՁ-ով, ապա N f  N D   i 1

Այսինքն՝

բուլյան ֆունկցիայի՝ որևէ ԴՆՁ-ով իրացման

խնդիրը կարելի է ձևակերպել «երկրաչափորեն»՝ որպես չափանի միավոր խորանարդի վրա թյունը այնպիսի

N f գագաթների

N K1 , N K2 ,…, N Ks միջակայքերով

բազմու-

ծածկելու

խնդիր, որտեղ N Ki  N f , i  1, s . N f   N Ki : Նաև՝ հակաi 1

ռակը՝

N K1 , N K 2 ,…, N Ks միջակայքերով N f -ի ցանկացած

ծածկույթին, որտեղ տասխանեցնել

N Ki  N f , i  1, s , կարելի է համապա-

բուլյան ֆունկցիան իրացնող ԴՆՁ:

f (~ x n ) բուլյան ֆունկցիան իրացնող ԴՆՁ-երից այն ԴՆՁ-ն (ԴՆՁ-երը), որն ունի նվազագույն երկարություն կոչվում է

ֆունկցիայի կարճագույն ԴՆՁ:

f (~ x n ) բուլյան ֆունկցիան իրացնող ԴՆՁ-երից այն ԴՆՁ-ն

(ԴՆՁ-երը), որն ունի նվազագույն քանակով փոփոխականների տառեր, կոչվում է

ֆունկցիայի մինիմալ ԴՆՁ:

K1 և K 2 տարրական

կոնյունկցիաները

կոչվում

են

օրթոգոնալ, եթե K1 & K 2  0 , կամ որ նույնն է՝ N K1  N K2  :

NK միջակայքը կոչվում է թույլատրելի միջակայք f ֆունկցիայի համար, եթե N K  N f :

N K միջակայքը կոչվում է մաքսիմալ միջակայք f ֆունկցիայի համար, եթե՝ ա) այն թույլատրելի է f ֆունկցիայի համար,

բ) գոյություն չունի այնպիսի N

K

թույլատրելի միջակայք

ֆունկցիայի համար, որ N K  N

ֆունկցիայի N K մաքսիմալ միջակայքին համապա-

տասխանող

տարրակայն

K

կոնյունկցիան

կանվանենք

ֆունկցիայի պարզագույն կոնյունկցիա:

ֆունկցիայի բոլոր պարզագույն կոնյունկցիաներից

կազմված ԴՆՁ-ն կոչվում է

f եթե

ֆունկցիայի կրճատված ԴՆՁ:

ֆունկցիան իրացնող ԴՆՁ-ն կոչվում է փակուղային, նրա

բոլոր

կոնյունկցիաները

պարզագույն

են,

հնարավոր չէ դրանցից որևէ մեկը հեռացնելուց հետո ստանալ

ֆունկցիան իրացնող ԴՆՁ:

ֆունկցիայի K պարզագույն կոնյունկցիան (ինչպես

նաև նրան համապատասխանող N K մաքսիմալ միջակայքը) կոչվում է միջուկային, եթե գոյություն ունի  հավաքածու, որ s

K ( )  & Ki ( ) , որտեղ Ki -երը ( i  1, s ) l 1

-ի բոլոր մնացած

պարզագույն կոնյունկցիաներն են: Այլ կերպ ասած՝

N K մաքսիմալ

ցիայի

միջակայքը

միջուկային

ֆունկ-

է,

եթե

N K   N Ki , որտեղ N Ki -երը ( i  1, s ) f -ի բոլոր մնացած i 1 մաքսիմալ միջակայքերն են:

13 ԴՆՁ-ԵՐԻ ՄԻՆԻՄԱՑՄԱՆ ԽՆԴՐԻ ԵՐԿՐԱՉԱՓԱԿԱՆ

ՄԵԿՆԱԲԱՆՈՒՄԸ

~ n n ~ 13.1 Դիցուք,   B ,   B տրված վեկտորներ են և ~ ~  (~ ,  )  r : Ցույց տալ, որ {~ ~  B n ,  (~ , ~ )   (~ ,  )  r} բազմության վեկտորները կազմում են րանարդ:

r -չափանի

ենթախո-

13.2 Ցույց տալ, որ n -չափանի միավոր խորանարդի երկու ենթախորանարդների ոչ դատարկ հատումը ենթախորանարդ է: 13.3 Ցույց տալ, որ բազմության Bn k m , m  1, m  2,. .., m  2  1 համարներով վեկտորները կազմում են k -չափանի ենթախորանարդ միայն այն դեպքում, երբ  n  1  2k  m  lk , l  0,1,...,  : k   13.4 Գտնել n -չափանի միավոր խորանարդի՝ 1) k -չափանի ենթախորանարդների քանակը, 2) բոլոր ենթախորանարդների քանակը, 3) k -չափանի ենթախորանարդների քանակը, որոնք պարունակում են տրված ~  B n վեկտորը, 4) k -չափանի ենթախորանարդների քանակը, որոնք պարունակում են տրված l -չափանի ենթախորանարդը, 5) k -չափանի ենթախորանարդների քանակը, որոնք չեն հատվում տրված l -չափանի ենթախորանարդի հետ:

13.5 Գտնել n - չափանի միավոր խորանարդում բոլոր

S0, S1, S2, ..., Sn հաջորդականությունների քանակը, որտեղ

i -չափանի S0  S1  S2 ... Sn : Si -ն

ենթախորանարդ

( i  0, n )

13.6 Դիցուք, Si -ն n - չափանի միավոր խորանարդում i չափանի ենթախորանարդ է (i  0, n) ,

և S0  S1 S2 ... Sn :

Գտնել բոլոր այն S0 , S1, S2 , ..., Sn հաջորդականությունների քանակը, որոնք պարունակում են տրված Sr -ը: ( k .m )

( x ) գոտկային ֆունկցիայի բոլոր այն 13.7 Գտնել S մաքսիմալ միջակայքերի քանակը, որոնք պարունակում են n տվյալ ~  Bk կետը:

13.8 Ցույց տալ, որ n -չափանի միավոր խորանարդում (n  2) գոյություն ունի ցիկլ, որը պարունակում է յուրաքանչյուր գագաթ ճիշտ մեկ անգամ: 13.9 Ցույց տալ, որ n -չափանի միավոր խորանարդում գոյություն չունի կենտ երկարության ցիկլ: 13.10 n -չափանի միավոր խորանարդում երկու ենթախորանարդներ կոչվում են անհամեմատելի, եթե դրանցից ոչ մեկը մյուսի ենթաբազմությունը չէ: Ցույց տալ, որ. 1) n -չափանի միավոր խորանարդում գոյություն ունեն  n  [n / 3]  առնվազն  [ n n/ 3 ]   [ n / 3 ]  զույգ առ զույգ անհա   մեմատելի ենթախորանարդներ:

2) n -չափանի միավոր խորանարդում զույգ առ զույգ անհամեմատելի ենթախորանարդների ցանկացած բազմության հզորությունը չի գերազանցում  n  . 2 n  [ n / 3 ] -ը:  [n / 3]

13.11 Ցույց տալ, որ n -չափանի միավոր խորանարդում ~ գոյություն ունի ~ և  գագաթները միացնող համիլտոնյան ~ ճանապարհ այն և միայն այն դեպքում, երբ ~   թիվը կենտ է: 13.12 Հաշվել x1 , x2 ,…, xn փոփոխականներից բոլոր ԴՆՁ-երի քանակը: 13.13 Հաշվել x1 , x2 ,…, xn փոփոխականներից բոլոր այն ԴՆՁերի քանակը, որոնք պարունակում են կենտ քանակությամբ կոնյունկցիաներ, որոնցից յուրաքանչյուրն ունի ճիշտ երեք երկարություն և պարունակում է միայն ժխտումներով փոփոխականներ: 13.14 Հաշվել x1 , x2 ,…, xn փոփոխականներից այն ԴՆՁ-երի քանակը, որոնք պարունակում են զույգ քանակությամբ կոնյունկցիաներ, որոնցից յուրաքանչյուրն ունի ճիշտ չորս երկարություն և պարունակում է միայն առանց ժխտումների փոփոխականներ: 13.15 Հաշվել x1 , x2 ,…, xn փոփոխականներից այն ԴՆՁ-երի քանակը, որոնք պարունակում են n հատ կոնյունկցիաներ, որոնց երկարությունները զույգ առ զույգ տարբեր են: 13.16 Հաշվել x1 , x2 ,…, xn փոփոխականներից այն ԴՆՁ-երի քանակը, որոնց կոնյունկցիաներն ունեն նույն երկարությունը:

14 ԿՐՃԱՏՎԱԾ ԴՆՁ: ՓԱԿՈՒՂԱՅԻՆ ԴՆՁ-ԵՐ

14.1 Տրված A բազմության տարրական կոնյունկցիաներից յուրաքանչյուրի համար պարզել՝ արդյոք այն տրված f բուլյան ֆունկցիայի պարզագույն կոնյունկցիա է. 1) 2) 3)

A  {x1 , x3 , x1 x2 , x2 x3 },

f ( x 3 )  (00101111) A  {x1 x2 , x2 x3 , x1 x2 x3}, f ( x 3 )  (01111110) A  {x1 , x4 , x2 x3 , x1 x2 x4 }, f ( x 4 )  (1010111001011110) :

14.2 Կառուցել տրված բուլյան ֆունկցիայի կրճատված ԴՆՁն. 1) f ( x )  (0000111111110110), 2) f ( x )  (11111101111110), 3) f ( x )  (0000111101111111), 4) f ( x )  (0001101111011011),

x 4 )  (0001101111011011) : 5) f ( ~ 14.3 Ապացուցել, որ մոնոտոն ֆունկցիայի կրճատված ԴՆՁ-ն չի պարունակում փոփոխականի ժխտում: 14.4 Գտնել հետևյալ բուլյան ֆունկցիաների կրճատված ԴՆՁ-ի երկարությունը. 1) 2)

f (~ x n )  x1  x2  ...  xn

f (~ x n )  ( x1  x2  x3 )( x1  x2  x3 )  x4  ...  xn

3) 4)

f ( x )  ( x1  ...  xk )( xk 1  ...  xn ), n

f ( x n )  ( x1  ...  xk )( xk 1  ...  xn ),

f ( x n )  ( x1  ...  xn )( x1  ...  xk  xk 1  ...  xn ),

f ( x n )  ( x1  x2 )( x2  x3 )...( xn 1  xn )( xn  x1 ),

f ( x n )  ( x1  ...  xn )( x1  ...  xn ), f (~ x 2 n )  ( x1  x2 )( x3  x4 )...( x2 n 1  x2 n ) :

9) 14.5

f (~ x n )  ( x1  x2  x3 )(x1  x2  x3 )(x4  ...  xn )

S k ,m ( ~ x n ) գոտկային ֆունկցիայի համար գտնել. 1) նրա բոլոր մաքսիմալ միջակայքերի քանակը, 2) այն մաքսիմալ միջակայքերի քանակը, որոնք պարունակում են տրված ~ n  Bln (k  l  m) վեկտորը, 3) k -ի և և m -ի այն արժեքները, որոնց դեպքում նրա մաքսիմալ միջակայքերի քանակը առավելագույն հնարավորն է:

14.6 Գտնել 14.4 խնդրի ֆունկցիաների միջուկային կոնյունկցիաների քանակը: 14.7 Ապացուցել, որ մոնոտոն ֆունկցիայի ցանկացած պարզագույն կոնյունկցիա միջուկային է: 14.8 Ապացուցել, որ ֆունկցիայի պարզագույն կոնյունկցիան միջուկային է միայն այն դեպքում, երբ այն մտնում է այդ ֆունկցիայի բոլոր փակուղային ԴՆՁ-երի մեջ:

14.9 Ապացուցել, որ եթե ֆունկցիայի N K մաքսիմալ միջաs

կայքը բավարարում է N K   N Ki , որտեղ N Ki -երը ( i  1, s ) l 1

-ի միջուկային միջակայքեր են, ապա N K -ն չի մտնում ֆունկցիայի ոչ մի փակուղային ԴՆՁ-ին համապատասխանող ծածկույթի մեջ: 14.10 Հետևյալ ֆունկցիաների համար կառուցել դրանց բոլոր փակուղային ԴՆՁ-երը. 1) D  zw  yzw  xyw  xyz  xyw, 2) D  xyz  xyw  xyw  xyw  yzw , 3) D  z w  x yw  xyz  xyz  xyw : 14.11 Հետևյալ ֆունկցիաների համար կառուցել դրանց բոլոր փակուղային ԴՆՁ-երը. 1) 2) 3) 4) 5)

f (~ x 4 )  (0000111111110110) , f (~ x 4 )  (1111111101111110) , f (~ x 4 )  (1111010010011111) , f (~ x 4 )  (0000111101111111) , f (~ x 4 )  (0001101111100111) :

14.12 Գտնել հետևյալ ֆունկցիաների փակուղային ԴՆՁ-երի քանակը. x n )  x1  x2  ...  xn  1 , 1) f ( ~ 2)

f (~ x n )  ( x1  x2  x3 )( x1  x2  x3 )  x4  ...  xn

f (~ x n )  ( x1  x2  x3 )(x1  x2  x3 )(x4  ...  xn )

3) 4) f ( ~ x 4 )  (0111111111111110) ,

5) f ( x n )  ( x1  x2  x3  x4  x5  ...  xn )( x1  ...  xn ), 6) f ( x n )  ( x1  ...  xk )( xk 1  ...  xn ),

7) f ( ~ x n )  ( x1  ...  xk )( xk 1  ...  xn ) :

x n ) շղթայական ֆունկցիայի համար, 14.13 Ապացուցել, որ f ( ~ ~ ~ ~ որի համար N f  { 1 , 2 ,...,  m 1} , որտեղ  (~i , ~i 1 )  1 ,

i  1, m և  (~i ,~ j )  1 , երբ i  j , բոլոր փակուղային ԴՆՁերի քանակը՝  (m) -ը հավասար է. եթե m  3

1,

 ( m)    ( m  2)   ( m  3), եթե m  3 : 14.14 Գտնել հետևյալ ֆունկցիաների տրված կրճատված ԴՆՁ-ից այն պարզագույն կոնյունկցիաները, որոնք չեն պատկանում նրա

DT

-ին.

1) f ( x )  x1 x3  x2 x4  x1 x2  x2 x3  x1 x4  x3 x4 ,

2) f ( x 4 )  x1 x3  x3 x4  x1 x2  x2 x4  x1 x4  x2 x3  x2 x3 :

15 ՄԻՆԻՄԱԼ ԵՎ ԿԱՐՃԱԳՈՒՅՆ ԴՆՁ-ԵՐ

15.1 Ապացուցել, որ ֆունկցիայի ցանկացած մինիմալ ԴՆՁ-ի ցանկացած կոնյունկցիա պարզագույն է այդ ֆունկցիայի համար: 15.2 Ապացուցել, որ գոյություն ունի ֆունկցիայի այնպիսի կարճագույն ԴՆՁ, որի ցանկացած կոնյունկցիա պարզագույն է այդ ֆունկցիայի համար: 15.3 Ապացուցել, որ մոնոտոն ֆունկցիայի կրճատված ԴՆՁ-ն մինիմալ է: 15.4 Գտնել 14.12 խնդրի ֆունկցիաների բոլոր մինիմալ ԴՆՁերի քանակները: 15.5 Հաշվել ցիկլիկ ֆունկցիայի մինիմալ ԴՆՁ-երի քանակը: 15.6 Հաշվել շղթայական ֆունկցիայի մինիմալ ԴՆՁ-երի քանակը:

15.7 Կառուցել թյուն ունենա

f1 և f 2 ֆունկցիաներ, որոնց համար գոյուK պարզագույն կոնյունկցիա, այնպիսին, որ

S 4 ( K , Dc ( f1 ))  S 4 ( K , Dc ( f c )) , սակայն K  DM ( f1 ) և K  DM ( f 2 ) , որտեղ Dc ( f1 ) և Dc ( f1 ) համապատասխանաբար

ֆունկցիաների կրճատված ԴՆՁ-երն են,

S 4 ( K , Dc ( f1 )) և S 4 ( K , Dc ( f c )) -ը՝ K -ի 4-րդ կարգի շրջակայքերը Dc ( f1 ) և Dc ( f1 ) -ում:

ԳՐԱԿԱՆՈՒԹՅԱՆ ՑԱՆԿ

1. Տոնոյան Ռ. Ն., Դիսկրետ մաթեմատիկայի դասընթաց, ԵՊՀ հրատ., Երևան, 1999: 2. Алексеев В. Б., Алешин С. В., Буевич В. А., Кудрявцев В. Б., Подколзин А. С., А. А. Сапоженко, Яблонской С. В. Методическая разработка по курсу “Математическая логика и дискретная математика”, Саратовский университет, Саратов, 1982. 3. Алексеев В. Е., Киселева Л. Г., Смирнова Т. Г., Сборник задач по дискретной математике, электронное учебно-методическое пособие. Нижегородский университет, Нижний Новгород, 2012. 4. Андерсон Дж., Дискретная математика и комбинаторика, изд. Вильямс, Москва, Санкт-Петербург, Киев, 2004. 5. Аниськов В. В., Близнец И. В., Бородич Р. В., Дискретная математика, практическое пособие. Гомелевский государственный университет, Гомель, 2011. 6. Белоусов А. И., Ткачев С. Б., Дискретная математика, издание 3-е, “МГТУ им. Баумана”, 2004. 7. Гаврилов Г. П., Сапоженко А. А., Задачи и упражнения по дискретной математике, “Физматлит”, Москва, 2006. 8. Гиндикин С. Г., Алгебра логики в задачах, “Наука”, Москва, 1972. 9. Дехтарь М.И., “Булевы функции: лекции по дискретной математике”. 10. Ерусалимский Я. М., Дискретная математика: теория, задачи, приложения, “Вузовская книга”, Москва, 2000. 11. Ерусалимский Я. М., Уховский М. Р., Козак А. В., Задачи и упражнения по математической логике и теории множеств, часть 1-ая, “Ростовский ГУ”,Ростов-на-Дону, 1980. 12. Жданов С. А., Матросов В. Л., Стеценко В. А., Сборник задач по дискретной математике, МПГУ, Москва, 2005. 13. Киселева Л. Г., Смирнова Т. Г., Функции алгебры логики в примерах и задачах: учебно-методическое пособие, Нижегородской ГУ, Нижний Новгород, 2008. 14. Клюшин А. В., Кожухов И. Б., Олейник Т. А., Сборник задач по дискретной математике, MИЭТ, Москва, 2008.

15. Лавров И. А., Максимова Л. Л., Задачи по теории множеств, математической логике и теории алгоритмов, изд. 5-ое, Физматлит, Москва, 2004. 16. Лупанов О. Б., Кострикин И. А. (под ред.), Избранные вопросы алгебры, геометрии и дискретной математики, “МГУ им. Ломоносова”, Москва, 1992. 17. Марченков С. С., Замкнутые классы булевых функций, Физматлит, Москва, 2000. 18. Новиков Ф. А., Дискретная математика для программистов, учебник, 2-ое издание, Изд. “Питер”, Санкт-Петербург, 2007. 19. Очан Ю. С., Сборник задач и теорем по теории функций действительного переменного, “Просвещение”, Москва, 1963. 20. Плотников А. Д., Дискретная математика, Изд. “Новое знание”, Москва, 2005. 21. Порошенко Е. Н., Сборник задач по дискретной математике, учебное пособие, 2-ое издание, Новосибирский государственный технический университет, Новосибирск, 2013. 22. Столл Р.Р. “Множества. Логика. Аксиоматические теории”, “Просвещение”, Москва, 1968. 23. Таран Т. А., Мыценко Н. А., Темникова Е. Л., Сборник задач по дискретной математике, 2-ое изд., “Инрес”, Киев, 2005. 24. Хаггарти Р., Дискретная математика для программистов, “Техносфера”, Москва, 2003. 25. Шиханович Ю. А., Введение в современную математику, “Наука”, 1965. 26. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б., Функции алгебры логики и классы Поста, “Наука”, Москва, 1966. 27. Яблонский С. В., Введение в дискретную математику, изд. 4-ое, “Высшая школа”, Москва, 2003. 28. Яблонский С. В., Лупанов О. Б. (под ред.), Дискретная математика и математические вопросы кибернетики, том 1, “Наука”, Москва, 1974. 29. Gries David, Schneider Fred B., A Logical Approach to Discrete Math, Springer-Verlang, New York, 1994. 30. Grimaldi Ralph P., Discrete and Combinatorial Mathematics: An Applied Introduction, 5-th edition, Pearson Education Ltd, 2014.

31. Rosen Kenneth H., Discrete mathematics and Its Applications, 7-th edition, McGraw- Hill, 2006. 32. Wegener I., The complexity of Boolean Functions, John Wiley &Sons Ltd, Stuttgart, 1987.

ԵՐԵՎԱՆԻ ՊԵՏԱԿԱՆ ՀԱՄԱԼՍԱՐԱՆ

Հ. Ց. ՀԱԿՈԲՅԱՆ, Հ. Գ. ՄՈՎՍԵՍՅԱՆ

ԲՈՒԼՅԱՆ ՖՈՒՆԿՑԻԱՆԵՐ

ԽՆԴԻՐՆԵՐԻ ԺՈՂՈՎԱԾՈՒ

ՈՒՍՈՒՄՆԱՄԵԹՈԴԱԿԱՆ ՁԵՌՆԱՐԿ

Համակարգչային ձևավորումը՝ Կ. Չալաբյանի Կազմի ձևավորումը՝ Ա. Պատվականյանի Հրատ. սրբագրումը՝ Լ. Հովհաննիսյանի

Ստորագրված է տպագրության՝ 20.12.2017: Չափսը՝ 60x84 1/16: Տպ. մամուլը՝ 5: Տպաքանակը՝ 100: ԵՊՀ հրատարակչություն ք. Երևան, 0025, Ալեք Մանուկյան 1 www.publishing.am