Теорема 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), дві множини, котрі можна утворити за допомогою операції об’єднання з множин А, В й С, узятих у певному порядку, рівні. Домовимося позначати таку єдину множину через А È В È С. Закон асоціативності стверджує, що порядок розміщення дужок у цьому виразі не є суттєвим. Можна узагальнити цей результат, тобто показати, що усі множини, які можна побудувати із заданих множин А 1, А 2,…, Аn, узятих у зазначеному порядку, є рівними. Множину, яка утворюється таким способом з А 1, А 2,…, Аn, позначатимемо через А 1È А 2È…È Аn. Відповідне узагальнення можна зробити й для операції перетину. Такі загальні закони асоціативності дають змогу установити загальні закони комутативності: якщо 1',2',…, n ' – це числа 1,2,…, n, узяті у довільному порядку, то
А 1È А 2È…È Аn = А 1'È А 2'È…È Аn ',
А 1Ç А 2Ç…Ç Аn = А 1'Ç А 2'Ç…Ç Аn '.
Можна узагальнити й закони дистрибутивності:
А È(В 1Ç В 2Ç…Ç Вn)=(А È В 1)Ç(А È В 2)Ç…Ç(А È Вn),
А Ç(В 1È В 2È…È Вn)=(А Ç В 1)È(А Ç В 2)È…È(А Ç В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 1, R 2,…, Rk попарно еквівалентні» означає, що для будь-яких i та j, i =1,…, k, j =1,…, k, Ri еквівалентне Rj, тобто з Ri випливає Rj, а з Rj випливає Ri.)
Доведення. Достатньо показати, що з а) випливає б), з б) випливає в), а з в) випливає а). Покажемо, що з а) випливає б). Нехай А Í В. Виходячи з означення рівних множин, треба довести, що А Ç В Í А та А Í А Ç В. Оскільки для будь-яких множин А та В А Ç В Í А, то залишається показати, що А Í А Ç В. Нехай х Î А, але тоді х Î В, отже, х Î А Ç В. Таким чином, А Í А Ç В.
Доведемо, що з б) випливає в). Нехай А Ç В = А. Підставивши А Ç В замість А у вираз А È В, а потім послідовно застосувавши закони комутативності (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 елементів.
Доведення. Нехай Х ={ х 1,…, хn }. Розглянемо такий спосіб подання підмножини Y множини Х. Нехай lY = l 1… ln – послідовність n нулів та одиниць така, що li =1, якщо хi Î Y, й li =0, якщо xi Ï Y, i Î{1,…, n }. Наприклад, якщо n =5, то підмножина Y ={ x 2, x 4, x 5} множини { х 1, х 2, х 3, х 4, х 5} подається у вигляді послідовності lY =01011. З іншого боку, кожна послідовність l 1… ln з n нулів та одиниць визначає деяку підмножину Y n-елементної множини Х таким чином: якщо li =1, то хi Î Y, а якщо li =0, то xi Ï Y. Наприклад, якщо lY =00110, то Y ={ x 3, x 4}. Отже, n-елементна множина Х має стільки ж підмножин, скільки існує послідовностей з n нулів та одиниць. Оскільки таких послідовностей 2 n, то й кількість елементів множини P(Х) теж 2 n.
Покриття та розбиття множини
Покриттям множини Х називається така сукупність Х 1,…, Хk,… підмно-жин множини Х, що Х = Х 1È…È Хk È….
Наприклад, множини Х 1={2,4}, Х 2={2,3,5}, Х 3= X 4={1,2,4} утворюють покриття множини Х ={1,2,3,4,5}, тому що Х 1Í Х, Х 2Í Х, Х 3Í Х, Х 4Í Х, а також Х = Х 1È Х 2È Х 3È Х 4. Множини Y 1={1,2}, Y 2={2,4}, Y 3={2,3}, Y 4={1,2,3} не утворюють покриття множини Х (хоча усі вони є підмножинами Х), тому що Х ≠ Y 1È Y 2È Y 3È Y 4. Множини Z 1={1,2,5,6}, Z 2={2,3,5}, Z 3={1,4} теж не утворюють покриття множини Х, оскільки не кожна з них є підмножиною множини Х (Z 1Ë Х).
Розбиттям множини Х називається множина таких непорожніх підмножин множини Х, що попарно не перетинаються й утворюють її покриття.
Наприклад, множина {{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 =2 y +1, y Î N }, 2) { x | x =2 y -1, y Î N },
3) { x | 10< x <100, x =5 y, y Î N }, 4) { x | x =2 y, y Î N },
5) { x | x = y 2, y Î N, 1£ y £10}, 6) { x | x = y 2, y Î N },
7) {(x, y, z)| x, y, z Î R, x 2+ y 2+ z 2>1}, 8) { x | 10 y +9, y Î N },
9) { x | x =2 y -1, y Î N, 1£ y £100}, 10) { x | x =2 y +1, y Î N, 1£ y £10},
11) {(x, y, z)| x, y, z Î R, x 2+ y 2+ z 2=1}, 12) { x | 1£ x £100, x Î N },
13) { x | x =3 y або x =5 z, y, z Î N }, 14) { x | x =100 y +7, y Î N, y ¹0},
15) { x | x =11 y або x =7 z, y, z Î N }, 16) { x | x =3 y +1, y Î N, 1£ y £35},
17) {(x, y)| a £ x £ b, a £ y £ b, a, b Î R }, 18) {(x, y)| x 2+ y 2>1, x, y Î R },
19) { x | x =100 y, x <1000, y Î N }, 20) { x | x = y 2, y Î N, y £3},
21) {(x, y, z)| x, y, z Î R, x 2+ y 2+ z 2<1}, 22) { x | x =5 y, y Î N },
23) { x | x Î Z, x >5 або x <0}, 24) { x | x Î Z, x ¹3 k, k Î N },
25) { x | x Î N, x ділиться на 2 й x ділиться на 5}.
ІІ. Записати множину B у явній формі.
1) A ={2,4,6}, B ={ x | x =2 y +1, y Î A }.
2) A ={1,2,3}, B ={ x | x = z 3+1, z Î A }.
3) A ={1,2,3,4}, B ={ x | x =2 y +3 z, 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 2 + z - y, z, y, y 2 Î A }.
6) A ={2,3,4}, В ={ y | y = x 2+ z, x, z Î А }.
7) A ={0,1,2}, B ={ x | x = y +2 z, 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 2+3 z +3, y 2, z Î A }.
10) A ={1,2,3,4}, B ={ x | x =2 y +3 z +1, y, z ÎA}.
11) A ={2,4,6}, B ={ x | x =3 y - z +2, y, z Î A }.
12) A ={1,2,3}, B ={ x | x = y 2+ z 2, y, z Î A }.
13) A ={1,2,3}, B ={ x | x =2 y + z -2, y, z Î A }.
14) A ={1,4,7}, B ={ x | x =5 y - z +2, y, z Î A }.
15) A ={0,1,2,3}, B ={ x | x =2 y +5 z -1, y, z Î A }.
16) A ={-1,1,-2,2,}, B ={ x | x = y 2+5 z +1, y, z Î A }.
17) A ={1,3,5,7}, B ={ x | x =2 y +3 z, 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 2+ z + y, z, y, y 2 Î A }.
20) А ={2,3,5,7}, B ={ x | x = z 2+ 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 1, a 2, a 3}, 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 =6 y для деякого цілого числа y }={ x | x Î Z, x =2 u та x =3 v для деяких цілих чисел u та v }.
2) { x | x Î R, x = y 2 для деякого дійсного числа y }={ x | x Î R, x ≥0}.
3) { x | x Î Z, x =6 y для деякого цілого числа y }Í{ x | x Î Z, x =2 y для деякого цілого числа 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. Нехай А 1, А 2,…, Аn – множини. Довести, що А 1Í А 2Í…Í Аn Í А 1 Û А 1= А 2=…= Аn.
XІ. Обчислити подані вирази при заданих значеннях U, A, B, C.
1) (A È B)Ç(A \ B), (B \ A)È A, A D(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)D 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 D B, 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 =2 y + z, y, z Î A }.
8) A Ç A 1, A \ A 1, A È A 1, A D A 1; А ={ x: x – додатне ціле число, кратне 10}, A 1={10,20,30,40,50}.
9) A È B, A Ç B, A \ B, B \ A; A ={1,2,4}, B ={ x: x =2 y - z, y, z Î A }.
10) Нехай A ={ a, b, c, d }. Побудувати такі підмножини B, C, D множини A, що B D C = 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, (A D 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 D 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 ¢D 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 D(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 D 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 D B ¢)Ç C, (A È(B D C))¢. U ={1,2,3,4,5,6}, A ={1,2,5}, B ={2,4,5}, C ={2,3,4,6}.
20) С \(B Ç А)¢, (A ¢D B)È C ¢, (A È B ¢)D 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, х =2 y для деякого додатного цілого числа y },
В ={ х | х Î Z, х =2 y -1 для деякого додатного цілого числа y },
С ={ х | х Î Z, х <10}.
Описати словами й задати неявно множини А ', (А È В)', А \ С ', С \(А È В).
XІІІ. Розглянемо такі підмножини множини цілих додатних чисел Z +:
A ={ x | x Î Z +, x =2 y для деякого цілого числа y },
B ={ x | x Î Z +, x =2 y +1 для деякого цілого числа y },
C ={ x | x Î Z +, x =3 y для деякого цілого числа y }.
Описати словами множини А Ç С, В È С, В \С.
XІV. Обчислити вирази (А – довільна множина):
А ÇÆ, А ÈÆ, А \Æ, А \ А, Æ\ А, ÆÇ{Æ}, {Æ}Ç{Æ}, {Æ,{Æ}}\Æ, {Æ,{Æ}}\{Æ}, {Æ,{Æ}}\{{Æ}}.
XV. За допомогою діаграм Венна з’ясувати, чи правильні твердження:
а) якщо А, В та С – такі підмножини множини U, що А Ç В Í С ' та А È С Í В, то А Ç С =Æ;
б) якщо А, В та С – такі підмножини множини U, що А Í(В È С)' та В Í(А È С)', то В =Æ.
XVI. Обчислити наведені вирази при заданих умовах.
1) Нехай A D B =Æ. Що можна сказати про A Ç B й A \ B?
2) Нехай A Ç B =Æ. Що можна сказати про множини A \ B та B \ A?
3) Нехай A Í B ¢. Що можна сказати про множини A D 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 D B, B D 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 D Y)\ Z =Æ, X ¹Æ, Y ¹Æ, Z ¹Æ, 8) X D 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 D B = C та B D 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) А Ë В й А 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 ¹Æ, (A D C)Ç 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 =Æ Þ A D 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 D 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 D B = C Û B D C = A,
17) (A È B)D(C È D) Í (A D C)È(B D D), 18) A Í B Þ A ¢Ç B ¢= B ¢,
19) A Ç B =Æ Þ A È B = A D 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 D B = B D 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 D 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)D B,
21) A \(B Ç C)=(A \ B)È(A \ C), 22) (A ¢È B)Ç A = A Ç B,
23) A È B =(A D B)D(A Ç B), 24) A È(B \ A)= A È B,
25) A È B =(A D B)È(A Ç B), 26) A Ç(B \ C)= В Ç(А \ C),
27) A \ B =(A È B ¢)D(A D B ¢), 28) (A Ç B)È A = A,
29) A Ç(B D C)=(A Ç B)D(A Ç C), 30) A \ B = A D(A Ç B),
31) A È B = A D(B D(A Ç B)), 32) A Ç B ¢= A D(B \ A ¢),
33) A È B =(A D B)D(A \(A \ B)), 34) (В D А)D В = А,
35) A D A ¢= U, 36) A D A =Æ,
37) (A È B)Ç A =(A Ç B)È A, 38) A D(A D B)= B,
39) A È B =(A D B)È(A \ B ¢), 40) A È B = A È(A ¢\ B ¢),
41) A Ç B =(A È B)D(A D B), 42) A D(B D C)=(A D B)D C,
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(B D C), P(C 'Ç B), P(B Ç A '), P(A D B '), 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 (Ai).
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.
