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

Теория множеств: основы и базовые операции над множествами

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

Сегодня поговорим о структуре данных, которая в теории очень догматична, а на практике очень популярна. На самом деле вы так или иначе уже сталкивались с этой структурой, а также слышали о ней на уроках математики в школе. Вы уже догадались, что речь идёт о множествах.

Теория множеств без страха

Прежде чем разбирать устройство множеств, давайте поймём, откуда они появляются. То есть давайте сразу погрузимся в теорию — да-да, в теорию множеств! Не бойтесь сложностей — высока вероятность того, что вы уже так или иначе использовали эту теорию. Возможно, вы сталкивались с теорией множеств, когда проходили в школе диаграмму Венна. Диаграмму Венна включили в программу изучения множеств, так как она хорошо иллюстрирует отношения подмножеств.

Мы выяснили, что теория множеств не должна никого пугать. Теперь пришло время разобраться, что это за теория на самом деле. Множество — математическая концепция. Теорией множеств описывают отношения множеств.

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

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

Нужно понять, почему это важно. Для начала давайте посмотрим на множества в действии. Как сказано выше, отношения множеств удачно иллюстрирует диаграмма Венна. Давайте взглянем на два множества: книги, которые есть у человека дома, и книги, которые этот человек прочитал.

Если вы знакомы с диаграммой Венна, то понимаете, что в центре в зелёном круге находятся книги, которыми человек владеет, и которые он прочитал. Здесь множества пересекаются. Также вы понимаете, что два множества — прочитанные человеком книги и книги, которые есть у человека — существуют внутри другого множества. Это все существующие в мире книги.

Диаграмма Венна — хорошая база для понимания теории множеств, так как с её помощью легче понять более сложные вещи. Допустим, вы хотите представить два множества книг в какой-то структуре данных. Вы уже знаете, что книги надо разделить на два множества: которые человек прочитал и которые есть у него дома. Для удобства назовём первое множество Set X, а второе Set Y. Эти множества после реконфигурации в структуры данных можно представить с помощью диаграммы Венна.

Можно заметить, что множества Set X и Set Y стали похожи на объекты или хэши: элементы внутри них не имеют индексов или других элементов, позволяющих их упорядочить. В них также нет повторяющихся элементов, что делает эти структуры данных множествами. Как вы уже знаете, множество — это коллекция неупорядоченных элементов, которые не повторяются.

Начните изучать разработку с бесплатного курса «Основы современной вёрстки». Вы научитесь создавать статические веб-страницы, стилизовать элементы, использовать редакторы кода с полезными расширениями. В конце курса вы опубликуете свой первый сайт на GitHub Pages.

Об операциях с множествами без боли

Какие возможности открывает представление множеств в формате структур данных? С ними теперь можно выполнять разные операции. Две самые важные операции, которые выполняются над множествами — это пересечение и объединение.

Пересечение множеств часто записывается с помощью такой нотации: X ∩ 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.

Никогда не останавливайтесь: В программировании говорят, что нужно постоянно учиться даже для того, чтобы просто находиться на месте. Развивайтесь с нами — на Хекслете есть сотни курсов по разработке на разных языках и технологиях.

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

Источник

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

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

Содержание

Сравнение множеств

Множество A содержится во множестве B (множество B включает множество A ), если каждый элемент A есть элемент B :

Два множества называются равными, если они являются подмножествами друг друга:

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

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

Бинарные операции

Ниже перечислены основные операции над множествами:

Для лучшего понимания смысла этих операций используются диаграммы Эйлера — Венна, на которых представлены результаты операций над геометрическими фигурами как множествами точек.

Унарные операции

Результатом является кардинальное число (для конечных множеств — натуральное).

Обозначение происходит из того, что

Приоритет выполнения операций

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

Полезное

Смотреть что такое “Операция над множествами” в других словарях:

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

Операции над нечёткими множествами — обобщают операции над обыкновенными множествами. Эти операции обычно определяются поэлементно над значениями функции принадлежности. Наиболее популярны операции пересечения и объединения нечётких множеств, определяемые, соответственно, операциями … Википедия

Операции над нечеткими множествами — Операции над нечёткими множествами обобщают операции над обыкновенными множествами. Эти операции обычно определяются поэлементно над значениями функции принадлежности. Наиболее популярны операции пересечения и объединения нечетких множеств,… … Википедия

