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

Алгеброй называется пара множеств А=(М,), где М - называется основным, несущим множеством или носителем алгебры, а ={f(1), f(2), ...} - множество операций, определенных на множестве М, называется сигнатурой алгебры.

Пусть P(J) - булеан универсального множества J. Тогда булевой алгеброй множеств называют алгебру B=(P(J),), где ={ , , }, т.е. множество, включающее в себя операции объединения, пересечения и дополнения.

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

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. Закон двойного отрицания. =A

11. A B=B A

12. A\B = A

13. A B=( B) (A )

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

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

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

Покажем, что NM.

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

Покажем, что MN.

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

Замечание.

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

Двойственность в алгебре множеств.

Операция объединения является двойственной к операции пересечения и наоборот, операция пересечения является двойственной к операции объединения. Операция дополнение является двойственной сама к себе (самодвойственной). Пустое множество является двойственным к универсальному множеству и наоборот, универсальное множество является двойственным к пустому множеству.

Если в формуле алгебры множеств F используются лишь операции из сигнатуры алгебры, а так же среди множеств могут присутствовать пустое и универсальное множества, то формула F*, получающаяся из формулы F заменой каждого символа на двойственный, называется формулой двойственной к F. Принцип двойственности в алгебре множеств заключается в том, что если справедливо тождество F=R, то справедливо и двойственное тождество F*=R*. Выполнимость принципа двойственности иллюстрируют вышеприведенные законы алгебры множеств.