На простом примере напомним, что называется подмножеством, какие бывают подмножества (собственные и несобственные), формулу нахождения числа всех подмножеств, а также калькулятор, который выдает множество всех подмножеств.
Пример 1. Дано множество А = <а, с, р, о>. Выпишите все подмножества
данного множества.
Решение:
Несобственные: <а, с, р, о>, Ø.
Всего: 16 подмножеств.
Пояснение. Множество A является подмножеством множества B если каждый элемент множества A содержится также в B.
• пустое множество ∅ является подмножеством любого множества, называется несобственным;
• любое множество является подмножеством самого себя, также называется несобственным;
• У любого n-элементного множества ровно 2 n подмножеств.
Последнее утверждение является формулой для нахождения числа всех подмножеств без перечисления каждого.
Вывод формулы: Допустим у нас имеется множество из n-элементов. При составлении подмножеств первый элемент может принадлежать подмножеству или не принадлежать, т.е. первый элемент можем выбрать двумя способами, аналогично для всех остальных элементов (всего n-элементов), каждый можем выбрать двумя способами, и по правилу умножения получаем: 2∙2∙2∙ . ∙2=2 n
Для математиков сформулируем теорему и приведем строгое доказательство.
Теорема . Число подмножеств конечного множества, состоящего из n элементов, равно 2 n .
1. Для n = 1 (база индукции) (и даже для n = 2, 3) теорема доказана.
2. Допустим, что теорема доказана для n = k, т.е. число подмножеств множества, состоящего из k элементов, равно 2 k .
3. Докажем, что число подмножеств множества B, состоящего из n = k + 1 элемента равно 2 k+1 .
Выбираем некоторый элемент b множества B. Рассмотрим множество A = 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 4 =16.
Если вам необходимо выписать все подмножества, или составить программу для написания множества всех подмножеств, то имеется алгоритма для решения: представлять возможные комбинации в виде двоичных чисел. Поясним на примере.
Пример 2. Eсть множество , в соответствие ставятся следующие числа:
000 = <0>(пустое множество)
001 =
010 =
011 =
100 =
101 =
110 =
111 =
Калькулятор множества всех подмножеств.
В калькуляторе уже набраны элементы множества А = , достаточно нажать кнопку Submit. Если вам необходимо решение своей задачи, то набираем элементы множества на латинице, через запятую, как показано в примере.
Множество – совокупность любых объектов. Множества обозначают большими буквами латинского алфавита – от A до Z.
Основные числовые множества: множество натуральных чисел и множество целых чисел, всегда обозначаются одними и теми же буквами:
N – множество натуральных чисел
Z – множество целых чисел
Элемент множества – это любой объект, входящий в состав множества. Принадлежность объекта к множеству обозначается с помощью знака ∈ . Запись
читается так: 5 принадлежит множеству Z или 5 – элемент множества Z .
Множества делятся на конечные и бесконечные. Конечное множество – множество, содержащее определённое (конечное) количество элементов. Бесконечное множество – множество, содержащее бесконечно много элементов. К бесконечным множествам можно отнести множества натуральных и целых чисел.
Для определения множества используются фигурные скобки, в которых через запятую перечисляются элементы. Например, запись
означает, что множество L состоит из четырёх чётных чисел.
Термин множество употребляется независимо от того, сколько элементов оно содержит. Множества не содержащие ни одного элемента называются пустыми.
Подмножество
Подмножество – это множество, все элементы которого, являются частью другого множества.
Визуально продемонстрировать отношение множества и входящего в него подмножества можно с помощью кругов Эйлера. Круги Эйлера – это геометрические схемы, помогающие визуализировать отношения различных объектов, в нашем случае, множеств.
Рассмотрим два множества:
Каждый элемент множества L принадлежит и множеству M, значит, множество L является подмножеством множества M. Такое соотношение множеств обозначают знаком ⊂ :
Запись L⊂M читается так: множество L является подмножеством множества M .
Множества, состоящие из одних и тех же элементов, независимо от их порядка, называются равными и обозначаются знаком = .
Рассмотрим два множества:
Так как оба множества состоят из одних и тех же элементов, то L = M.
Пересечение и объединение множеств
Пересечение двух множеств – это совокупность элементов, принадлежащих каждому из этих множеств, то есть их общая часть. Пересечение обозначается знаком ∩ .
Запись L∩M читается так: пересечение множеств L и M .
Из данного примера следует, что пересечением множеств называется множество, которое содержит только те элементы, которые встречаются во всех пересекающихся множествах.
Объединением двух множеств называется множество, содержащее все элементы исходных множеств в единственном экземпляре, то есть если один и тот же элемент встречается в обоих множествах, то в новое множество этот элемент будет включён только один раз. Объединение обозначается знаком ∪ .
Запись L∪M читается так: объединение множеств L и M .
При объединении равных множеств объединение будет равно любому из данных множеств: