Что значит разность множеств

Бинарные операции над упорядоченными множествами

В предыдущей статье я писал о бинарных операциях над неупорядоченными множествами. В этой статье мы рассмотрим алгоритмы с меньшей сложностью выполнения, для упорядоченных множеств.

I. Пересечение упорядоченных множеств

Пересечение двух упорядоченных множеств A и B — это множество только с теми элементами A и B, которые одновременно принадлежат обоим множествам, без дублей. Сложность алгоритма O(m+n), где m и n — длины входных множеств A и B соответственно.

Сделал небольшую анимацию, чтобы показать как работает алгоритм.

Пример реализации на javascript:

Обращение к функции:

II. Разность упорядоченных множеств

Разность двух упорядоченных множеств A и B — это множество с элементами A, не совпадающими с элементами B, без дублей. Сложность алгоритма O(m+n), где m и n — длины входных упорядоченных множеств A и B соответственно.

III. Объединение упорядоченных множеств

Объединение двух упорядоченных множеств A и B — это множество с элементами A и элементы множества B, без дублей. Сложность алгоритма O(m+n), где m и n — длины входных упорядоченных множеств A и B соответственно.

IV. Симметрическая разность упорядоченных множеств

Симметрическая разность двух упорядоченных множеств A и B — это такое множество, куда входят все те элементы первого упорядоченного множества, которые не входят во второе упорядоченное множество, а также те элементы второго упорядоченного множества, которые не входят в первое упорядоченное множество. Сложность алгоритма O(2(m+n)), где m и n — длины входных упорядоченных множеств A и B соответственно.

По сути это вычитание множеств, сначала A из B, затем B из A.

Источник

Лекция 5. Вычитание множеств.

Онлайн-конференция

«Современная профориентация педагогов
и родителей, перспективы рынка труда
и особенности личности подростка»

Свидетельство и скидка на обучение каждому участнику

Лекция 4. Вычитание множеств, дополнение подмножества.

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

Разность множеств А и В обозначают А \ В. Таким образом, по определению разности А \ В = < х | х ∈ А и х ∉ В>.

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

Определение. Пусть В является подмножеством множества А. В этом случае разность множеств А и В называют дополнением подмножества В до множества А и обозначают В’ _А. Дополнение можно изобразить как показано на рис. 5. Если В – подмножество универсального множества U, то дополнение подмножества В до U обозначают В’.

Например, если В – множество однозначных натуральных чисел, то В’– множество неоднозначных натуральных чисел, если С – множество равнобедренных треугольников, то С’ – множество треугольников, у которых все стороны имеют разную длину.

Разность множеств и дополнение к подмножеству обладают рядом свойств.

1) (А \ В) \ С = (А \ С) \ В.

2) (А ∪ В) \ С = (А \ С) ∪ (В \ С).

3) (А \ В) ∩ С = (А ∩С) \ (В ∩ С).

Задания для самостоятельной работы по теме:

1. Найдите разность множеств А и В, если

2. В каких случаях, выполняя упражнение 1, вы находили дополнение множества В до множества А?

3. Из каких чисел состоит дополнение:

а) множества натуральных чисел до множества целых;

б) множества целых чисел до множества рациональных;

в) множества рациональных чисел до множества действительных.

Источник

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

План лекции:

2) Объединение множеств.

3) Разность множеств.

4) Симметрическая разность.

5) Дополнение множеств.

6) Декартово (прямое) произведение двух множеств.

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

Пересечение множеств А и В обозначают: А Ç В.

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

В том случае, когда множества А и В не имеют общих элементов, то говорят, что их пересечение пусто и пишут: А Ç В = Æ.

Если ВÌ А, то А Ç В = В.

Операция, при помощи которой находят пересечение множеств, называется также пересечением.

2) Пересечением множества прямоугольников и множества ромбов является множество квадратов.

3) Пересечением множества чётных чисел и множества нечётных чисел пусто.

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

Объединение множеств А и В обозначают: А È В.

Если представить множества А и В при помощи кругов Эйлера, то объединение данных множеств изобразится заштрихованной областью (рис. 2).

Если ВÌ А, то А È В = А.

Операция, при помощи которой находят объединение множеств, называется также объединением.

2) Объединение множества положительных чётных чисел и множества положительных нечётных чисел является множество натуральных чисел.

Если в выражении есть Ç и È множеств, но нет скобок, то сначала выполняют Ç.

Операции пересечения и объединения множеств обладают свойствами:

1° Коммутативность пересечения

2° Коммутативность объединения

3º Ассоциативность пересечения

«А, В, С (А Ç В) Ç С = А Ç (В Ç С)

4º Ассоциативность объединения

