Смекни!
smekni.com

Множини і відношення (стр. 2 из 12)

б) Перетином множин A і B (позначається AÇB ) називається множина, що складається з тих і тільки тих елементів, які належать множинам A і B одночасно. Тобто

AÇB = { x | xÎA і xÎB} або xÎAÇB Û

Приклад 1.4. {a,b,c}Ç{a,c,d,e} = {a,c},

{a,b,c}Ç{d,e} = Æ.

Кажуть, що множини A і Bне перетинаються, якщо AÇB = Æ.

Операції об’єднання та перетину множин можуть бути поширені на випадок довільної сукупності множин {Ai | iÎІ}. Так об’єднання множин Ai (записується Ai ) складається з тих елементів, які належать хоча б одній з множин Ai даної сукупності. А перетин множин A (записується Ai) містить тільки ті елементи, які одночасно належать кожній з множин Ai.

в). Різницею множин A і B (записується A\B ) називається множина тих елементів, які належать множині A і не належать множині B. Отже,

A \ B = { x | xÎA і xÏB} або xÎA \ B Û

Приклад 1.5. {a,b,c} \ {a,d,c} = {b},

{a,c,d,e} \ {a,b,c} = {d,e},

{a,b} \ {a,b,c,d} = Æ.

г). Симетричною різницею множин A і B (записується ADB, AÅB або A¸B ) називається множина, що складається з усіх елементів множини A, які не містяться в B, а також усіх елементів множини B, які не містяться в A. Тобто

ADB = { x | ( xÎA і xÏB ) або ( xÎB і xÏA )} або xÎADB Û

Приклад 1.6. {a,b,c}D{a,c,d,e} = {b,d,e},

{a,b}D {a,b} = Æ.

Введені теоретико-множинні операції можна проілюструвати діаграмою (рис.1.1).

Тут множини A і B - це множини точок двох кругів.

Тоді AÈB - складається з точок областей І, ІІ, ІІІ,

AÇB - це область ІІ,

A \ B - область І,

B \ A - область ІІІ,

ADB - області І і ІІІ.

Рис. 1.1.

д). У конкретній математичній теорії буває зручно вважати, що всі розглядувані множини є підмножинами деякої фіксованої множини, яку називають універсальною множиною або універсумом і позначають через E (або U). Наприклад, в елементарній алгебрі такою універсальною множиною можна вважати множину дійсних чисел R, у вищій алгебрі - множину комплексних чисел C, в арифметиці - множину цілих чисел Z, в традиційній планіметрії - множину всіх точок площини або множину всіх геометричних об’єктів, тобто множину множин точок на площині тощо.

Якщо зафіксована універсальна множина E, то доповненням множини A (яке є підмножиною універсальної множини E ) - записується - називається множина всіх елементів універсальної множини, які не належать множині A.

Тобто

= { x | xÎE і xÏA } або xÎÛxÏA.

Неважко помітити, що = E \ A.

Приклад 1.7. Якщо за універсальну множину прийняти множину N всіх натуральних чисел, то доповненням множини P всіх парних натуральних чисел буде множина всіх непарних натуральних чисел.

Зазначимо у вигляді тотожностей властивості введених вище теоретико-множинних операцій.

