П.5. Свойства операций над множествами.
1. Законы коммутативности.
Для любых множеств , :
Доказательство:
Для того, чтобы доказать равенство двух множеств, нужно доказать, что каждое из этих множеств является подмножеством другого множества.
Пусть
.
Второе равенство доказано.
Для того, чтобы доказать равенство двух множеств, нужно доказать, что каждое из этих множеств является подмножеством другого множества. Пусть
.
2. Законы ассоциативности.
Для любых множеств , :
Доказательство:
3. Законы дистрибутивности.
Для любых множеств , , :
Доказательство:
4. Законы идемпотентности.
Доказательство:
5. Законы для разности.
Для любых множеств , , :
Доказательство:
6. Законы Де Моргана для разности.
Для любых множеств , , :
Доказательство:
П.6. Универсальные множества. Дополнение и его свойства.
Определение.
Если все рассматриваемые множества
являются подмножествами некоторого
множества
,
то
- универсальное множество.
Пример.
Множество действительных чисел
- универсальное множество.
Определение.
Пусть
,
тогда дополнением множества
,
обозначается
или
,
называется множество, определяемое
формулой:
.
Свойства дополнения:
Свойства 1) и 2) – законы Де Моргана для дополнения.
Доказательства:
Дано: , доказать:
,
т.е. нужно доказать, что каждый элемент
из
лежит в
.
Возьмём
,
.Таким
образом,
§6. Прямое произведение двух множеств. Бинарные отношения. Отношения эквивалентности и фактор множества. Функции. Отношение порядка. П.1. Прямое произведение множеств.
- упорядоченная
пара элементов, т.е.
- первый элемент,
- второй элемент.
Описание.
Определение.
Прямое произведение множеств
и
(обозначается:
) – это множество всех упорядоченных
пар
.
Прямое произведение множеств часто называют декартовым произведением множеств.
Пример.
;
Упорядоченную пару иначе можно назвать кортежем длины 2.
Обобщение понятия
упорядоченной пары является понятие
кортежа (упорядоченного множества
n-объектов).
Кортеж n-объектов
записывается:
.
Определение.
Два кортежа
и
равны тогда и только тогда, когда
.
Прямое произведение
n-множеств
(
)
– это множество всех кортежей вида
.
Множество
степени n,
где
равно прямому произведению n-множеств.
Пример.
.
П.2. Бинарные отношения.
Определение. Бинарное отношение – это любое множество упорядоченных пар. Другими словами, бинарное отношение – это подмножество прямого произведения двух множеств.
Пример.
-
бинарное отношение - отношение равенства
на множестве натуральных чисел.
Обозначения:
- пара
принадлежит бинарному отношению
;
- элемент
находится в отношении
с элементом
;
- пара
принадлежит бинарному отношению
тогда и только тогда, когда элемент
находится в отношении
с элементом
.
Отрицание:
- элемент
не находится в отношении
с элементом
тогда и только тогда, когда пара
не принадлежит бинарному отношению
.
Бинарные отношения часто задают описанием.
Пример. Что такое отношение равенства на множестве ?
Отношение равенства
равно
Отношение равенства
меньше или равно на
Определение.
Если отношение
- подмножество прямого произведения
,
то
- бинарное отношение на множестве
.