4. Алгебра множеств.

Непосредственной проверкой можно доказать справедливость следующих соотношений:

1. Коммутативность

2. Ассоциативность

3. Дистрибутивность

4. Закон поглощения

5. Закон де Моргана

Приведенные выше соотношения называются тождествами алгебры множеств.

Заметим, что если в равенстве заменить  на , U на  и наоборот, то получим справедливое равенство.

Этот закон называется принципом двойственности.

Докажем, например, справедливость равенства аналитически и с помощью диаграмм Эйлера – Венна.

Пусть х Є АU В, что означает хU и хАВ. Отсюда следует, что хА и хВ, но тогда

Построим диаграммы для обеих частей равенства и сравним их.

Д иаграмма для левой части :

Д иаграмма для правой части:

Сравнивая диаграммы, убеждаемся в справедливости равенства.

Пользуясь тождествами можно производить преобразования над множественными выражениями и доказывать тождества.

Пример1: доказать тождество

Рассмотрим два способа: с помощью диаграмм и тождеств.

1 способ

Левая часть тождества

- результат

Правая часть тождества

- результат

2 способ

Преобразуем левую часть тождества :

Тем самым доказали верность тождества.

Пример2: Доказать тождество: Составить двойственное и тоже доказать.

Доказательство справедливости равенства и двойственного равенства с помощью диаграмм предлагаем выполнить самостоятельно.

Приведем доказательство справедливости данного равенства путем преобразований (доказательство для двойственного проведите самостоятельно):

Пример3: Доказать тождество:

Преобразуем правую часть тождества:

Тождество доказано.

5. Теорема о количестве подмножеств конечного множества.

Рассмотрим множество А = {1, 2, 3 }, где |A| = 3, и множество В = {5, 6, 7, 8}, где |B| = 4.

Составим всевозможные подмножества множества А:

А, , {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}.

Всего получили 8 подмножеств.

Составим всевозможные подмножества множества В:

В, , {5}, {6}, {7}, {8}, {5,6}, {5,7}, {5,8}, {6,7}, {6,8}, {7,8}, {5,6,7}, {5,7,8}, {6,7,8}, {5,6,8}.

Получили 16 подмножеств.

Используя результаты рассмотренных примеров, можно предположить справедливость следующего равенства: n = 2^m, где n – количество подмножеств данного конечного множества, m – мощность множества.

Справедливость предположения подтверждает теорема, которую мы примем без доказательства.

Теорема: Если для конечного множества А его мощность равна т, то количество всех подмножеств данного множества, обозначаемое Р(А), равно 2^т.

Пример: Вычислить количество подмножеств множества М – делителей числа 20.

Составим множество М и найдем его мощность :

М = {1,2,4,5,10,20}. Мощность |M| = 6, тогда количество подмножеств равно Р(М) = 2⁶ = 64.