1. Асоціативність (AÈB) ÈC = AÈ (BÈC); (AÇBC = AÇ(BÇC).

2. Комутативність AÈB = BÈA; AÇB = BÇA.

3. Дистрибутивність AÇ(BÈC)=(AÇB)È(AÇC); AÈ(BÇC)=(AÈB)Ç(AÈC),

4. Ідемпотентність AÈA = A; AÇA = A. (1.2)

5. Інволютивність = A.

6. Правила (закони) де Моргана = Ç; = È.

Зазначимо, що правила де Моргана припускають узагальнення для сукупності множин:

; .

Наведемо ще ряд корисних теоретико-множинних тотожностей:

AÈÆ = A, AÇÆ = Æ;

AÈE = E, AÇE = A;

AÈ = E, AÇ = Æ; (1.3)

= Æ, = E.

Окремо запишемо властивості операції симетричної різниці:

ADB = (A\B) È (B\A) = (AÈB) \ (AÇB) = (AÇ) È (ÇB),

(ADB)DC = AD(BDC) (асоціативність),

ADB = BDA (комутативність) (1.4)

AÇ(BDC) = (AÇB)D(AÇC) (дистрибутивність відносно перетину),

ADA =Æ, ADE = , ADÆ = A.

Приклад 1.8. Покажемо істинність однієї з наведених тотожностей - правила де Моргана.

= Ç. (1.5)

Доведемо спочатку, що

ÍÇ. (1.6)

Нехай елемент xÎ, тоді xÎE \ (AÈB), тобто xÏA і xÏB, звідси xÎ і xÎ, отже, xÎÇ. Таким чином, має місце ÍÇ.

Доведемо обернене включення

ÇÍ. (1.7)

Припустимо xÎÇ, це означає, що xÎ і xÎ, тобто xÏA і xÏB, звідси xÏAÈB, отже xÎ. Зі справедливості обох включень (1.6) і (1.7.) випливає істинність рівності (1.5).

Аналогічно можуть бути доведені всі інші наведені теоретико-множинні тотожності. Ці тотожності дозволяють спрощувати різні складні вирази над множинами.

Приклад 1.9. Послідовно застосовуючи тотожності з (1.2) і (1.3), маємо

(AÇBÇCÇ)È(ÇC)È(ÇC)È(CÇD) = (AÇBÇCÇ)È((ÈÈDC) = = ((AÇBÇ) È ())ÇC = EÇC = C.

5. Декартів (прямий) добуток множин

Окремо розглянемо ще одну дуже важливу операцію над множинами.

Декартовим (прямим) добутком множин A і B (записується A´B) називається множина всіх пар (a,b), в яких перший компонент належить множині A (aÎA), а другий - множині B (bÎB).


Тобто

A´B = {(a,b) | aÎA і bÎB } або (a,bA´B Û

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

D = { (a1,a2,...,an) | a1ÎA1, a2ÎA2,..., anÎAn },

яка складається з усіх наборів (a1,a2,...,an), в кожному з яких i-й член, що називається i-ю координатою або i-м компонентом набору, належить множині Ai, i=1,2,...,n. Декартів добуток позначається через A1´A2´...´An.

Набір (a1,a2,...,an), щоб відрізнити його від множини, яка складається з елементів a1,a2,...,an, записують не у фігурних, а в круглих дужках і називають кортежем, вектором або впорядкованим набором. Довжиною кортежу називають кількість його координат. Два кортежі (a1,a2,...,an) і (b1,b2,...,bn) однакової довжини вважаються рівними тоді і тільки тоді, коли рівні їхні відповідні координати, тобто ai=bi, i=1,2,...,n. Отже, кортежі (a,b,c) і (a,c,b) вважаються різними, в той час як множини {a,b,c} і {a,c,b} - рівні між собою.

Декартів добуток множини A на себе n разів, тобто множину A´A´...´A називають n-м декартовим (або прямим) степенем множини A і позначають An.

Прийнято вважати, що A0 = Æ (n=0) і A1 = A (n=1).

Приклад 1.9. 1. Якщо A = {a,b} і B = {b,c,d}, то

A´B = {(a,b),(a,c),(a,d),(b,b),(b,c),(b,d)},

A2 = {(a,a),(a,b),(b,a),(b,b)}.

2. Якщо R - множина дійсних чисел або множина точок координатної прямої, то R2 - це множина пар (a,b), де a,bÎR, або множина точок координатної площини.

Координатне зображення точок площини вперше було запропоновано французьким математиком і філософом Рене Декартом, тому введена теоретико-множинна операція і називається декартовим добутком.

3. Скінченна множина A, елементами якої є символи (літери, цифри, спеціальні знаки тощо), називається алфавітом. Елементи декартового степеня A називаються словами довжини n в алфавіті A. Множина всіх слів в алфавіті A - це множина

A* = {e} ÈAÈA2ÈA3È... = {eAi,

де e - порожнє слово (слово довжини 0), тобто слово, яке не містить жодного символу алфавіту A.

Замість запису слів з An у вигляді кортежів (a1,a2,...,an) частіше використовують традиційну форму запису слів у вигляді послідовності символів a1a2...an, ajÎA, j=1,2,...,n. Наприклад, 010111, 011, 0010, 100, 010 - слова в алфавіті B = {0,1}, а 67-35, -981, (450+12)/27, 349*2+17 - це слова в алфавіті C = {0,1, 2,3,4,5,6,7,8,9,+,-,*,/,(,)}.

Операція декартового добутку неасоціативна і некомутативна, тобто множини (A´BC і A´(B´C), а також множини A´B і B´A, взагалі кажучи, нерівні між собою.

Зв’язок декартового добутку з іншими теоретико-множинними операціями встановлюється такими тотожностями:

(AÈB) ´C = (A´C) È (B´C),