Суббота, 10.12.2016, 02:05
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 7
Гостей: 7
Пользователей: 0
» »
10:15
Подмножества множеств

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

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

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

Решение:

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

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

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

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

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

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

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

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

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


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


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


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

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

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

 

В примере 1 множество А = {а, с, р, о} состоит из четырех элементов, n=4, следовательно, число всех подмножеств равно 24=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. Если вам необходимо решение своей задачи, то набираем элементы множества на латинице, через запятую, как показано в примере.

 

Категория: Теория множеств | Просмотров: 11673 | Добавил: Admin | Теги: диаграмы Эйлера-Венна, характеристическое свойство, равенство множеств | Рейтинг: 0.0/0


Похожие материалы:

Всего комментариев: 0
avatar
  .