Об'єднанням множин називається безліч. Знаходження перетину та об'єднання числових множин

Лекція 13: Операції над безліччю. Впорядковане безліч

1. Об'єднання множин

Об'єднання множин X і Y - це безліч, що складається з усіх тих і тільки тих елементів, які належать хоча б одному з множин X або Y, тобто. належать X чи належать Y.

Об'єднання X та Y позначається через X∪Y

Формально x∈X∪Y ⇔ x∈X або x∈Y

Приклад 1. Якщо X=(1,2,3,4,5) та Y=(2,4,6,8), то

X∪Y=(1,2,3,4,5,6,7,8)

Приклад 2. Якщо X = (x: x - отл.гр.), і Y = (x: x - gib.), то

X∪Y=(x:x - або отл., або gib).

Приклад 3. Якщо X — множина точок лівого кола і Y — множина точок правого кола, то

X∪Y - заштрихована область, обмежена обома колами.

Поняття об'єднання можна поширити і на більша кількістьмножин, на систему множин. Позначимо через М = (X 1, X 2, ..., X n) сукупність n множин X 1, X 2, ..., X n, звану іноді системою множин. Об'єднання цих множин

∪X i =∪(X∈M), Х=X 1 ∪X 2 ∪...∪X n

є безліч, що складається з усіх тих і лише тих елементів, які належать хоча б одному з множин цієї системи М.

Для об'єднаних множин справедливі:

• X∪Y = Y∪X - комутативний закон
• (X∪Y)∪Z = X∪(Y∪Z) = X∪Y∪Z - асоціативний закон,

справедливість яких випливає з того, що ліва і права частини рівностей складаються з тих самих елементів.

Очевидно, що X∪∅ = X. Звідси можна бачити, що ∅ грає роль нуля в алгебрі множин.

2. Перетин множин

Перетин множин X і Y - це безліч, що складається з усіх тих і тільки тих елементів, які належать як множині X, так і множині Y.

Перетин множин позначається X∩Y.

Формально x∈X∩Y ⇔ x∈X та x∈Y

Приклад 4. X=(1,2,3,4,5) Y=(2,4,6,8) X∩Y = (2,4)

Приклад 5. Якщо Х — безліч точок лівого кола, а Y — безліч точок правого кола, то X∩Y є заштрихованою областю, що є загальною частиноюобох кіл.

