5. Алгебра множеств. Основные тождества алгебры множеств

Множества вместе с определенными на них операциями образуют алгебру множеств. Последовательность выполнения операций задается с помощью формулы алгебры множеств. Например,  (ВC), (А \ В) + C – формулы алгебры множеств.

Основные тождества алгебры множеств

Для любых множеств A, B, C справедливы следующие тождества:

1. Коммутативность.

а) A  B= B  A (для объединения);

б) A  B = B  A (для пересечения).

2. Ассоциативность.

а) A  (B  C) = (A  C)  C (для объединения);

б) A  (B  C) = (A  B)  C (для пересечения).

3. Дистрибутивность.

а) A (BC) = (AB)  (AC) (для объединения относительно пересечения);

б) A(BC) = (AB)(AC) (для пересечения относительно объединения).

4. Закон де Моргана.

а) =  (дополнение к объединению есть пересечение дополнений);

б) =  (дополнение к пересечению есть объединение дополнений).

5. Идемпотентность.

а) A  A = A (для объединения);

б) A  A = A (для пересечения).

6. Поглощение.

а) A  (A  B) = A;

б) A  (A  B) = A.

7. Расщепление (склеивание).

а) (A  B)  (A  ) = A;

б) (A  B)  (A  ) = A.

8. Двойное дополнение.

= A.

9. Закон исключенного третьего.

A  = U.

10. Операции с пустым и универсальным множествами.

а) A  U = U;

б) A   = A;

в) A  U = A;

г) A   = ;

д) = U;

е) = .

11. А \ В = A  .

Чтобы доказать некоторое тождество A = B, нужно доказать следующие факты:

1. если x А, то xВ;

2. если xВ, то x А.

Построив цепочку равносильностей A  В₁ В₂  … В_n B можно установить требуемое равенство. Докажем таким образом, например, свойство дистрибутивности для объединения (тождество 3а): A (BC) = (AB)  (AC).

Пусть некоторый элемент x принадлежит левой части тождества, т.е. x A (BC), и докажем, что x принадлежит правой части, т.е. x(AB)  (AC). Для этого будем использовать основные тождества алгебры множеств и алгебры высказываний.

x A (BC)  x A  x BC x A  (xB  x C) (x A  xB) ( x A x C) x(AB)  x (AC) x(AB)  (AC)

Построенная цепочка равносильностей доказывает факты 1 и 2.

Доказательство тождеств можно проиллюстрировать с помощью диаграмм Венна.

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

Пример.

Доказать тождество (AB) \ В = A  .

Пусть некоторый элемент x принадлежит левой части тождества, т.е. x(AB) \ В. Покажем, что x принадлежит правой части, т.е. x A  .

x (AB) \ В  x (AB)   x (A )  x (B ) x (A ).

Тождество доказано.

Пример.

Доказать тождество:

A \ (В \ C) = (A \ В)  (A  C).

Множества, стоящие в левой и правой частях тождества, изобразим с помощью диаграмм Эйлера – Венна (рис. 1.2).

Рисунок 2

Докажем тождество из нашего примера, воспользовавшись основными тождествами алгебры множеств. Получим:

xA \ (В \ C)  xA  xA  xA  (  ) xA  ( C) x (A  )  (A  C) x (A \ В)  (A  C).

6. Эквивалентность множеств

Если каждому элементу множества A сопоставлен единственный элемент множества B и при этом всякий элемент множества B оказывается сопоставленным одному и только одному элементу множества A, то говорят, что между множествами A и B существует взаимно однозначное соответствие. Множества A и B в этом случае называют эквивалентными или равномощными.

Эквивалентность множеств обозначается следующим образом: A  B.

Эквивалентность множеств обладает следующим свойством транзитивности.

Если A  B и B  C, то A  C.

Докажем это свойство. Так как A  B, то для всякого элемента a  А существует единственный элемент b  B. Но так как B  C, то для всякого элемента b  B существует единственный элемент c  C. Сопоставим этот элемент элементу a  А. Значит, для всякого элемента a  А существует единственный элемент c  C и для всякого элемента c  C существует единственный элемент a  А. Следовательно, A  C.

Очевидно, что два конечных множества эквивалентны тогда и только тогда, когда количество элементов в них одинаково. Например, множества А = {4, 5, 6} и В = {x, y, z} эквивалентны, A  B. Взаимно однозначное соответствие может быть установлено между элементами 4 и x, 5 и y, 6 и z.

Мощностью конечного множества А (обозначается А) называется число элементов этого множества. Например, мощность множества А = {1, 2} равна А= 2.

Пример.

Ранее мы рассматривали множество всех подмножеств данного множества А, которое называется множеством-степенью и обозначается P(A). Множество P(A) состоит из 2ⁿ элементов. Таким образом, P(A)  = 2ⁿ.

Рассмотрим задачу определения мощности объединения n конечных множеств.

Пусть n = 2 и A и B – два пересекающихся множества. Докажем с помощью диаграммы Эйлера – Венна следующее соотношение:

АB = А + B – АB . (1)

Из рис. 3 видим, что

АB = n₁+n₂+n₃;

А = n₁+n₂;

B = n₂+n₃;

АB = n₂.

Рисунок 3.

Очевидно, что n₁+n₂+n₃ = (n₁+n₂) +(n₂+n₃) – n₂, что и доказывает формулу (1).

