Файл: Ответы к экзамену комбинаторный признак умножения. Количество битовых строк длины.docx

.

Теорема 1:Для любых множестви следующие утверждения являются равносильными:

1)  ;

2)  ;

3)  .

Доказательство:Докажем сначала, что  .

Если  , то - очевидно. Докажем второе следствие. По определению операции пересечения множеств имеем: . Нужно получить обратное включение. Если удовлетворяется равенство , тогда , откуда . Если , то . Значит, по свойству антисимметричности отношения включения: . Покажем, что . По определению , но по условию , значит .

Аналогично можно показать, что выполняются и обратные утверждения.

---

Теорема 2:(свойства операций над множествами):Для любых множествА, В, Симеют место следующие равенства:

1)  ; (идемпотентность);

2)  ; (коммутативность);

3)  ; (ассоциативность);

4)  ; (дистрибутивность);

5)  ; .

Доказательство:Доказательства подобных утверждений можно проводить с помощью диаграмм Эйлера-Венна, или с помощью рассуждений. Докажем для примера одно из утверждений(5):

.

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

Теорема 3:Для любых множестви имеют место следующие утверждения:

1)  ;

2)  ;

3)  ;

4) 

---

(законы де Моргана).

Доказательство:Докажем некоторые утверждения.

1) Покажем, что если произвольный элементпринадлежит левой части, то он принадлежит и правой части равенства и наоборот.

Пусть  , это возможно тогда и только тогда, когда . Из последнего по определению разности множеств имеем: и . Значит, по определению дополнения имеем: и . Последнее равносильно тому, что . Следовательно, по определению операции пересечения. Таким образом, выполнено равенство: . Оно означает, что дополнение к дополнению множества , есть само множество .

3) Докажем один из законов де Моргана.

Пусть  . Это возможно тогда и только тогда, когда . Используя свойства операций над множествами (теорема 2), преобразуем разность: . Последнее означает, что . Что и требовалось доказать.

Замечание:В теории множеств очень распространённым являетсясоотношение двойственности.

---

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

Теорема 4:Пусть- конечное множество, содержащее элементов: . Тогда множество всех подмножеств множества содержит элементов.

Доказательство:Для доказательства можно использовать свойства биномиальных коэффициентов. Формула бинома Ньютона имеет следующий вид:  . Применим её для нашего случая: . Здесь - это число подмножеств, не содержащих элементов (т.е. пустое множество); - это число одноэлементных подмножеств; - число всех двухэлементных подмножеств и т. д., - это само множество . Значения биномиальных коэффициентов могут быть взяты из соответствующих строк треугольника Паскаля. Таким образом, будет посчитано количество всех подмножеств данного множества.

Замечание:Для произвольного множествамножество всех его подмножеств часто обозначают .

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

---

В математике встречаются и другие объекты, кроме множеств, для которых определены операции «сложения», «умножения» и «дополнения», удовлетворяющие свойствам операций над множествами (коммутативность, ассоциативность и др.). Такие системы впервые изучал в 1847 г. английский математик Дж. Буль, поэтому такие системы называютбулевыми алгебрами.

---