Властивості операцій над множинами

Теорема 1. Для будь-яких підмножин А, В, С універсальної множини U наведені нижче рівності є тотожностями (вираз А' слід розуміти як U\А):

1) АÈ(ВÈС)=(АÈВ)ÈС, 1') АÇ(ВÇС)=(АÇВ)ÇС,

2) АÈВ=ВÈА, 2') АÇВ=ВÇА,

3) АÈ(ВÇС)=(АÈВ)Ç(АÈС), 3') АÇ(ВÈС)=(АÇВ)È(АÇС),

4) АÈÆ=А, 4') АÇU=А,

5) АÈА'= U , 5') АÇА'=Æ.

Довести тотожності можна використовуючи означення рівності множин, тобто показавши для кожної з даних рівностей, що множина ліворуч від знака «=» включається у множину праворуч від знака «=» й навпаки. Доведемо таким способом тотожність 3. Спочатку доведемо, що

АÈ(ВÇС)Í(АÈВ)Ç(АÈС). (*)

Нехай хÎАÈ(ВÇС). Тоді, згідно з визначенням операції об’єднання множин, хÎА або хÎВÇС. Розглянемо два випадки: хÎА та хÎВÇС. Якщо в кожному з них ми покажемо, що хÎ(АÈВ)Ç(АÈС), то твердження (*) буде доведено. Отже, перший випадок: хÎА. З визначення операції об’єднання множин випливає, що коли деякий об’єкт є елементом деякої множини Х, то він є елементом множини ХÈY, де Y – довільна множина. Таким чином, з хÎА випливає: хÎАÈВ та хÎАÈС. Згідно з визначенням операції перетину множин це означає, що хÎ(АÈВ)Ç(АÈС). Розглянемо другий випадок: хÎВÇС. З визначення операції Ç випливає, що хÎВ та хÎС. Але тоді та хÎАÈВ та хÎАÈС. Згідно з визначенням операції перетину множин це означає, що хÎ(АÈВ)Ç(АÈС).Отже, твердження (*) доведено.

Тепер доведемо, що

(АÈВ)Ç(АÈС)ÍАÈ(ВÇС) (**)

Нехай хÎ(АÈВ)Ç(АÈС). Згідно з визначенням операції перетину множин маємо: хÎ(АÈВ) та хÎ(АÈС). Використовуючи визначення операції об’єднання множин, маємо: хÎА або хÎВ, а разом з тим хÎА або хÎС. Отже, можливі такі випадки: а) хÎА, б) хÎА й хÎС, в) хÎВ й хÎА, г) хÎВ й хÎС. У випадках а), б) та в), оскільки хÎА, то х належить й множині, що є об’єднанням множини А з довільною множиною, отже, хÎАÈ(ВÇС). У випадку г) можна зробити висновок, що хÎВÇС, але тоді хÎАÈ(ВÇС). Таким чином, у кожному з випадків а), б), в), г) ми показали, що хÎАÈ(ВÇС), отже, включення (**) доведено й тим самим завершено доведення тотожності 3.

Інші наведені вище тотожності теж можна довести виходячи з визначення рівності множин.

Тотожності 1 та 1' називаються законами асоціативності, відповідно, для операцій об’єднання та перетину множин, тотожності 2 та 2' – законами комутативності для цих операцій, тотожності 3 та 3' – законами дистрибутивності для цих операцій.

Відповідно до закону асоціативності (тотожність 1), дві множини, котрі можна утворити за допомогою операції об’єднання з множин А, В й С, узятих у певному порядку, рівні. Домовимося позначати таку єдину множину через АÈВÈС. Закон асоціативності стверджує, що порядок розміщення дужок у цьому виразі не є суттєвим. Можна узагальнити цей результат, тобто показати, що усі множини, які можна побудувати із заданих множин А₁,А₂,…,А_n, узятих у зазначеному порядку, є рівними. Множину, яка утворюється таким способом з А₁,А₂,…,А_n, позначатимемо через А₁ÈА₂È…ÈА_n. Відповідне узагальнення можна зробити й для операції перетину. Такі загальні закони асоціативності дають змогу установити загальні закони комутативності: якщо 1',2',…,n' – це числа 1,2,…,n, узяті у довільному порядку, то

А₁ÈА₂È…ÈА_n = А_1'ÈА_2'È…ÈА_n_',

А₁ÇА₂Ç…ÇА_n = А_1'ÇА_2'Ç…ÇА_n_'.

Можна узагальнити й закони дистрибутивності:

АÈ(В₁ÇВ₂Ç…ÇВ_n)=(АÈВ₁)Ç(АÈВ₂)Ç…Ç(АÈВ_n),

АÇ(В₁ÈВ₂È…ÈВ_n)=(АÇВ₁)È(АÇВ₂)È…È(АÇВ_n).

