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

В нашем курсе считаем неопределяемыми три понятия:

1) множество; 2) элемент; 3) принадлежность.

Будем обозначать множества заглавными буквами, элементы множества – строчными, например, А – множество; a, b, c – элементы, при этом, если элемент a принадлежит множеству A, пишем , если элемент c не принадлежит множеству A, пишем .

Задавать множества можно различными способами, например, перечислив все его элементы: , причем порядок записи элементов безразличен. Часто задают множество, указав его характеристическое свойство, которое для каждого элемента позволяет выяснить, принадлежит ли он множеству или нет, например:

B={xçx - целый корень уравнения },

C={ x - целое}.

В дальнейшем будем использовать следующие обозначения для числовых множеств: N - множество натуральных чисел, N={1,2,3,...}; Z - множество целых чисел, Z={...-2,-1,0,1,2,3,...}; Q - множество рациональных чисел; R - множество действительных чисел.

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

Пустым множеством называется множество Æ, обладающее свойством: при любом x.

Универсальным множеством называется множество U всех рассматриваемых в данной задаче элементов.

Пример. В задаче: найти все решения уравнения - ответы будут разными в зависимости от того, какое множество рассматривается как универсальное. Если U=Z, то множество решений M=Æ; если U=R, то .

Будем говорить, что множество A включается во множество B , если каждый элемент множества A является элементом множества B. Из определения включения непосредственно следуют свойства:

1) для любого множества A;

2) если и , то ;

3) для любого множества A;

4) для любого множества A.

Подмножество называется собственным подмножеством множества B ( - строгое включение), если A не пусто и не совпадает с B. Например: .

На основе понятия включения можно определить равенство множеств: A=B тогда и только тогда, когда одновременно выполняются два включения и , т.е.

(1.1)

Свойства равенства множеств:

1) для любого A справедливо A=A;

2) если A=B, то и B=A;

3) если A=B и B=C, то A=C.

Взаимное расположение множеств изображается с помощью диаграмм Эйлера-Венна, на которых универсальное множество изображается прямоугольником, а произвольные множества, являющиеся подмножествами универсального - кругами.

При этом возможны следующие случаи взаимного расположения двух множеств A и B:

1) одно из множеств строго включается в другое ( или );

2) множества равны;

3) множества не имеют общих элементов;

4) множества находятся в общем положении, т.е. не подходит ни один из вышеперечисленных случаев, а множества имеют общие элементы, не равны, и ни одно из них не является подмножеством другого.

Диаграммы Эйлера-Венна применяются для изображения операций над множествами.

Объединением множеств A и B называется множество , состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств A или B (заштрихуйте объединение множеств на рис.1.1,а). Пусть A={0,1,2}, B={-1,2,3}, тогда .

		U

Пересечением множеств A и B называется множество , состоящее из тех и только тех элементов, которые принадлежат одновременно и множеству A, и множеству B (заштрихуйте пересечение множеств на рис.1.1,б). Если A={0,1,2},B={-1,2,3}, то .

Разностью множества A и B называется множество A\B тех и только тех элементов, которые принадлежат множеству A и не принадлежат множеству B (рис.1.2,а). Пример:

Дополнением множества A до универсального U называется множество (рис.1.2,б).

Симметрической разностью множеств A и B называется множество или . Нарисуйте диаграмму Эйлера-Венна для симметрической разности.

Элементы множества могут сами быть множествами: A={{1,2},{2,3},{4,5,6}}, в таком случае удобно говорить о семействе множеств. Рассмотрим некоторые семейства множеств: булеан множества, покрытие, разбиение множества.

Булеаном B(X) множества X называется множество всех подмножеств множества X. Например, для множества X={0,1} булеаном является множество .

Разбиением R(X) множества X называется семейство его непустых непересекающихся подмножеств, в объединении дающая множество X, т.е. разбиение множества X есть множество такое, что: 1)

2)

3)

Например, для множества X={1,2,3,4,5} можно построить разбиение , состоящее из двух элементов - они называются блоками разбиения, или - из четырех блоков; возможны и другие разбиения.

Покрытием множества X называется система его непустых подмножеств, в объединении дающая множество X. Здесь отсутствует слово “непересекающаяся” - т.е. блоки покрытия могут иметь общие элементы. Пример покрытия для множества X={1,2,3,4,5}: .

Задача 1. Задано универсальное множество U={1,2,3,4,5,6,7} и множества X={2,4,6}, Y={1,3,5,7}, Z={2,3,5,6}. Выполнить действия: Построить булеан множества X, какое-либо разбиение множества Y, какое-либо покрытие множества Z.

Решение. Выполним операции над множествами в следующем порядке:

- по определению операции дополнения;

- по определению пересечения множеств;

- по определению объединения множеств.

Для построения булеана множества X воспользуемся двоичной записью числа. Если множество X содержит n элементов, его булеан содержит элементов – подмножеств множества Х (в нашем случае 8 подмножеств). Будем записывать номер подмножества трехразрядным двоичным числом от 0 до 7, включая в подмножество только те элементы, которым соответствуют единицы в записи двоичного числа. В табл.1.1 приведены построенные таким образом все подмножества множества X.

Таблица 1.1 Булеан множества X

Для множества Y построим разбиение из трех блоков где Проверим выполнение определения:

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

Здесь и следовательно, система - покрытие множества Z.

Операции над множествами так же, как операции в обычной алгебре, выполняются по законам (табл.1.2), которые доказываются на основе введенных выше определений.

Задача 2. Доказать закон дистрибутивности

(1.2)

Решение. Обозначим X левую часть равенства (1.2), Y - правую. Согласно определению (1.1) покажем, что выполняются одновременно

Пусть x - произвольная точка из Тогда по определению объединения множеств Далее по определению пересечения множеств Следовательно,

Таким образом, для любого выполняется т.е.

Докажем теперь, что Пусть y - произвольная точка из множества Тогда

В силу произвольности заключаем

Таким образом, и , следовательно X=Y, и закон дистрибутивности доказан.

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

Таблица 1.2 Законы алгебры множеств

№	Формула	Название
		свойства пустого множества
		свойства универсального множества
		Закон коммутативности
		Закон ассоциативности
		Закон дистрибутивности
		Закон двойного дополнения
		Закон идемпотентности
		Закон де Моргана
		Закон поглощения

Задача 3. Упростить выражение, пользуясь законами алгебры множеств:

Решение. Выполним преобразования, указывая номер закона (табл.1.2) над знаком равенства:

а)

б)

в)

Ответ: