"Чистая"
и прикладная математика

МНОЖЕСТВА И ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

Что такое множества, где и как они применяются

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

Подмножества

Основные числовые множества

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

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

Решение различных задач на множества

Что такое множества, где и как они применяются

В математике понятие множества является одним из основных, фундаментальным, однако единого определения множества не существует. Одним из наиболее устоявшихся определений множества является следующее: под множеством понимают любое собрание определённых и отличных друг от друга объектов, мыслимых как единое целое. Создатель теории множеств немецкий математик Георг Кантор (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:=[hleb, moloko]; Veterok:=[hleb, syr, maslo]; Ogonyok:=[hleb, myaso, ryba, sol, sahar]; ... MinFood:=Solnyshko * Veterok * Ogonyok; MaxFood:=Solnyshko + Veterok + Ogonyok; End.

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

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

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

- простых чисел

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

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

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

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

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

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

hlebVETEROK,

что означает: элемент "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}

означает множество корней уравнения x² - 3x + 2 = 0, т. е. множество {1, 2}. Это конечное множество.

А следующим описанием задаётся множество всех целых чисел больше 5:

M = {xZ | x > 5},

это множество является бесконечным.

Описанием предпочтительно задавать и конечные множества, в которых очень много элементов, например, множество всех натуральных чисел от 2 до 22³:

M = {xN | 2< x < 22³}.

Множество, не содержащее ни одного элемента, называется пустым и обозначается знаком ∅.

Множество может состоять из одного элемента. Необходимо различать элемент a и множество {a}, содержащее только один элемент a, хотя бы потому, что допускаются множества, элементы которых сами являются множествами. Например, множество a={2, 1} состоит из двух элементов 2 и 1, а множество {a}, состоит из одного элемента a, который сам является двухэлементным множеством.

Два множества называюся равными, если они состоят из одних и тех же элементов. Например, равны множество равносторонних треугольников и множество равноугольных треугольников, так как это одни и те же треугольники: если в треугольнике все стороны равны, то равны и все его углы. Обратно, из равенства всех трёх углов треугольника вытекает равенство всех трёх его сторон. Равны любые два конечных множетсва, отличающиеся друг от друга только лишь порядком их элементов, например, {abc} = {cab}.

Пример 1. Равны ли множества

{0, 1, 2} и {0, 2, 1};

{0, 1} и {{0, 1}}?

Решение. Так как множества {0, 1, 2} и {0, 2, 1} состоят из одних и тех же элементов, то они равны.

Множества {0, 1} и {{0, 1}} не равны, так как первое множество двухэлементное, а второе - одноэлементное.

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

A = {0, 1}

B = {{0, 1}, 2}

C = {{{0, 1}, 2}, 3}.

Верны ли следующие соотношения: AB, BC, AC?

Решение.

Соотношение AB верно, так как множество A является первым элементом множества B.

Соотношение BC верно, так как множество B является первым элементом множества C.

Соотношение AC верно, так как множество A не является элементом множества C. Множество A является элементом множества B, которое является элементом множества C, но множества A и B - это разные множества.

Если А - конечное множество, то через обозначается число его элементов, которое называется мощностью множества.

Подмножества

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

Множество А включено в множество В (символическая запись ), если любой элемент множества А принажлежит множеству В. В этом случае множество А является подмножеством множества В.

Если и , то пишут и говорят, что множество А строго включено в множество В или что А есть собственное подмножество В.

Например, если и , то А есть собственное подмножество В.

Верно следующее утверждение: пустое множество есть подмножество любого множества, то есть для любого множества А

.

Если множество содержит по крайней мере два элемента, то оно имеет всевозможные подмножества, среди которых есть и собственные подмножества.

Например, всевозможные подмножества множества это

из которых и - собственные подмножества множества .

Множество всех подмножеств множества А называется множеством-степенью множества А и обозначается .

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

Теорема о мощности множества степени:

Если , то .

Основные числовые множества

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

Числа, которые можно использовать для счёта предметов (то есть положительные целые числа, часто к ним относят и ноль) составляют множество натуральных чисел N:

N = {0, 1, 2, 3, ...}

Натуральные числа, числа противоположные им по знаку (то есть, отрицательные целые числа) и ноль составляют множество целых чисел Z:

Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}

