Как найти множества

Примеры решения типовых задач

1. Записать множество Е, если , причем А=, B=.
Решение.
есть не что иное, как объединение множеств А и В, т.е. множество Е будет состоять из элементов, принадлежащих как множеству А, так и множеству В: Е=.

2. Записать множество , если А=, B=.
Требуется выполнить операцию пересечения т.е. множество Е будет состоять только из элементов, одновременно входящих как в множество А, так и в множество В: Е=.

3. Записать множество , если А=, B=.
Требуется выполнить операцию разности т.е. множество Е будет состоять из всех элементов множества А, не принадлежащих В: Е=.

4. Записать множество , если А=, B=.
Из предыдущего примера имеем . Для получения окончательного ответа требуется выполнить операцию дополнения т.е. множество Е будет состоять из элементов множества В: Е=.

5. Проиллюстрировать с помощью кругов Эйлера следующую формулу:
Выполняя действие в скобках получим:

После этого получаем А\Е т.е. необходимо выделить участок множества А, не принадлежащий множеству Е. Ответ примет форму:

6. Проиллюстрировать с помощью Диаграмм Венна верность тождества:

Проиллюстрируем левую часть тождества, обозначив сначала объединение множеств В и С,

затем пересечение множеств А и . Окончательный вид левой части:

Теперь проиллюстрируем правую часть:

окончательный вид правой части:

Как видим диаграммы совпадают, следовательно тождество верно.

7. По диаграмме Венна записать формулу:

8. Доказать
Решение.

по закону да Моргана и закону дистрибутивности

9. Доказать, что , где А и В — множества.
Решение. — по определению операции разности.
Подставим выражение в формулу и вынесем А за скобки:

10. Доказать, что тогда и только тогда, когда иначе .
Решение. Пусть U — универсальное множество, тогда .
Покажем, что .
Пусть .
Покажем, что .
Пусть .
Отсюда следует, что .

© 2010 Харьковский национальный университет радиоэлектроники, ПОЭВМ, Белоус Наталия Валентиновна, belous@kture.kharkov.ua
Разработано с помощью LERSUS

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

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

• Теория множеств без страха
• Об операциях с множествами без боли
• Множества вокруг нас
• Заключение

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

Бесплатные курсы по программированию в Хекслете

• Освойте азы современных языков программирования
• Изучите работу с Git и командной строкой
• Выберите себе профессию или улучшите навыки

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

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

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

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

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

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

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

Диаграмма Венна — хорошая база для понимания теории множеств, так как с её помощью легче понять более сложные вещи. Допустим, вы хотите представить два множества книг в какой-то структуре данных. Вы уже знаете, что книги надо разделить на два множества: которые человек прочитал и которые есть у него дома. Для удобства назовём первое множество 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.

var s = new Set(); s.add(2); // Set s.add(45); // Set s.add(45); // Set s.add('hello world!'); // Set s.has(2); // true s.has('cats'); // false s.size; // 3 s.delete(45); // Set s.has(45); // false 

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

Бесплатные курсы по программированию в Хекслете

• Освойте азы современных языков программирования
• Изучите работу с Git и командной строкой
• Выберите себе профессию или улучшите навыки

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

Литература: Сборник задач по математике. Часть 1. Под ред А. В. Ефимова, Б. П. Демидовича.

Под множеством понимается любая совокупность некоторых объектов. Эти объекты называются элементами множества. Множества обозначают большими буквами, а элементы — маленькими.

То что элемент $a$ принадлежит множеству $A$ (то есть является элементом множества $A$) записывают так $a\in A,$ а то что элемент $b$ не принадлежит множеству $A$ (не является его элементом) записывают так $b\notin A.$

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

Запись $A\subset B $ ($A$ содержится в $B$) означает, что каждый элемент множества $A$ является элементом множества $B;$ в этом случае множество $A$ называется подмножеством множества $B.$ Множества $A$ и $B$ называют равными $(A=B),$ если $A\subset B$ и $B\subset A.$

Существует два основных способа задания (описания) множеств.

