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

Доказательство единственности дополненияможно провести «от противного».

Пусть, напротив, есть два различныхдополнения множества А (А Í Е), обозначим их В и С (В ¹ С). Тогда должно быть: А Ç В = А Ç С = Æ, А È В = А È С = Е.

Получаем: В = В Ç Е = В Ç (А È С) = (В Ç А) È (В Ç С) = Æ È (В Ç С) = В Ç С, т. е. В Î В Ç С, или В Í С.

Аналогично, С Í В. В итоге В = С =А¢.

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

Доказательство выражений для дополнений при попарном непересечении трех множествпредставлено ниже в аналитической форме.

А È В È С = Е, А Ç В = А Ç С = В Ç С = Æ,

доказать: А¢ = В È С, В¢ = А È С, С¢ = А È В.

Вообще-то достаточно доказать одно из трех равенств (полная симметрия относительно А, В, С). Итак,

А È (В È С) = А È В È С = Е,

А Ç (В È С) = (А Ç В) È (А Ç С) = Æ È Æ = Æ.

Таким образом, действительно, А¢ = В È С.

Как и в алгебре логики, в теории множеств также имеются законы де Моргана(для пересечения Ç и для объединения È множеств). Инверсия уподобляется дополнению. Например, закон де Моргана для пересечения: (X Ç Y)¢ = X¢ È Y ¢.

Достаточно доказать: (X Ç Y) Ç (X¢ È Y¢) = Æ,

(X Ç Y) È (X¢ È Y¢) = E.

В первом равенстве используем дистрибутивность Ç относительно È:

((X Ç Y) Ç X¢) È ((X Ç Y) Ç Y¢) = Æ È (X Ç (Y Ç Y¢)) = X Ç Æ = Æ.

Во втором равенстве – обратная дистрибутивность (È относительно Ç):

((X È X¢) Ç (Y È X¢)) È Y¢= (E Ç (Y È X¢)) È Y¢ = (Y È X¢) È Y¢ = E.

Здесь еще привлекаются коммутативность и ассоциативность объединения È:

(Y È X¢) È Y¢ = ( X¢ È Y) È Y¢ = X¢ È (Y È Y¢) = X¢ È E = E.

Неэквивалентные множества: А ¹ В Û А \ В = Æ или В \ А ¹ Æ.

Степень(булеан) множества – это множество всех его подмножеств, начиная с пустого множества Æ и заканчивая самим множеством: Р (М) = 2^М = {X : X Í M}.

Пример.М = {1, 2}, Р (M) = {Æ, {1}, {2}, M}.

Мощность степени: | Р (M) | = 2^|M| .

Доказательство можно провести, по крайней мере, тремя способами:

– с помощью биномиальных коэффициентов;

– методом полной математической индукции;

– с использованием двоичной системы счисления.

В последнем случае заметим, что |М| = n отвечают n-разрядные двоичные числа. Причем Æ соответствует 0…0, М – 1…1₂, и т. д. Количество различныхдвоичных чисел и равно 2ⁿ , т.е. 2^|M|.