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

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

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

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

; .

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

A = A, A = ;

A E = E, AE = A;

A = E, A = ; (1.3)

= , = E.

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

AB = (A\B) (B\A) = (A B) \ (AB) = (A) (B),

(AB)C = A(BC) (асоціативність),

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

A(BC) = (AB) (AC) (дистрибутивність відносно перетину),

AA =, AE = , A = A.

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

= . (1.5)

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

. (1.6)

Нехай елемент x, тоді xE \A B), тобто xA і xB, звідси x і x, отже, x. Таким чином, має місце .

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

. (1.7)

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

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

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

(ABC)(C)(C)(CD) = (ABC)(( D) C) = = ((AB) ()) C = EC = C.

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

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

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

Тобто

AB = {(a,b) | aA і bB } або (a,b)AB

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

D = { (a1,a2,...,an) | a1A1, a2A2,..., anAn },

яка складається з усіх наборів (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 разів, тобто множину AA...A називають n-м декартовим (або прямим) степенем множини A і позначають An.

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

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

AB = {(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,bR, або множина точок координатної площини.

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

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

A* = {e} A A2 A3 ... = {e} Ai,

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

Замість запису слів з An у вигляді кортежів (a1,a2,...,an) частіше використовують традиційну форму запису слів у вигляді послідовності символів a1a2...an, ajA, 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,+,-,*,/,(,)}.

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

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

(A B) C = (AC) (BC),

(AB) C = (AC)(BC),

A (B C) =(AB) (AC), (1.8)

A (BC) =(AB)(AC).

Проекцією на i-у вісь (або i-ою проекцією) кортежу w=(a1,a2,...,an) називається i-а координата ai кортежу w, позначається Pri(w) = ai.

Проекцією кортежу w=(a1,a2,...,an) на осі з номерами i1,i2,...,ik називається кортеж (ai1,ai2,...,aik), позначається Рri1,i2,...,ik(w) = (ai1,ai2,...,aik).

Нехай V - множина кортежів однакової довжини. Проекцією множини V на i-у вісь (позначається PriV ) називається множина проекцій на i-у вісь усіх кортежів множини V:

PriV = { Pri(v) | vV }.

Аналогічно означається проекція множини V на декілька осей:

Pri1,i2,...,ikV = { Pri1,i2,...,ik(v) | vV }.

Приклад 1.10. Pri1,i2,...,ik( A1 A1 ... An ) = Ai1 Ai2 ... Aik.

Якщо V={(a,b,c),(a,c,d),(a,b,d)}, то Pr1V={a}, Pr2V={b,c}, Pr2,3V={(b,c),(c,d), (b,d)}.

6. Відповідності, функції і відображення

Відповідністю між множинами A і B називається будь-яка підмножина CAB.

Якщо (a,b)C, то кажуть, що елемент b відповідає елементу a при відповідності C.

Поняття віповідності можна проілюструвати за допомогою так званого графіка відповідності. Нехай A={1,2,3,4,5} і B={a,b,c,d}, а C = {(1,a),(1,d),(2,с), (2,d),(3,b),(5,а),(5,b)} - відповідність між A і B. Позначимо через 1,2,3,4,5 вертикальні прямі, а через a,b,c,d - горизонтальні прямі на координатній площині (рис.1.2). Тоді виділені вузли на перетині цих прямих позначають елементи відповідності C і