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

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

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

Пример 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) Перечисление – в списке задаются все элементы множества.

Например:

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

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

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

Множество натуральных чисел меньших 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 и
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

• #
• #
• #