«А, В, С (А È В) È С = А È (В È С)

5º Пересечение дистрибутивно относительно объединения

«А, В, С А Ç (В È С) = (А Ç В) È (А Ç С)

6º Объединение дистрибутивно относительно пересечения

«А, В, С А È (В Ç С) = (А È В) Ç (А È С)

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

Например, докажем свойство 6º.

а) Докажем, что А È (В Ç С) Ì (А È В) Ç (А È С).

Пусть х Î А È (В Ç С). Тогда х Î А или х Î (В Ç С).

Если х Î А, то х Î А È В и х Î А È С, а, следовательно, х Î (А È В) Ç (А È С).

Если х Î (В Ç С), то х Î В и х Î С. Следовательно, х Î А È В и х Î А È С, т.е. и в этом случае х Î (А È В) Ç (А È С).

б) Докажем, что (А È В) Ç (А È С) Ì А È (В Ç С).

Пусть х Î (А È В) Ç (А È С). Тогда х Î А È В и х Î А È С.

То есть, (х Î А или х Î В) и (х Î А или х Î С).

Значит, х Î А или (х Î В и х Î С), т.е. х Î А È (В Ç С).

3. Разностью множеств А и В называется множество, элементы которого принадлежат множеству А и не принадлежат множеству В.

Обозначают А \ В; А – В.

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

Операция, при помощи которой находят разность множеств, называется вычитанием.

2) Разностью множества чётных чисел и множества целых чисел является пустое множество.

4. Симметрической разностью множеств А и В называется множество, состоящее из элементов, принадлежащих только множеству А или только множеству В.

Симметрическую разность множеств А и В обозначают: А х В; А – В.

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

А х В = (А È В) \ (А Ç В)

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

Универсальное множество часто изображают прямоугольником.

Например, для N универсальным считается множество Z.

Дополнением множества А называется разность между универсальным множеством и множеством А.

Дополнение множества А обозначают .

= U \ A =

При помощи кругов Эйлера дополнение изображается рис. 5.

È А = U = Æ

Ç А = Æ = U

1) А = <2k>; U = Z ® = Z \A = <2k+1>.

Операции разности и дополнения множеств обладают свойствами:

9º Разность антидистрибутивна относительно пересечения. «А, В, С

А \ (В Ç С) = (А \ B) È (A \ C)

10º Разность антидистрибутивна относительно объединения. «А, В, С

А \ (В È С) = (А \ B) Ç (A \ C)

11º (частный сл. 9º) Дополнение пересечения А и В равно объединению дополнений А и В.

12º (частный сл. 10º) Дополнение объединения А и В равно пересечению дополнений А и В.

Докажем св. 9º и проиллюстрируем его на диаграммах Эйлера–Венна.

а) Докажем, что А \ (В Ç С) Ì (А \ B) È (A \ C).

Пусть х Î А \ (В Ç С).

Тогда х Î А и х Ï (В Ç С), т.е. или х Ï В, или х Ï С.

Значит, или (х Î А и х Ï В), или (х Î А и х Ï С), т.е. х Î А \ B или хÎА\ С.

б) Докажем, что (А \ B) È (A \ C) Ì А \ (В Ç С).

Пусть х Î (А \ B) È (A \ C).

Тогда х Î (А \ B) или х Î (A \ C), т.е. (х Î А и х Ï В) или (х Î А и х Ï С)

Значит, х Î А и (х Ï В и х Ï С), т.е. х Î А \ (В Ç С).

Дом. задание. Доказать и проиллюстрировать на диаграммах Эйлера–Венна свойства 1 – 5, 7 – 12.

Задание. Найти пересечение, объединение, разность и симметрическую разность множеств А и В, если А = <хÎR ½–1£ х

Источник

Python и теория множеств

В Python есть очень полезный тип данных для работы с множествами – это set. Об этом типе данных, примерах использования, и небольшой выдержке из теории множеств пойдёт речь далее.

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

Множество

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

Множество – это не более чем неупорядоченная коллекция уникальных элементов.

Что значит неупорядоченная? Это значит, что два множества эквивалентны, если содержат одинаковые элементы.

Элементы множества должны быть уникальными, множество не может содержать одинаковых элементов. Добавление элементов, которые уже есть в множестве, не изменяет это множество.

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

Множества в Python

Множество в Python можно создать несколькими способами. Самый простой – это задать множество перечислением его элементов в фигурных скобках:

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

Для создания пустого множества нужно непосредственно использовать set() :

Также в set() можно передать какой-либо объект, по которому можно проитерироваться (Iterable):

Ещё одна возможность создания множества – это использование set comprehension. Это специальная синтаксическая конструкция языка, которую иногда называют абстракцией множества по аналогии с list comprehension (Списковое включение).

