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

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

1. Объединением множеств А и В называется множество АВ, все элементы которого являются элементами хотя бы одного из множеств А или В:

АВ = {x / x АﭙxВ}.

Из определения следует, что А  АВ и В  АВ.

Аналогично определяется объединение нескольких множеств

2. Пересечением множеств А и В называется множество АВ, все элементы которого являются элементами обоих множеств А и В:

АВ = {x / x А xВ}.

Из определения следует, что АВ  А, АВ  В и АВ  АВ.

Аналогично определяется пересечение нескольких множеств.

Может оказаться, что множества не имеют ни одного общего элемента. Тогда говорят, что множества не пересекаются или что их пересечение – пустое множество.

3. Разностью множеств A и B называется множество А \ В, все элементы которого являются элементами множества А, но не являются элементами множества В:

А \ В = {x / x А xВ}.

4. Симметрической разностью множеств А и В называется множество А + В:

А + В = (А \ В)  (В \ А).

Универсальным множеством называется такое множество U, что все рассматриваемые в данной задаче множества являются его подмножествами.

5. Дополнением множества А называется множество всех таких элементов x  U, которые не принадлежат множеству А: = U \ A.

Примеры.

1. Пусть А = {4, 5, 6}, В = {2, 4, 6}. Тогда АВ = {2, 4, 5, 6}.

2. Пусть А – множество чисел, которые делятся на 2, а В – множество чисел, которые делятся на 3: А = {2, 4, 6, …}, В = {3, 6, 9, …}. Тогда АВ множество чисел, которые делятся на 2 или на 3: АВ = {2, 3, 4, 6, 8, 9, 10, …}.

3. Пусть А = {4, 5, 6}, В = {2, 4, 6}. Тогда АВ = {4, 6}.

4. Пусть А – множество чисел, которые делятся на 2, а В – множество чисел, которые делятся на 3: А = {2, 4, 6, …}, В = {3, 6, 9, …}. Тогда АВ множество чисел, которые делятся и на 2 и на 3: АВ = {6, 12, 18, …}.

5. Пусть А = {1, 2}, В = {2, 3}, C = {3, 4}. Тогда АВC =.

6. А = {4, 5, 6}, В = {2, 4, 6}. Тогда А \ В = {4, 5}, В \ А= {2}.

7. А = {2, 4, 6, …}, В = {3, 6, 9, …}. Тогда А \ В – множество чисел, которые делятся на 2, но не делятся на 3, а В \ А – множество чисел, которые делятся на 3, но не делятся на 2: А \ В = {2, 4, 8, 10, 14, …}. В \ А= {3, 9, 15, 21, 27, …}.

8. Пусть А = {4, 5, 6}, В = {2, 4, 6}. Тогда А \ В = {4, 5}, В \ А= {2}, А + В = {2, 4, 5}.

9. А = {2, 4, 6, …}, В = {3, 6, 9, …}, А \ В = {2, 4, 8, 10, 14, …}. Тогда В \ А= {3, 9, 15, 21, 27, …}, А + В = {2, 3, 4, 8, 9, …}.

3. Геометрическое моделирование множеств. Диаграммы Венна

Для наглядного представления множеств и отношений между ними используется диаграммы Венна (иногда их называют кругами Эйлера или диаграммами Эйлера – Венна).

Универсальное множество изображают в виде прямоугольника, а множества, входящие в универсальное множество, – в виде кругов внутри прямоугольника; элементу множества соответствует точка внутри круга (рис 1а).

С помощью диаграмм Венна удобно иллюстрировать операции над множествами.

Рисунок 1. Диаграммы Венна для основных операций над множествами.

4. Соотношение между множествами и составными высказываниями

Существует тесная связь между множествами — с одной стороны, и высказываниями — с другой, а также между операциями над множествами, с одной стороны, и операциями образования составных высказываний — с другой.

Пусть X, Y, Z,... некоторые высказывания, и пусть U — их множество логических возможностей. Пусть А, В, С,... подмножества U, для которых истинны соответственно высказывания X, Y, Z,.... Тогда А, В, С,... называются соответственно множествами истинности высказываний X, Y, Z,....

Если X и Y — высказывания, то ХY и ХY также высказывания, следовательно, они должны иметь множества истинности. Чтобы найти множество истинности высказывания ХY, необходимо поставить в соответствие логические возможности, которые лежат в А или в В (или в них обоих); то есть, поставить в соответствие ХY множество AB. С другой стороны, высказыванию ХY можно поставить в соответствие множество АВ.

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

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

Мы рассмотрели такие множества истинности составных высказываний, которые образованы посредством связок , , . Все остальные связки можно определить через эти три основные и тем самым вывести, какие множества истинности им соответствуют.

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

Предположим теперь, что X — логически истинное высказывание. Поскольку высказывание X логически истинно тогда и только тогда, когда оно истинно в каждом логически возможном случае, множеством истинности для высказывания X должно быть универсальное множество U. Подобным же образом, если высказывание X логически ложно, то оно ложно в каждом логически возможном случае, и поэтому его множеством истинности будет пустое множество .

Рассмотрим отношение следствия, реализуемое операцией импликации. Высказывание X Y тогда и только тогда логически истинно, когда его множество истинности совпадает с U, т. е. и A\B = . Но если A\B пусто, то В включает в себя А. Отношение включения читается «А является подмножеством В». Таким образом, высказывание X Y логически истинно тогда и только тогда, когда АВ.

Таким образом, каждому высказыванию соответствует его множество истинности, каждой логической связке соответствует операция над множеством. Каждому отношению между высказываниями соответствует отношение между множествами истинности. Множествами истинности высказываний ХY, ХY, и X Y служат соответственно:

AB, АВ, ,

Высказывание X логически истинно, если А = U, и логически ложно, если А =. Высказывание X и Y эквивалентны тогда и только тогда, когда А = В; из X следует Y тогда и только тогда, когда АВ.