Булеан множини

Кожна непорожня множина Х має принаймні дві різні підмножини:  та Х. Крім того, кожен елемент множини Х визначає деяку підмножину множини Х: якщо аХ, то {а}X. Множина усіх підмножин множини Х називається булеаном, або множиною-степенем множини Х й позначається P(Х) (або В(Х)), тобто P(Х)={Y| YX}. Якщо, наприклад, А={а,b,с}, то P(А)={А,{а,b},{a,c},{b,c},{a},{b},{c},}.

Теорема 4. Нехай множина Х складається з n елементів. Тоді P(Х) містить 2ⁿ елементів.

Доведення. Нехай Х={х₁,…,х_n}. Розглянемо такий спосіб подання підмножини Y множини Х. Нехай l_Y=l₁…l_n – послідовність n нулів та одиниць така, що l_i=1, якщо х_iY, й l_i=0, якщо x_iY, i{1,…,n}. Наприклад, якщо n=5, то підмножина Y={x₂,x₄,x₅} множини {х₁,х₂,х₃,х₄,х₅} подається у вигляді послідовності l_Y=01011. З іншого боку, кожна послідовність l₁…l_n з n нулів та одиниць визначає деяку підмножину Y n-елементної множини Х таким чином: якщо l_i=1, то х_iY, а якщо l_i=0, то x_iY. Наприклад, якщо l_Y=00110, то Y={x₃,x₄}. Отже, n-елементна множина Х має стільки ж підмножин, скільки існує послідовностей з n нулів та одиниць. Оскільки таких послідовностей 2ⁿ, то й кількість елементів множини P(Х) теж 2ⁿ.

Покриття та розбиття множини

Покриттям множини Х називається така сукупність Х₁,…,Х_k,… підмно-жин множини Х, що Х=Х₁…Х_k… .

Наприклад, множини Х₁={2,4}, Х₂={2,3,5}, Х₃=X₄={1,2,4} утворюють покриття множини Х={1,2,3,4,5}, тому що Х₁Х, Х₂Х, Х₃Х, Х₄Х, а також Х=Х₁Х₂Х₃Х₄. Множини Y₁={1,2}, Y₂={2,4}, Y₃={2,3}, Y₄={1,2,3} не утворюють покриття множини Х (хоча усі вони є підмножинами Х), тому що Х≠Y₁Y₂Y₃Y₄. Множини Z₁={1,2,5,6}, Z₂={2,3,5}, Z₃={1,4} теж не утворюють покриття множини Х, оскільки не кожна з них є підмножиною множини Х (Z₁Х).

Розбиттям множини Х називається множина таких непорожніх підмножин множини Х, що попарно не перетинаються й утворюють її покриття.

Наприклад, множина {{1}, {2,3}, {4,6}, {5}} є розбиттям множини Х={1,2,3,4,5,6}. Множина {{1,4}, {2,3}, {4,6}, {1,5}} не є розбиттям множини Х, оскільки, зокрема, множини {1,4} та {4,6} перетинаються. Множина {{1,4}, {2}, {6}, {3}} також не є розбиттям множини Х, тому що сукупність {1,4}, {2}, {6}, {3} не є покриттям множини Х.

Задачі та вправи

І. Описати словами множини:

1) {x| x=2y+1, yN}, 2) {x| x=2y-1, yN},

3) {x| 10<x<100, x=5y, yN}, 4) {x| x=2y, yN},

5) {x| x=y², yN, 1y10}, 6) {x| x=y², yN},

7) {(x,y,z)| x,y,zR, x²+y²+z²>1}, 8) {x| 10y+9, yN},

9) {x| x=2y-1,yN, 1y100}, 10) {x| x=2y+1, yN, 1y10},

11) {(x,y,z)| x,y,zR, x²+y²+z²=1}, 12) {x| 1x100, xN},

13) {x| x=3y або x=5z, y,zN}, 14) {x| x=100y+7, yN, y0},

15) {x| x=11y або x=7z, y,zN}, 16) {x| x=3y+1, yN, 1y35},

17) {(x,y)| axb, ayb, a,bR}, 18) {(x,y)| x²+y²>1, x,yR},