Багато X і Y називаються непересічними (диз'юнктними), якщо вони не мають загальних елементів, тобто якщо X∩Y=∅.

Приклад 7. (1,2,3) та (4,5,6)

На відміну від алгебри чисел, де може бути три можливості: a

X = Y; X⊂Y; Y⊂X; X∩Y=∅ та X та Y знаходяться у загальному положенні.

Кажуть, що множини X і Y перебувають у загальному становищі, якщо виконуються три умови:

1. існує елемент множини X, що не належить Y;
2. існує елемент множини Y, що не належить X;
3. існує елемент, що належить як X, і Y.

Аналогічно об'єднанню поняття перетину можна поширити на систему множин:

∩X=∩X i =X 1 ∩X 2 ∩...∩X n

Перетин множин є безліч, елементи якого належать кожному з множин системи М.

Для перетину множин справедливі:

• X∩Y=Y∩X - комутативний закон
• (X∩Y)∩Z = X∩(Y∩Z) = X∩Y∩Z - асоціативний закон

Зауважимо також, що має місце співвідношення X∩∅=∅.

Приклад 8. A = (a, b), B = (b, c), C = (a, c).

A∩B∩C=∅, хоча A∩B=(b), B∩C=(c)

3. Різниця множин

Різниця множин визначена тільки для двох множин. Різницею множин X і Y називається безліч, що складається з усіх тих і лише тих елементів, які належать X і не належать Y.

Позначається: X\Y.

Формально: x∈X\Y ⇔ x∈X та x∉Y

Приклад 9. (див. Приклад 1) X=(1,2,3,4,5), Y=(2,4,6,8), XY=(1,3,5), YX =(6,8)

Різниця множин не має властивості комутативності.

Якщо A\B=∅, то A⊂B поставити? назад

при A∩B≠∅

4. Універсальна множина

Роль нуля в алгебрі множин грає порожня безліч. А чи немає такої множини, яка грає роль «1», тобто. задовольняє умові: X∪I = X, що означає, що перетин або «загальна частина» множини I і множини X для будь-якої множини X збігаються з цим самим безліччю. Це можливо лише в тому випадку, якщо множина I містить усі елементи, з яких може складатися множина X, так що будь-яка множина X повністю міститься в множині I.

Безліч I, що задовольняє цій умові, називається повним, або універсальним, або одиничним.

Якщо при деякому розгляді беруть участь лише підмножини деякої фіксованої множини, то це найбільше безліч вважатимемо універсальним і позначатимемо I.

Приклад 12 (Приклад 1). I - безліч цілих чисел

Приклад 13 (Приклад 2). I - безліч студ. гр.

Приклад 14 (Приклад 3). I - аркуш паперу, дошка

Універсальна множина зазвичай позначають графічно у вигляді множини точок прямокутника, а окремі множини у вигляді окремих областей усередині цього прямокутника. Зображення множин у вигляді областей у прямокутнику, що представляє універсальну множину, називається діаграмою Ейлера-Венна.

Універсальна множина має цікаву властивість, яка не має аналогії у звичайній алгебрі, а саме, для будь-якої множини X справедливе співвідношення X∪I = I.

5. Доповнення безлічі

Множина, що визначається зі співвідношення X = I \ X, називається доповненням множини X (до універсальної множини I).

На діаграмі безліч X являє собою незаштриховану область.

Формально: X = (x: x∈I та x∉X).

З визначення випливає, що X і X не мають загальних елементів. Х∩X¯=∅.

Крім того, немає елементів I, які не належали б ні X, ні X (його доповнення), так як ті елементи, які не належать X, належать X (його доповнення). Отже, Х∪X = I.

З симетрії даної формули щодо Х і X випливає не тільки те, що X є доповненням Х, але і що Х є доповненням X. Але доповнення X' є X'. Таким чином, X? = X?.

За допомогою операції доповнення представимо різницю множин:

XY = (x: x∈X і x∉Y) = (x: x∈X і x∈Y¯ ), тобто. XY = Х∩Y¯.

Порядок виконання операцій:

1. доповнення;
2. перетин;
3. об'єднання, різницю.

Для зміни порядку використовують дужки.

6. Розбиття множини

Однією з найпоширеніших операцій над множинами є операція розбиття множини на систему підмножин.

Так, система курсів цього факультету є розбиттям багатьох студентів факультету; Система груп даного курсу є розбиттям багатьох студентів курсу.

приклад. Продукція підприємства: - Вищий сорт, I, II, шлюб.

Розглянемо деяку множину M і систему множин

М = (X 1, X 2, ..., X n)

Система множин M називається розбиттям множини M, якщо вона задовольняє наступним умовам:

Будь-яка множина X з M є підмножиною множини М

∀X∈M: X⊆M;

Будь-які два множини X і Y з М є непересічними

∀X∈М, ∀Y∈M: X≠Y → X∩Y=∅.

Об'єднання всіх множин, що входять до розбиття, дає безліч M

X 1 ∪X 2 ∪...∪ X n =M.

7. Тотожності алгебри множин

За допомогою операцій об'єднання, перетину та доповнення з множин можна складати різні вирази алгебри.

Якщо алгебраїчні вирази V(X,Y,Z) і S(X,Y,Z) являють собою те саме безліч, то їх можна прирівняти один одному, отримуючи алгебраїчну тотожність виду V(X,Y,Z) = S( X, Y, Z)

1. (X∪Y)∩Z = (X∩Z)∪(Y∩Z) (аналогічне дистрибутивному закону (a+b)c=(a+c)(b+c) у звичайній алгебрі).
2. (X∩Y)∪Z = (X∪Z)∩(Y∪Z)
3. Якщо Y⊆X, то X∩Y=Y, X∪Y=X. Дійсно, всі елементи множини Y є в той же час і елементами множини X. Отже перетин цих множин, тобто загальна множин Х і Y збігається з Y. В об'єднання множин X і Y безліч Y не внесе жодного елемента, який вже не входив б у нього, будучи елементом множини Х. Отже, X∪Y збігається з X.
4. Нехай у прикладі 3 Y=X. Тоді, враховуючи, що X⊆X, X∩Х=Х, X∪Х=X. (Ідемопотентність).
5. Доведемо тотожність (X∪Y) = X¯∩Y. Припустимо, що х∈(X∪Y), тобто х∉X∪Y. Це означає, що х∉X і х∉Y, тобто і x&isinX¯ і x&isinY¯;. Отже, x∈X¯∩Y¯. Припустимо тепер, що y∈X¯∩Y¯, тобто y∈X¯ та y∈Y¯. Це означає, що y∉X та y∉Y, тобто що y∉X∪Y. Отже, y∈(X∪Y).
6. Тотожність (X∩Y) = X¯∪Y. Зазвичай тотожності 5) та 6) називаються тотожностями де-Моргана.
7. (A\B)∩C=(A∩C)\B=(A∩C)\(B∩C)
8. A\B=A\(A∩B)
9. A=(A∩B)∪(A\B)

