Викия

Математика

Булеан

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

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

Пусть Aмножество. Множество всех подмножеств множества A называется булеаном A (также степенью множества, показательным множеством или множеством частей) и обозначается \mathcal P(A) или 2^A. Ясно, что \varnothing \in \mathcal P(A) и A\in \mathcal P(A).

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

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

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

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

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

  1. содержащие a_0,
  2. не содержащие a_0, то есть являющиеся подмножествами множества M-\left\{a_0\right\}.

Подмножеств типа (2) по предположению индукции 2^n. Но подмножеств типа (1) ровно столько же, так как подмножество типа (1) получается из некоторого и притом единственного подмножества типа (2) добавлением элемента a_0 и, следовательно, из каждого подмножества типа (2) получается этим способом одно и только одно подмножество типа (1).

Поэтому число всех подмножеств множества M равно 2^n+2^n=2^{n+1}.ca:Conjunt de les parts cs:Potenční množina da:Potensmængdeel:Δυναμοσύνολοfiu-vro:Alambhulkõ hulkhe:קבוצת החזקה hu:Hatványhalmaznl:Machtsverzameling no:Potensmengde pl:Zbiór potęgowysr:Партитивни скуп

Викия-сеть

Случайная вики