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

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

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

EF&FE.

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

aEa(AB)C a(AB)& aC (aA aB)& aC a(AC) a( BC) a (AC) (BC)⟹a∈F.

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

aFa(AC) (BC)a(AC) a( BC)(aA & aC)(aВ& aC) a(AB)& aC a(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) &(aA aB)

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

Пример 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)является их объединением. Сравнивая эти два рисунка, можно сделать вывод, что эти множества равны, следовательно, тождество доказано.