2.4Доказательства теоретико-множественных тождеств.

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

a) Исходят непосредственно из определений операций, при этом обычно сначала доказывают, что левая часть равенства содержится в правой части, а затем, наоборот, что правая часть содержится в левой. Из этого заключают, что они совпадают. Для этого берут какой-либо один элемент из левой части равенства и доказывают, что он должен содержаться и в правой его части, а потом эту же процедуру повторяют, взяв элемент из правой части равенства.

b) Сводят всё к формуле математической логики и доказывают, что она есть тавтология.

Продемонстрируем оба способа на примерах.

Доказать тождество: А\(ВÈС)=(А\В)Ç(А\С)

1. Пусть некий элемент хÎА\(ВÈС). Тогда хÎА и хÏ(ВÈС). Значит он не принадлежит ни В, ни С. А тогда хÎА\В и хÎА\С, а значит, и их пересечению, т.е., всей правой части. Итак, левая часть содержится в правой. Пусть теперь хÎ(А\В) Ç (А\С). Это значит, что хÎА и хÏВ, хÏС. Значит, хÎА и хÏ(ВÈС). А значит, он содержится в левой части.

2. Введём предикаты р(х): (хÎА) ; q(х): (хÎB; r(х): (хÎC). Тогда утверждение сводится к доказательству логической эквивалентности pÙØ(qÚr)~(p ÙØq)Ù(pÙØr) которая легко проверяется.

Доказать тождество: АÇВ=АÛАÌВ

1. (Þ) Опять, допустим хÎА. Так как АÇВ=А, то хÎАÇВ; Þ хÎВ. Итак, (хÎА)Þ(хÎВ). Значит, по определению, АÌВ. (Ü) Поскольку всегда АÇВÌА, то надо лишь доказать, что АÌАÇВ. Пусть хÎА. Так как АÌВ ,то хÎВ. Следовательно, хÎАÇВ.

2. В обозначениях предыдущего примера получим: ((pÙq~p))~(pÞq). Надо доказать, что это – тавтология. Используем упражнение 7 пункт i) из части 1. Преобразуем сначала внутреннюю эквивалентность и импликацию: ((pÙqÙp)Ú(ù(pÙq) Ùùp))~(ùpÚq). В левой части от знака эквивалентности делаем преобразования: (pÙq)Ú((ùpÚùq)Ùùp); (дистрибутивность, идемпотентность, коммутативность) pÙqÚ(ùpÙùqÚùp); (поглощение) pÙqÚùp; Теперь снова применяем замену эквивалентности: [(pÙqÚùp)Ù(ùpÚq)]Ú[ù (pÙqÚùp)Ùù(ùpÚq)]. По дистрибутивности в каждой из квадратных скобок получим: [pÙqÙùpÚpÙqÙq Ú ùpÙùpÚùpÙq] Ú [(ùpÚùq)ÙpÙ(p Ùùq]; [FÚpÙqÚùpÚùpÙq]Ú[(FÚùqÙp) Ù(p Ùùq]; [pÙqÚùp] Ú[p Ùùq]; Итак, получили: pÙqÚ p ÙùqÚùp. Это (выносим р за скобку) эквивалентно рÙ( qÚùq)ÚùpÛ рÙТÚùp ÛрÚùp Û Т.

3. (Þ): АÇВÌВ; А=АÇВÞАÌВ. (Ü): АÌА и АÌВÞАÌ(АÇВ), а так как всегда АÇВÌА, то АÇВ=А

Упражнение 7. Докажите следующие тождества:

1. АÈВ=ВÛАÌВ

2. А\(ВÇС)= (А\В)È(А\С)

3. А\(А\В)=АÇВ

4. А\В=А\(АÇВ)

5. АÈВ=АÈ(В\А)

6. (АÇВ)ÌСÛАÌСÈВ^с

7. АÌ(ВÈС)ÛАÇВ^сÌС

8. (А\В)ÈВ=АÛВÌА

9. (АÇВ)ÈС=АÇ(ВÈС)ÛСÌА

10. АÈВ=АÇВÛА=В

11. АD(ВDС)=(АDВ)DС

12. АÇ(ВDС)=(АÇВ)D(АÇС)

13. АD(АDВ)=В

14. А\В=АD(АÇВ)

Упражнение 8.

Докажите все тождества из следующей таблицы сведением их к логическим тавтологиям.

Здесь U обозначает некоторое универсальное множество; черта сверху обозначает операцию дополнения. Сравните эту таблицу с таблицей из части 1. Что мы можем наблюдать?

Таблица основных теоретико-множественных тождеств.

закон двойного дополнения: =A
законы “сокращения”
AÈU=U; AÇU=A	AÇÆ=Æ; AÈÆ=A
законы идемпотентности
AÈA=A	AÇA=A
Закон исключённого третьего
AÈ =U	AÇ = Æ
законы коммутативности
AÈB=BÈA	AÇB=BÇA
законы ассоциативности
(AÈB)ÈC=AÈ(BÈC)	(AÇB)ÇC= AÇ(BÇC)
законы дистрибутивности
(AÈB)ÇC=(AÇC)È(BÇC)	(AÇB)ÈC=(AÈC)Ç(BÈC)
законы де Моргана
= Ç	= È
законы поглощения.
AÈ(AÇB)=A	AÇ(AÈB)=A