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

Операция Â(А₁, А₂, ... , А_k)=В сопоставляет нескольким множествам A₁, A₂,...,A_k множество B - результат операции. Число k называется арностью операции Â.

Одну операцию мы уже ввели – операцию дополнения. Её арность равна 1 (унарная операция).

Пусть даны два множества A и B и множество C является результатом операции над ними (бинарная операция). Перечислим элементарные бинарные операции:

- пересечение множеств С = А ÇВ, если С={с½c Î А & с ÎВ }. Эту операцию называют еще умножением множеств или операцией И;

- объединение множеств С = АÈВ, если С={с | сÎА | сÎВ}. Другое название операции - сложение множеств или операция ИЛИ ;

- разность множеств C = A\B, если С={с | с ÎА & с ÏВ}. Иначе операцию называют А без В;

- симметрическая разность C = ADВ, если С={с| сÎА\В È сÎВ\А}.

Результат любой описанной операции снова является множеством той же предметной области, его можно использовать в качестве аргумента операций над множествами. Таким образом, можно строить сложные формулы, описывающие множество через другие множества. Например, (А Ç`В) È (`А Ç В ÇС).

Две формулы эквивалентны, если им соответствуют равные множества. Обозначим это как F1=F2.

Операции на множествах можно графически представить в виде кругов Эйлера, когда множествам сопоставляются замкнутые фигуры на плоскости, взаимное расположение которых определяет результат операции (рис. 1.1). Так, пересечение двух фигур, сопоставленных

множествам AиB,образует новую замкнутую фигуру, соответствующую общей части фигурАиВ– результату операции пересечения, и т.п.

Разбиением или покрытием множества А называют множество его подмножеств {A₁, A₂, ..., A_k} такое, что имеет место (A₁È A₂È ... ÈA_k)=A, и для любой пары подмножеств А_i Ç A_j=Æ, если i ¹j . При этом говорят, что множество А разбито на подмножества A₁, A₂, ...,A_k или покрыто подмножествами A₁, A₂, ..., A_k, а подмножества А₁, А₂,... называются классами разбиения или классами покрытия. Выбор того или другого термина определяется смыслом предметной задачи.

1.3. Свойства операций

1. А Ç А=А - идемпотентность операции пересечения.

2. А Ç В = В ÇА - коммутативность операции пересечения.

3. А Ç(В ÇС) = (А ÇВ) ÇС - ассоциативность операции пересечения.

4. Свойства 1-3 имеет также операция È .

5. А Ç (В È С) = (А Ç В) È (А Ç С) - дистрибуция операции пересечения по отношению к операции объединения. Справедливо также свойство дистрибуции для операции объединения относительно операции пересечения.

6. Дополнение дополнения множества равно множеству, т.е. ~ ~А=А.

7. Равенства де Моргана ~(А Ç В ) = ~ А È ~В, ~( А ÈВ ) = ~А Ç~В.

8. Для любого множества А Ç U = А, А Ç Æ = Æ, A È Æ = A, A È U = U, А Ç~A = Æ; A È~A = U; A\A = Æ.

Представленные в свойствах равенства используют для преобразования формул. Если в формуле заменить множество равным ему множеством, получится формула, равносильная исходной. Таким образом, можно в формулах удалять одинаковые члены (свойство 1), выносить за скобки или раскрывать скобки (свойство 4) и т.п.

Пример. (А ÇВ ÇС) È( А ÇВ Ç~С) = (А ÇВ) Ç(~C ÈC) =A ÇB.