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

• Множество 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, и под каждым элементом записаны двоичные цифры . В левой колонке приведены десятичные эквиваленты двоичных трехразрядных чисел . В правой части таблицы перечисле ... Смотреть решение »

Формула включений и исключений

Пусть задано конечное множество А. Число его элементов обозначим n(А). Найдем сколько элементов содержится в множестве А ∪ В. Основная формула нахождения числа элементов суммы двух множеств

n(А ∪ В) = n(А) + n(В) – n(А ∩ В)        (1)

Действительно, n(А ∪ В) — это сумма числа элементов множеств А и В, но при подсчете элементы, принадлежащие А ∩ В учитывались дважды. С помощью формулы (1) можно получить формулы для определения числа элементов суммы любого числа множеств. Например,

n(А ∪ В ∪ С) = n(А ∪ (В ∪ С)) = n(А) + n(В ∪ С) – n(А ∩ (В ∪ С)) =

= n(А) + n(В) + n(С) – n(В ∩ С) – n((А ∩ В) ∪ (А ∩ С)) =

= n(А) + n(В) + n(С) – n(В ∩ С) – (n(А ∩ В) + n(А ∩ С) – n((А ∩ В) ∩ (А ∩ С))) =

=n(А) + n(В) + n(С) – n(В ∩ С) – n(А ∩ В) – n(А ∩ C) + n(А ∩ В ∩ С).

n(А ∪ В ∪ С) = n(А) + n(В) + n(С) – n(А ∩ В) – n(В ∩ С) – n(А ∩ C) + n(А ∩ В ∩ С) &n ... Смотреть решение »

Найти булеан

• Множество всех подмножеств некоего множества A называют булеаном или степенью множества A. Обозначается булеан как P(A) или 2^A .
  • Пусть множество A содержит n элементов. Булеан множества A содержит 2ⁿ элементов, т.е. кардинальное число булеана |P(A)|=2ⁿ, n=|A|.

Пример 1. Дано множество А = { a,b,c,d,e}. Найти булеан множества А. Кардинальное число булеана.

Решение. Булеан множества А:

P(A): ∅ | {a} | {b} | {c} | {d} | {e} | {a, b} | {a, c} | {a, d} | {a, e} | {b, c} | {b, d} | {b, e} | {c, d} | {c, e} | {d, e} | {a, b, c} | {a, b, d} | {a, b, e} | {a, c, d} | {a, c, e} | {a, d, e} | {b, c, d} | {b, c, e} | {b, d, e} | {c, d, e} | {a, b, c, d} | {a, b, c, e} | {a, b, d, e} | {a, c, d, e} | {b, c, d, e} | {a, b, c, d, e}

Кардинальное число булеана находим по формуле |P(A)|=2ⁿ , ... Смотреть решение »