Далее приведены основные равенства, используемые при преобразовании выражений с несколькими операциями над множествами: A – A — закон двойного дополнения (отрицания);A U A -1 — закон исключения третьего; A П A – 0 — закон противоречия; AU0^A;AПI = A; законы Моргана:(АГВ) = АЦВ;ЩЩ = АГВ; O законы коммутативности (перестановки):AUB^BUA;AПB^BПA; O законы ассоциативности (группировки): AU{BUC)^(AUB)UC;АП(ВПС)^(АПВ)ПС; законы дистрибутивности (сочетания операций): AU(Bnc)^(AUB)n(AUc)iАП(вис)^(АГв)и(АГс).Чтобы доказать равенство двух множеств, обычно показывают, что первое множество включается во второе, а второе — в первое. Кроме того, в самом доказательстве относительно множеств используют предложения типа «пусть некоторый элемент x принадлежит такому-то множеству». Поскольку рассмотрение ситуации начинается с достаточно произвольного элемента, то в итоге мы получаем утверждение относительно не только этого элемента, но и всего множества, которому этот «произвольный» элемент принадлежит. Это общие правила доказательства равенств и включения множеств. B качестве упражнения докажем одно из приведенных ранее равенств, а именно один из законов дистрибутивности: AU(Bnc)^(AUB)n(AUc). Для этого достаточно доказать два включения: AU(Bnc)^(AUB)n(AUc)и(AUB)n(AUc)^AU(Bnc).1. Доказательство включения AU(BПC)^(AUB)П(AUC). Выберем произвольный элемент x&AU(BПC). Тогда x&A или x Доказательство включения (AUB)П(AUC)^AU(BПC).Пусть x&(AUB)П{AUC). Тогда x&AUB и x&AUC. Следовательно, x e A или же x e B и x e C, т. е. x&AU{BПC).Ha этом доказательство равенства двух множеств заканчивается.

недорогие стенки