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

Основные понятия теории множеств.

Понятия «множество», «элемент множества» являются одними из основных, исходных понятий математики. Принято считать, что эти понятия, как и любые другие исходные понятия некоторой математической теории не определяются [24]. Действительно, всякое определение содержит другие понятия, логически предшествующие определяемому, поэтому, по крайней мере, первое определение теории должно содержать не определяемые понятия. В качестве исходных обычно выбираются понятия, в понимании которых не возникает существенных разногласий (возможные разногласия не нарушают правильности ни одного положения теории). Вообще в дискретной математике имеются специальные принципы построения математических теорий.

Под множеством понимают любое собрание определенных и различимых между собой объектов, мыслимых как единое целое. В этом нестрогом, интуитивном определении, принадлежащем одному из родоначальников современной теории множеств – немецкому математику Г. Кантору (1845-1918 гг.) существенным является то обстоятельство, что собрание различных объектов рассматривается как один объект [24]. Нам будет вполне достаточно интуитивного понимания понятий «множество», «быть элементом множества». Объекты, образующие множество, называют элементами множества и обозначают, как правило, строчными, а множества – прописными буквами латинского алфавита.

Для обозначения принадлежности элемента m множеству М будем использовать запись mÎ М, где знак Î является стилизацией первой буквы греческого слова esti (есть, быть) [9-10].

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

Каждое множество полностью задается своими элементами. Для этого можно перечислить элементы конечного множества или указать свойства элементов. Обычно для задания множеств используются фигурные скобки {}. Например:

А={a, b, c, d}

B={i: i – четное число}.

А – конечное множество, состоящее из четырех элементов a, b, c, d. В – бесконечное множество, заданное свойством элементов i, которое записывается справа от двоеточия. По существу это свойство задается так называемым одноместным предикатом Р(i) («быть четным числом»), о которых речь пойдет в дальнейшем. Множество может быть задано также некоторой порождающей процедурой. Весьма распространенной порождающей процедурой является образование множеств из других множеств с помощью операций над множествами.

В множестве могут быть выделены подмножества. Если каждый элемент множества С принадлежит множеству D, то множество С называется подмножеством множества D. Это обозначается как СÍ D (DÊ С), где Í – знак включения (вспомним знак принадлежности Î). Говорят, что множества С и D находятся в отношении включения, а элементы множества к самому множеству – в отношении принадлежности.

Если АÍ В и А¹ В, то А называют собственным, строгим или истинным подмножеством и обозначают АÌ В, где Ì – знак строгого включения.

Для каждого множества М существует множество, элементами которого являются все его подмножества. Такое множество называется булеаном множества и обозначается В(М), а множество М – универсумом (универсальным) и обозначается I [9-10].

Пусть I={a, b}, тогда B(I)={Æ, {a}, {b}, {а, b}}. Для I={a, b, с}, B(I)={Æ, {a}, {b}, {c}, {а, b}, {a, c}, {b, c}, {a, b, с}}.

Множества часто задают графически с помощью диаграмм Эйлера (рис. 1).

Рис. 1. Пример диаграммы Эйлера для множеств

{{а, b, с}, {b, d, e}} в универсуме {а, b, с, d, e}

На рис. 1 заданы множества {{а, b, с}, {b, d, e}} в универсуме I={а, b, с, d, e}, замкнутая линия, называемая кругом Эйлера, соответствует одному из рассматриваемых множеств и ограничивает его элементы, при этом рамка, в верхнем правом углу которой обозначено I, ограничивает элементы универсума (универсального множества).

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

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

АUВ={x: xÎ A или хÎ В},

где U – знак объединения.

На диаграмме Эйлера это может быть показано штриховкой (рис. 2).

Рис. 2. Объединение множеств АUВ

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

АIВ={x: xÎ A и хÎ В},

где I – знак пересечения.

Соответствующая диаграмма Эйлера изображена на рис. 3.

Рис. 3. Пересечение множеств АIВ

Разностью множеств А и В называется множество А\В, состоящее из элементов, принадлежащих множеству А и не принадлежащих множеству В:

А\В={x: xÎ A и х В},

где – знак непринадлежности (отрицание принадлежности), \ – знак разности.

Соответствующая диаграмма Эйлера изображена на рис. 4.

Так, если А={1, 2, 3, 4, 5}, В={4, 6}, то А\В={1, 2, 3, 5}, В\А={6}.

Симметрической разностью множеств А и В называется множество АÅ В=(А\В)U(В\А), изображенное на рис. 5, Å – знак симметрической разности.

Так, если А={1, 2, 3}, В={3, 4, 5}, то АÅ В={1, 2, 4, 5}.

Рис. 5. Симметрическая разность множеств АÅ В

Рассмотренные операции являются двухместными (бинарными). Имеется одноместная (унарная) операция дополнения.

Дополнением множества А является множество , содержащее элементы универсума I, не включенные во множество А:

где – знак дополнения, «инверсия», читается «не А».

Соответствующая диаграмма Эйлера изображена на рис. 6.

Рис. 6. Дополнение множества А до универсума I

Так, если А={3, 4}, а I={1, 2, 3, 4, 5}, то`A={1, 2, 5}.

Используя рассмотренные операции, можно выражать одни множества через другие, при этом сначала выполняется одноместная операция дополнения, затем пересечения и только потом – операция объединения (разности). Для изменения порядка выполнения операций в выражении используют скобки.