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

Для любых множеств 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, нужно доказать, что, во-первых, если xÎ А, то xÎВ и, во-вторых, если xÎВ, то xÎ А. Докажем таким образом, например, свойство дистрибутивности для объединения (тождество 3а)):

AÈ (BÇC) = (AÈB) Ç (AÈC).

1. Сначала предположим, что некоторый элемент x принадлежит левой части тождества, т.е. xÎ AÈ (BÇC), и докажем, что x принадлежит правой части, т.е. xÎ(AÈB) Ç (AÈC).

Действительно, пусть xÎ AÈ (BÇC). Тогда либо xÎ A, либо xÎ BÇC. Рассмотрим каждую из этих возможностей.

Пусть xÎ A. Тогда xÎ A È B и xÎ A ÈC (это верно для любых множеств B и C). Следовательно, xÎ(AÈB) Ç (AÈC).

2. Предположим, что некоторый элемент x принадлежит правой части тождества, т.е. xÎ (AÈB) Ç (AÈC), и докажем, что x принадлежит левой части, т.е. xÎ AÈ (BÇC) .

Действительно, пусть xÎ (AÈB) Ç (AÈC). Тогда xÎAÈB, и одновременно xÎ AÈC. Если xÎ AÈB, то либо xÎ A, либо xÎ B, если .xÎ AÈC, то либо xÎ A, либо xÎ C. Пусть xÎ A, Тогда xÎ AÈ (BÇC) и утверждение доказано. Если xÏ A, то одновременно должны выполняться условия xÎ B и xÎ C, т.е. xÎ BÇC. Но тогда xÎ BÇC и xÎ AÈ (BÇC), что также доказывает наше утверждение.

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

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

Пример 1.14.

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

Преобразуем левую часть тождества, используя тождество 11:

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

Затем используем закон дистрибутивности (тождество 3б):

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

Используем закон исключенного третьего (тождество 9):

B Ç = Æ.

Получим

A Ç ÈB Ç = A Ç È Æ.

Используем свойство пустого множества (тождество 10б):

A Ç È Æ = A Ç .

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

Пример 1.15.

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

A \ (В \ C) = (A \ В)È (A Ç C).

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

Рис. 1.2

Рис. 1.2б) и рис. 1.2д) иллюстрируют равенство множеств A \ (В \ C) и (A \ В)È (A Ç C).

Докажем тождество из нашего примера, воспользовавшись тождествами:

А \ В = A Ç , = È , = A, AÇ(BÈC) = (AÇB)È(AÇC).

Получим:

A \ (В \ C) = A Ç = A Ç = A Ç ( È ) = A Ç ( ÈC) = (A Ç ) È (A Ç C) = (A \ В)È (A Ç C).

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

Пример 1.16.

Упростить выражение:

(AÈB) Ç ( ÈB) Ç (AÈ ).

Используя закон коммутативности (тождество 1б), поменяем местами вторую и третью скобки:

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

Применим закон расщепления (тождество 7а) для первой и второй скобок:

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

Воспользуемся законом дистрибутивности (тождество 3б):

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

Используем закон исключенного третьего (тождество 9):

A Ç = Æ.

Получим

A Ç ÈA Ç B = Æ ÈA Ç B.

Используем свойство пустого множества (тождество 10б):

Æ ÈA Ç B = A Ç B.

Итак,

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

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

Определение 1.2. Если каждому элементу множества 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.

Пример 1.17.

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

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

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

çАÈB ç= çА ç+ çB ç– çАÇB ç. (1.1)

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

çАÈB ç= n₁+n₂+n₃;

çА ç= n₁+n₂;

çB ç= n₂+n₃;

çАÇB ç= n₂.

Рис. 1.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 ç. (1.2)

Из рис. 1.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₅.

Рис. 1.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₅,

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

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

çАÈBÈ Сç= çА ç+ çB ç+ çC ç.

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

