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

Пример 1. Доказать или опровергнуть справедливость тождества (A B) C=(A C) (B C).

Доказательство. Докажем, используя метод взаимного включения. Пусть (A B) C=E, a (A C) (B C)=F. Тогда необходимо доказать или опровергнуть следующее:

E F & F E.

1. Докажем необходимость: E F.

a E a (A B) C a (A B)& a C (a A a B)& a C a (A C) a (B C) a (A C) (B C)⟹ a∈ F.

2. Докажем достаточность: F E

a F a (A C) (B C) a (A C) a (B C) (a A & a C) (a В& a C) a (A B)& a C a (A B) C⟹ a E.

3. Следовательно, E=F, т.е. исходное тождество справедливо.

Пример 2. Доказать или опровергнуть справедливость тождества A ((A B) (A B))= .

Доказательство. Докажем методом от противного: предположим, что это выражение не равно пустому множеству.

a A ((A B) (A B)) a A & a ((A B) (A B)) a A & (a (A B)& a (A B)) a A & (a A & a B) & (a A a B)

Получаем противоречие: элемент одновременно принадлежит и не принадлежит множеству . Значит, первоначальное предположение неверно и исходное тождество справедливо, т.е. равно .

Пример 3. Доказать, что A B B’ A’.

Доказательство. Пусть А и В – подмножества некоторого универсума U, А B

x U, x A x B

x U, x A x B

x U, x B’ x A’

Значит B’ A’.

Пример 4. Доказать (A B) C=(A C) (B C).

Доказательство. Докажем, используя геометрический метод. Построим диаграммы Эйлера-Венна для множеств (A B) C и (A C) (B C):

На первой диаграмме множество (A B) C выделено черной штриховкой, на второй множество (A C) – светлой, множество (B C) – серой, а множество (A C) (B C) является их объединением. Сравнивая эти два рисунка, можно сделать вывод, что эти множества равны, следовательно, тождество доказано.

Булеан

Множество всех подмножеств множества М называется булеаном и обозначает­ся 2^М:

2^М = {А| А М}

Теорема. Для конечного множества М |2^М| = 2^|M|