19) {x| x=100y, x<1000, yN}, 20) {x| x=y², yN, y3},

21) {(x,y,z)| x,y,zR, x²+y²+z²<1}, 22) {x| x=5^y, yN},

23) {x| xZ, x>5 або x<0}, 24) {x| xZ, x3k, kN},

25) {x| xN, x ділиться на 2 й x ділиться на 5}.

ІІ. Записати множину B у явній формі.

1) A={2,4,6}, B={x| x=2y+1, yA}.

2) A={1,2,3}, B={x| x=z³+1, zA}.

3) A={1,2,3,4}, B={x| x=2y+3z,y,zA}.

4) A={0,1,2}, B={x| x=y-z, y,zA}.

5) A={4,8,9,15,16}, B={x| x=y² + z-y, z,y,y²  A}.

6) A={2,3,4}, В={y| y=x²+z, x,zА}.

7) A={0,1,2}, B={x| x=y+2z, y,zA}.

8) A={0,2,3}, B={x| x=2(y-z), y,zA}.

9) A={0,1,4,5,9,10}, B={x| x=y²+3z+3, y²,zA}.

10) A={1,2,3,4}, B={x| x=2y+3z+1, y,zA}.

11) A={2,4,6}, B={x| x=3y-z+2, y,zA}.

12) A={1,2,3}, B={x| x=y²+z², y,zA}.

13) A={1,2,3}, B={x| x=2y+z-2, y,zA}.

14) A={1,4,7}, B={x| x=5y-z+2, y,zA}.

15) A={0,1,2,3}, B={x| x=2y+5z-1, y,zA}.

16) A={-1,1,-2,2,}, B={x| x=y²+5z+1, y,zA}.

17) A={1,3,5,7}, B={x| x=2y+3z, y,zA}.

18) A={-3,0,1,2}, B={x| x=y-z, y,zA}.

19) A={4,8,9,15,16}, B={x| x=y²+z+y, z,y,y²  A}.

20) А={2,3,5,7}, B={x| x=z²+y-4, z=-y+3, yA}.

ІІІ. Визначити, які з наведених тверджень правильні, а які – ні. Відповіді обґрунтувати.

1) {a,b,c}, 2) {a,b,c}, 3) {a}{a,b,c},

4) {a,c}{a,b,c}, 5) {1,2}{1,2,3}, 6) 0,

7) ={0}, 8) {{}}{{{}}}, 9) {0},

10) {}{2,3,1}, 11) a{b,a,c}, 12) {{b}}{a,b,c},

13) a{a₁,a₂,a₃}, 14) {{х}}{у,х,z}, 15) {a}{b,d,ac},

16) {d,b}{b,d,ac}, 17) {{},1,2}, 18) 1{{1,2},0},

19) {a,}{a,b,c}, 20) {{0,1}}{0,1,2}.

ІV. Визначити, чи рівні множини:

1) {{x},{y},{z}} та {x,y,z}, 2) {a,b} та {{a,b}},

3) {1,2,3} та {{1,2},{1,3},{1,2,3}}, 4) {b,c,d} та {d,{b,c}},

5) {x,y,z} та {{x,y,z}}, 6) {a,b,{a,b}} та {x,y,{x,y}},

7) {a,c,e,f} та {a,b,e,f}, 8) {a,б,г,д} та {,,,},

9) {{a,b},{b,c,d}} та {{a,c},{b,d,a}}, 10) {x,y,z} та {ікс, ігрек, зет},

11) {1,{2,},{3}} та {1,{2},{3},}, 12) {a,b,{a,b}} та {x,y,{x,y}},

13) {a,b,c} та {{a,b},{a,c},{b,c}}, 14) {{a,b},a,{a,c}} та {a,b,c},

15) {{1,3},3,4} та {{3,4},1,3}, 16) {1,2,{ }} та {1,2},

17) {{a,b},{b,c,d}} та {{a,c},{b,d,a}}, 18) {a,c,e,f} та {a,b,e,f}.

V. Довести твердження.

1) {x| xZ, x=6y для деякого цілого числа y}={x| xZ, x=2u та x=3v для деяких цілих чисел u та v}.

