Что такое булеан множества
Перейти к содержимому

Что такое булеан множества

  • автор:

1.4 Булеан множества

Напомним, что число элементов конечного множества называется мощностью множества и обозначается символом A или Card A (от английского cardinality — мощность).

Определение. Множество всех подмножеств данного множества называют булеаном множества. Булеан обозначают символом B(A).

Пример. Пусть A = < 1,2,3 >. Перечислить элементы булеана множества A.

Пример. Пусть A = < 1,2,3,4. n >, т.е. |A | = n. Найдем мощность множества B(A).

Для определения CardB(A) воспользуемся биномиальными коэффициентами Cn k (число сочетаний из n по k) 4 . Перечислим по порядку, начиная с пустого множества, все подмножества множества A:

пустому подмножеству множества A поставим в соответствие число 1 = Cn 0 ;

булеан содержит одноэлементные подмножества:

Число одноэлементных подмножеств равно n = Cn 1 ;

булеан содержит следующие двухэлементные подмножества:

Количество двухэлементных подмножеств равно

продолжая этот подсчет, получим, что булеан содержит Cn 3 трехэлементных подмножеств, Cn 4 четырехэлементных подмножеств и так далее;

наконец, мы отметим, что булеан содержит Cn n  1 (n  1)-элементных подмножеств и одно n-элементное подмножество — само множество A, которому мы сопоставим биномиальный коэффициент Cn n = 1.

В результате сумма всех биномиальных коэффициентов покажет нам количество элементов булеана B(A):

Таким образом, для любого множества A, если Card A = n, то Card B(A)=2 n .

1.5 Представление множеств в эвм

Для конечного универсума, мощность которого не превосходит разрядности машинного слова, подмножества универсума могут представляться битовой шкалой (аналог характеристической функции – 0 или 1 для каждого элемента). Битовая шкала имеет размерность универсума, и для каждого подмножества число единиц в соответствующей ему битовой шкале определяется мощностью этого подмножества. Если элемент входит в подмножество, то ему соответствует 1, иначе 0. Тогда операции над подмножествами осуществляются посредством поразрядных логических операций

Если универсум велик, а подмножества имеют сравнительно небольшую мощность, то использование характеристических функций невыгодно, т.к. в них будет много нулей. Для представления таких множеств обычно используют списки элементов. Элемент множества тогда может быть представлен записью с двумя полями: информационным и указателем на следующий элемент. Трудоемкость операций включения, пересечения и объединения определяется как O(m× n), где m и n – мощности множеств; операции Î – как O(n).

При использовании списков, упорядоченных по информационному полю, трудоемкость всех операций является линейной (О(n)). В таком случае эффективная организация всех операций над множествами основана на общем алгоритме, известном как алгоритм типа слияния.

Алгоритм типа слияния параллельно просматривает два множества, представленных упорядоченными списками, причем на каждом шаге продвижение вперед (увеличение номера рассматриваемого элемента) происходит в том множестве, в котором текущий элемент меньше.

В качестве простейшей организации множеств можно использовать упорядоченный массив элементов.

Проверка включения AÌ B

Вход: Два упорядоченных множества A и B (массивы).

Выход: да или нет (1 или 0, true или false).

i:=1; j:=1; // указатели на начало множеств

// элемент A отсутствует в B

если A[i] > B[j] то j:=j+1

// переход к след. элементу B

// элементы совпали – перейти к следующим

если i=|A|+1 то вернуть 1, иначе вернуть 0.

Алгоритмы, вычисляющие объединение множеств, пересечение и дополнение устроены совершенно аналогичным образом. Общее действие – продвижение вперед (увеличение индекса) в том массиве, элемент которого меньше, и сразу в обоих, если элементы равны.

Для определения объединения в результирующее множество заносятся каждый из меньших элементов и один, если они равны. Если конец одного из множеств достигнут раньше, все оставшиеся элементы другого дописываются в конец итогового множества.

Для определения пересечения в результирующее множество заносится тот элемент, который совпал у обоих множеств. Если конец одного из множеств достигнут раньше, работа алгоритма заканчивается.

Найти булеан (степень множества)

Онлайн калькулятор для вычисления булеана (степень множества, показательное множество, множество частей) — множество всех подмножеств некоего множества A называют булеаном или степенью множества A. Обозначается булеан как P(A) или 2A .

Пожалуйста напишите с чем связна такая низкая оценка:

Для установки калькулятора на iPhone — просто добавьте страницу
«На главный экран»

Для установки калькулятора на Android — просто добавьте страницу
«На главный экран»

Булеан

Пусть A— множество. Множество всех подмножеств множества Aназывается булеаном A(также степенью множества (англ. power set ), показательным множеством или множеством частей) и обозначается \mathcal P(A). Также оно обозначается 2^A, так как оно соответствует множеству отображений из Aв 2 = \< 0,1\>» width=»» height=»» />.</p><div class='code-block code-block-9' style='margin: 8px 0; clear: both;'>
<!-- 9joomlaumnik -->
<script src=

