Свойства операций над множествами

1 2 3 4 5

1) идемпотентность АÈА=А

АÇА=А;

2) коммутативность АÇВ=ВÇА

АÈВ=ВÈА;

3) ассоциативность (АÇВ)ÇС=АÇ(ВÇС)

(АÈВ) ÈС=АÈ (ВÈС);

4) дистрибутивность (АÇВ) ÈС=(АÈC)Ç(BÈС)

(АÈВ)ÇС=(АÇC) È (BÇС);

5) поглощение (АÇВ) ÈА=А

(АÈВ)ÇА=А;

6) свойства нуля АÈÆ=А

АÇÆ=Æ;

7) свойства единицы AÈU=U

AÇU=A;

8) законы де Моргана АÇВ=ВÈА

АÈВ=В ÇА;

9) инволютивность A=A;

10) свойства дополнения AÈA=U

AÇA=Æ;

11) выражение разностей A\B=A ÇB

A Δ B=(AÈB)\(BÇA).

1.4.3.Декартовое произведение множеств

ПРИМЕР. Используя две цифры, 3 и 5, можно записать четыре двузначных числа: 35, 53, 33 и 55. Несмотря на то, что числа 35 и 53 записаны с помощью одних и тех же цифр, эти числа различные. В том случае, когда важен порядок следования элементов, в математике говорят об упорядоченных наборах элементов.

В рассмотренном примере мы имели дело с упорядоченными парами.

Упорядоченную пару, образованную из элементов a и b, принято записывать, используя круглые скобки: (a; b). Элемент a называют первой координатой (компонентой) пары, а элемент b – второй координатой (компонентой) пары.

Пары (а; b) и (с; d) равны в том и только том случае, когда а = с и b = d.

В упорядоченной паре (а; b) может быть, что а=b. Так, запись чисел 33 и 55 можно рассматривать как упорядоченные пары (3; 3) и (5; 5).

Упорядоченные пары можно образовывать как из элементов одного множества, так и двух множеств.

ПРИМЕР. Даны множества А ={1,2,3}, В ={3,5}. Образовать упорядоченные пары так, чтобы первая компонента принадлежала множеству А, а вторая – множеству В.

Перечислив все такие пары, получим множество: {(1; 3), (1; 5), (2; 3), (2; 5), (3;3), (3;5)}.

Видим, что имея два множества А и В, мы получили новое множество, элементами которого являются упорядоченные пары чисел. Это множество называют декартовым произведением множеств А и В.

Определение. Декартовым произведением множеств А и В называется множество С элементами которого являются все пары вида (а; b), первая компонента которых принадлежит множеству А, а вторая компонента принадлежит множеству В, то есть . Порядок в паре очень важен, в общем виде

Если А = В, то А × В называют декартовым квадратом множества А и обозначают А ².

ПРИМЕР. Найти декартово произведение множеств А и В, если:

а) А = {m, p}, B ={e, f, k}; б) A = B ={3, 5}.

РЕШЕНИЕ. а) Действуем согласно определению – образуем все пары, первая компонента которых выбирается из А, а вторая – из В: А ´ B = {(m; p); (m; f); (m; k); (p; e); (p; f);(p; k)}.

б) Декартово произведение равных множеств находят, образуя всевозможные пары из элементов данного множества: А ´ А = А ² = {(3; 3); (3; 5); (5; 3); (5; 5)}.

В дискретной математике рассматривают не только упорядоченные пары, но и упорядоченные наборы из трех, четырех и т.д. элементов.

ПРИМЕР, запись числа 367 – это упорядоченный набор из трех элементов, а запись слова «математика» – это упорядоченный набор из 10 элементов.

Определение. Упорядоченные наборы различные по длине называются кортежами. Длина кортежа – это число элементов, из которых он состоит.

В предыдущем примере (3; 6; 7) – это кортеж длины 3, (м, а, т, е, м, а, т, и, к, а) – это кортеж длины 10.

Рассматривают и декартово произведение трех, четырех и вообще n множеств.

Определение. Декартовым произведением не пустых множеств А ₁, А ₂, …, А _n называется множество всех кортежей длины n (a ₁, …, а_n), первая компонента которых принадлежит множеству А _1,вторая – множеству А ₂, …, n – я – множеству А _n, то есть (i = 1, …, n), и обозначается A ₁ × … × A _n.

Если хотя бы одно из множеств A ₁, …, A _n пустое, то декартовым произведением множеств A ₁, …, A _n будем называть пустое множество.

Если A ₁ = … = A _n = А, то A ₁ × … × A _n называют n -й декартовой степенью множества А и обозначают А ⁿ.

ПРИМЕР. Даны множества: А ₁= {2, 3}, А ₂= {3, 4, 5}, А ₃ = {6, 7}. Найти А ₁´ А ₂ ´ А ₃.

РЕШЕНИЕ. Элементами множества А ₁´ А ₂ ´ А ₃ будут кортежи длины 3 такие, что первая их компонента принадлежит множеству А _1,вторая – множеству А ₂, третья – множеству А ₃.