а) Множество $A$ определяется непосредственным перечислением всех своих элементов $a_1, a_2, . a_n,$ то есть записывается в виде $$A=\.$$

Например множество простых чисел от 10 до 20 можно записать так: $\.$

б) Множество $A$ определяется как совокупность тех и только тех элементов из некоторого основного множества $T,$ которые обладают общим свойством $\alpha.$ В этом случае используется обозначение $$A=\,$$ где запись $\alpha(x)$ означает, что элемент $x$ обладает свойством $\alpha.$

Объеденением множеств $A$ и $B$ называется множество $$A\cup B=\$$

Пересечением множеств и называется множество $$A\cap B=\$$

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

$$A\cup B=B\cup A;\qquad A\cap B=B\cap A;$$

$$A\cup(B\cup C)=(A\cup B)\cup C; (A\cap B)\cap C=A\cap(B\cap C);$$

$$(A\cup B)\cap C= (A\cap C)\cup(B\cap C);\quad (A\cap B)\cup C= (A\cup C)\cap(B\cup C);$$

$$A\cup A=A;\quad A\cap A=A.$$

Множество, стостоящее из всех элементов множества $A,$ не принаждлежащих множеству $B,$ называется разностью множеств $A$ и $B:$ $$A\setminus B=\.$$

Если $A\subset B$ , то $B\setminus A$ называют дополнением множества $A$ до множства $B:\,\, A_B’.$

Если, в частности, $A -$ подмножество некоторого универсального множества $U,$ то разность $U\setminus A$ обозначается символом $\overline A$ или $A’$ и называется дополнением множества $A$ (до множества $U$).

Из определения дополнения множества следуют равенства $$A\cup A’ =U;\quad A\cap A’ =\emptyset,\quad (A’)’=A.$$

Симметрической разностью множеств $A$ и $B$ называют множество $A\Delta B,$ состоящее из тех и только тех элементов, которые принадлежат только одному из множеств $A$ или $B,$ то есть $$A\Delta B =(A\setminus B)\cup (B\setminus A).$$

Для любых подмножеств $A$ и $B$ множества $U$ справедливы следующие равенства, которые называют законами двойственности или законами де Моргана: $$(A\cup B)’=A’\cap B’;\quad (A\cap B)’=A’\cup B’.$$

Примеры:

Доказать справдливость равенств

1) $(A\cap B)’=A’\cup B’$

Доказательство .

$x\in(A\cap B)’ \Leftrightarrow x\notin (A\cap B)\Leftrightarrow x\notin A\vee x\notin B \Leftrightarrow $ $x\in A’\vee x\in B’ \Leftrightarrow$

$ x\in (A’\cup B’)\Leftrightarrow (A\cap B)’= A’\cup B’. $

Что и требовалось доказать.

2) $(A\setminus B)\setminus C =A\setminus (B\cup C).$

Доказательство .

$x\in (A\setminus B)\setminus C \Leftrightarrow a\in A\setminus B \wedge a\notin C \Leftrightarrow (a\in A \wedge a\notin B)\wedge a\notin C\Leftrightarrow $

$\Leftrightarrow a\in A \wedge (a\notin B \wedge a\notin C)\Leftrightarrow a\in A \wedge a\notin (B\cup C)\Leftrightarrow a\in A\setminus(B\cup C).$

Что и требовалось доказать.

3) $A\setminus (A\setminus B)=A\cap B.$

Доказательство .

$a\in A\setminus(A\setminus B)\Leftrightarrow (a\in A)\wedge (a\notin A\setminus B)\Leftrightarrow $

$(a\in A) \wedge ((a\notin A)\vee (a\in B))\Leftrightarrow $

$((a\in A)\wedge(a\notin A))\vee((a\in A)\wedge(a\in B))\Leftrightarrow $

$(a\in A) \wedge (a\in B) \Leftrightarrow a\in A\cap B.$

Что и требовалось доказать.

4) $A\cup(B\setminus C)\supset (A\cup B)\setminus C.$

Доказательство .

$a\in (A\cup B)\setminus C\Leftrightarrow (a\in A \vee a\in B)\wedge a\notin C \Leftrightarrow$

$ (a\in A \wedge a\notin C)\vee(a\in B\wedge a\notin C)\Rightarrow (a\in A )\vee(a\in B\wedge a\notin C)\Leftrightarrow$

$ a\in A\cup(B\setminus C).$

Что и требовалось доказать.

1.28. (a)

Установить, какая из двух записей верна:

Решение.

Запись $\\in\\>$ означает, что эелемент $\$ содержится в множестве, состоящем из трех элементов $\,$ $\,$ и $\\>.$ Очевидно элемента $\$ среди данных трех элементов нет. Поэтому такая запись не верна.

Запись $\\subset\\>$ означает, что все элементы множества $\$ (то есть $\,$ и $\$ ) содержатся в множестве $\\>.$ Последнее множество состоит из элементов $\,$ $\,$ и $\\>,$ поэтому данная запись верна.

В задачах 1.29, 1.30 заданные множества задать перечислением всех своих элементов

Решение.

Найдем множество действительных решений уравнения $x^3-3x^2+2x=0:$

Решим квадратное уравнение $x^2-3x+2=0.$

Все корни уравнения действительные, поэтому запишем ответ:

Решение.

Решим неравенство $x+\frac\leq 2:$

Поскольку $x>0,$ то $x^2+1\leq 2x.$ Решим квадратное уравнение

$x^2-2x+1=0\Rightarrow (x-1)^2=0\Rightarrow x_=1.$

Так как $y=x^2-2x+1$ это парабола, направленная осями вверх, то при всех остальных значениях $x,$ функция будет положительна.

Таким образом решение неравенства $x+\frac\leq 2$ при условии $x>0:$

Ответ: $\.$

Домашнее задание.

1.28 (б)

Установить, какая из двух записей верна:

Ответ: обе записи верны.

В задачах 1.31, 1.32 заданные множества задать перечислением всех своих элементов

Изобразить на координатной плоскости следующие множества:

1.43. Описать перечислением всех элементов множества $A\cup B, \,\, A\cap B, \,\, A\setminus B, \,\, B\setminus A.$

Ответ: $A\cup B=\,\,\, A\cap B =\, \,\,\, A\setminus B=\, B\setminus A= \.$

В задачах 1.50, 1.53, приняв отрезок за универсальное множество $T=[0, 1]$ найти и изобразить на числовой оси дополнения следующих множеств:

Ответ: $(0, \, 1).$

1.53. $\\cup[3/4,\, 1).$

Ответ: $[0, \, 1/4)\cup (1/4, 3/4)\cup \.$

1.55. Доказать, что операции $\cup$ и $\cap$ связаны законом дистрибутивности:

$$(A\cup B)\cap C=(A\cap C)\cup(B\cap C);$$

$$(A\cap B)\cup C=(A\cup C)\cap(B\cup C);$$

1.57. $A\setminus B=A\cap\overline B.$

1.58. $\overline=\overline A\cup B.$

3. Пересечение и объединение множеств

Пересечением множеств \(A\) и \(B\) является множество их общих элементов, т. е. всех элементов, принадлежащих и множеству \(A\), и множеству \(B\). Пересечение множеств обозначается: A ∩ B .

Для наглядности множества изображают кругами Эйлера.

На рисунке зелёным цветом показано пересечение множеств \(A\) и \(B\).
Определение можно коротко записать так: A ∩ B = z z ∈ A и z ∈ B .

найди пересечение множеств \(X\) и \(Y\), если X = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и Y = 2, 4, 6, 8, 10 .

Решение. Найдём общие элементы множеств.
X ∩ Y = 2, 4, 6, 8 .

Объединением множеств \(A\) и \(B\) является множество элементов, принадлежщих множеству \(A\), или множеству \(B\), или обоим множествам. Объединение множеств обозначается: A ∪ B .

На рисунке объединение множеств закрашено в зелёный цвет.
Определение ещё можно записать так: A ∪ B = z z ∈ A или z ∈ B .

найди объединение множеств \(A\) и \(B\), если X = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и Y = 2, 4, 6, 8, 10 .