\kappa \mapsto 2^\kappa

Если два множества равномощны, то равномощны и их булеаны. Обратное утверждение (т.е. инъективность операции для кардиналов) является независимым от ZFC.

\mathcal<P></p>
<p>В категории множеств можно снабдить функцию » width=»» height=»» /> структурой ковариантного или контравариантного функтора следующим образом.</p><div class='code-block code-block-10' style='margin: 8px 0; clear: both;'>
<!-- 10joomlaumnik -->
<script src=

  • Ковариантный функтор отображает функцию f\colon A\to Bв функцию \mathcalf\colon \mathcalA \to \mathcalB такую, что она отображает Xв образXотносительно f.
  • Контравариантный функтор отображает функцию f\colon A\to Bв \mathcalf\colon \mathcalB \to \mathcalA такую, что она отображает Xв полный прообразXотносительно f.

Справедливо следующее утверждение:

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

Доказательство проведем методом математической индукции.

База. Если n=0, т. е. множество пусто, то у него только одно подмножество — оно само, и интересующее нас число равно 2^0=1.

Индукционный шаг. Пусть утверждение справедливо для некоторого n и пусть M— множество с кардинальным числом n+1. Зафиксировав некоторый элемент a_0\in M, разделим подмножества множества Mна два типа:

  1. M_1, содержащее a_0,
  2. M_2, не содержащее a_0, то есть являющиеся подмножествами множества M-\left\<a_0\right\>» width=»» height=»» />.</li>
</ol>
<p>Подмножеств типа (2) по предположению индукции <img decoding=. Но подмножеств типа (1) ровно столько же, так как подмножество типа (1) получается из некоторого и притом единственного подмножества типа (2) добавлением элемента a_0и, следовательно, из каждого подмножества типа (2) получается этим способом одно и только одно подмножество типа (1).

    Следовательно имеем 2^M = M_1 \bigcup M_2и M_1 \bigcap M_2 = \varnothing. По индукционному предположению \left| M_1 \right| = 2^n и \left| M_2 \right| = 2^n . Получаем \left| 2^M \right| = \left| M_1 \right| + \left| M_2 \right| = 2^n + 2^n = 2^<n+1>= 2^\left| M \right|» width=»» height=»» />.</p><div class='code-block code-block-12' style='margin: 8px 0; clear: both;'>
<!-- 12joomlaumnik -->
<script src=

См. также

4.2. Булеан множества. Разбиение множества

Пусть задано непустое множество X. Множество всех подмножеств этого основного множества, включая его само и пустое множество, называется булеаном данного множества и обозначается Р(X) или 2 х . Если X содержит n элементов, то булеан содержит 2 п элементов, которыми есть подмножества множества А, собственные и несобственные.

Говорят, что элементы Х1, Х2,…Хп булеана 2 х образуют разбиение множества X, если

(4.2.1)

В этом случае множества Х1, Х2,…Хп называются блоками разбиения множества X.

Правило суммы (лежащее в основе многих комбинаторных вычислений и оценок). Пусть X – конечное множество, ,X- его мощность (число его элементов). Тогда имеет место условие:

причём равенство достигается, когда Х1, Х2,…Хп образуют разбиение множества X, т.е. удовлетворяют (4.2.1).

Множество А: Х1 = , X2 = ; A = X1X2. Это единственный способ разбиения множества А.

Множество В: первый способ: Х1 = a>, X2 = b>; X3 = c>;

Множество С: первый способ: Х1 = , X2 = ; X3 = ; Х4 = ;

второй способ: Х1 = , X2 = ; X3 = ;

третий способ: Х1 = , X2 = ; X3 = ;

четвёртый способ: Х1 = , X2 = ;

пятый способ: Х1 = , X2 = ; и т.д.

Задачи для самостоятельного решения.

1. Найти булеаны следующих множества: А =, B =, C =, D =m, n, p, q>. Найти разбиение множеств A, B, C, D.

4.3. Декартово произведение множеств. Понятие упорядоченного множества

Пусть X и Y – некоторые непустые множества, где xX, yY. Рассмотрим двухэлементное множество, состоящее из пар x и y. Пара (или двойка) x, y> называется неупорядоченной. Здесь порядок записи элементов не важен, поэтому x, y> = y, x>. Пара (x, y) называется упорядоченной. Здесь порядок записи существенен, поэтому (x, y)  (y, x).

Множество, для которого имеет значение порядок записи его элементов, называется упорядоченным. В противном случае – неупорядоченным.

Декартовым (или прямым) произведением множеств X и Y называется множество всех упорядоченных пар, где первый элемент принадлежит множеству X, а второй – Y.