Хешируемые объекты

Существует ограничение, что элементами множества (как и ключами словарей) в Python могут быть только так называемые хешируемые (Hashable) объекты. Это обусловлено тем фактом, что внутренняя реализация set основана на хеш-таблицах. Например, списки и словари – это изменяемые объекты, которые не могут быть элементами множеств. Большинство неизменяемых типов в Python (int, float, str, bool, и т.д.) – хешируемые. Неизменяемые коллекции, например tuple, являются хешируемыми, если хешируемы все их элементы.

Объекты пользовательских классов являются хешируемыми по умолчанию. Но практического смысла чаще всего в этом мало из-за того, что сравнение таких объектов выполняется по их адресу в памяти, т.е. невозможно создать два «равных» объекта.

Скорее всего мы предполагаем, что объекты City(«Moscow») должны быть равными, и следовательно в множестве cities должен находиться один объект.
Этого можно добиться, если определить семантику равенства для объектов класса City :

Чтобы протокол хеширования работал без явных и неявных логических ошибок, должны выполняться следующие условия:

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

Тип set в Python является подтипом Collection (про коллекции), из данного факта есть три важных следствия:

Принадлежность множеству

Мощность множества

Мощность множества – это характеристика множества, которая для конечных множеств просто означает количество элементов в данном множестве. Для бесконечных множеств всё несколько сложнее.

Перебор элементов множества

Как уже было отмечено выше, множества поддерживают протокол итераторов, таким образом любое множество можно использовать там, где ожидается iterable-объект.

Отношения между множествами

Между множествами существуют несколько видов отношений, или другими словами взаимосвязей. Давайте рассмотрим возможные отношения между множествами в этом разделе.

Равные множества

Тут всё довольно просто – два множества называются равными, если они состоят из одних и тех же элементов. Как следует из определения множества, порядок этих элементов не важен.

Непересекающиеся множества

Если два множества не имеют общих элементов, то говорят, что эти множества не пересекаются. Или другими словами, пересечение этих множеств является пустым множеством.

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

Подмножество множества S – это такое множество, каждый элемент которого является также и элементом множества S. Множество S в свою очередь является надмножеством исходного множества.

Пустое множество является подмножеством абсолютно любого множества.

Само множество является подмножеством самого себя.

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

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

Объединение множеств

Объединение множеств – это множество, которое содержит все элементы исходных множеств. В Python есть несколько способов объединить множества, давайте рассмотрим их на примерах.

Добавление элементов в множество

Пересечение множеств

Пересечение множеств – это множество, в котором находятся только те элементы, которые принадлежат исходным множествам одновременно.

Разность множеств

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

Удаление элементов из множества

Симметрическая разность множеств

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

Заключение

Я надеюсь, мне удалось показать, что Python имеет очень удобные встроенные средства для работы с множествами. На практике это часто позволяет сократить количество кода, сделать его выразительнее и легче для восприятия, а следовательно и более поддерживаемым. Я буду рад, если у вас есть какие-либо конструктивные замечания и дополнения.

Источник

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

Будут и задачи для самостоятельного решения, к которым можно посмотреть ответы.

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

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

Ели ли Вы сегодня обед? Сейчас станет известна страшная тайна. Обед является множеством. А именно, множеством блюд, из которых он состоит. В нём (как правило) нет одинаковых блюд, и во множестве все элементы должны быть разными. А, если на обед у Вас был тот же самый салат, что и на завтрак, то этот салат является пересечением множеств «Обед» и «Завтрак».

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

А улица, на которой Вы живёте? Она является собранием многих разных объектов, но обязательно есть множество домов, расположенных на этой улице. Поэтому множество домов является подмножеством множества «Улица».

Но пока ещё один пример практического рассмотрения множеств.

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

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

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

Код PASCAL

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

Если , то .

Решить задачу на множества самостоятельно, а затем посмотреть решение

Пример 3. Сколько элементов содержит множество

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

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

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

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

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

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

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

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

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

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

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

.

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

Операция пересечения множеств

.

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

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

Разность множеств

.

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

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

Выполнить операции над множествами самостоятельно, а затем посмотреть решение

Пример 5. Выполните следующие операции над множествами:

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

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

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

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

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

,

,

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

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

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

Выполнить операции над множествами самостоятельно, а затем посмотреть решение

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

Выполнить операции декартова произведения множеств:

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

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

,

,

,

,

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

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

.

,

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

, , ,

,

.

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

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

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

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

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

,

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

но ,

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

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

,

.

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

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

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

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

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

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

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

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

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

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

, , , .

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

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

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

.

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

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

.

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

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

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

.

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

.

.

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

.

.

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

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

Источник