Свойства операций над множествами

Пусть задан универсум . Тогда выполняются следующие свойства.

1. Инволютивность:

;

2. Идемпотентность:

, ;

3. Коммутативность:

, ;

4. Ассоциативность:

, ;

5. Дистрибутивность:

, ;

6. Поглощение:

, ;

7. Свойство нуля:

, ;

8. Свойство единицы:

, ;

9. Законы де Моргана:

, ;

10. Свойства дополнения:

, ;

11. Выражение для разности:

.

Булеан

Множество всех подмножеств множества называется булеаном.

Теорема 5.1. Множество из n элементов имеет подмножеств.

Доказательство: Эту теорему можно доказать разными способами (так же, как и многие другие теоремы). Мы докажем ее, используя бинарные представления чисел. Предположим, что мы имеем множество из трех элементов . Каждое подмножество этого множества зашифруем с помощью бинарного кода. Этот код будет состоять из трех бит (по количеству членов исходного множества). Если в рассматриваемом подмножестве присутствует элемент , первому биту кода присваиваем значение единицы, в противном случае – нуля. Если в подмножестве присутствует элемент , второму биту присваиваем значение единицы, в противном случае – нуля. Если в подмножестве присутствует элемент , третьему биту присваиваем значение единицы, в противном случае – нуля. Рассматривая все возможные подмножества исходного множества , включая пустое множество , получим следующий результат.

Как можно видеть, подмножества множества соответствуют восьми числам: 0, 1, …, 7. Мы рассмотрели все бинарные комбинации в пределах трех бит. Как известно, количество таких комбинаций равно .

Применяя данный метод к множеству из четырех элементов, получим количество подмножеств: . Для множества из пяти элементов: . Обобщая эти результаты, приходим к выводу, что множество из n элементов имеет подмножеств.