Аналогично определяется декартово произведение любого конечного числа n множеств:

Упорядоченные элементы этого произведения (x1, x2, …, xn) называются векторами, последовательностями, кортежами или просто «энками».

Если декартово произведение выполняется на одном и том же множестве, то его называют декартовой степенью этого множества.

X1 X2 Xn = X п

Правило произведения (лежащее в основе многих комбинаторных вычислений и оценок). Для конечных множеств Х1, Х2,…Хп :

| X1 X2 Xn | = | X1| | X2| | Xn|

Декартово произведение обладает следующими свойствами:

  1. некоммутативность: АВВА, если АВ;
  2. неассоциативность: (АВ)СА(ВС);
  3. дистрибутивность относительно операций :

(АВ)С = (АС)(ВС), (АВ)С = (АС)(ВС), (А \ В)С = (АС) \ (ВС), (АВ)С = (АС)(ВС), В)С = (АС)С). Для случая двух множеств декартово произведение можно иллюстрировать с помощью диаграммы Венна. Пусть А = a1, a2,…, an>; B = b1, b2,…, bm>. Рис. 4.5 Рассмотрим прямое произведение множества R действительных чисел самое на себя. Множество RR или R2 состоит из всех упорядоченных пар вещественных чисел (х, у). Их можно трактовать как координаты точек плоскости XOY, то есть декартовой плоскости. Часто в дискретной математике множество вещественных чисел обозначают D (вместо R). Смысл этого обозначения станет понятным из дальнейшего изложения. Задача 4.3.1. Найти декартово произведение АВ и ВА на множествах А= и B=a, b, c>. Решение. АВ =  a, b, c> = <(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)>; BA = a, b, c>  = <(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)>. Задача 4.3.2. Найти декартовы степени А 2 , А 3 , В 2 , А= и B=a, b, c>. Решение. А 2 = АА =  = ; A 3 = AAA = A 2 A =  = = = ; B 2 = BB = a, b, c>a, b, c> = = <(a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c)>. Задача 4.3.3. Найти геометрическую интерпретацию множеств:

  1. [1, 4]  [2,3];
  2. [1, 2] 2 ;
  3. [1, 2] 3 .

Решение.

  1. Пусть А =x1 x 4>, B = у2 у 3>. Отложим на оси ОХ множество А, а множество В – на оси OY. Совершенно ясно, что множества А и В содержат бесконечное множество элементов. Их произведение АВ=<(x,y)xA, yB> есть множество точек прямоугольника с вершинами в точках (1,2), (1,3), (4,2) и (4,3).

  1. Множество [1,2] 2 = [1,2]  [1,2] – это множество точек квадрата с вершинами в точках (1,1), (1,2), (2,1), (2,2).
  2. Множество [1, 2] 3 – это множество точек куба с вершинами в точках (1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2).

Задача 4.3.4. Проверить справедливость равенства С(В\А)=(СВ)(С(АВ)) для множеств А=a, d>, B=b, d>, C=c>.Решение.Найдём множество в левой части равенства: В\А = \ = ; C(B\A) =  = <(c, b)>; Аналогично находим множество в правой части равенства: СВ =  = <(c, b), (c, d)>; AB =  = ; C(AB ) =  = <(c, d)>; (СВ)(С(АВ)) = = <(c, b), (c, d)> <(c, d)> = <(c, b)>; В левой и правой части равенства имеем одно и то же множество. Следовательно, для данных множеств равенство справедливо. Задача 4.3.5. Доказать, что (АВ)С = (АС)(ВС). Решение. Воспользуемся определением равенства множеств. Ясно, что мы имеем дело с множествами, состоящими из упорядоченных пар. Пусть элемент (х, у)(АВ)С, откуда имеем, что х(АВ), уС. Значит хА или хВ, а тогда (х, у)АС или (х, у)ВС. Мы показали, что всякий элемент, принадлежащий множеству слева, принадлежит также и множеству справа, то есть (АВ)С (АС)(ВС). Пусть теперь (х, у)  (АС)(ВС). Отсюда вытекает, что (х, у)(АС) или что (х, у)(ВС). В первом случае хА, уС, во втором – хВ, уС. Следовательно, хАВ, а (х, у)(АВ)С. Итак, (АС)(ВС) (АВ)С. Что и доказывает наше равенство. Задачи для самостоятельного решения. 1. Найти декартово произведение АВ и ВА на множествах

  1. А= и B=;
  2. A=k, m> и B=m, n, l>.

2. Найти декартовы степени А 2 , А 3 , если А=a, b, c>. 3. Проверить справедливость равенства С(AB)=(СA)(С(B\A)) для множеств А=, B=, C=. 4. Доказать, что

  1. если ВА и СА, то (ВС)(АА); b) A(BC) = (AB)(AC).

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *