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

Множество - это совокупность объектов, рассматриваемая как одно целое. Понятие множества принимается за основное, т. е. не сводимое к другим понятиям. Объекты, составляющие данное множество, называются его элементами. Основное отношение между элементом a и содержащим его множеством A обозначается так (a есть элемент множества A ; или a принадлежит A , или A содержит a ). Если a не является элементом множества A , то пишут (a не входит в A , A не содержит a ). Множество можно задать указанием всех его элементов, причем в этом случае употребляются фигурные скобки. Так {a , b , c } обозначает множество трех элементов. Аналогичная запись употребляется и в случае бесконечных множеств, причем невыписанные элементы заменяются многоточием. Так, множество натуральных чисел обозначается {1, 2, 3, ...}, а множество четных чисел {2, 4, 6, ...}, причем под многоточием в первом случае подразумеваются все натуральные числа, а во втором - только четные.

Два множества A и B называются равными , если они состоят из одних и тех же элементов, т. е. A принадлежит B и, обратно, каждый элемент B принадлежит A . Тогда пишут A = B . Таким образом, множество однозначно определяется его элементами и не зависит от порядка записи этих элементов. Например, множество из трех элементов a , b , c допускает шесть видов записи:

{a , b , c } = {a , c , b } = {b , a , c } = {b , c , a } = {c , a , b } = {c , b , a }.

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

Если каждый элемент множества A входит во множество B , то A называется подмножеством B , а B называется надмножеством A . Пишут (A входит в B или A содержится в B , B содержит A ). Очевидно, что если и , то A = B . Пустое множество по определению считается подмножеством любого множества.

Если каждый элемент множества A входит в B , но множество B содержит хотя бы один элемент, не входящий в A , т. е. если и , то A называется собственным подмножеством B , а B - собственным надмножеством A . В этом случае пишут . Например, запись и означают одно и то же, а именно, что множество A не пусто.

Заметим еще, что надо различать элемент a и множество {a }, содержащее a в качестве единственного элемента. Такое различие диктуется не только тем, что элемент и множество играют неодинаковую роль (отношение не симметрично), но и необходимостью избежать противоречия. Так, пусть A = {a , b } содержит два элемента. Рассмотрим множество {A }, содержащее своим единственным элементом множество A . Тогда A содержит два элемента, в то время как {A } - лишь один элемент, и потому отождествление этих двух множеств невозможно. Поэтому рекомендуется применять запись , и не пользоваться записью .

В математике понятие множества является одним из основных, фундаментальным, однако единого определения множества не существует. Одним из наиболее устоявшихся определений множества является следующее: под множеством понимают любое собрание определённых и отличных друг от друга объектов, мыслимых как единое целое. Создатель теории множеств немецкий математик Георг Кантор (1845-1918) говорил так: "Множество есть многое, мыслимое нами как целое".

Множества как тип данных оказались очень удобными для программирования сложных жизненных ситуаций, так как с их помощью можно точно моделировать объекты реального мира и компактно отображать сложные логические взаимоотношения. Множества применяются в языке программирования Паскаль и один из примеров решения мы ниже разберём. Кроме того, на основе теории множества создана концепция реляционных баз данных, а на основе операций над множествами - реляционная алгебра и её операции - используемые в языках запросов к базам данных, в частности, SQL.

Пример 0 (Паскаль). Существует набор продуктов, продаваемых в нескольких магазинах города. Определить: какие продукты есть во всех магазинах города; полный набор продуктов в городе.

Решение. Определяем базовый тип данных Food (продукты), он может принимать значения, соответствующие названиями продуктов (например, hleb). Объявляем тип множества, он определяет все подмножества, составленные из комбинаций значений базового типа, то есть Food (продукты). И формируем подмножества: магазины "Солнышко", "Ветерок", "Огонёк", а также производные подмножества: MinFood (продукты, которые есть во всех магазинах), MaxFood (полный набор продуктов в городе). Далее прописываем операции для получения производных подмножеств. Подмножество MinFood получается в результате пересечения подмножеств Solnyshko, Veterok и Ogonyok и включает те и только те элементы этих подмножеств, которые включены в каждое их этих подмножеств (в Паскале операция пересечения множеств обозначается звёздочкой: A * B * C, математическое обозначение пересечения множеств дано далее). Подмножество MaxFood получается в результате объединения тех же подмножеств и включает элементы, которые включены во все подмножества (в Паскале операция объединения множеств обозначается знаком "плюс": A + B + C, математическое обозначение объединения множеств дано далее).

