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

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

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

EF & FE.

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

aEa(AB)Ca(AB)& aC(aAaB)& aCa(AC)a( BC)a(AC)(BC)⟹a∈F.

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

aFa(AC)(BC)a(AC)a( BC)(aA & aC)(aВ& aC)a(AB)& aCa(AB)C⟹aE.

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

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

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

aA((AB)(AB))aA & a((AB)(AB))aA & (a(AB)& a(AB))aA & (aA & aB) &(aAaB)

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

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

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

xU, xA xB

xU, xA xB

xU, xB’ xA’

Значит B’ A’.

Пример 4.Доказать(AB)C=(AC)(BC).

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

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