Теория топосов — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Теория топосов раздел теории категорий, изучающий топосы категор … Википедия

Объединение (значения) — Объединение многозначный термин, входит в состав сложных терминов. В Викисловаре есть статья «объединение» Объединение разновидность организаций. Объединение общее название крупных воинских формирований … Википедия

ДЕСКРИПТИВНАЯ ТЕОРИЯ МНОЖЕСТВ — раздел теории множеств, изучающий внутреннее строение множеств в зависимости ют тех операций, при помощи к рых эти множества могут быть построены из множеств сравнительно простой природы (напр., замкнутых или открытых подмножеств данного… … Математическая энциклопедия

Множеств теория — учение об общих свойствах множеств, преимущественно бесконечных. Понятие множества, или совокупности, принадлежит к числу простейших математических понятий; оно не определяется, но может быть пояснено при помощи примеров. Так, можно… … Большая советская энциклопедия

ВЫЧИСЛИТЕЛЬНЫЙ АЛГОРИТМ — точно определенное указание действий над данными, позволяющее с помощью цифровой вычислительной машины дискретного действия преобразовать за конечное количество операций нек рый массив данных (входные данные) в другой массив данных (выходные… … Математическая энциклопедия

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

Источник

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

1. Для задания множеств применяется еще один способ – с помощью теоретико-множественных операций, позволяющих строить из одних множеств другие. Рассмотрим несколько таких операций и их представления диаграммами Венна.

A. Пересечением двух множеств A и B называется множество М = A ∩ B, состоящее из элементов, принадлежащих обоим множествам: и множеству A, и множеству B. Пересечение – это общая часть двух множеств (область D на рис. 1.2). Аналогично определяется пересечение
трех или более множеств (показано частой штриховкой на рис. 1.3). Символ ∩ означает операцию пересечения множеств.

Термин «пересечение» – по существу геометрического происхождения. Пересечением прямой и плоскости, если прямая не лежит на плоскости и не параллельна ей, является их единственная общая точка. Если прямая и плоскость параллельны, то их пересечение не содержит ни одной точки, т.е. пусто. Если же прямая имеет с плоскостью более одной общей точки, то, как известно, она целиком лежит на плоскости, и их пересечение совпадает с множеством точек этой прямой.
В этом случае множество точек прямой есть подмножество множества точек плоскости.

B. Объединением двух множеств A и B называется множество М = A È B, состоящее из всех элементов, принадлежащих хотя бы одному из множеств A или B (или обоим). При этом каждый элемент входит в объединение один раз. Символ È означает операцию объединения множеств (области С, D, E вместе на рис. 1.2). Объединение трех и более множеств определяется аналогично (показано редкой штриховкой на рис. 1.3).

C. Разностью М = A \ B двух множеств A и B называется множество, состоящее из всех элементов A, не принадлежащих B. Иначе говоря, чтобы получить разность, нужно из множества A удалить его общие элементы с множеством B (на рис. 1.2 разность A\B=C ). Разность B \ A – область E на рис. 1.2.

Симметрическую разность называют также суммой по модулю 2. Очевидно соотношение: АΔВ = (A È В) \ (A ∩ B).

На рис. 1.4 – частные случаи общей картины, изображенной на рис. 1.2.

Если С = A \ B = Æ, т.е. A Í B, то D = A, E = B \ A, (рис. 1.4, а).

Если E = B \ A = Æ, т.е. B Í A, то С = A \ B, D = B (рис. 1.4, в).

При равенстве множеств A и B и имеем C = E = Æ, D = A = B, (рис. 1.4, г).

E. Пусть A – некоторое множество в универсальном множестве U. Дополнением множества A называется множество, состоящее из всех элементов множества U, не принадлежащих A. Иными словами, = U \ A (рис. 1.5).

Примеры. 1. Пересечением множества 5-этажных домов и множества кирпичных домов является множество кирпичных пятиэтажек.

2. Пусть в множестве учеников школы (оно будет служить универсальным множеством U) A – подмножество учащихся, занимающихся спортом; B – подмножество учащихся, интересующихся музыкой; C – подмножество мальчиков. Тогда пересечению A ∩ B принадлежат все учащиеся, увлекающиеся и спортом, и музыкой; в пересечение A ∩ C входят мальчики, увлекающиеся музыкой; объединение A È B – множество учащихся, увлекающихся или спортом, или музыкой, или тем и другим; дополнение – множество школьниц; разность C \ B – множество мальчиков, не интересующихся музыкой; разность B \ C – множество девочек, увлекающихся музыкой.

3. Пусть множество натуральных чисел A = <1, 2, 3, 4, 6, 8, 12, 24>– делители числа 24;
B = <1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90>– делители числа 90. Тогда пересечение
A ∩ B = <1, 2, 3, 6>– множество общих делителей этих чисел (6 – наибольший общий делитель).

С помощью введенных операций можно образовывать более сложные комбинации. Например, формула (A \ B)∩ C представляет множество элементов множества A, не принадлежащих B, но принадлежащих C (рис. 1.6); множество A È (B ∩ C) содержит все элементы, которые принадлежат A, а также общие элементы множеств B и C (рис. 1.7).

Упражнение. Сформулируйте словами, какие подмножества универсального множества U учеников школы (пример 2) представляются формулами , C \ (AÈ B), (A ∩ B) \ .

2. На диаграммах Венна легко проверить соотношения:

Перечислим основные свойства операций над множествами. Пусть U – универсальное множество, A, B, C – его подмножества, Æ – пустое множество. Равенства 1–10, 15–18 относятся к операциям объединения и пересечения; равенства 11–14 и 19–21 – к операции дополнения.

11. = ∩ 12. = È

13. A È = U 14. A ∩ = Æ

19. = Æ 20. = U

21. = A

Приведем также некоторые свойства операции разности множеств: A \ B = A ∩ ; A \ A = Æ;
A \ Æ = A; A \ U = Æ; U \ A = .

3.Разбиение множества A – такая система <B_α> непустых подмножеств множества A, что все попарные пересечения – пусты (B_i ∩ B_j = Æ, если i ≠ j – это свойство называется чистотой разбиения), а их объединение ÈB_α равно A (это называется полнотой разбиения). Сами
B_α называются классами, или блоками разбиения.

При анкетировании или классификации объекты распределяются по группам; не входящие в ту или иную конкретную группу, могут составлять группировку «прочие» – для полноты разбиения.

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

Множество квартир дома разбивается на подмножества квартир, расположенных на одном этаже; другое разбиение – на подмножества квартир из одного подъезда.

Множество R действительных чисел разбивается на множество рациональных и множество иррациональных чисел; множество Z целых чисел разбивается на множество четных и множество нечетных чисел.

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

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

Указание: множество M₀, например, можно представить так: M₀ = .

Замечание. Стоит заметить, что возможно и другое представление: M₀ = ∩ ∩ (равенство этих двух формул – обобщение закона де Моргана).

Порождающая процедура

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

Простейший пример – задание последовательности элементов множества формулой, содержащей параметр: A = <X_k = 3 + 2(k 2 + 1)>, k = 0, 1, 2.

Задавая различные значения параметра k, мы можем вычислять элементы множества
A: X₀ = 5, X₁ = 7, X₂ = 13 и т.д. Подобное задание может быть явным, как в данном примере, или неявным, требующим разрешения. В частности, могут использоваться возвратные, или рекуррентные соотношения, когда одни элементы множества определяются через другие.

Примеры: 1. Арифметическая прогрессия определяется заданием ее первого члена а₁, разности прогрессии d и соотношением а_n+1 = а_n + d для n ≥ 1. Рекуррентная формула позволяет вычислять значения а₂ = а₁ + d, а₃ = а₂ + d = а₁ +2d, а₄ = а₃ + d = а₁ + 3d и т.д. Можно выразить
n-й член прогрессии в явном виде: а_n = а₁ + d • (n – 1).

Последняя формула позволяет последовательно вычислять значения а₃ = а₂ + а₁ = 1 + 1 = 2,
а₄ = а₃ + а₂ = 2 + 1 = 3, а₅ = а₄ + а₃ = 3 + 2 = 5, а₆ = а₅ + а₄ = 5 + 3 = 8. и т.д. Выражение общего
n-го члена этой последовательности в явном виде существует, но более сложно.

Рассмотрим еще один способ задания числового множества M:

Упражнение. Проследите, какое число в множестве М порождается, начиная с элемента 5, конечной последовательностью операций (2), (3), (3), (2), (2), (3), (2).

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций.

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций.

Источник