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

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

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

Пример 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. Если вам необходимо решение своей задачи, то набираем элементы множества на латинице, через запятую, как показано в примере.

Нахождение числа всех подмножеств данного множества

Если
задано некоторое множество А,
то можно рассматривать новое множество
М (А) –
множество всех его подмножеств.

Пример
1.
Сколько
подмножеств имеет множество А={}?

По
свойствам отношения включения, имеем
ÆА
и А.

Таким
образом, одноэлементное множество А={}
имеет
2 подмножества.

Пример
2.
Сколько всего подмножеств имеет
двухэлементное множество А={а,
в}?

По
свойствам отношения включения, имеем
ÆА
и А.

Одноэлементные
подмножества: {а},
{в}.

Таким
образом, двухэлементное множество А={а,
в}
всего
имеет 4 подмножества.

Пример
3.
Сколько всего подмножеств имеет
трехэлементное множество А
=
{,
○, ◊}?

По
свойствам отношения включения, имеем
ÆА
и А.

Одноэлементные
подмножества: {},
{○},
{◊}.

Двухэлементные
подмножества: {,
○},
{,
◊},
{○,
◊}.

Таким
образом, трехэлементное множество А
=
{,
○, ◊}
всего имеет 8 подмножеств.

Пример
4.
Сколько всего подмножеств имеет
четырехэлементное множество А
=
{а,
в,
с, d}?

По
свойствам отношения включения, имеем
ÆА
и А.

Одноэлементные
подмножества: {а},
{в}, {с}, {d}.
Двухэлементные
подмножества: {а,
в}, {а, с}, {a,
d},
{в, с},
{в,
d},
{с, d}.
Трехэлементные
подмножества: {а,
в, с}, {a,
в, d},
{а, с, d},
{в, с,
d}.

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

Нетрудно
заметить, что с увеличением количества
элементов множества А,
число всех его подмножеств значительно
увеличивается. Возникает
вопрос: сколько подмножеств имеет
множество из n
– элементов?

Ответ
на поставленный вопрос дает следующее
утверждение.

Теорема
5. Конечное
множество, содержащее n
элементов, имеет 2^п
подмножеств, то есть если
А_п
= {а₁,
а₂,
… , a_п
}, то
п(М(А_п))=2^п.

 Доказательство
проведем,
используя метод математической индукции.

1)
Путь п
=
1, то есть А₁
= {
а₁}.
Значит, М(А₁)=
{Æ,
{
а₁}}.

В
этом случае п(М(А₁))
=
2¹
=
2 что и доказывает справедливость теоремы
при п
= 1.

2)
Пусть п
= к,
то
есть A_к
= {
а₁,
а₂,
…, a_к
}.

Предположим,
что п(М(A_к))
=
2,
то есть множество A_к
имеет
2
подмножеств.

3)
Докажем, что тогда множество A_к+1,
имеет
2
подмножеств. В самом деле, если к элементам
множества A_к,
содержащего
к
элементов,
добавить еще один элемент a_к+1,
то к имеющимся 2
подмножествам добавятся еще 2
новых подмножества, и, следовательно,
множество A_к+1,
содержащее
к
+
1 элементов, будет иметь 2
+ 2
=
2
2
= 2
подмножеств.

Таким
образом, п(М(A_к+1))
=
2.

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

Понятие факториала

Название «факториал»
происходит от слова «factor»
− «множитель». Термин «factorielle»
ввёл французский математик Луи Арбогаст
(1759–1803) в 1800 году.¹³

Факториал
– это функция,
определённая на множестве целых
неотрицательных чисел
,
значение которой равно произведению
целых неотрицательных чисел от 1 до
данного числаn,
то есть 1∙2∙3∙ …∙n;
Обозначают символом n!.

По определению 0!
= 1, 1! = 1.

Обозначение n!
впервые использовал французский
математик Христиан Крамп (1760 – 1826 гг.)
в 1808 году.

По
определению факториала имеем:
,.

