![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Пусть задан универсум . Тогда
выполняются следующие свойства.
1. Инволютивность:
;
2. Идемпотентность:
,
;
3. Коммутативность:
,
;
4. Ассоциативность:
,
;
5. Дистрибутивность:
,
;
6. Поглощение:
,
;
7. Свойство нуля:
,
;
8. Свойство единицы:
,
;
9. Законы де Моргана:
,
;
10. Свойства дополнения:
,
;
11. Выражение для разности:
.
Булеан
Множество всех подмножеств множества называется булеаном.
Теорема 5.1. Множество из n элементов имеет подмножеств.
Доказательство: Эту теорему можно доказать разными способами (так же, как и многие другие теоремы). Мы докажем ее, используя бинарные представления чисел. Предположим, что мы имеем множество из трех элементов . Каждое подмножество этого множества зашифруем с помощью бинарного кода. Этот код будет состоять из трех бит (по количеству членов исходного множества). Если в рассматриваемом подмножестве присутствует элемент
, первому биту кода присваиваем значение единицы, в противном случае – нуля. Если в подмножестве присутствует элемент
, второму биту присваиваем значение единицы, в противном случае – нуля. Если в подмножестве присутствует элемент
, третьему биту присваиваем значение единицы, в противном случае – нуля. Рассматривая все возможные подмножества исходного множества
, включая пустое множество
, получим следующий результат.
Как можно видеть, подмножества множества соответствуют восьми числам: 0, 1, …, 7. Мы рассмотрели все бинарные комбинации в пределах трех бит. Как известно, количество таких комбинаций равно
.
Применяя данный метод к множеству из четырех элементов, получим количество подмножеств: . Для множества из пяти элементов:
. Обобщая эти результаты, приходим к выводу, что множество из n элементов имеет
подмножеств.
Дата публикования: 2014-11-03; Прочитано: 332 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!