ответы к экзамену по дискретной математике

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

Алгеброй множеств⁷⁾ называется пара , где — некоторая совокупность множеств, а — набор операций над множествами. Обычно полагают, что — множество всех подмножеств универсума , а в качестве берут рассмотренные выше операции

Законы алгебры множеств.

1. Коммутативность.

относительно операции объединения, относительно операции пересечения.

А В=В А А В=В А

2. Ассоциативность.

относительно операции объединения, относительно операции пересечения.

А (В С)=(А В) С А (В С)=(А В) С

3. Дистрибутивность.

пересечения относительно объединения, объединения относительно пересечения.

А (В С)=( А В) (А С) А (В С)=( А В) (А С)

4. Закон де Моргана.

относительно объединения, относительно пересечения.

= =

5. Законы поглощения.

относительно объединения, относительно пересечения.

A (A B)=A A (A B)=A

A ( В )= А В A ( B)= А В

6. A A=A A A=A

7. A =J A =

8. A =A A J=A

9. A J=J A =

10. Закон двойного отрицания.

11. A B=B A

12. A\B = A

13. A B=( B) (A )

Все эти законы могут быть доказаны с помощью поэлементной схемы доказательства.

Покажем, например, справедливость закона 12.

Пусть N= A\B, M= A .

Покажем, что N M.

Пусть x A\B, т.е. x A и x B. Так как x B, то x . Отсюда x A и x , т.е. x A =M.

Покажем, что M N.

Пусть x M= A , т.е. x A и x . Отсюда x A и x B, т.е. x A\B =N.

Замечание.

Для сокращения записи в дальнейшем будем считать, что операция пересечение “сильнее” чем объединение, разность, симметрическая разность, поэтому, там где это возможно мы будем опускать скобки. Кроме того, иногда мы будем опускать знак операции пересечения (как в алгебре знак операции умножения). Так, например, запись ABC\B означает (A B C)\C. Здесь кроме выше оговоренных правил применен закон ассоциативности, позволяющий опускать скобки при выполнении последовательности операций объединения или пересечения множеств.