Как составить все подмножества множества

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

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

Пример 1.  Дано множество А = {а, с, р, о}. Выпишите все подмножества
данного множества.
Решение:

Собственные подмножества: {а} , {с} , {р} , {о} , {а, с} , {а, р} , {а, о}, {с, р} , {с, о } ∈, {р, о}, {а, с,р} , {а, с, о}, {с, р, о}.

Несобственные: {а, с, р, о}, Ø.

Всего: 16 подмножеств.

Пояснение. Множество A является подмножеством множества B если каждый элемент множества A содержится также в B.

• пустое множество ∅ является подмножеством любого множества, называется несобственным;
• любое множество является подмножеством самого себя, также называется несобственным;
• У любого n-элементного множества ровно 2ⁿ подмножеств.

Последнее утверждение является формулой для нахождения числа всех подмножеств без перечисления каждого.

Вывод формулы: Допустим у нас имеется множество из n-элементов. При составлении подмножеств первый элемент может принадлежать подмножеству или не принадлежать, т.е. первый элемент можем выбрать двумя способами, аналогично для всех остальных элементов (всего n-элементов), каждый можем выбрать двумя способами, и по правилу умножения получаем: 2∙2∙2∙ …∙2=2ⁿ

Для математиков сформулируем теорему и приведем строгое доказательство.

Теорема . Число подмножеств конечного множества, состоящего из n элементов, равно 2ⁿ .

Доказательство. Множество, состоящее из одного элемента a, имеет два (т.е. 2¹ ) подмножества: ∅ и {a}. Множество, состоящее из двух элементов a и b, имеет четыре (т.е. 2² ) подмножества: ∅, {a}, {b}, {a; b}.
Множество, состоящее из трех элементов a, b, c, имеет восемь (т.е. 2³ ) подмножеств:
∅, {a}, {b}, {b; a}, {c}, {c; a},{c; b}, {c; b; a}.
Можно предположить, что добавление нового элемента удваивает число подмножеств.
Завершим доказательство применением метода математической индукции. Сущность этого метода в том, что если утверждение (свойство) справедливо для некоторого начального натурального числа n₀ и  если  из  предположения,  что  оно  справедливо  для  произвольного  натурального n = k ≥ n₀ можно доказать его справедливость для числа k + 1, то это свойство справедливо для всех натуральных чисел.

1. Для n = 1 (база индукции) (и даже для n = 2, 3) теорема доказана.

2.  Допустим, что теорема доказана для n = k, т.е. число подмножеств множества, состоящего из k элементов, равно 2^k .

3. Докажем, что число подмножеств множества B, состоящего из n = k + 1 элемента равно 2^k+1 .
Выбираем некоторый элемент b множества B. Рассмотрим множество A = B {b}. Оно содержит k элементов. Все подмножества множества A – это подмножества множества B, не содержащие элемент b и, по предположению, их 2^k штук. Подмножеств множества B, содержащих элемент b, столько же, т.е. 2^k
штук.

Следовательно, всех подмножеств множества B: 2^k + 2^k = 2 ⋅ 2^k = 2^k+1 штук.
Теорема доказана.

В примере 1 множество А = {а, с, р, о} состоит из четырех элементов, n=4, следовательно, число всех подмножеств равно 2⁴=16.

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

Пример 2. Eсть множество {a b c}, в соответствие ставятся следующие числа:
000 = {0} (пустое множество)
001 = {c}
010 = {b}
011 = {b c}
100 = {a}
101 = {a c}
110 = {a b}
111 = {a b c}

Калькулятор множества всех подмножеств.

В калькуляторе уже набраны элементы множества А = {а, с, р, о}, достаточно нажать кнопку Submit. Если вам необходимо решение своей задачи, то набираем элементы множества на латинице, через запятую, как показано в примере.

Подмножества множеств. Алгебра подмножеств

Два множества A и
B равны, если они состоят из одних и тех
же элементов.

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

Подмножества. Определение
равенства множеств можно сформулировать
иначе, используя понятие подмножества.

Определение. Множество
A называется подмножеством множества
B
,
если каждый элемент A является элементом
B.