Код PASCAL

Program Shops; type Food=(hleb, moloko, myaso, syr, sol, sahar, maslo, ryba); Shop = set of Food; var Solnyshko, Veterok, Ogonyok, MinFood, MaxFood: Shop; Begin Solnyshko:=; Veterok:=; Ogonyok:=; ... MinFood:=Solnyshko * Veterok * Ogonyok; MaxFood:=Solnyshko + Veterok + Ogonyok; End.

Какие бывают множества

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

Натуральных чисел 0, 1, 2, 3, 4, ...

Простых чисел

Чётных целых чисел

и т.п. (основные числовые множества рассмотрены в этого материала).

Объекты, составляющие множество, называются его элементами. Можно сказать, что множество - это "мешок с элементами". Очень важно: в множестве не бывает одинаковых элементов.

Множества бывают конечными и бесконечными. Конечное множество - это множество, для которого существует натуральное число, являющееся числом его элементов. Например, множество первых пяти неотрицательных целых нечётных чисел является конечным множеством. Множество, не являющееся конечным, называется бесконечным. Например, множество всех натуральных чисел является бесконечным множеством.

Если M - множество, а a - его элемент, то пишут: a ∈M , что означает "a принадлежит множеству M ".

Из первого (нулевого) примера на Паскале с продуктами, которые есть в тех или иных магазинах:

hleb ∈VETEROK ,

что означает: элемент "hleb" принадлежит множеству продуктов, которые есть в магазине "VETEROK".

Существуют два основных способа задания множеств: перечисление и описание.

Множество можно задать, перечислив все его элементы, например:

VETEROK = {hleb , syr , maslo } ,

A = {7 , 14 , 28 } .

Перечислением можно задать только конечное множество. Хотя можно сделать это и описанием. Но бесконечные множества можно задать только описанием.

Для описания множеств используется следующий способ. Пусть p (x ) - некоторое высказывание, которое описывает свойства переменной x , областью значений которых является множество M . Тогда через M = {x | p (x )} обозначаентся множество, состоящее из всех тех и только тех элементов, для которых высказывание p (x ) истинно. Это выражение читается так: "Множество M , состоящее из всех таких x , что p (x ) ".

Например, запись

M = {x | x ² - 3x + 2 = 0}

Пример 6. Согласно опросу 100 покупателей рынка, купивших цитрусовые, апельсины купили 29 покупателей, лимоны - 30 покупателей, мандарины - 9, только мандарины - 1, апельсины и лимоны - 10, лимоны и мандарины - 4, все три вида фруктов - 3 покупателя. Сколько покупателей не купили ни одного вида перечисленных здесь цитрусовых? Сколько покупателей купили только лимоны?

Операция декартова произведения множеств

Для определения ещё одной важной операции над множествами - декартова произведения множеств введём понятие упорядоченного набора длины n .

Длиной набора называется число n его компонент. Набор, составленный из элементов , взятых именно в этом порядке, обозначается . При этом i я () компонента набора есть .

Сейчас последует строгое определение, которое, возможно, не сразу понятно, но после этого определения будет картинка, по которой станет понятно, как получить декартово произведение множеств.

Декартовым (прямым) произведением множеств называется множество, обозначаемое и состоящее из всех тех и только тех наборов длины n , i -я компонента которых принадлежит .

Например, если , , ,

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

Естественно, что два множества могут иметь одинаковые элементы (их можно выделить в отдельное множество), из всех элементов двух множеств можно составить одно новое множество, также можно рассмотреть отдельно элементы одного множества, которых во втором множестве нет.

Например, А – множество наклеек (марок), которые есть у Пети, В – множество наклеек, которые собрал Вася. Можно выделить множество наклеек, которые есть у обоих ребят; коллекцию различных наклеек, собранных ими вместе; множество наклеек Пети, которых нет у Васи.

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

Опр.2.3.1. Пересечением множеств А и В называется множество С, состоящее из всех тех и только тех элементов, которые принадлежат каждому из данных множеств: С={х |хÎА и хÎВ}. Обозначается, А∩В.

Примеры. 1) Пусть A = {1; 2; 3}, B = {2; 3; 4; 5}, D = {10; 11}, тогда A ∩ B = {2; 3}, A ∩ D = Æ.

