Пример 1.12
1. Закон дистрибутивности пересечения относительно объединения.
Доказательство закона проведем методом включений.
Требуется доказать, что А (В С) = (А В) (А С).
Шаг 1. Докажем сначала, что А (В С) (А В) (А С).
Пусть х А (В С), тогда х А и х В С (т.е. х В или х С). Если х В, то х А В и, следовательно, х (А В) (А С). Если х С, то х А С и, следовательно, х (А В) (А С).
Шаг 2. Теперь покажем, что (А В) (А С) А (В С).
Пусть х (А В) (А С), тогда х А В или х А С. Если х А В, то х А и х В, следовательно, х В С. Если х А С, то х А и х С, следовательно, х В С. Таким образом, х А и х В С, т.е. х А (В С).
Шаг 3. Поскольку доказано, что
А (В С) (А В) (А С) и (А В) (А С) А (В С),
то А (В С) = (А В) (А С).
Приведем теперь доказательство этого закона с использованием "формы от x":
А (В С) = {x | x A и x (В С)} = {x | x A и (x В или x С)} = = {x |(x A и x В) или ( x A и x С)} = (А В) (А С).
1. Второй закон поглощения.
Требуется доказать, что А (А В) = А.
Пусть x А (А В). Тогда x А.
Пусть теперь x А. Тогда x А B, следовательно, x А (А В).
Отсюда А (А В) = А.
2. Следующая цепочка равенств доказывает 1-й закон поглощения (используются известные тождества) :
А (A B) = (A A) (A B) = A (A B) = A. Следовательно, А (A B) = A.
Пример 1.13
Справедливо утверждение, что предложения: 1) А В; 2) А В = A; 3) А В = В о произвольных множествах А и В попарно эквивалентны.
Покажем, что из предложения 1) следует предположение 2). Действительно, А В A. Пусть теперь x А, так как А В, то x B, следовательно, x А В.
Покажем, что из предложения 2) следует предположение 3). Действительно, так как А В = A, то А В = (А В) В = B (на основании законов коммутативности и поглощения).
Покажем, что из предложения 3) следует предположение 1). Действительно, так как А A В и А В = В, то А В.
Метод характеристических функций
Для доказательства сложных теоретико-множественных тождеств более эффективно использовать характеристические функции.
Характеристической функцией A множества A U называется функция, заданная на множестве U (универсальное множество) со значениями на множестве {0,1}:
A(x)
=
Очевидно, тождество L = R будет справедливым, если характеристические функции множеств L, R равны, т.е. L(x) =R(x). Поэтому, для доказательства справедливости теоретико-множественного тождества, следует выразить характеристические функции его левой и правой частей через характеристические функции входящих в них множеств. С этой цель приведем характеристические функции пересечения, объединения, разности, абсолютного дополнения и симметрической разности:
1) AB(x) = A(x) B(x);
2) AB(x) = A(x) + B(x) - A(x) B(x);
3) A\B(x) = A(x) - A(x) B(x);
4) A(x) = 1 - A(x);
5) A+B(x) = A(x) + B(x) - 2A(x) B(x).
Кроме
того, из определения характеристической
функции следует, что
=
A(x).
Пример 1.14.
Докажем справедливость тождества А (В С) = (А В) (А С) методом характеристических функций. Имеем, с одной стороны:
A(BC)(x) = A(x) BC (x) = A(x) (B(x) + C(x) - B(x) C(x)) =
= A(x) B(x) + A(x) C(x) - A(x) B(x) C(x).
С другой стороны:
(AB) (A C)(x) = AB(x) + AC(x) - AB (x) AC (x) =
= A(x) B(x) + A(x) C(x) - A(x) B(x) A(x) C(x) =
= A(x)
B(x)
+A(x)
C(x)
-
B(x)
C(x)
=
= A(x) B(x) +A(x) C(x) - A(x) B(x) C(x).
Таким образом, характеристическая функция левой части совпадает с характеристической функцией правой части. Следовательно, рассматриваемое теоретико-множественное тождество справедливо.
1.2. Отношения
Бинарные отношения
Прямое произведение множеств
Композиция отношений
Бинарные отношения
Упорядоченной парой <x, y> называется совокупность, состоящая из двух элементов x и у, расположенных в определенном порядке.
Две пары <x ,y> и <u, v> считаются равными, если x = u , y = v.
Упорядоченная n-ка элементов определяется индуктивно с помощью понятия пары.
Упорядоченной n-кой элементов <x1, x2,..., xn> называется упорядоченная пара элементов <<x1, x2,..., xn-1>, xn>. Иначе говоря, для n ≥ 2 имеем: <x1, x2,..., xn> = <<x1, x2,..., xn-1>, xn>.
Бинарным (или двуместным) отношением называется множество упорядоченных пар. Если – это некоторое отношение, то наряду с записью <x, y> употребляется также запись: x у (обычно такая запись используется, когда является специальным обозначением отношения, знаком). Элементы x и y называются координатами или компонентами отношения .
Областью определения бинарного отношения называется множество:
D = {x существует такое y, что x y}.
Областью значений бинарного отношения называется множество:
E = {y существует такое x, что x у}.