Доповнення до заняття «операції над безліччю»

Багато елементів, що належать або A, або B, називають симетричною різницею або дизюнктивною сумою.

S = A⊕B = (A\B)∪(B\A) = (A∩B¯)∪(A∪B) = (A∪B)∩(A∩B)¯

Для симетричної різниці виконуються такі закони:

1. 1) A⊕B = B⊕A - комутативність,
2. 2) A⊕(B⊕С) = (A⊕B)⊕С — асоціативність,
3. 3) A⊕∅ = А=∅⊕A - існування нейтрального елемента,
4. 4) A ⊕А = ∅
5. 5) A∩(B⊕С) = (A∩B)⊕(А∩С) — дистрибутивність щодо перетину.

Впорядковане безліч

Упорядкованим безліччю (чи кортежем) називається послідовність елементів, тобто сукупність елементів, у якій кожен елемент займає певне місце. Самі елементи – компоненти кортежу.

Приклад 1. Безліч людей, що стоять у черзі, безліч слів у фразі, алфавіт. У всіх цих множинах місце кожного елемента є цілком певним і може бути довільно змінено.

Число елементів кортежу називається його довжиною. Позначають кортеж дужками.< >», Іноді круглими «()». А = . Кортежі довжини 2 називаються впорядкованими парами, 3 - трійками, n-ками.

Частковий випадок: кортеж довжини 1

Так, кортеж може розглядатися як точка на площині або вектор, проведений з початку координат дану точку. Тоді компоненти a1, a2 - проекції вектора на осі 1 і 2.

Пр 1 = a 1 , Пр 2 = a 2 , = a i , Пр 1 2 = - Двоелементний кортеж. Проекція кортежу на порожню множину осей - порожній кортеж.

Узагальнюючи ці поняття, розглядатимемо впорядковане n-елементне безліч дійсних чисел(a 1 , ..., a n) як точку в уявному n-мірному просторі (іноді званому гіперпростором), або як n-мірний вектор. При цьому компоненти n-елементного кортежу будемо розглядати як проекції цього кортежу на відповідні осі.

При a = a i , i=1,2,...,n

Пр i,j,...,l a = , i=1,2,...,n

= ⇔ m = n та a 1 = b 1 , b 1 = b 2 , ...

A =< , , >

Прямий твір множин

Прямим (декартовим) твором множин X і Y називається безліч, що складається з усіх і лише тих упорядкованих пар, перша компонента яких належить множині X, а друга належить множині Y.

Формально: X * Y = ( : x∈X, y∈Y)

Приклад 2. Нехай X =<1,2>, Y=<1,3,4>

Тоді X * Y = (<1,1>,<1,3>,<1,4>,<2,1>,<2,3>,<2,4>) Див. Рис. а).

Приклад 3. Нехай X та Y — відрізки речової осі. Прямий твір X*Y зображується заштрихованим прямокутником. рис. б).

Прямий твір змінюється за зміни порядку співмножників тобто.

Прямий добуток множин X 1 , X 2 , ..., X n - це безліч, що позначається X 1 * X 2 * ... * X n і складається з усіх тих і тільки тих кортежів довжини n, права компонента яких належить X 1 , друга - X 2 і т.д.

Очевидно, X*Y = ∅ ⇔ X = ∅ або Y = ∅.