2) А = {2n: n Î N } - множество чисел, делящихся на 2, B = {3n: n Î N} - множество чисел, делящихся на 3, тогда A ∩ B = {6n | n Î N} - множество чисел, делящихся на 6.

3) А - отрезок , В - отрезок , тогда A ∩ B - отрезок .

4) Студент, сдавший все экзамены на «отлично» получает повышенную стипендию. Сессия состоит из четырех экзаменов. Пусть Аi – множество студентов, сдавших i -й экзамен на «отлично» (i = 1, 2, 3,4), тогда:

I – множество студентов, получающих повышенную стипендию.

Опр. 2.3.2. Объединением множеств А и В называется множество С, которое состоит из всех элементов данных множеств А и В и только из них: С={х |хÎА или хÎВ}. Обозначается, А UВ.

Примеры. 1) A = {1; 2; 3}, B = {2; 3; 4; 5}, тогда C = A U B == {1; 2; 3; 4; 5}.

2) A = (–∞, 2], B = (1, +∞), тогда C = A U B = R .

3) А = , В = , тогда A U B = .

3) Если А – множество студентов, не сдавших первый экзамен, В – второй, то А U В – множество студентов – задолжников после двух экзаменов (не исключено, что кто-то не сдал оба экзамена).

Опр.2.3.3. Разностью множеств А и В называется множество С, состоящее из всех элементов множества А, не принадлежащих множеству В: С={х | х Î А и х Ï В}. Обозначается, А\В.

Примеры 1) A = {1; 2; 3}, B = {2; 3; 4; 5}, тогда А\В={1}, В\А={4, 5}.

2) R \ Q – множество иррациональных чисел.

3) Q \ R = Æ.

Опр.2.3.4 . Симметричной разностью множеств А и В называется множество С, состоящее из всех элементов множества А, не принадлежащих множеству В и всех элементов множества В, не принадлежащих множеству А: С={х | (х Î А и х Ï В) или (х Î В и х Ï А) }. Обозначается, А∆В.

Пример. А={1,2,3,4,5}, В={4,5,6,7}, А∆В= {1,2,3,6,7}

В каждом отдельном случае мы рассматриваем всевозможные подмножества одного и того же множества. Например, в начальной школе дети учатся работать (выполнять основные арифметические операции) сначала с числами из первого десятка натуральных чисел, затем из первой сотни и т.д. Но их действия не выходят за рамки натуральных чисел (отрицательные и дробные числа они будут проходить позже). Аналогично, учитель может работать с некоторыми группами учеников, которые будут являться подмножествами определенного множества обучаемых данным учителем школьников. Каждый человек носит различные комбинации вещей, но только из своего личного гардероба. Это основное множество (свое в каждом отдельном случае) называется универсальным множеством.

Опр.2.3.5. Универсальным множеством называется множество, подмножества которого (и только они) в данный момент рассматриваются. Обозначают, Е (или U в разной литературе).

При работе с числовыми множествами, если не дается дополнительных указаний, в качестве основного (универсального) множества будем считать множество R действительных чисел.

Опр.2.3.6. Дополнением множества А называется разность Е \А. Обозначается, А’ или и читается «не-А». Иначе, дополнением множества А называется множество А’, состоящее из всех элементов, не принадлежащих множеству А.

Примеры. 1) Е ={ множество студентов в группе}, A ={ множество студентов, сдавших первый экзамен}, то А’ ={ множество студентов, не сдавших первый экзамен}.

2) Е={буквы русского алфавита}, А={множество гласных букв}, тогда

А’={множество согласных букв и букв ь и ъ}.

3) Пусть Е – множество сотрудников школы, A – множество сотрудников старше 30 лет, B – множество сотрудников мужского пола, C – множество сотрудников занимающих должности вспомогательного персонала.

Тогда В ’ – множество женщин; А’ÇВÇC – множество мужчин занимающих должности вспомогательного персонала младше 30 лет; А È(В ÇС ’) – множество сотрудников старше 30 лет или мужчин не занимающих должности вспомогательного персонала; B \C – множество мужчин, не являющихся вспомогательным персоналом; C \B – множество сотрудников вспомогательного персонала – женщин.

4) Даны множества А={2, 3, 5, 8, 13, 15}, В={1, 3, 4, 8, 16}, С={12, 13, 15, 16}, D={0, 1, 20}. Найти АUВ, СUD, В∩С, А∩D, А\С, D\В, АUВUС, А∩В∩С, ВUD∩С, А∩С\D.

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

