Автор работы: Пользователь скрыл имя, 20 Декабря 2011 в 10:03, лекция
Под множеством (совокупностью) М понимают набор объектов произвольной природы, которые называются элементами множества. Если число элементов конечно, множество называется конечным. В противном случае говорят о бесконечном множестве.
Подразумевается, что элементы множества различны и различимы между собой. Само множество элементов рассматривается как единое целое, и в качестве такого может быть элементом любого другого множества. Элементы могут быть любыми объектами числами, людьми, яблоками, буквами и тому подобное. В математике в качестве элементов множества рассматривают математические объекты числа и множества чисел, точки и множества точек, абстрактные элементы, образующие алгебраические структуры: группы, поля, кольца, решетки и т.д.
Определение. Булеаном множества А (обозначается 2А) называется семейство всех подмножеств данного множества А.
Значит, 2А={B|B A}. В частности, и
Примеры булеанов.
Пусть . Тогда .
Пусть . Тогда .
Пусть А = Æ. Тогда 2А = {Æ}.
Определение. Мощностью конечного множества А (обозначение: ) называют число его элементов.
Пример. |Æ| = 0; |{Æ}| = |{x}| = 1; |{1, {1}, 2, {1, 2}}| = 4; |{{1, 2, 3, 4, 5}, Æ}| = 2.
Утверждение. Если , то .
Доказательство (1 способ). Припишем элементам множества А номера от 1 до п. Тогда можно записать, что А = {a1, a2 ,…, an}. Закодируем всякое подмножество В множества А последовательностью х1х2…хп длины n, состоящей из нулей и единиц, так что
Следовательно, пустое множество представляется n нулями, а множество A кодируется последовательностью, содержащей только единицы.
Таким образом, для каждого В Í А однозначно строится последовательность; по каждой последовательности однозначно восстанавливается соответствующее подмножество. Поэтому число подмножеств множества А равно числу последовательной длины n, содержащих только нули и единицы.
По принципу умножения число таких последовательностей равно
Доказательство (2 способ). Число подмножеств множества А, содержащих k элементов, равно числу способов отобрать из n элементов множества А k элементов, образующих данное подмножество, т. е. равно . Отсюда