Зауважимо, що у теоремі 1 властивості операцій над множинами зібрані попарно таким чином, що кожен член будь-якої пари утворюється з іншого члена одночасною заміною È на Ç, Æ на U. Така рівність (або вираз), що утворюється з іншої рівності (або виразу) заміною усіх входжень È на Ç, Ç на È, Æ на U та U на Æ, називається двоїстою (двоїстим) до даної (до даного).

Зазначимо, що коли твердження Q двоїсте до істинного твердження Т, що сформульовано у термінах È, Ç та ', причому для доведення твердження Т досить лише тотожностей 1-5 та 1'-5', то Q також є істинним. Дійсно, вважаючи, що Т складається з посилок (умов) та висновку, припустимо, що доведення твердження Т подано у вигляді послідовності кроків, а поруч з кожним кроком записано його обґрунтування. За припущенням кожне таке обґрунтування є однією з тотожностей 1-5, 1'-5' або умовою твердження Т. Замінимо кожну тотожність (співвідношення), що зустрічається у доведенні та обґрунтуванні, на двоїсту (двоїсте) до неї (до нього). Оскільки тотожність, двоїста до кожної з тотожностей 1-5, 1'-5', також є однією з цих тотожностей, а твердження, двоїсте до посилки твердження Т, є посилкою твердження Q, результат заміни кожного кроку обґрунтування у доведенні твердження Т може служити обґрунтуванням відповідного кроку нової послідовності, яка, таким чином, буде доведенням. Отже, останній рядок нової послідовності є висновком твердження Q, двоїстим до висновку твердження Т.

Теорема 2. Для будь-яких підмножин А й В універсальної множини U наведені нижче рівності є тотожностями (вираз А' слід розуміти як U\А):

6) Якщо для усіх А АÈВ=А, 6') Якщо для усіх А АÇВ=А,

то В=Æ, то В=U,

7) Якщо АÈВ=U та АÇВ=Æ, то В=А',

8) (А')'=А,

9) Æ'=U, 9') U'=Æ,

10) АÈА=А, 10') AÇA=A,

11) AÈU=U, 11') AÇÆ=Æ,

12) AÈ(AÇB)=A, 12') AÇ(AÈB)=A,

13) (AÈB)'=A'ÇB', 13') (AÇB)'=A'ÈB'.

Тотожності теореми 2 можна довести виходячи з визначення рівності множин, а також як наслідки тотожностей теореми 1.

Деякі з тотожностей теореми 2 мають спеціальні назви. Так, 10 та 10' – це закони ідемпотентності, 12 та 12' – закони поглинання, 13 та 13' – закони де Моргана.

Теорема 3. Для довільних множин А та В твердження

а) АÍВ,

б) АÇВ=А,

в) АÈВ=В

попарно еквівалентні.

(Зазначимо, що фраза «Твердження R₁,R₂,…,R_k попарно еквівалентні» означає, що для будь-яких i та j, i=1,…,k, j=1,…,k, R_i еквівалентне R_j, тобто з R_i випливає R_j, а з R_j випливає R_i.)

Доведення. Достатньо показати, що з а) випливає б), з б) випливає в), а з в) випливає а). Покажемо, що з а) випливає б). Нехай АÍВ. Виходячи з означення рівних множин, треба довести, що АÇВÍА та АÍАÇВ. Оскільки для будь-яких множин А та В АÇВÍА, то залишається показати, що АÍАÇВ. Нехай хÎА, але тоді хÎВ, отже, хÎАÇВ. Таким чином, АÍАÇВ.

Доведемо, що з б) випливає в). Нехай АÇВ=А. Підставивши АÇВ замість А у вираз АÈВ, а потім послідовно застосувавши закони комутативності (2), дистрибутивності (3), ідемпотентності (10), комутативності (2'), поглинання (12'), маємо:

АÈВ=(АÇВ)ÈВ=ВÈ(АÇВ)=(ВÈА)Ç(ВÈВ)=(ВÈА)ÇВ=ВÇ(ВÈА)=В.

Покажемо, що з в) випливає а). Нехай АÈВ=В. Оскільки АÍАÈВ, а АÈВ=В то АÍВ.

Тотожності 1-13 та 1'-13' дають змогу спрощувати різні складні вирази, що містять множини. Наведемо приклади.

І. (АÇВ')'ÈВ=А'È(В')'ÈВ=А'ÈВÈВ=А'ÈВ.

Для спрощення початкового виразу були послідовно застосовані: закон де Моргана (13'), тотожність 8, закон ідемпотентності (10). При перетвореннях ми також дотримувалися домовленості щодо закону асоціативності.

ІІ. (АÇВÇС)È(А'ÇВÇС)ÈВ'ÈС'=((АÈА')ÇВÇС)ÈВ'ÈС'=

=(UÇВÇС)È(ВÇС)'=(ВÇС)È(ВÇС)'=U.