.

Следствие 1. Очевидно,
для любого множества A, т.к. каждый элемент
из A есть элемент из A.

Следствие 2. Для
любого множества A,
,
ибо если бы пустое множество не являлось
подмножеством A, то в пустом подмножестве
существовали бы элементы, не принадлежащие
A. Однако пустое множество не содержит
вообще ни одного элемента.

Если
,
то пишут,
и если,
то A – собственное подмножество B.

Понятие подмножества
множеств позволяет легко формализовать
понятие равенства двух множеств.

Утверждение. Для
любых A и B

. (1.1)

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

Замечание. Отношение
включения 
обладает рядом очевидных свойств:

(рефлексивность);

(транзитивность).

Для любого
множества X можно определить специальное
множество всех подмножеств множества
X, которое называется булеаном ℬ,
которое включает в себя само множество
X, все его подмножества и пустое множество
.

Пример. Пусть
– это множество, состоящее из трех
элементов. Тогда булеанℬ(X)
это множество:

ℬ

Собственными
подмножествами ℬ(X)
являются следующие множества:

{a},{b},{c},{a,b},{b,c},{a,c}.

В общем случае,
если множество X содержит n элементов,
то множество его подмножеств ℬ(X)
состоит из

элементов.

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

Пусть U – универсальное
множество,
.
Тогда для множеств X,Y можно определить
операции.

Определение. Объединением
множеств X и Y называется множество
,
состоящее из элементов, входящих хотя
бы в одно из множеств (X или Y):

. (1.2)

Рис.
1.1 – Объединение
множеств Рис.
1.2 – Пересечение
множеств

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

. (1.3)

Определение. Разностью
множеств X и Y называется множество
,
состоящее из элементов, входящих в
множество X, но не входящих в Y:

. (1.4)

Рис.
1.3 – Разность
множеств
Рис.
1.4 –
Симметрическая

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

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

. (1.5)

Определение. Для
любого множества
дополнением множествадо U называется такое множество,
что:

. (1.6)

Рис.
1.5 – Дополнение
множества X до U

На рис. 1.1 
1.5 представлены диаграммы Венна, наглядно
демонстрирующие результаты операций
.

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

, (1.7)

. (1.8)

В справедливости
законов де Моргана легко убедиться
самостоятельно.

В таблице 1.1
представлены основные свойства операций
над множествами.

Таблица 1.1

Операции объединения
и пересечения можно обобщить. Пусть
– множество индексов,– семейство подмножеств множества X.

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

,

.

Определение. Семейство
подмножеств
множества X называетсяпокрытием
множества X, если:
.

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

Определение. Класс
K подмножеств из U называется алгеброй,
если:

1. ;

2. из
того, что
следует, что;

3. из
того, что
следует, что.

Пример. Пусть
,
тогда классобразует алгебру.

Определение. Класс
F подмножеств из U образует
-алгебру,
если:

1. ;

2. из
того, что
следует;

3. из
того, что
,следует, что.

Пример. Множество
всех подмножеств U образует
-алгебру,
т.е.ℬ(U)
–
-алгебра.

Соседние файлы в папке ЛЕКЦИИ АиГ

• #
• #
• #

  14.04.2015904.7 Кб67Копия ЛЕКЦИЯ 14.wbk

• #
• #
• #

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

Что такое «множество», мы понимаем интуитивно. В этом смысле это понятие первично, так же как «точка» или «плоскость».

Создатель теории множеств Г.Кантор описывал множество как «многое, мыслимое нами как единое».

Приведём примеры множеств:

Конечное, бесконечное и пустое множества

Людей в салоне самолёта легко посчитать, это множество конечно.

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

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

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

Способы задания множеств

1) Перечисление – в списке задаются все элементы множества.

Например:

Множество всех континентов Земли:

{Евразия,Северная Америка,Южная Америка,Африка,Австралия,Антарктида}

Множество букв слова «математика»: {м,а,т,е,и,к}

Множество натуральных чисел меньших 5: {1,2,3,4}

2) Характеристическое свойство – указывается особенность элементов множества.

Например:

A = ${x|x gt 0, x in Bbb R}$ — множество всех действительных положительных x