Аналогічно X 1 * X 2 * ... * X n = ∅ тоді і тільки тоді, коли хоча б одна з множин X 1 X 2 ..., X n є порожнім.

Приватним випадком прямого твору є поняття ступенів (декартових) множини - прямий твір однакових множин

M s = M * M * ... * M, M 1 = M, M 0 = ∧.

Зазвичай R — безліч речових чисел, тоді R 2 =R*R — речова площина і R 3 =R*R*R — тривимірний речовий простір.

приклад. A = (a, b, c, d, e, f, g, h), B = (1,2,3, ..., 8)

Тоді A*B =(a 1 , a 2 , a 3 , ..., h7, h8) — множина, що позначає всі 64 клітини шахової дошки.

приклад. Нехай A — кінцева множина, елементами якої є символи (літери, цифри, розділові знаки тощо). Такі множини зазвичай називають алфавітами. Елементи множини a n називаються словами довжини n в алфавіті A. Безліч всіх символів в алфавіті A — це множина A * = ∪A i = A 1 ∪A 2 ∪A 3 ... . При написанні слів не прийнято користуватися ні комами, ні дужками, ні роздільниками.

СЛОВО ⇔<С,Л,О,В,О>

Теорема. Нехай a 1 , a 2 , ..., a n - кінцеві множини і | a 1 | = m 1 , | a 2 | = m 2 , ..., | Тоді потужність множини a 1 *a 2 *a 3 *...*a n дорівнює добутку потужностей a 1 , a 2 , ..., a n

|a 1 *a 2 *...*a n |=|a 1 |*|a 2 |*|a 3 |*...*|a n |= m 1 *m 2 *...*m n

Наслідок | a n | = | A | n

Проекція множини.

Операція програмування множини тісно пов'язана з операцією проектування кортежу і може застосовуватися лише до таких множин, елементами яких є кортежі однакової довжини.

Нехай M — безліч, що складається з кортежів довжини S. Тоді пролінією множини M називатимемо безліч пролинь усіх кортежів із М

приклад. Нехай М = (<1,2,3,4,5>,<2,1,3,5,5>,<3,3,3,3,3>,<3,2,3,4,3>}

тоді Пр 2 М=(2,1,3), Пр 3 M=(3), Пр 4 M=(4,5,3), Пр 24 M=(<2,4>,<1,5>,<3,3>), Пр 13 M=(<1,3>,<2,3>,<3,3>), Пр 15 M=(<1,5>,<2,5>,<1,3>), Пр 25 M = (<2,5>,<1,5>,<3,3>,<2,3>}.

Очевидно, що якщо М=Х*Y то Пр 1 М=Х, Пр 2 М=Y

і якщо Q⊆Х*Y то Пр 1 Q⊆Х і Пр 2 Q⊆Y

приклад. V=( ,,}

Пр 1 V = (a, c, d)

Пр 1 2V = ( ,,}

Пр 2 3V = ( ,}

Пр 1 3V = ( ,,}

Нехай V - множина векторів однакової довжини S.

Пр i V = (Пр i v/v∈Y), Пр i i ... i k v = (П i i ... i k v / v∈Y).

Якщо V = A 1 *A 2 *...*A n , то П i ... i k V = A i1 * A i2 * ... * A ik .

У загальному випадкуПриV - зовсім не обов'язково прямий твір: він може бути підмножиною.

Операція над множинами - це правило, в результаті виконання якого з даних множин однозначно виходить деяка нова множина.

Позначимо довільну операцію знаком *. Безліч, одержуване з цих множин А і В,записують у вигляді А*В.Отриману множину і саму операцію прийнято називати одним терміном.

Зауваження.Для основних числових операцій використовують два терміни: один означає саму операцію як дію, інший - число, що отримується після виконання дії. Наприклад, операція, що позначається +, називається додаванням, а число, отримане в результаті додавання, - сумою чисел. Аналогічно – знак операції множення, а результат а b -добуток чисел а та Ь.Тим не менш часто цю різницю не враховують і кажуть «Розглянемо суму чисел», маючи на увазі не конкретний результат, а саму операцію.

Операція перетину.Перетином множин А і В АглВ, що складається з усіх об'єктів, кожен з яких належить обом множинам Аі Уодночасно.

