Операции над множествами, их свойства. Связь с логическими законами.

Операции над множествами.

Операции над множествами подразумевают то или иное комбинирование элементов этих множеств. Поэтому операции можно выполнять только над множествами объектов, которые принадлежат одному и тому же универсуму: AÌ U, BÌ U.

На конечном универсуме U, состоящем из элементов x, мы можем создать 2^{| U |} различных множеств, включая сам универсум и пустое множество Æ.

Объединение множеств AÈB есть множество элементов x, принадлежащих либо A, либо B: AÈB={ x | x ÎAÚ x ÎB}.

Пересечение множеств AÇB есть множество элементов x, принадлежащих одновременно A и B: AÇB={ x | x ÎA& x ÎB}.

Разность множеств A\B есть множество элементов x, принадлежащих A, но не принадлежащих B: A\B={ x | x ÎA& x ÏB}.

Симметрическая разность множеств ADB есть множество элементов x, принадлежащих либо A, либо B, но не принадлежащих A и B одновременно: ADB= (AÈB)\(AÇB)={ x |(x ÎA& x ÏBÚ x ÎB& x ÏA}.

Дополнением множества A называется множество ={ x|x Ï A }. Дополнение рассматривается относительно универсума:

Любой последовательности операций над множествами можно сопоставить логическую формулу, где логическими переменными являются предикаты принадлежности элементов множествам. Этот способ выполнения операций над множествами иногда называют методом характеристических функций [2].

Связь с логическими операциями.

AÈB={ x | x ÎAÚ x ÎB}={ x | a Ú b } Û дизъюнкция: a Ú b.

AÇB={ x | x ÎA& x ÎB}={ x | a & b } Û конъюнкция a × b.

A\B={ x | x ÎA& x ÏB}= Û разность:

ADB= (AÈB)\(AÇB)={ x |(x ÎA& x ÏBÚ x ÎB& x ÏA}= сложение по модулю 2:

={ x|x ÏA}= Û отрицание: .

Свойства операций над множествами.

Введем обозначения: a =«x ÎA», b =«x ÎB» и рассмотрим последовательно все логические законы.

1. Закон отрицания отрицания: . Согласно нашим обозначениям, = «x ÏA», а мы знаем, что - дополнение множества A до универсума: . Тогда Отсюда . Это свойство операции над множествами иногда называют инволютивностью [1].

2. Коммутативность, ассоциативность и дистрибутивность операций над множествами вытекают из соображения, что предикаты принадлежности, через которые мы определяем эти операции, не задают никакого правила расположения элементов внутри самих множеств. Следовательно, «x ÎAÚ x ÎB»Û«x ÎBÚ x ÎA» Þ AÈB=BÈA (коммутативность объединения). Аналогичные рассуждения можно провести и для двух других операций.

3. Закон нуля и единицы: ={ x | x Î A & x Ï A }={ x | }=Æ, поскольку выражение является противоречием. ={ x | x Î A Ú x Ï A }={ x | }= U, поскольку - тождество. A Ç U = U, A È U = U, так как A Ì U. , так как .

4. Законы де Моргана. Покажем, что . Пусть Q={ x | x Î }. Это означает, что x ÏAÇB. Значит, либо x Ï A, либо x Ï B. Перейдем к записи этого условия через предикаты принадлежности и получим: С другой стороны, в соответствии с записью операции пересечения через предикаты принадлежности, имеем: То есть , откуда и получаем . Точно так же можно показать, что .

5. Законы поглощения. A È(A Ç B)={ x | x Î A Ú(x Î A & x Î B)}, а поскольку Q ={ x | x Î A & x Î B }ÌA, то множество A можно рассматривать по отношению к Q как универсум. Используя закон нуля и единицы, имеем: A È Q = A. Следовательно, A È(A Ç B)= A. Аналогично можно получить, что A Ç(A È B)= A.

6. Законы склеивания. . Воспользуемся дистрибутивным законом: . Применив к левой скобке в операции объединения закон поглощения, а к правой – еще раз дистрибутивный закон, а затем закон нуля и единицы, имеем: . Еще раз применяем закон поглощения и получаем Q = A. В качестве упражнения, покажите самостоятельно, что .

Пример 1. Найти результат следующих операций над множествами A,B,C:

Q =((A D B)È(B Ç C))\(A Ç C).

Введем обозначения: a =«x Î A», b =«x Î B», с =«x ÎС» и запишем данное выражение в предикатной форме:

Q ={ x |((a Å b)Ú b × c)- a × c }.

Выполним преобразования над логическим условием, используя представление логических операций через ДНФ и логические законы: После преобразования получаем: .

Пример 2. Показать, что ((B D C)\ A)Ç(A D C)Ì С.

Выполним операции над множествами через преобразование соответствующего этим операциям логического выражения:

Отсюда имеем, что , то есть Q является подмножеством C.