B = ${n|n⋮5,n in Bbb N}$ — множество всех натуральных n, кратных 5

C = ${(x,y)|x^2+y^2 ge 1,x in Bbb R,y in Bbb R}$ – множество всех действительных точек координатной плоскости (x,y), расстояние от которых до начала координат не больше 1 (круг с центром в начале координат, радиусом 1).

D = {k|k-материк Земли} – множество всех материков планеты Земля

3) Графическое изображение – визуальное моделирование с помощью различных диаграмм (круги Эйлера, интервалы, графики и т.п.)

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

Знак $subseteq$ является аналогом $ge$, т.е. «нестрогим» неравенством. Это значит, что множества A и B могут и совпадать (любое множество является подмножеством самого себя).

Между множествами можно также ввести отношение «строгое подмножество», $A subset B$, в котором B заведомо «шире» множества A (аналог строгого неравенства $lt$).

Примеры подмножеств:

Множество людей является подмножеством приматов, живущих на Земле.

Множество натуральных чисел меньших 5 является подмножеством натуральных чисел меньших $10: A = {n|n lt 5, n in Bbb N}, B = {m|m lt 10, m in Bbb N}, A subseteq B$

Множество квадратов является подмножеством прямоугольников.

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

Примеры

Пример 1. Запишите данное множество с помощью перечисления элементов:

а) $A = {x|x^2 lt 5, x in Bbb Z}$

Задано множество целых чисел, квадрат которых меньше 5. Перечисляем:

A = {-2;-1;0;1;2}

б) $B = {x||x| ge 3, x in Bbb Z}$

Задано множество целых чисел, модуль которых не больше 3. Перечисляем:

B = {-3;-2;-1;0;1;2;3}

в) $ C = {x|(x-1)(2x+5) = 0, x in Bbb Q}$

Задано множество рациональных чисел, являющихся корнями уравнения

(x-1)(2x+5) = 0. Перечисляем:

C = {1;-2,5}

г) $D = {n|9 lt n ge 12, n in Bbb N}$

Задано множество натуральных чисел, входящих в полуинтервал $9 lt n le 12$.

Перечисляем:

D = {10;11;12}

Пример 2. Запишите данное множество с помощью характеристического свойства:

а) Множество всех натуральных чисел меньше 10

$$ A = {n|n lt 10, n in Bbb N} $$

б) Множество всех действительных чисел, кроме 0

$$ B = {x|x neq 0, x in Bbb R} $$

в) Множество всех точек с целыми координатами, принадлежащих прямой y = 2x+1

$$C = {(x,y)|y = 2x+1, x in Bbb Z, y in Bbb Z}$$

г) Множество всех целых решений уравнения $x^3+x^2+4 = 0$

$$ D = {x|x^3+x^2+4 = 0, x in Bbb Z} $$

Пример 3. Изобразите на графике в координатной плоскости данное множество:

а) $A = {(x,y)|y = x+2, x le 3, x in Bbb N}$

Задано конечное множество точек, которое можно представить перечислением:

A = {(1;3);(2;4);(3;5) }

На графике:

б)$ B = {(x,y)|y = frac{4}{x},-4 le x le -1, x in Bbb R}$

Задано бесконечное множество точек, принадлежащих данной гиперболе $y = frac{4}{x}$ в данном интервале $-4 le x le -1$. На графике:

Пример 4. Укажите и запишите с помощью перечисления одно из непустых конечных подмножеств для данного множества:

а) A = {k|k-электронное устройство}

$B subseteq A, B$ = {компьютер, смартфон, планшет}

б) A = {m|m-четырёхугольник}

$B subseteq A, B$ = {квадрат, ромб, прямоугольник}

в) A = {p|p-музыкальный инструмент}

$B subseteq A, B$ = {пианино, скрипка, виолончель}

г) A = {t|t-средство передвижения}

$B subseteq A, B$ = {автомобиль,автобус,поезд}

Пример 5*. Найдите булеан данного множества:

а) A = {5;10;27}

$$ P(A) = {{varnothing},{5},{10},{27},{5;10},{5;27},{10;27},{5;10;27} } $$

