diskr_edit (1023554), страница 2
Текст из файла (страница 2)
Тогда АВC =.
Относительным дополнением множества В до множества А называется множество А \ В, все элементы которого являются элементами множества А, но не являются элементами множества В:
А \ В = {x x А и xВ}.
Пример 1.11.
Рассмотрим данные из примера 1.8.
а) А = {4, 5, 6}, В = {2, 4, 6}.
А \ В = {4, 5}, В \ А= {2}.
б) А = {2, 4, 6, …}, В = {3, 6, 9, …}.
Тогда А \ В – множество чисел, которые делятся на 2, но не делятся на 3, а В \ А – множество чисел, которые делятся на 3, но не делятся на 2:
А \ В = {2, 4, 8, 10, 14, …}.
В \ А= {3, 9, 15, 21, 27, …}.
Симметрической разностью множеств А и В называется множество А + В:
А + В = (А \ В) (В \ А).
Пример 1.12.
Рассмотрим данные из примера 1.11.
а) А = {4, 5, 6}, В = {2, 4, 6}.
А \ В = {4, 5}, В \ А= {2}, А + В = {2, 4, 5}.
б) А = {2, 4, 6, …}, В = {3, 6, 9, …}, А \ В = {2, 4, 8, 10, 14, …}.
В \ А= {3, 9, 15, 21, 27, …}, А + В = {2, 3, 4, 8, 9, …}.
Универсальным множеством называется такое множество U, что все рассматриваемые в данной задаче множества являются его подмножествами.
Абсолютным дополнением множества А называется множество 
всех таких элементов x U, которые не принадлежат множеству А: = U \ A.
Пример 1.13.
Пусть А – множество положительных четных чисел.
Тогда U – множество всех натуральных чисел и - множество положительных нечетных чисел.
1.3. Геометрическое моделирование множеств. Диаграммы Венна
Для наглядного представления множеств и отношений между ними используется диаграммы Венна (иногда их называют кругами Эйлера или диаграммами Эйлера – Венна).
Универсальное множество изображают в виде прямоугольника, а множества, входящие в универсальное множество, – в виде кругов внутри прямоугольника; элементу множества соответствует точка внутри круга (рис 1.1а)).
С помощью диаграмм Венна удобно иллюстрировать операции над множествами.
Рис.1.1
1.4. Алгебра множеств. Основные тождества алгебры множеств
Множества вместе с определенными на них операциями образуют алгебру множеств. Последовательность выполнения операций задается с помощью формулы алгебры множеств. Например, (В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 (BC) = (AB) (AC) (для объединения относительно пересечения);
б) A(BC) = (AB)(AC) (для пересечения относительно объединения).
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 (BC) = (AB) (AC).
1. Сначала предположим, что некоторый элемент x принадлежит левой части тождества, т.е. x A (BC), и докажем, что x принадлежит правой части, т.е. x(AB) (AC).
Действительно, пусть x A (BC). Тогда либо x A, либо x BC. Рассмотрим каждую из этих возможностей.
Пусть x A. Тогда x A B и x A C (это верно для любых множеств B и C). Следовательно, x(AB) (AC).
2. Предположим, что некоторый элемент x принадлежит правой части тождества, т.е. x (AB) (AC), и докажем, что x принадлежит левой части, т.е. x A (BC) .
Действительно, пусть x (AB) (AC). Тогда xAB, и одновременно x AC. Если x AB, то либо x A, либо x B, если .x AC, то либо x A, либо x C. Пусть x A, Тогда x A (BC) и утверждение доказано. Если x A, то одновременно должны выполняться условия x B и x C, т.е. x BC. Но тогда x BC и x A (BC), что также доказывает наше утверждение.
Доказательство тождеств можно проиллюстрировать с помощью диаграмм Венна.
Основные тождества алгебры множеств можно использовать для доказательства других тождеств.
Пример 1.14.
Доказать тождество (AB) \ В = A .
Преобразуем левую часть тождества, используя тождество 11:
(AB) \ В = (AB) .
Затем используем закон дистрибутивности (тождество 3б):
(AB) = 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(BC) = (AB)(AC).
Получим:
A \ (В \ C) = A 
= A 
= A (
) = A ( C) = (A ) (A C) = (A \ В) (A C).
Основные тождества алгебры множеств можно также использовать для упрощения формул алгебры логики.
Пример 1.16.
Упростить выражение:
(AB) ( B) (A ).
Используя закон коммутативности (тождество 1б), поменяем местами вторую и третью скобки:
(AB) ( B) (A ) = (AB) (A ) ( B).
Применим закон расщепления (тождество 7а) для первой и второй скобок:
(AB) (A ) ( B) = A ( B).
Воспользуемся законом дистрибутивности (тождество 3б):
A ( B) = A A B.
Используем закон исключенного третьего (тождество 9):
A = .
Получим
A A B = A B.
Используем свойство пустого множества (тождество 10б):
A B = A B.
Итак,
(AB) ( B) (A ) = A B.
1.5. Эквивалентность множеств
Определение 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) состоит из 2n элементов. Таким образом, P(A) = 2n.
Рассмотрим задачу определения мощности объединения n конечных множеств.
Пусть n = 2 и A и B – два пересекающихся множества. Докажем с помощью диаграммы Эйлера – Венна следующее соотношение:
АB = А + B – АB . (1.1)
Из рис. 1.3 видим, что
АB = n1+n2+n3;
А = n1+n2;
B = n2+n3;
АB = n2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
