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

 

 

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

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

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

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

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

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

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

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

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

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

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

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

Как и в алгебре логики, в теории множеств также имеются законы де Моргана (для пересечения Ç и для объединения È множеств). Инверсия уподобляется дополнению. Например, закон де Моргана для пересечения: (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|.

 

 

Теорема (о мощности объединения n множеств)

Пусть имеется n множеств А₁, А₂, … А_n, вычислить мощность их объединения

|А₁ А₂ … А_n|=|А₁|+|А₂|+…+|А_n|-

-|А₁ А₂|-|А₁ А₃|-|А₂ А₃|-…-|А_n-1 А_n|+

+|А₁ А₂ А₃|+|А₁ А₃ А₄|+…+|А_n-2 А_n-1 А_n|-…+

(-1)^n-1|А₁ А₂ … А_n| (*)

Доказательство:

Для доказательства будем использовать предыдущее утверждение и метод математической индукции.

1. База индукции выполняется по утверждению, n=2

2. Предположим, что формула (*) выполняется для всех k=n-1. Введем следующие обозначения S₁(А₁, А₂, …, А_n), S₂(А₁, А₂, …, А_n),.., S_n(А₁, А₂, …, А_n)

 

(*)=S₁(А₁, А₂, …, А_n)- S₂(А₁, А₂, …, А_n)+ +(-1)^n-1 S_n(А₁, А₂, …, А_n)

 

Имеет место формула

|А₁ А₂ … А_n-1|= S₁(А₁, А₂, …, А_n-1)- S₂(А₁, А₂, …, А_n-1)+…+

+(-1)^n-1 S_n-1(А₁, А₂, …, А_n-1) (**)

 

3. Произведем индукционный переход, т.е. покажем, что формула выполняется для всех k=n, для этого рассмотрим мощность объединения всех n множеств и произведем следующую операцию |А₁ А₂ … А_n|, пользуясь утверждением.

Распишем по утверждению çА₁ Вç=çА₁ç+çВç-çА₁ Вç где В=|А₂ … А_n|

 

=|А₁|+|А₂ … А_n|-|А₁ А₂| |А₁ А₃| … |А₁ А_n|=|А₁|+ S₁(А₂, …, А_n)-

- S₂(А₂,…,А_n)+…+(-1)^n-2 S_n-1(А₂,…,А_n)- S₁((А₁ А₂),А₁ А₃),…,(А₁ А_n))-

- S₂((А₁ А₂),(А₁ А₃),…,(А₁ А_n))+…+ (-1)^n-2S_n-1((А₁ А₂),(А₁ А₃),…,(А₁ А_n))

 

Формула (*) выполняется для всех k=n.

Из пунктов 1-3 следует, что по методу математической индукции формула (*) выполняется для всех nÎN\{1}.

Задача: Каждый ученик класса либо девочка, либо блондин, либо любит математику. В классе 20 девочек, из них 12 блондинок и одна блондинка любит математику. Всего в классе 24 ученика блондина, математику из них любят 12. А всего учеников, мальчиков и девочек, которые любят математику – 17, из них 6 девочек. Сколько учеников в классе?

А – девочки

В – блондины

С – любят математику

|А|=20, |В|=24, |С|=17, |А В|=12,|А С|=6, |В С|=12, |А В С|=1

|А В С|=|А|+|В|+|С|-|А В|-|А С|-|В С|+|А В С|=20+24+17-12-6-12+1=32