Как сделать разность множеств с
Обновлено: 04.07.2024
Пусть даны два множества $latex A $ и $latex B ,$ тогда их объединением называется множество $latex A\cup<> B, $ содержащее в себе все элементы
исходных множеств:
Объединение более чем двух множеств:
Пусть дано семейство множеств $latex \left\,\,\alpha \in A, $ тогда его объединением называется множество, состоящее из всех элементов всех множеств семейства:
Пересечение
Пусть даны два множества $latex A $ и $latex B $, тогда их пересечением называется множество $latex A\cap<> B $, которому принадлежат те и только те элементы, которые одновременно принадлежат двум множествам:
3.Разность
Пусть даны два множества $latex A $ и $latex B $, тогда их разностью называется множество $latex A \setminus B $, содержащее в себе элементы $latex A $, но не $latex B $ :
4.Симметрическая разность
Пусть даны два множества $latex A $ и $latex B, $ тогда их симметрической разностью называется множество $latex A \Delta B $, куда входят все те элементы первого множества, которые не входят во второе множество, а, также те элементы второго множества, которые не входят в первое множество:
$latex A \Delta B = (A \setminus B) \cup (B \setminus A) $
5.Дополнение
Пусть дано множество $latex A, $ его дополнением называется семейство элементов, не принадлежащие данному множеству:
$latex \overline A = \left\ $
Свойства операций
Пусть $latex A, $ $latex B, $ $latex C $ — произвольные множества, тогда:
1. Операция объединение множеств коммутативна:
$latex A \cup B = B \cup A $
2. Операция объединение множеств ассоциативна:
$latex (A \cup B) \cup C = A \cup (B \cup C) $
3. Операция пересечение множеств коммутативна:
$latex A \cap B = B \cap A $
4. Операция пересечения множеств ассоциативна:
$latex (A \cap B) \cap C = A \cap (B \cap C) $
5. $latex (A \cup B) \cap C = (A \cap B) \cup (B \cap C) $
6. $latex (A \cap B) \cup C = (A \cup B) \cap (B \cup C) $
7. $latex C \setminus ( A \cap B) = ( C \setminus A) \cup ( C \setminus B) $
8. $latex C \setminus ( A \cup B) = ( C \setminus A) \cap ( C \setminus B) $
9. $latex C \setminus B \setminus C = (A \cap B) \cup ( C \setminus B) $
10. $latex A \Delta B = ( A \cup B) \setminus ( A \cap B) $
11. Симметрическая разность коммутативна:
$latex A \Delta B = B \Delta A $
12. Симметрическая разность ассоциативна:
$latex ( A \Delta B) \Delta C = A \Delta ( B \Delta C) $
Примеры
1. Пусть $latex A = \left\< 1, 2, 3, 4 \right\>, $ $latex B = \left\< 4, 5, 6, 7 \right\>, $тогда
2. Пусть $latex A = \left\ < 1, 2, 3, 4 \right\>$, $latex B = \left\< 3, 4, 5, 6 \right\>, $ тогда
3. Пусть $latex A = \left\< 1, 2, 3, 4 \right\>, $ $latex B = \left\< 4, 5, 6, 7 \right\>, $ тогда
$latex A \setminus B = \left\< 1, 2, 3 \right\>, $ $latex B \setminus A = \left\< 5, 6, 7 \right\>. $
Мы знаем довольно много о структурах данных, понимаем их устройство, разбираемся, какие структуры работают быстро и помогают решать конкретные задачи. Но эти знания бесполезны, если мы не понимаем, как это использовать в реальной жизни. Это похоже на изучение геометрии в школе. Вы долго считаете предмет бесполезным, пока однажды не появляется необходимость рассчитать площадь пола, чтобы заказать новое ковровое покрытие. Впрочем, пользу геометрии можно почувствовать, даже если вы никогда не считали площадь пола в комнате самостоятельно.
Сегодня поговорим о структуре данных, которая в теории очень догматична, а на практике очень популярна. На самом деле вы так или иначе уже сталкивались с этой структурой, а также слышали о ней на уроках математики в школе. Вы уже догадались, что речь идёт о множествах.
Теория множеств без страха
Прежде чем разбирать устройство множеств, давайте поймём, откуда они появляются. То есть давайте сразу погрузимся в теорию — да-да, в теорию множеств! Не бойтесь сложностей — высока вероятность того, что вы уже так или иначе использовали эту теорию. Возможно, вы сталкивались с теорией множеств, когда проходили в школе диаграмму Венна. Диаграмму Венна включили в программу изучения множеств, так как она хорошо иллюстрирует отношения подмножеств.
Мы выяснили, что теория множеств не должна никого пугать. Теперь пришло время разобраться, что это за теория на самом деле. Множество — математическая концепция. Теорией множеств описывают отношения множеств.
Множество — ни что иное, как неупорядоченная коллекция, в которой нет дублирующихся элементов.
Нужно понять, почему это важно. Для начала давайте посмотрим на множества в действии. Как сказано выше, отношения множеств удачно иллюстрирует диаграмма Венна. Давайте взглянем на два множества: книги, которые есть у человека дома, и книги, которые этот человек прочитал.
Если вы знакомы с диаграммой Венна, то понимаете, что в центре в зелёном круге находятся книги, которыми человек владеет, и которые он прочитал. Здесь множества пересекаются. Также вы понимаете, что два множества — прочитанные человеком книги и книги, которые есть у человека — существуют внутри другого множества. Это все существующие в мире книги.
Диаграмма Венна — хорошая база для понимания теории множеств, так как с её помощью легче понять более сложные вещи. Допустим, вы хотите представить два множества книг в какой-то структуре данных. Вы уже знаете, что книги надо разделить на два множества: которые человек прочитал и которые есть у него дома. Для удобства назовём первое множество Set X, а второе Set Y. Эти множества после реконфигурации в структуры данных можно представить с помощью диаграммы Венна.
Можно заметить, что множества Set X и Set Y стали похожи на объекты или хэши: элементы внутри них не имеют индексов или других элементов, позволяющих их упорядочить. В них также нет повторяющихся элементов, что делает эти структуры данных множествами. Как вы уже знаете, множество — это коллекция неупорядоченных элементов, которые не повторяются.
Об операциях с множествами без боли
Какие возможности открывает представление множеств в формате структур данных? С ними теперь можно выполнять разные операции. Две самые важные операции, которые выполняются над множествами — это пересечение и объединение.
Объединение двух множеств обозначается так: X ∪ Y. Объединение возвращает общность двух множеств или объединённое множество. Иными словами, с помощью объединения множеств можно получить новое множество элементов, которые существуют хотя бы в одном исходном множестве. В нашем случае объединение вернёт все книги, которые человек читал, а также все книги, которые есть у него дома. Обратите внимание, если книга входит одновременно в Set X и Set Y, она не может дублироваться в новом множестве после объединения, так как в множества входят только уникальные элементы.
С помощью диаграммы Венна пересечение и объединение можно представить так:
Теперь давайте рассмотрим более сложные вещи. Объединение и пересечение — важные операции над множествами, но это только азы теории. Нам надо познакомиться с другими операциями, чтобы решать более серьёзные задачи. Важно понимать разность множеств и относительные дополнения множеств. Ниже мы разберём, почему это важные операции, но сначала нужно понять, как они работают.
Как понятно из названия, разность множеств определяет разницу между множествами. Иными словами, мы определяем, какие элементы останутся в множестве X, если удалить из него все элементы, которые содержатся в множестве Y. Это действие можно обозначить так: X — Y. В примере на иллюстрации ниже разница между множеством X и множеством Y — это элементы, которые существуют в Set X, но не существуют в Set Y. Они обозначены буквами C, Z и W.
Относительное дополнение — противоположность разности множеств. Например, относительное дополнение Y по сравнению с X возвращает все элементы множества Y, которые не входят в множество X. Относительное дополнение можно обозначить так: X \ Y. Относительное дополнение X \ Y фактически возвращает такой же набор элементов, как разность Y — X. В нашем примере множество Y меньше множества X. Единственный элемент, который входит в Set Y, но не входит в Set X — число 2.
По сути, мы просто вычитаем множество X из множества Y и отвечаем на вопрос: что существует в Y, чего нет в X?
Вы могли заметить, что в части примеров мы имеем дело со строками, в другой части в качестве элементов выступают буквы и числа. Здесь надо подчеркнуть важный момент: множество может включать любой тип элементов или объектов. Вы можете рассматривать множества как хэши: они включают любые сущности, если те встречаются во множестве только один раз.
Теперь давайте рассмотрим ещё одну операцию, она самая сложная из всех. Но не пугайтесь, с ней тоже можно разобраться.
В некоторых случаях требуется найти противоположность пересечению множеств. Иными словами, речь идёт о книгах, которые есть у человека, и книгах, которые он прочитал, но которые не входят одновременно в оба множества. Как назвать это подмножество? И как найти его?
В примере выше симметрическая разность похожа на поиск относительного дополнения множества X и множества Y. Если подходить к этому с позиции математики, поиск симметричной разницы — то же самое, что и объединение относительных дополнений множества X и множества Y. Эту операцию можно записать так: X △ Y= (X ∖ Y) ∪ (Y ∖ X).
Но не дайте сбить себя с толку!
Всё, что нужно для поиска симметрической разности — найти элементы, которые есть в множестве X, но отсутствуют в множестве Y, и какие элементы есть в множестве Y, но отсутствуют в множестве X. Иными словами, надо найти уникальные элементы в каждом множестве.
В примере выше числа 1, 2 и 3 входят в множества X и Y одновременно. А буквы A, B, C, X, Y, Z входят только в множества X или Y. Поэтому они представляют симметрическую разность множеств X и Y.
Мы рассмотрели теоретические вопросы. Теперь можно посмотреть, как теория множеств работает на практике.
Множества вокруг нас
К этому моменту вы наверняка задумались, зачем надо изучать теорию множеств. Это хороший вопрос, и пришло время ответить на него.
Уже догадались? Множества повсюду. Это структуры данных, которые мы можем использовать при работе с разными языками программирования, например, Python, Java, Ruby, JavaScript и так далее. Если вы знакомы с этими или другими языками программирования, то уже вспомнили методы, которые позволяют работать с множествами.
Вот пример на JavaScript.
Очевидно, что имена методов могут меняться в зависимости от языка. Например, метод has из примера выше в Ruby называется include?, но эти методы работают практически одинаково. А в Python при работе с множествами можно использовать методы intersection, union и symmetric_difference.
Но в чём именно польза множеств? Понятно, что с ними можно работать в разных языках программирования, но зачем это нужно на практике?
Один из моментов — множества могут сэкономить вам много времени. Помните все эти сложные операции — intersection, union, difference? Уже догадались? Продолжительность выполнения этих операций зависит от размера множеств. Это связано с тем, что для выполнения операций нам надо обойти все элементы множества. Обычно даже гигантские множества можно обойти достаточно быстро.
Но как насчёт основных операций? Как насчёт добавления элементов в одно из множеств, удаления элементов, поиска конкретного элемента в множестве? Все эти операции выполняются за константное время или 0(1). Это очень мощный инструмент, и это значит, что множества могут быть даже более удобной структурой данных, чем словарь или хэш.
Но подождите, почему все операции с множествами выполняются так быстро? Как это возможно? Как оказалось, под капотом множества представляют собой хэши. Теперь вся информация собирается воедино. С хэш-таблицами знакомо большинство программистов, но почему с их помощью так удобно реализовывать множества?
Это возможно благодаря нескольким факторам. Первый: в хэш-таблицах каждый элемент всегда имеет уникальный индекс. Это очень хорошо с точки зрения реализации множеств, так как множества могут включать только уникальные элементы. Второй фактор: в хэш-таблицах порядок элементов не имеет значения. В множествах порядок элементов тоже не имеет значения. Наконец, хэш-таблицы обеспечивют константное время доступа 0(1). Это идеально для выполнения базовых операций с множествами.
Заключение
Теория множеств используется в разных областях computer science. Это важная для программистов концепция, понимание которой помогает разработчикам эффективно работать с данными.
Адаптированный перевод статьи Set Theory: the Method To Database Madness by Vaidehi Joshi.
Никогда не останавливайтесь: В программировании говорят, что нужно постоянно учиться даже для того, чтобы просто находиться на месте. Развивайтесь с нами — на Хекслете есть сотни курсов по разработке на разных языках и технологиях.
Коммуникативный педагогический тренинг: способы взаимодействия с разными категориями учащихся
Сертификат и скидка на обучение каждому участнику
Лекция 4. Вычитание множеств, дополнение подмножества.
Определение. Разностью множеств А и В называется множество, содержащее те и только те элементы, которые принадлежат множеству А и не принадлежат множеству В.
Разность множеств А и В обозначают А \ В. Таким образом, по определению разности А \ В = < х | х ∈ А и х ∉ В>.
Если изобразить А и В при помощи кругов Эйлера-Венна, то разность данных множеств является заштрихованная область (рис. 5).
Определение. Пусть В является подмножеством множества А. В этом случае разность множеств А и В называют дополнением подмножества В до множества А и обозначают В' А. Дополнение можно изобразить как показано на рис. 5. Если В – подмножество универсального множества U, то дополнение подмножества В до U обозначают В'.
Например, если В – множество однозначных натуральных чисел, то В'– множество неоднозначных натуральных чисел, если С – множество равнобедренных треугольников, то С' – множество треугольников, у которых все стороны имеют разную длину.
Разность множеств и дополнение к подмножеству обладают рядом свойств.
1) (А \ В) \ С = (А \ С) \ В.
2) (А ∪ В) \ С = (А \ С) ∪ (В \ С).
3) (А \ В) ∩ С = (А ∩С) \ (В ∩ С).
Задания для самостоятельной работы по теме:
1. Найдите разность множеств А и В, если
2. В каких случаях, выполняя упражнение 1, вы находили дополнение множества В до множества А?
Разность двух множеств — это теоретико-множественная операция, результатом которой является множество, в которое входят все элементы первого множества, не входящие во второе множество. Обычно разность множеств и обозначается как , но иногда можно встретить обозначение и .
Пусть и — два указанных в определении множества, тогда их разность определяется (на теоретико-множественном языке):
Это множество часто называют дополнением множества до множества . (только когда множество В полностью принадлежит множеству А)
Обычно предполагается, что рассматриваются подмножества одного и того же множества, которое, в этом случае называют универсумом, скажем, . Тогда можно рассматривать вместе с каждым множеством и его относительное дополнение , при обозначении которого часто опускается значок универсума: ; при этом говорится, что — (просто) дополнение множества (без указания, дополнением до чего является данное множество).
С учётом данного замечания, оказывается, что , то есть дополнение множества до множества есть пересечение множества и дополнения множества .
Также применяется и операторная запись вида , A" width="" height="" />
или (если опустить универсальное множество) .
Операция разности множеств не является по определению симметричной по отношению входящим в неё множествам. Симметричный вариант теоретико-множественной разности двух множеств описывается понятием симметрической разности.
Содержание
Примеры
Свойства
Пусть — произвольные множества.
Компьютерные реализации
В пакете Mathematica операция реализована с помощью функции Complement . В пакете MATLAB она же реализована с помощью функции setdiff .
Дополнение множества
Определение
Если из контекста следует, что все рассматриваемые множества являются подмножествами некоторого фиксированного универсума , то определяется операция дополнения:
Читайте также: