Лекции ДМ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 способ

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

- результат

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

- результат

2 способ

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

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

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

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

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

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

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

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