Пример 1.
Вычислим:

Пример
2. Упростим
выражение:

Пример
3. Докажем
формулу
.

 Воспользуемся
методом математической индукции.

1. При
   п=1
   имеем,
   откуда 1=1, значит дляп=1
   формула верна.

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

3. Докажем,
   что формула верна, для п=к+1,
   то есть

.

Действительно,

=,
что и требовалось доказать.

На
основании метода математической индукции
заключаем, что формула верна для любого
натурального числа п.

Пример
4. Найти сумму

Решение.
Заменим
каждое слагаемое разностью по формуле

.

Имеем,

=так как все слагаемые в левой части
равенства, за исключением второго и
предпоследнего взаимно уничтожаются.

Следовательно,
=

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

Определение[править | править код]

Множество называется подмножеством множества , если все элементы, принадлежащие , также принадлежат ^[1]. Формальное определение:

Существует две системы символических обозначений для подмножеств:

« является подмножеством (нестрогим)» обозначается	« является строгим подмножеством » обозначается	Примечание
		Символ является аналогом , то есть в случае допускается равенство множеств; символ является аналогом , то есть в случае в есть элементы, которых нет в .
		Для понятия «(нестрогое) подмножество» используется более простой символ, так как оно считается более «фундаментальным».

Обе системы обозначений предусмотрены стандартом ISO 31-11, но используют символ в разных смыслах, что может привести к путанице. В данной статье мы будем использовать последнюю систему обозначений.

Множество называется надмно́жеством множества , если является подмножеством множества .

То, что является надмножеством множества , записывают , то есть

Множество всех подмножеств множества обозначается .

Множества и называются равными , только когда они состоят из одних и тех же элементов, то есть и .^[2]

Собственное и несобственное подмножество[править | править код]

Любое множество среди своих подмножеств содержит само себя и пустое множество. Само множество и пустое множество называют несобственными подмножествами, остальные подмножества называют собственными^[3].

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

множество является собственным подмножеством множества , только если и , .

Зарубежная литература[править | править код]

В зарубежной литературе несобственные подмножества в вышеуказанном смысле (само множество B и пустое множество) называют тривиальными, а собственные — нетривиальными, а термин «собственное подмножество» (proper subset) применяется в значении «строгое включение A в B» или «подмножество A, строго входящее в множество B, то есть такое, которому не принадлежит как минимум один элемент множества B», то есть здесь понятие «собственное подмножество» уже, наоборот, включает пустое множество.

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

множество является нетривиальным подмножеством множества , если является собственным подмножеством (proper subset) и .

Примеры[править | править код]

Свойства[править | править код]

Отношение подмножества обладает целым рядом свойств^[4].

Подмножества конечных множеств[править | править код]

Если исходное множество конечно, то у него существует конечное количество подмножеств. А именно, у -элементного множества существует подмножеств (включая пустое). Чтобы убедиться в этом, достаточно заметить, что каждый элемент может либо входить, либо не входить в подмножество, а значит, общее количество подмножеств будет -кратным произведением двоек. Если же рассматривать только подмножества -элементного множества из элементов, то их количество выражается биномиальным коэффициентом . Для проверки этого факта можно выбирать элементы подмножества последовательно. Первый элемент можно выбрать способами, второй способом, и так далее, и, наконец, -й элемент можно выбрать способом. Таким образом мы получим последовательность из элементов, и ровно таким последовательностям соответствует одно подмножество. Значит, всего найдётся таких подмножеств.

Примечания[править | править код]

Литература[править | править код]

• Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств.. — 3-е изд., стереотип. — М.: МЦНМО, 2008. — 128 с. — ISBN 978-5-94057-321-0.
• Биркгоф Г., Барти Т. Современная прикладная алгебра. — М.: Мир, 1976. — 400 с.

Ссылки[править | править код]

• Weisstein, Eric W. Subset (англ.) на сайте Wolfram MathWorld.

Учитывая набор 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 – это размер заданного набора.