çА₁È А₂ È…ÈА_nç= çА₁ç+çА₂ç+…+ çА_nç– (çА₁Ç А₂ç+ çА₁Ç А₃ç+ … +çА_n–1ÇА_nç)+ çАÇB ÇC ç+ (çА₁Ç А₂ Ç А₃ç + … +çА_n–2ÇА_n–1ÇА_nç) – … + (–1)^{n – 1} çА₁ÇА₂ …ÇА_nç. (1.3)

Эта формула выводится индукцией по n, [3].

Если множества А_i попарно не пересекаются, т.е. А_i ÇА_j = Æ, i ¹ j,то получим частный случай формулы (1.3):

çА₁È А₂ È…ÈА_nç= çА₁ç+çА₂ç+…+ çА_nç.

В общем случае справедливо неравенство

çА₁È А₂ È…ÈА_nç£ çА₁ç+çА₂ç+…+ çА_nç.

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

Пример 1.18.

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

Пример 1.19.

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 и т.д.

Примеры 1.18 и 1.19 показывают, что множество может быть эквивалентно своему подмножеству. Так, в примере 1.18 BÌ A, а в примере 1.19 A Ì B. И в том, и в другом случае A ~ B.

Установить эквивалентность множеств, т.е. установить взаимно однозначное соответствие между их элементами можно различными путями. На рис. 1.5 показано, что множества точек двух отрезков [a, b] и [c, d] эквивалентны.

Рис.1.5

Таким же образом можно установить эквивалентность множеств точек двух интервалов. На рис.1.6 показано, что множества точек любого интервала (a, b) эквивалентно множеству точек всей прямой.

Рис. 1.6

Для установления эквивалентности двух множеств можно применять следующую теорему.

Теорема Бернштейна. Если множество A эквивалентно части множества B, а множество B эквивалентно части множества A, то множества A и B эквивалентны.

Применим теорему Бернштейна для доказательства того, что множество точек любого отрезка эквивалентно множеству точек любого интервала.

Пусть A = [a, b] – произвольный отрезок, а B = (c, d) – произвольный интервал.

Пусть A₁ = [a₁, b₁] – любой внутренний интервал отрезка [a, b], A₁Ì A. Тогда A₁ ~ B.

Пусть B₁ = (c₁, d₁) – любой внутренний отрезок интервала (c, d), B₁Ì B. Тогда B₁ ~ A.

Таким образом, выполняются условия теоремы Бернштейна. Поэтому A ~ B.

Итак, все интервалы, отрезки и вся прямая эквивалентны между собой.

Счетные множества

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

Можно сказать также, что множество счетно, если его элементы можно перенумеровать.

Пример 1.20.

Следующие множества являются счетными.:

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

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

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

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

Чтобы установить счетность некоторого множества, достаточно указать взаимно однозначное соответствие между элементами данного множества и множества натуральных чисел. Для примера 1.19 взаимно однозначное соответствие устанавливается по следующим правилам: для множества A₁: –n « n; для множества A₂: 2ⁿ « n; для множества A₃: 2n « n; счетность множества A₄ установлена в примере 1.19;

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

Теорема 1. Всякое бесконечное подмножество счетного множества счетно.

Пример 1.21.

Множество A = {3, 6, …, 3n,…} счетно, т.к. A – бесконечное подмножество множества натуральных чисел, A Ì N.

Теорема 2. Объединение конечной или счетной совокупности счетных множеств счетно.

Пример 1.22.

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

Теорема 3. Множество всех рациональных чисел, т.е. чисел вида , где p и q целые числа, счетно.

Теорема 4. Если А = {a₁, a₂, …} и B = {b₁, b₂, …} – счетные множества, то множество всех пар С = {(a_k, b_n), k = 1, 2,…; n = 1, 2, …} счетно.

Пример 1.23.

Геометрический смысл пары (a_k, b_n) – точка на плоскости с рациональными координатами (a_k, b_n). Поэтому можно утверждать, что множество всех точек плоскости с рациональными координатами счетно.

Теорема 5. Множество всех многочленов P(x) = a₀ + a₁x + a₂x² + … + a_nxⁿ любых степеней с рациональными коэффициентами a₀, a₁, a₂, … a_n счетно.

Теорема 6. Множество всех корней многочленов любых степеней с рациональными коэффициентами счетно.