Формула (1) справедлива и для случая, если множества A и B не пересекаются. В этом случае

АB = А + B .

Пусть n = 3 и A, B и С – три пересекающихся множества. В этом случае справедливо следующее соотношение:

АB С= А + B + C – АB – АC – BC + АB C . (2)

Из рис. 4 видим, что

АB С= n₁+n₂+n₃+n₄+n₅+n₆+n₇;

А = n₁+n₂+n₄+n₅;

B = n₂+n₃+n₅+n₆;

С=n₄+n₅+n₆+n₇;

АB = n₂+n₅;

АC = n₄+n₅;

BC = n₅+n₆;

АB C = n₅.

Рисунок 4.

Очевидно, что

n₁+n₂+n₃+n₄+n₅+n₆+n₇ =(n₁+n₂+n₄+n₅) + (n₂+n₃+n₅+n₆) +(n₄+n₅+n₆+n₇) – (n₂+n₅) – (n₄+n₅) – (n₅+n₆) + n₅,

что и доказывает формулу (2).

Формула (2) справедлива и для случая, если множества A, B и С попарно не пересекаются. В этом случае

АB С= А + B + C .

В общем случае мощность объединения n множеств определяется по формуле:

А₁ А₂ …А_n= А₁+А₂+…+ А_n– (А₁ А₂+ А₁ А₃+ … +А_n–1А_n)+ АB C + (А₁ А₂  А₃ + … + А_n–2А_n–1А_n) – … + (–1)^{n – 1} А₁А₂ …А_n. (3)

Понятие эквивалентности годится и для бесконечных множеств. Пусть, например, A = {1, 2, 3, …, n,…}, B = {– 1, –2, …, –n, …}. Тогда A  B. Взаимно однозначное соответствие устанавливается по правилу: элементу n A соответствует элемент – n B, т.е. n  – n.

Пример.

A = {1, 2, 3, …, n,…}, B = {2, 4 …, 2n, …}. Тогда A  B. Взаимно однозначное соответствие устанавливается по правилу: n  2*n.

A = {1, 2, 3, …, n,…} – множество натуральных чисел, B = {…, –n, …– 2, –1, 0, 1, 2, …, n, …} – множество всех целых чисел.

Перепишем множество B следующим образом:

B = {0, –1, 1, – 2, 2, …, –n, n, …}, так, что 0 будет на первом месте, –1 на втором, 1 на третьем, –2 на четвертом и т.д. Нетрудно заметить, что отрицательные числа будут стоять на местах с четными номерами, а 0 и положительные числа – на местах с нечетными номерами. Поэтому взаимно однозначное соответствие между множествами A и B устанавливается по правилу: для всякого n  0 элементу a = 2n +1 из множества A (т.е. нечетному элементу) соответствует элемент b = n из множества B; элементу a = 2n из множества A (т.е. четному элементу) соответствует элемент b = –n из множества B. Таким образом, реализуется взаимно однозначное соответствие между множествами A и B: 1  0, 2  –1, 3  1, 4  –2 и т.д.

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

Множество, эквивалентное множеству натуральных чисел N = {1, 2, 3, …, n,…}, называется счетным. Можно сказать также, что множество счетно, если его элементы можно перенумеровать.

Пример.

Установить, являются ли следующие множества счетными:

1. A₁ = {–1, –2, …, – n, …};

2. A₂ = {2, 2², …, 2ⁿ,…};

3. A₃ = {2, 4, …, 2n,…};

4. A₄ = {…, – n, …, – 1, 0, 1, …, n,…};

Решение. Чтобы установить счетность некоторого множества, достаточно указать взаимно однозначное соответствие между элементами данного множества и множества натуральных чисел. Взаимно однозначное соответствие устанавливается по следующим правилам:

• для множества A₁: –n  n;

• для множества A₂: 2ⁿ  n;

• для множества A₃: 2*n  n;

• счетность множества A₄ установлена ранее в примере.

Упорядоченной парой (x, y) называется совокупность двух элементов x и y, расположенных в определенном порядке.

Две упорядоченные пары (x, y) и (u, v) равны межу собой тогда и только тогда, когда x = u и y = v.

Например, (a, b), (1, 2), (x, 4) – упорядоченные пары.

Аналогично можно рассматривать тройки, четверки, n-ки элементов (x₁, x₂, … x_n).

Прямым (или декартовым) произведением двух множеств A и B называется множество упорядоченных пар, таких, что первый элемент каждой пары принадлежит множеству A, а второй – множеству B:

A  B = {(a, b), / a А и b В}.

В общем случае прямым произведением n множеств А₁, А₂,… А_n называется множество А₁  А₂  … А_n, состоящее из упорядоченных наборов элементов (a₁, a₂, …, a_n) длины n, таких, что i- ый a_i принадлежит множеству А_i, a_i  А_i.

Пример.

Пусть А = {1, 2}, В = {2, 3}. Тогда A  B = {1, 2, 1, 3,2, 2,2, 3}.

Пусть А = {x / 0  x  1} и B = {y / 2  y  3}. Тогда A  B = { x, y  / 0  x  1 и 2  y  3}. Таким образом, множество A  B состоит из точек, лежащих внутри и на границе прямоугольника, образованного прямыми x = 0 (ось ординат), x = 1, y = 2 и y = 3.

Французский математик и философ Декарт впервые предложил координатное представление точек плоскости. Это исторически первый пример прямого произведения.