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

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

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

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

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

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

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

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

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

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

b) В обозначениях предыдущего примера получим: ((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 Û Т.

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

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

a) АÈВ=ВÛАÌВ

b) А\(ВÇС)= (А\В)È(А\С)

c) А\(А\В)=АÇВ

d) А\В=А\(АÇВ)

e) АÈВ=АÈ(В\А)

f) (АÇВ)ÌСÛАÌСÈВ^с

g) АÌ(ВÈС)ÛАÇВ^сÌС

h) (А\В)ÈВ=АÛВÌА

i) (АÇВ)ÈС=АÇ(ВÈС)ÛСÌА

j) АÈВ=АÇВÛА=В

k) АD(ВDС)=(АDВ)DС

l) АÇ(ВDС)=(АÇВ)D(АÇС)

m) АD(АDВ)=В

n) А\В=АD(АÇВ)