2) {x| xR, x=y² для деякого дійсного числа y}={x| xR, x≥0}.

3) {x| xZ, x=6y для деякого цілого числа y}{x| xZ, x=2y для деякого цілого числа y}.

VI. Довести, що для довільних множин А,В,С істинні такі твердження.

1) АВ, ВС  АС, 2) АВ, ВС  АС, 3) АВ, ВС  АС.

VII. Які з поданих тверджень правильні для будь-яких множин А, В, С?

1) AB й BC  AC, 2) AB, BC  AC,

3) AB, BC  AC, 4) AB, BC  AC,

5) AB, BC  AC, 6) AB, BC  AC.

VIII. Навести приклади таких множин Х, для яких кожен елемент множини Х є підмножиною множини Х.

IX. Чи можна побудувати:

1) 4 різні підмножини множини {*,?,!}, що складаються з двох елементів?

2) 6 різних підмножин множини {a,b,c}?

3) 2 підмножини множини {,{}}, що не містять спільних елементів? Відпові-ді обгрунтуйте.

X. Нехай А₁,А₂,…,А_n – множини. Довести, що А₁А₂…А_nА₁  А₁=А₂=…=А_n.

XІ. Обчислити подані вирази при заданих значеннях U, A, B, C.

1) (AB)(A\B), (B\A)A, A(AB); A={1,2,3,4}, B={c,d}.

2) A(B\A), (AB)(BA); A={3,4,5}, B={5,6,7,8}.

3) (BC)\A, (AB)C, (C\B)A; A={1,2,3,4,5}, B={2,3,4}, C={1,3,5}.

4) (АВ)\С, (АВ)С, (А\В)(СА); А={a,b,c,d}, В={b,c,f},С={a,c,e,f}.

5) AB, AB, AB, A\B, B\A; A={,,,}, B={,:,,?}.

6) (АВ)(АВ), А(АВ), (АВ)\В; А={1,2,3}, В={5,6,7}.

7) AB, AB, A\B, B\A; A={1,2,3}, B={x: x=2y+z, y,zA}.

8) AA₁, A\A₁, AA₁, AA₁; А={x: x– додатне ціле число, кратне 10}, A₁={10,20,30,40,50}.

9) AB, AB, A\B, B\A; A={1,2,4}, B={x: x=2y-z, y,zA}.

10) Нехай A={a,b,c,d}. Побудувати такі підмножини B,C,D множини A, що BC=D, й знайти B\D, (CD)B, (C\B)D.

11) (A\B)C, (AC)(B\A), (AC)(C\B); U={1,2,3,4,5}, A={1,3,5}, B={2,3,4}, C={1,2,5}.

12) A, B, C, (ABC), (ABC); U={a,b,c,d,1,2,3,4}, A={a,b}, B={c,d}, C={1,2,3,4}.

13) AB, (BC)\A, (AC)B; U={a,b,c,d,e,f}, A={a,b,c}, B={c,d,f,e}, C={a,d,f}.

14) (AB)C, (AC)\B, (AC)(B\A); U={a,b,c,d}, A={a,b}, B={b,c}, C={a,c,d}.

15) (AB)\C, (AB)B, (C\B)(A\C); U={a,b,c,d,e,f}, A={b,c,d}, B={b,a,f,e}, C={c,d,e}.

16) (A\B)C, (AB)C, AC; U={1,2,3,4,5}, A={1,3,5}, B={2,4}, C={2,3}.

17) AB, AC, (BC)\A, A(B\C); U={a,b,c,d,e}, A={a,b,c}, B={c,d,e}, C={a,c,e}.

18) A(BC), B\(AC), (AB)(AB); U={1,2,3,4,5}, A={1,3}, B={1,2,4},C={2,5}.

19) ((A\B)C), (AB)C, (A(BC)). U={1,2,3,4,5,6}, A={1,2,5}, B={2,4,5}, C={2,3,4,6}.

20) С\(BА), (AB)C, (AB)C; U={1,2,3,4,5,6,9}, A={1,3,4,5}, B={2,4,6}, C={2,5,9}.

XІІ. Нехай універсальною множиною є Z й нехай

А={х| хZ, х=2y для деякого додатного цілого числа y},