Іншими словами, АсВ -це безліч усіх.г, таких, що хеАі хеВ:

Операція об'єднання.Об'єднанням множин А і Вназивається безліч, що позначається А"іВ,що складається з усіх об'єктів, кожен з яких належить хоча б одній множині Аабо Ст.

Операцію об'єднання іноді позначають знаком + і називають додаванням множин.

Операції різниці.Різницею множин А і Вназивається безліч, що позначається АВ, що складається з усіх об'єктів, кожен з яких лежить у А,але не лежить Ст.

Вираз АпВчитають «Ау перетині з У», AkjB- «А в поєднанні з В», АВ – «Абез В».

Приклад 7.1.1.Нехай А = {1, 3,4, 5, 8,9}, У = {2,4, 6, 8}.

Тоді AkjB = (1,2, 3,4, 5, 6, 8, 9), AcB=( 4,8}, АВ= (1,3, 5, 9), ЯЛ = (2,6).

На основі зазначених операцій можна визначити ще дві важливі операції.

Операція доповненняНехай AQS. Тоді різниця SAназивається доповненням множини А до Sі позначається A s.

Нехай будь-яка розглянута множина є підмножиною деякої множини U.Доповнення до такої фіксованої (в контексті вирішення того чи іншого завдання) безлічі Uпозначають просто А. Також використовуються позначення СА,з А, А".

Приклад 7.1.2.Доповнення множини (1, 3,4, 5, 8, 9) до множини всіх десяткових цифр дорівнює (0, 2, 6, 7).

Доповнення множини Q до множини Rє безліч 1.

Доповнення безлічі квадратів до безлічі прямокутників є безлічю всіх прямокутників, що мають нерівні суміжні сторони.

Ми бачимо, що операції об'єднання, перетину та доповнення множин відповідають логічним операціямдиз'юнкції, кон'юнкції та заперечення.

Операція симетричної різниці.Симетричною різницею множин А і Вназивається безліч, що позначається А®В, що складається з усіх об'єктів, кожен з яких належить точно одній з множин А і В:

Неважко бачити, що симетрична різниця є об'єднання двох множин АВі ВА.Це ж саме безліч можна отримати, якщо спочатку об'єднати множини Аі В,а потім прибрати з множини загальні елементи.

Приклад 7.1.3. Нехай дані дійсні числа а Тоді маємо для відповідних числових проміжків:

Зауважимо, що оскільки відрізок [а; Ь]містить число з>а інтервал (с; d)точку зне містить, го число злежить у різниці [а; Ь]без [з; cf.А ось різницю, наприклад, (2;5), число 3 не містить, тому що воно лежить у відрізку . Маємо (2; 5) = (2; 3).

Нехай дані безлічі, що не перетинаються. Аі Ст.Оскільки п - знак операції перетину, запис А(ЬВ)некоректна. Неправильно також говорити, що у множин немає перетину. Перетин є завжди, він визначений для будь-яких множин. Те, що множини не перетинаються, означає, що їхнє перетинання порожнє (тобто, виконавши зазначену операцію, ми отримуємо порожню множину). Якщо ж множини перетинаються, значить, їх перетин не порожній. Робимо висновок:

Узагальним операції об'єднання перетину на випадок, коли множин більше двох.

Нехай дана система Домножин. Перетином множин даної системи називається безліч всіх елементів, кожен з яких лежить у всіх множинах їх До.

Об'єднанням множин даної системи називається безліч всіх елементів, кожен з яких лежить хоча б в одній множині їх До.

Нехай безлічі системи Дозанумеровані елементами якогось сімейства індексів/. Тоді будь-яка безліч з Доможна позначити А,-,де iel.Якщо сукупність кінцева, то як / використовують множину перших натуральних чисел (1,2,...,і). Загалом / може бути нескінченним.

Тоді в загальному випадку об'єднання множин Адля всіх ielпозначають (J А( , а перетин - f]A i.

Нехай сукупність Докінцева, тоді К=В цьому випадку

пишуть AyjA 2 v...KjA„і АГ4 2 (^---Г4п-

Приклад 7.1.4. Розглянемо проміжки числової прямої Л| = [-оо; 2], Л 2 = Н °; 3], Л 3 =)