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

.

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

1)  ;

2)  ;

3)  .

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

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

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

---

Теорема 2:(свойства операций над множествами):Для любых множествА, В, Симеют место следующие равенства:1)  ; (идемпотентность);2)  ; (коммутативность);3)  ; (ассоциативность);4)  ; (дистрибутивность);5)  ; .Доказательство:Доказательства подобных утверждений можно проводить с помощью диаграмм Эйлера-Венна, или с помощью рассуждений. Докажем для примера одно из утверждений(5):.Для доказательства равенства нужно показать, что если произвольный элемент принадлежит левой части, то он принадлежит и правой части.Теорема 3:Для любых множестви имеют место следующие утверждения:1)  ;2)  ;3)  ;4) 

---

(законы де Моргана).Доказательство:Докажем некоторые утверждения.1) Покажем, что если произвольный элементпринадлежит левой части, то он принадлежит и правой части равенства и наоборот.Пусть  , это возможно тогда и только тогда, когда . Из последнего по определению разности множеств имеем: и . Значит, по определению дополнения имеем: и . Последнее равносильно тому, что . Следовательно, по определению операции пересечения. Таким образом, выполнено равенство: . Оно означает, что дополнение к дополнению множества , есть само множество .3) Докажем один из законов де Моргана.Пусть  . Это возможно тогда и только тогда, когда . Используя свойства операций над множествами (теорема 2), преобразуем разность: . Последнее означает, что . Что и требовалось доказать.Замечание:В теории множеств очень распространённым являетсясоотношение двойственности.

---

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

---

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

---