Что называется симметрической разностью множеств

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

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

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.

Источник

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

План лекции:

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£ х

Источник

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

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

На рисунке 4.5. изображено множество С, являющееся симметричной разностью множеств А и В.

3.3. Включения. Подмножество. Пустое множество

Множество А называется подмножеством множества В, если любой элемент из А является элементом множества В. Факт, что А является подмножеством В записывается с помощью « Ì » – знак включения.

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

Введем понятие строгого включения множества (символ «Í»).

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

Введем понятие множества всех подмножеств в некотором множестве Х, по-другому называемом множеством-степенью:

Из основных принципов теории множеств следует существование единственного множества, не имеющего элементов – “Æ” – пустое множество.

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

Пример. Дано множество A=. Построить P(А) – множество-степень для множества А.

Если некоторое множество содержит n элементов, то его степень множества будет содержать 2n элементов.

3.4. Универсум. Дополнение.

Обычно все множества, с которыми имеют дело в том или ином рассуждении, являются подмножествами некоторого фиксированного множества U. Например, множества рыб, моллюсков, планктона, крабообразных являются подмножествами объемлющего их множества фауны. Это общее множество назовем универсумом.

Универсумили универсальное множество (U) – множество, которое состоит из всех элементов, а также подмножеств множества исследуемых объектов исследуемой области, т.е. универсум должен удовлетворять следующим условиям:

— если А Î U, то P(А) Î U, где P(А) – множество всех подмножеств множества А;

Множество Ā= U \ A называют дополнением множества А.

На рис. 4.7 приведено изображение универсального подмножества, множества А и дополнения множества Ā.

Анализируя рис. 4.7. можно сделать следующие выводы:

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

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

Источник

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 имеет очень удобные встроенные средства для работы с множествами. На практике это часто позволяет сократить количество кода, сделать его выразительнее и легче для восприятия, а следовательно и более поддерживаемым. Я буду рад, если у вас есть какие-либо конструктивные замечания и дополнения.

Источник

Что называется симметрической разностью множеств

Объединение множеств X и Y — это множество, состоящее из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X или Y, т.е. принадлежат X или принадлежат Y.

Объединение X и Y обозначается через X∪Y

Формально x∈X∪Y ⇔ x∈X или x∈Y

Пример 3. Если X — множество точек левого круга и Y — множество точек правого круга, то

X∪Y — заштрихованная область, ограниченная обоими кругами.

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

Для объединенных множеств справедливы:

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

Очевидно, что X∪∅ = X. Отсюда можно видеть, что ∅ играет роль нуля в алгебре множеств.

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

Пересечение множеств X и Y — это множество, состоящее из всех тех и только тех элементов, которые принадлежат как множеству X, так и множеству Y.

Пересечение множеств обозначается X∩Y.

Формально x∈X∩Y ⇔ x∈X и x∈Y

Пример 5. Если Х — множество точек левого круга, а Y — множество точек правого круга, то X∩Y представляет собой заштрихованную область, являющуюся общей частью обоих кругов.

Множества X и Y называются непересекающимися (дизъюнктными), если они не имеют общих элементов, то есть если X∩Y=∅.

Частный случай: кортеж длины 1 —

кортеж длины 0 — или ∧ — пустой кортеж.

Отличие кортежа и обыкновенного множества: в кортеже могут быть одинаковые элементы.

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

Два вектора равны, если они имеют одинаковую длину и соответствующие координаты их равны.

Компонентами кортежа (вектора) могут быть также компоненты кортежи (векторы):

Пример. Слова в предложении,

Прямое произведение множеств

Прямым (декартовым) произведением множеств X и Y называется множество, состоящее из всех тех и только тех упорядоченных пар, первая компонента которых принадлежит множеству X, а вторая принадлежит множеству Y.

Пример 3. Пусть X и Y — отрезки вещественной оси. Прямое произведение X*Y изображается заштрихованным прямоугольником. См. рис. б).

Прямое произведение изменяется при изменении порядка сомножителей т.е.

Очевидно X*Y = ∅ ⇔ X = ∅ или Y = ∅.

Частным случаем прямого произведения является понятие степеней (декартовых) множества — прямое произведение одинаковых множеств

M s =M*M*. *M, M 1 =M, M 0 =∧.

Обычно R — множество вещественных чисел, тогда R 2 =R*R — вещественная плоскость и R 3 =R*R*R — трехмерное вещественное пространство.

Проекция множества.

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

Пусть M — множество, состоящее из кортежей длины S. Тогда пролинией множества M будем называть множество пролиний всех кортежей из М

Очевидно что если М=Х*Y то Пр₁М=Х, Пр₂М=Y

и если Q⊆Х*Y то Пр₁Q⊆Х и Пр₂Q⊆Y

Пусть V — множество векторов одинаковой длины S.

В общем случае Пр_iV — вовсе не обязательно прямое произведение: оно может быть подмножеством.

Источник