У даному випадку послідовно застосовувалися: закон дистрибутивності (3') (до виразу (АÇВÇС)È(А'ÇВÇС)), тотожності 5, 4' й знов 5. При перетвореннях ми також дотримувалися домовленостей щодо законів асоціативності та комутативності.

ІІІ. (АÇВÇСÇD')È(A'ÇC)È(B'ÇC)È(CÇD)= (AÇBÇCÇD')È((A'ÈB'ÈD)ÇC)=((AÇBÇD')È(AÇBÇD')')ÇC=C.

Тут послідовно застосовано узагальнений закон дистрибутивності (до виразу (A'ÇC)È(B'ÇC)È(CÇD)), закон де Моргана (двічі) з тотожністю 8, тотожності 5 та 4'. Як і раніше, ми дотримувалися домовленостей щодо законів кому-тативності та асоціативності.

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

Кожна непорожня множина Х має принаймні дві різні підмножини: Æ та Х. Крім того, кожен елемент множини Х визначає деяку підмножину множини Х: якщо аÎХ, то {а}Í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,б,г,д} та {a,b,g,d},

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, AD(AÇB); A={1,2,3,4}, B={c,d}.

2) AÇ(B\A), (AÇB)D(BÈA); A={3,4,5}, B={5,6,7,8}.

3) (BÈC)\A, (AÇB)DC, (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, ADB, A\B, B\A; A={,¯,±,«}, B={®,:,¯,?}.

6) (АÈВ)Ç(АDВ), АD(АÈВ), (АDВ)\В; А={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₁, ADA₁; А={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, що BDC=D, й знайти B\D, (CÇD)ÈB, (C\B)ÇD.

11) (A\B)¢ÈC, (AÇC)D(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, (ADC)\B, (AÇC)¢È(B\A); U={a,b,c,d}, A={a,b}, B={b,c}, C={a,c,d}.

15) (AÇB)\C¢, (ADB)¢È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¢DC¢; U={1,2,3,4,5}, A={1,3,5}, B={2,4}, C={2,3}.

17) AÇB¢, A¢ÈC, (BÇC)\A, AD(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\(ADC¢), (AÇB)¢È(A¢ÈB¢); U={1,2,3,4,5}, A={1,3}, B={1,2,4},C={2,5}.

19) ((A\B)ÈC)¢, (ADB¢)ÇC, (AÈ(BDC))¢. U={1,2,3,4,5,6}, A={1,2,5}, B={2,4,5}, C={2,3,4,6}.

20) С\(BÇА)¢, (A¢DB)ÈC¢, (AÈB¢)DC; 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) Нехай ADB=Æ. Що можна сказати про AÇB й A\B?

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

3) Нехай AÍB¢. Що можна сказати про множини ADB та 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. Що можна сказати про ADB, BDA, (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) (XDY)\Z=Æ, X¹Æ, Y¹Æ, Z¹Æ, 8) XDY=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) ADB=C та BDC=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) АËВ й АDВ=Æ,

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¹Æ, (ADC)ÇB¹Æ, 22) АDВÍС, АÇВÍСDВ.

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=Æ Þ ADBÍ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) ADB=Æ Û A=B,

13) A\B=Æ Þ A\B¢=A, 14) AÍBÈC Û AÇB¢ÍC,

15) (A\B)ÈB=A Û A¢ÍB¢, 16) ADB=C Û BDC=A,

17) (AÈB)D(CÈD) Í (ADC)È(BDD), 18) AÍB Þ A¢ÇB¢=B¢,

19) AÇB=Æ Þ AÈB=ADB, 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) ADB=BDA,

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) ADU=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)DB,

21) A\(BÇC)=(A\B)È(A\C), 22) (A¢ÈB)ÇA=AÇB,

23) AÈB=(ADB)D(AÇB), 24) AÈ(B\A)=AÈB,

25) AÈB=(ADB)È(AÇB), 26) AÇ(B\C)=ВÇ(А\C),

27) A\B=(AÈB¢)D(ADB¢), 28) (AÇB)ÈA=A,

29) AÇ(BDC)=(AÇB)D(AÇC), 30) A\B=AD(AÇB),

31) AÈB=AD(BD(AÇB)), 32) AÇB¢=AD(B\A¢),

33) AÈB=(ADB)D(A\(A\B)), 34) (ВDА)DВ=А,

35) ADA¢=U, 36) ADA=Æ,

37) (AÈB)ÇA=(AÇB)ÈA, 38) AD(ADB)=B,

39) AÈB=(ADB)È(A\B¢), 40) AÈB=AÈ(A¢\B¢),

41) AÇB=(AÈB)D(ADB), 42) AD(BDC)=(ADB)DC,

43) (AÇB)\(AÈB)=AÇ((A¢ÈB)Ç(A¢ÈB¢)), 44) АDÆ=А,

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(BDC), P(C'ÇB), P(BÇA'), P(ADB'), P((B\C)DA'), P((A\C)D(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.