Получим АUВ={1, 2, 3, 4, 5, 8, 13, 15, 16};

СUD={0, 1, 12, 13, 15, 16, 20};

А\С={2, 3, 5, 8};

АUВUС={1, 2, 3,4, 5, 8, 12, 13, 15, 16};

А∩В∩С=Æ;

ВUD∩С={1, 3, 4, 8, 16};

А∩С\D={13, 15}.

5) Пусть Е={1, 2, 3, 4, 5, 6, 7, 8,9}, A={1, 2, 3, 5}, B={2, 4, 6, 8}, C={1, 3, 5, 7}, D={4, 5, 7, 8}. Выразить через заданные множества A, B, C, D следующие множества: 1) К={1,2,3,4,5,7,8}, 2) L={4, 7 ,8}, 3) F={2, 5}, 4) G={5, 7, 9}.

Решение : 1) K={1,2,3,4,5,7,8}=AUD.

2) L={4, 7 ,8}=D\A.

б) A\(C\D)={2, 5}.

б) AUB={1, 2, 3, 4, 5, 6, 8},

в) (AUB)’={7, 9},

г) (A∩D)U((AUB)’)={5, 7, 9}.

Свойства операций над множествами:

Таблица 2.3.1.

Свойства операции пересечения: 1) А∩А=А; 2) А∩Ø=Ø; 3) А∩А’= Ø; 4) А∩Е =А; 5) А∩В=В∩А.	Свойства операции объединения: 1) АUА=А; 2) АU Ø =А; 3) АUА’=Е ; 4) АUЕ =Е ; 5) АUВ=ВUА.
Свойства операции разности:
1) А\А=Ø; 2) А\ Ø =А; 3) А\А’= А; 4) А\Е =Ø;	5) Е \А=А’; 6) Ø \А=Ø; 7) А\В ≠ В\А.

§ 2.4. Диаграммы Эйлера-Венна, таблицы вхождения элементов, координатная плоскость.

Для наглядного представления (графического изображения) множеств и результатов операций над ними удобно пользоваться так называемыми диаграммами Эйлера-Венна (кругами Эйлера).

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

Таблица 2.4.1.

Объединение АВ:

Пересечение А∩В:

Разность: А\В

Примеры: Изобразить следующие множество с помощью диаграммы Венна

1) (АUВ)\(С∩А):

Таблица 2.4.2.

1)(АUВ)

2) (С∩А)

3) (АUВ)\(С∩А)

2) А∩В∩С;

а) А∩В

б) А∩В∩С

а) АUС

2. В∩С

3.(А∩В)U(В∩С)

Есть и другой способ проиллюстрировать операции над множествами. Это, так называемая, таблица вхождения элементов в множества , в которой рассматриваются все возможные случаи вхождения выбранного элемента в множества А и В и их комбинации. Результат принадлежности этого элемента множествам А и В отмечают в первых двух столбцах таблицы по правилу: 1 – если элемент входит в данное множество, 0 – если не входит. Получится четыре случая или четыре строчки в таблице. Столбцы, соответствующие операциям A U B , A ∩ B , A \ B , заполняются согласно определений этих операций (табл. 1).

Например, вторая строка в табл. 1 читается так: если элемент входит в A , но не входит в B , то он входит в А U В , не входит в А ∩ В , но входит в A \B .

Примеры. 1) С помощью таблицы вхождения элементов определите верно ли следующее равенство (А UВ) ’ = А ’ ∩В ’

Из таблицы вхождения элементов в множества видно, что при различных вариантах вхождения элемента в множества А , В он входит или не входит в левую и правую части рассматриваемого равенства одновременно (см. четвертый и седьмой столбцы). Значит (А UВ) ’ = А ’ ∩В ’.

2) С помощью таблицы вхождения элементов определите верно ли следующее равенство (В UС ) \ В = С.

Второй и четвертый столбцы не совпадают, поэтому это равенство неверное.

На координатной прямой множества изображаются в виде отрезка, концы которого показываются кружками: закрашенным кружком, если координата конца отрезка принадлежит множеству, в противном случае – не закрашенным кружком. Например, множество A = {x: − 2 < x ≤ 3} на координатной прямой можно показать так:

Примеры : Даны множества: