Дискретная математика (стр. 6 )

2.2 Операции над множествами: объединение, пересечение, дополнение

Рассмотрим достаточно широкое множество, за пределы которого не будем выходить. Такое множество будем называть универсальным и обозначать через I. Природа элементов множества I безразлична. Без ограничения общности будем считать, что множества А, В, С, Х, …, рассматриваемые ниже в определениях и утверждениях данного параграфа, являются подмножествами множества I (напомним, что каждое подмножество основного множества I выделяется из I некоторым отличительным свойством).

Например, можно рассматривать в качестве основного множества I множества R всех действительных чисел, а в качестве А, В, С, Х, … – любые числовые множества. Итак, пусть А и В – произвольные множества.

Определение. Дополнением А ко множеству I называется множество или СА, состоящее из тех и только тех элементов универсального множества I, которые не принадлежат множеству А.

Определение. Объединением множеств А и В называется множество , которое состоит из тех и только тех элементов универсального множества I, каждый из которых принадлежит хотя бы одному из множеств или А или В.

Определение. Пересечением множеств А и В называется множество , которое состоит из тех и только тех элементов, каждый из которых принадлежит и множеству А, и множеству В.

Рассмотрим несколько примеров.

1 , .

Их объединением и пересечением будут множества

, .

2 , .

Получим, что , .

Аналогично определяется объединение и пересечение любого числа множеств. Например, объединение есть множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств А, В, С или D, а пересечение есть множество, состоящее из всех элементов, принадлежащих одновременно всем множествам А, В и С.

Определения и свойства операций над множествами будем для наглядности иллюстрировать рисунками (или так называемыми диаграммами Виенна); условимся изображать основное множество I в виде прямоугольника, а его подмножества А, В, С, … – в виде кругов. Тогда:

здесь заштриховано множество ;

А

здесь заштриховано множество .

Если множества А и В не имеют ни одного общего элемента, то говорят, что они не пересекаются, или что их пересечение есть пустое множество: Ø.

Свойства операций объединения и пересечения

1   ,

2   ,

3   ,

4   ,

5   Если множества А и В таковы, что , то

, ,

В частности, , , , .

Можно заметить, что объединение и пересечение множеств обладают свойствами, аналогичными свойствам суммы и произведения чисел. Например, и , и , и и т. д. однако, далеко не все арифметические правила переносятся на операции над множествами. Например, и для любого множества А, в то время как соответствующие равенства для чисел, очевидно, неверны.

Для любых двух множеств А и В справедливы также равенства:

1 ,

2 ,

которые называются законами де Моргана. Второй закон де Моргана проиллюстрирован ниже.

 

Рассмотренные операции дополнения, объединения и пересечения принято называть булевыми операциями над множествами, и для них справедлива следующая теорема.

Теорема. Множества относительно операций дополнения, объединения и пересечения образуют булеву алгебру множеств, т. е. для них выполняются следующие 19 основных равенств:

0 А – закон двойного дополнения

} – коммутативные законы

} – ассоциативные законы

} – дистрибутивные законы

} – законы идемпотентности

} – законы де Моргана

 

– законы Ø и единицы

} – законы поглощения

17 А I

18 А Ø

Рассмотрим теперь другие (не являющиеся булевыми) операции над множествами.

Пусть А и В – произвольные множества (напомним, что и , где I – универсальное множество).