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

• Множество B называется подмножеством множеством A, если все элементы множества B принадлежат множеству A.
  • Будем различать следующие две записи : B ⊆ A и B ⊂ A, где символы ⊆ и ⊂ представляют собой знаки включения.
    • Запись B ⊆ A читается так : « множество B включено в множество A, причем множество A является подмножеством самого себя ».
    • Запись B ⊂ A говорит о том , что все элементы множества B входят в множество A, но само множество A не является своим подмножеством .

 Выясним , сколько всего существует подмножеств данного множества . Запишем элементы заданного множества P в каком - либо порядке и каждому элементу поставим в соответствие двоичный разряд Пусть 0 ( нуль ) обозначает , что соответствующий элемент отсутствует в подмножестве , а 1 — что этот элемент входит в подмножество . Тогда каждому |P|- разрядному двоичному числу будет соответствовать определенное подмножество . Известно , что всего существует 2^|P| |P|- разрядных двоичных чисел . Следовательно , число всех подмножеств также равно 2^|P| .

 Проиллюстрируем это на примере множества P = {a, b, c}. В табл . 1 указаны элементы a, b, c, и под каждым элементом записаны двоичные цифры . В левой колонке приведены десятичные эквиваленты двоичных трехразрядных чисел . В правой части таблицы перечислены сами подмножества . В верхней строке под элементами a, b, c записаны нули . Это значит , что в подмножество с нулевым номером не входит ни один элемент множества P. Следовательно , получаем пустое подмножество.

Таблица 1

Заметим , что при табличном представлении подмножеств в таблице всегда будет присутствовать строка с номером 0 ( нуль ), которой соответствует |P|- разрядное двоичное число , состоящее из |P| нулей . Следовательно , пустое множество является подмножеством любого множества . В строке с номером 1 под элементом c записана единица . Это значит , что в подмножество с номером 1 входит элемент c, и подмножество имеет вид {c}. В строке с номером 2 единица соответствует элементу b, следовательно , подмножество номер 2 имеет вид {b}, и т . д . до последней строки , где нет нулей , что соответствует случаю , когда в подмножество входят все элементы множества P. Такое подмножество совпадает с множеством P. Таким образом , рассмотренный прием позволяет не только найти все подмножества , но и пронумеровать их .

• Подмножества бывают двух видов : собственные и несобственные .
  • Само множество P и пустое множество называются несобственными подмножествами . Все остальные подмножества называются собственными . Следовательно , всякое непустое множество P содержит два несобственных подмножества и 2^|P| – 2 собственных подмножеств . Согласно табл . 1 несобственные подмножества имеют вид ∅ и {a, b, c}, все остальные шесть подмножеств являются собственными .
• Множество всех подмножеств множества P называют булеаном этого множества P и обозначают B(P).
  • Булеан множества P = {a, b, c} имеет вид B(P) = {∅ ,{a},{b},{c},{a,b},{a,c},{b,c},{a ,b,c}}

• Кардинальное число (число элементов) любого собственного подмножества множества P меньше |P|.
  • Чтобы убедиться в этом , поставим в соответствие каждому элементу множества P двоичный разряд , как показано в табл.1. Среди всех |P|- разрядных двоичных чисел существует только одно число , не содержащее нулей . Ему соответствует несобственное подмножество , совпадающее с множеством P. Удалим это число . В каждом из оставшихся |P|-разрядных чисел содержится хотя бы один нуль , показывающий , какой элемент множества P не входит в соответствующее подмножество . А это значит , что в каждом из собственных подмножеств число элементов меньше , чем |P|.

Упражнения.

1. Сколько одноэлементных подмножеств содержится в множестве вида Q = {1, 2, 3, 4, 5}?

2. Дано множество вида A = {a, b, c, d}. Укажите верные записи (с ответами):

а ) a ∈ A – истинно; {a} ∈ A - ложно;

б ) d ⊂ A - ложно; {d} ⊂ A - истинно;

в ) ∅ ∈ A – ложно; ∅ ⊂ A - истинно;

г ) {a, b, c, d} ⊆ A – истинно; {a, b, c, d} ∈ A - ложно;

д ) {a, b} ⊂ {a, b, c} – истинно; a, b ⊆ {a, b} – ложно.

3. Сколько собственных подмножеств имеет множество M = {x / x — натуральное число ∧ x < 6}?

Решение. M = {1,2,3,4,5}, следовательно число собственных подмножеств равно

2|M|-2 = 25-2 = 32 – 2 = 30

Задачи с решением:

M0004. Известно , что число собственных подмно - жеств некоторого множества K равно числу его не - собственных подмножеств . Найдите |K| и кардинальное число булеана множества K.

M0005. В множестве R отсутствуют собственные под - множества . Определите кардинальное число множества R и кардинальное число булеана множества R.

M0006. Известно , что число собственных под - множеств некоторого множества в 15 раз больше числа его несобственных подмножеств . Найдите кардинальное число этого множества .

M0007. Некоторое множество имеет 62 собствен - ных подмножества . Найдите число элементов булеана этого множества .

M0008. Некоторое множество содержит пять одно - элементных подмножеств . Найдите кардинальное число булеана этого множества .

M0009. Кардинальное число множества S равно 7. Найдите число собственных подмножеств множества S.

M0010. Булеан некоторого множества P содержит 256 элементов . Найдите число собственных подмножеств множества P.

M0011. Булеан множества P состоит из 128 элементов . Найдите кардинальное число множества P.

M0012. Дано множество P. Когда из него удалили три элемента , получилось множество , булеан которого содержит 64 элемента . Найдите |B(P)| .

M0013. Булеан множества M имеет 16 элементов . В множество M добавили несколько элементов . Получи - лось новое множество P, для которого |B(P)| = 1024. Найдите разность |P| – |M| .

M0014. Множество P имеет 56 собственных под - множеств , среди которых нет ни одного одноэлемент - ного подмножества . Найдите |B(P)| .

M0015. Множество P имеет 27 подмножеств , среди которых нет ни одного одноэлементного под - множества . В множество P добавили два элемента . Получилось множество M. Найдите |B(M)| .

M0016. Дано множество S = {a, b, 1, 2, 3, 4}. Сколько существует подмножеств этого множества , не содер - жащих букв ? Сколько существует подмножеств , не со - держащих цифр ? Сколько существует подмножеств , не содержащих ни букв , ни цифр ?

M0017. Сколько собственных подмножеств имеет синглетон ? Сколько несобственных подмножеств имеет синглетон? Синглетон — это конечное множество , содержащее только один элемент .

Стоимость решения одной задачи 100руб.