Числа, записанные в виде p/q, причём p и q - целые числа и q не равно нулю, составляют множество рациональных чисел Q.

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

Q = {p/q |, p и q - целые числа и q≠0}

Рациональные числа могут быть представлены в виде конечных либо бесконечных периодических дробей, например:

Числа и не являются рациональными числами. Они не могут быть представлены в виде периодических дробей. Но они могут быть представлены в виде непериодических дробей.

Числа, которые можно представить в виде непериодических дробей, составляют множество иррациональных чисел I:

I = {x |, x непериодическая дробь}

Рациональные и иррациональные числа составляют множество действительных чисел R:

R = {x |, x рациональное или иррациональное число}

Числа вида a+bi (abR), где i=√-1 - мнимая единица корень из минус единицы - составляют множество комплексных чисел C.

Таким образом, имеют место следующие включения множеств:

NZQRC.

Пример 3. Пусть A - множество всех натуральных чётных чисел больше нуля, а B - множество всех натуральных чисел, представимых в виде суммы двух нечётных натуральных чисел. Доказать, что A=B.

Решение. Для доказательства равенства данных множеств покажем, что каждый элемент множества A является элементом и множества B, и наоборот, каждый элемент множества B является и элементом множества A.

Шаг 1. Элемент принадлежит множеству A: xA. Докажем, что элемент x принадлежит и множеству B. Если xA, то x = 2k, где k ≥ 1 (любое число, умноженное на 2, является чётным числом). Но x = 2k можно представить и в виде (2k - 1) + 1, что является суммой двух нечётных натуральных чисел. Натуральных, поскольку k ≥ 1. Следовательно, xB.

Шаг 2. Элемент принадлежит множеству B: xB. Докажем, что элемент x принадлежит и множеству A. Если xB, то x = (2k - 1) + (2m - 1), где 2k - 1 и 2m - 1 - нечётные натуральные числа, т.е. 2k - 1 ≥ 1 и 2m - 1 ≥ 1. Следовательно, x = (2k + 2m - 2) = 2(k + m - 1), где k + m - 1 ≥ 1, значит, xA.

Таким образом, равенство множеств A и B доказано.

Устоявшиеся ныне представления о числовых множествах явились результатом эволюции изучения математиками различных чисел и добавления новых множеств (систем) чисел. Древнегреческие математики считали "настоящими" только натуральные числа, но в практических расчётах за два тысячелетия до н.э. в Древнем Египте и Древнем Вавилоне уже применялись дроби. Следующим важным этапом в развитии понятий о числе было введение отрицательных чисел - это было сделано китайскими математиками за два века до н.э. Отрицательные числа применял в III веке н.э. древнегреческий математик Диофант, знавший уже правила действий над ними. А в VII веке н.э. эти числа подробно изучили индийские математики, которые сравнивали такие числа с долгом. С помощью отрицательных чисел можно было единым образом описывать изменения величин. В результате всех этих занятий и сложилось близкое к современному понятие о множестве целых чисел, а в результате изучения свойств дробей - о множествах рациональных и иррациональных чисел.

После XVI века в связи с изучений квадратных и кубических уравнений оказалось необходимым извлекать квадратные корни из отрицательных чисел. В начале такая постановка вопроса казалась парадоксом, но целый ряд таких задач был решён - так было заложено понятие множества комплексных чисел.

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

Объединением множеств А и В называется множество, обозначаемое , состоящее из всех тех и только тех элементов, которые принадлежат или А или В, то есть

.

Например, если , , , то , , .

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

Операция объединения есть в реляционной алгебре, используемой для манипулирования данными в языках запросов к базам данных, например, SQL.

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

.

Например, если , , , то , , .

На рисунке ниже - результат пересечения множеств А и В - заштрихованная фигура.

В одном из материалов сайта показано, как выглядит пересечение множеств решений систем линейных неравенств.

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

Разностью множеств А и В называется множество, обозначаемое и состоящее из всех тех и только тех элементов множества А, которые не являются элементами множества В, то есть

.

Например, если , , , то , , , , .

На рисунке ниже слева - результат разности множеств А и В, а справа - результат разности множеств В и А.

Операция разности есть в реляционной алгебре, используемой для манипулирования данными в языках запросов к базам данных, например, SQL.

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

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

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

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

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

то

,

,

А теперь обещанная картинка

На картинке точками (узлами) дерева обозначены элементы множеств , , . Для получения каждой упорядоченной тройки (так как перемножаем три множества) нужно пройти каждый полный маршрут от корня дерева (start) к конечным точкам и записать все пройденные точки. Таким образом, получаем декартово произведение множеств:

Операция декартова произведения есть в реляционной алгебре, используемой для манипулирования данными в языках запросов к базам данных, например, SQL.

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

Свойства используются для упрощения выражений. Они следующие.

Коммутативный закон:

,

Ассоциативный закон:

,

Дистрибутивный закон:

,

Законы де Моргана:

,

Черта сверху означает отрицание.

Закон двойного отрицания:

.

Законы поглощения:

,

Для следующего закона введём понятие универсума. Если допустить, что множество А является подмножеством некоторого фиксированного (поэтому на рисунке внизу оно ограничено сторонами квадрата) множества U, то множество U является универсальным (для данного случая) или универсумом. Например, в геометрии мы имеем дело с множествами точек данного пространства, в элементарной арифметике - с подмножествами множества всех целых чисел. Таким образом, множество всех целых чисел в данном случае можно считать универсальным множеством или универсумом.

Законы об универсуме и пустом множестве:

, , ,

,

.

Решение различных задач на множества

Пример 4. Найти декартово произведение множеств , , .

Решение. В качестве декартова произведения данных трёх множеств мы должны получить множество наборов длины 3 (по числу перемножаемых множеств). Смотрим на дерево для получения наборов (в теретической справке выше), проходим каждый полный маршрут от корня к конечным точкам и получаем:


Пример 5. Если , то что такое ? Что такое ? Что такое ? Что такое ?

Решение. Итак, множество А строго включено в множество В. Или, как на диаграмме Венна:

  • Объединение множеств состоит из тех и только из тех элементов, которые есть или в А или в В. Поскольку все элементы множества А идентичны части элементов множества В:

    ,

    или, что то же самое

    но ,

    следовательно, если , то .

  • Пересечение множеств состоит из тех и только из тех элементов, которые есть и в А, и в В. То есть,

    ,

    но не

    .

    следовательно, если , то .

  • Разность множеств состоит из тех и только из тех элементов, которые есть в А, но которых нет в В. То есть,

    и не

    . Дубликаты отбрасываются.

    следовательно, если , то .

  • Разность множеств состоит из тех и только из тех элементов, которые есть в В, но которых нет в А. То есть,

    и не

    . И, как уже показано, .

    Следовательно, если , то .


Пример 6. Даны множества , . Найти и . Равны ли перемножаемые множества?

Решение. Найдём декартово произведение двух множеств. Можем так же пользоваться рисунком дерева из теоретической части, но в случае двух множеств маршрутов для составления упорядоченных наборов будет меньше. Получаем:

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

, , , .

Теперь будет проще найти множество всех подмножеств:

Очевидно, что .

Найдём . Множество всех подмножеств:

.

Таким образом, .

Найдём . Множество всех подмножеств:

.

Таким образом, , .

Перемножаемые множества имеют равные размеры, но они не равны, так как состоят из разных элементов.


Пример 7. Упростить выражения.

  • .

    Решение. Используя законы де Моргана, получаем:

    .

  • .

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

    .

  • .

    Решение. Упростим выражение в первых внутренних скобках, используя законы де Моргана и закон о двойном отрицании:

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

Нет времени вникать в решение? Можно заказать работу!

Материал "Реляционная алгебра"

К началу страницы