В={х| хZ, х=2y-1 для деякого додатного цілого числа y},

С={х| хZ, х10}.

Описати словами й задати неявно множини А', (АВ)', А\С', С\(АВ).

XІІІ. Розглянемо такі підмножини множини цілих додатних чисел Z⁺:

A={x| xZ⁺, x=2y для деякого цілого числа y},

B={x| xZ⁺, x=2y+1 для деякого цілого числа y},

C={x| xZ⁺, x=3y для деякого цілого числа y}.

Описати словами множини АС, ВС, В\С.

XІV. Обчислити вирази (А – довільна множина):

А, А, А\, А\А, \А, {}, {}{}, {,{}}\, {,{}}\{}, {,{}}\{{}}.

XV. За допомогою діаграм Венна з’ясувати, чи правильні твердження:

а) якщо А, В та С – такі підмножини множини U, що АВС' та АСВ, то АС=;

б) якщо А, В та С – такі підмножини множини U, що А(ВС)' та В(АС)', то В=.

XVI. Обчислити наведені вирази при заданих умовах.

1) Нехай AB=. Що можна сказати про AB й A\B?

2) Нехай AB=. Що можна сказати про множини A\B та B\A?

3) Нехай AB. Що можна сказати про множини AB та B\A?

4) Нехай AB=. Що можна сказати про AB й AB?

5) Нехай AC, BA. Що можна сказати про B\C й C\(AB)?

6) Нехай AB=A. Що можна сказати про AB та B\A?

7) Нехай A\B=. Що можна сказати про, AB, AB, AB,(AB) й AB?

8) Нехай AB. Що можна сказати про AB, BA, (A\B)(AB)?

XVIІ. Чи існують такі підмножини X,Y,Z множини A={a,b,c,d}, що виконуються наведені нижче умови? Відповіді обґрунтуйте.

1) (X\Y)\(Z\Y), 2) (XY)\(XZ)=,

3) (X\Z)(Y\Z), 4) (X\Y)Z=,

5) (XYZ)\(XYZ)=, 6) ХY=, а Х\(Х\Y),

7) (XY)\Z=, X, Y, Z, 8) XY=Z, XY=Z,

9) X\Y=Z, ZY=, 10) (XY)\Z=Z.

XVIII. Чи існують такі множини A,B,C, що задовольняють задані сукупності умов? Відповіді обґрунтуйте.

1) ABC=U, A=BC й C=AB, 2) ABA й AB,

3) (CA)(AB)=, а A(BC), 4) AB й ACBC,

5) ABC, ACB, AC=, 6) АВ, ВС, АС,

7) A(BC), B  (AC) й B, 8) AB й (C\B)(C\A),

9) A\C=, B\C=, а (AB)\C, 10) AB=C та BC=A,

11) A(BC)=, a (AB)C, 12) А=В й АВ,

13) AB, AC=, (AB)\C=, 14) (A\B)\C=, a A\(B\C),

15) AB, BC=, AC, 16) АВ й АВ=,

17) ABC=U, A=BC й C=AB, 18) АВ, В≠С, АС,

19) AB=, AC, (AC)\B=, 20) АВ=, В\С=, АС,

21) AB=, A\C, (AC)B, 22) АВС, АВСВ.

XІX. Довести тотожності теореми 1.

XX. Довести тотожності теореми 2, виходячи з визначення рівності множин. Спробуйте одержати ті самі результати інакше, користуючись тільки теоремою 1. Принаймні для одного такого доведення випишіть співвідношення, двоїсті до кожного його кроку з метою одержати доведення двоїстого твердження.

XXІ. Довести, що для будь-яких множин А,В,С

1) AB  ACBC, 2) AB  (A\C)(B\C),

3) AB  (C\B)(C\A), 4) AB  (B\A)A=B,

5) AB=AB  A=B, 6) ABC  A\BC,

7) АВ=А= та В=, 8) AB=  ABAB,

9) CB  B\AC\A, 10) ABC  ABC,

11) ABC й ACB  AC=, 12) AB=  A=B,

13) A\B=  A\B=A, 14) ABC  ABC,

15) (A\B)B=A  AB, 16) AB=C  BC=A,

17) (AB)(CD)  (AC)(BD), 18) AB  AB=B,

19) AB=  AB=AB, 20) BA  (A\B)B=A,

21) (AB)C=A(BC)  CA, 22) AB=A  AB=U,

23) A=B  AB= й AB=U, 24) A\B=  AB=U,

25) ACB  ACB, 26) AB  (A\C)(B\C),

27) A=B A\B=, 28) A=B  AB=U,

29) AB=B  AB=U, 30) AB=A  A\B=.

XXІІ. Нехай АВС=U, А,В,С попарно не перетинаються. Довести, що А=ВС, В=АС, С=АВ.

XXIII. Довести тотожності:

1) (AB)=(AB)(AB)(AB), 2) AB=A\(A\B),

3) (AB)\C=(A\C)(B\C), 4) AB=BA,

5) (AB)\C=(AB)\(AC), 6) (AB)(AB)=A,

7) (AB)(AB)=(AB)(AB), 8) (AB)A=A,

9) A\(B\C)=(A\B)(A\C), 10) (AB)(AB)=U,

11) A\(BC) = (A\B)(A\C), 12) AU=A,

13) A(B\C)=(AB)\(A\C), 14) A(B\C)=(AB)\C,

15) A\(BC)=(A\C)\(B\C), 16) A(B\A)= ,

17) (AB)A=AB, 18) (AB)(AB)=A,

19) (AB)(AB)=, 20) A\B=(AB)B,

21) A\(BC)=(A\B)(A\C), 22) (AB)A=AB,

23) AB=(AB)(AB), 24) A(B\A)=AB,

25) AB=(AB)(AB), 26) A(B\C)=В(А\C),

27) A\B=(AB)(AB), 28) (AB)A=A,

29) A(BC)=(AB)(AC), 30) A\B=A(AB),

31) AB=A(B(AB)), 32) AB=A(B\A),

33) AB=(AB)(A\(A\B)), 34) (ВА)В=А,

35) AA=U, 36) AA=,

37) (AB)A=(AB)A, 38) A(AB)=B,

39) AB=(AB)(A\B), 40) AB=A(A\B),

41) AB=(AB)(AB), 42) A(BC)=(AB)C,

43) (AB)\(AB)=A((AB)(AB)), 44) А=А,

45) (AB)(CD)=(AC)(BC)(AD)(BD).

XXІV. Побудувати усі підмножини множини:

1) {C,T,O}, 2) {+,-,,/},

3) {x,xy}, 4) {a,A},

5) {x,y,{x}}, 6) {1,{1},{{1}}},

7) {{1,2}, {2,3}, {4,5}}, 8) {{0,2}, {2,4}, {4,6}},

9) {01,{0},1}, 10) {x,a,{x},{a}},

11) {X,,Y}, 12) {1,2,,{3}},

13) {0,{{}},}, 14) {{},a,ba},

15) {,{1,2},12}, 16) {,1,2},

17) {x{x}, y, z}, 18) {A,{,A},B},

19) {, XY, AB}, 20) {{x,y}, (x,y)}.

XXV. Задані множини U={1,2,3,4,5,6}, A={2,5,6}, B={1,3,4,5,}, C={1,2,4,6}. Побудувати P(AC), P((A\B)C'), P(BC), P(C'B), P(BA'), P(AB'), P((B\C)A'), P((A\C)(C\B)).

XXVI. Довести, що для будь-яких множин А, С

1) В(АС)={XY| XВ(А), YВ(С)}, 2) В(АС)=В(А)В(С).

XXVII. Довести, що

1) В(_iIА_i)=_iIС_і: С_iВ(А_i), 2) В(_iIА_i)=_iI B(A_i).

XXVIIІ. Знайти такі покриття множини {a,b,c,d,e,f} (принаймні два), які не є розбиттями цієї множини.

XXІX. Чи можна побудувати 10 різних покриттів множини {1,2,3}?

XXX. Знайти усі розбиття множини {1,2,3}.

XXXІ. Скільки існує розбиттів множини {1,2,3,4}?

XXXII. Побудувати покриття та розбиття множин N, Z, Q, R.