Исходное множество состоит из n = 3 элементов, булеан состоит из $2^3 = 8$ элементов.

б) B = {1;{2;16} }

$$ P(B) = {{varnothing},{1},{2;16},{1;{2;16} } } $$

Исходное множество состоит из n = 2 элементов, булеан состоит из $2^2 = 4$ элементов.

Множества

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

Множество — это совокупность любых объектов. Множества обозначают большими буквами латинского алфавита — от  A  до  Z.

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

N — множество натуральных чисел,

Z — множество целых чисел.

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

5∈Z

читается так:  5 принадлежит множеству  Z  или  5 – элемент множества  Z.

Множества делятся на конечные и бесконечные. Конечное множество — множество, содержащее определённое (конечное) количество элементов. Бесконечное множество — множество, содержащее бесконечно много элементов. К бесконечным множествам можно отнести множества натуральных и целых чисел.

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

L = {2, 4, 6, 8}

означает, что множество  L  состоит из четырёх чётных чисел.

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

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

Подмножество — это множество, все элементы которого, являются частью другого множества.

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

Рассмотрим два множества:

L = {2, 4, 6, 8}   и   M = {2, 4, 6, 8, 10, 12}.

Каждый элемент множества  L  принадлежит и множеству  M,  значит, множество  L  является подмножеством множества  M.  Такое соотношение множеств обозначают знаком  ⊂:

L⊂M.

Запись  L⊂M  читается так:  множество  L  является подмножеством множества  M.

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

Рассмотрим два множества:

L = {2, 4, 6}   и   M = {4, 6, 2}.

Так как оба множества состоят из одних и тех же элементов, то  L = M.

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

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

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

L = {1, 3, 7, 11}   и   M = {3, 11, 17, 19},  то   L∩M = {3, 11}.

Запись  L∩M  читается так:  пересечение множеств  L  и  M.

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

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

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

L = {1, 3, 7, 11}   и   M = {3, 11, 17, 19},

то   L∪M = {1, 3, 7, 11, 17, 19}.

Запись  L∪M  читается так: объединение множеств  L  и  M.

При объединении равных множеств объединение будет равно любому из данных множеств:

если  L = M,   то   L∪M = L   и   L∪M = M.

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

Например, если S установлен {x, y, x}, то подмножества S находятся:

Следовательно, различные подмножества в множестве мощностей S находятся: { {}, {x}, {y}, {x, y}, {x, x}, {x, y, x} }.

Потренируйтесь в этой проблеме

Подход 1: Использование рекурсии

Проблема очень похожа на 0/1 проблема с рюкзаком, где для каждого элемента множества S, у нас есть два варианта:

Следующее решение генерирует все комбинации подмножеств, используя приведенную выше логику. Чтобы распечатать только отдельные подмножества, сначала сортировать подмножество и исключить все соседние повторяющиеся элементы из подмножества вместе с текущим элементом в случае 2. Это показано ниже на C++, Java и Python:

Временная сложность приведенного выше решения равна O(n.2ⁿ), куда n — это размер заданного набора.

Подход 2

Для данного набора S, набор мощности можно найти, сгенерировав все двоичные числа от 0 до 2n-1, куда n это размер набора. Например, для набора S {x, y, z}, генерировать двоичные числа от 0 до 23-1 и для каждого сгенерированного числа соответствующий набор можно найти, рассматривая установленные биты в числе.

• 0 = 000 = {}
• 1 = 001 = {z}
• 2 = 010 = {y}
• 3 = 011 = {y, z}
• 4 = 100 = {x}
• 5 = 101 = {x, z}
• 6 = 110 = {x, y}
• 7 = 111 = {x, y, z}

Чтобы избежать печати повторяющихся подмножеств, сначала отсортируйте набор. Кроме того, вставьте каждое подмножество в набор. Поскольку набор поддерживает все различные комбинации, у нас будут уникальные подмножества в наборе. Ниже приведена программа на C++, Java и Python, которая демонстрирует это:

Временная сложность приведенного выше решения равна O(n.2ⁿ), куда n — это размер заданного набора.