Спирина, М.С. Дискретная математика

Задача 31. Найти число подмножеств (мощность булеана) ко­ нечного множества М. Решение. Очевидно, что если множество М пусто, то оно содер­ жит единственное подмножество — самого себя, 0 . Если \м \ = 1, например М = |а,}, то множество М содержит два подмножества: 0 и {Д|}. Если М I = 2, например множество содержит элементы д, и а2, то в него входят четыре подмножества: 0 , {д,}, {д2} и {дь д2}. Аналогично множество, состоящее из элементов д,, д2 и д3, содержит восемь подмножеств: 0 , {д,}, {д2}, {д3}, {д,, д2}, {дь д3}, (Й2- аъ Ь (й 1> а2> йз}- Пусть число подмножеств «-элементного множества М равно 5(я). Тогда имеем 5(0) = 1 = 2 ° , 5(1) = 2 = 2', 5(2) - 4 = 22, 5(3) = = 8 = 23... Напрашивается гипотеза о том, что число подмножеств «-элементного множества М равно 2". Проведем доказательство методом математической индукции. Поскольку база индукции уже проверена, причем начиная с « = 0, то сформулируем гипотезу: V к, S(k) = 2к. Докажем, что это утверждение справедливо для « = к + 1, т.е. в (к + 1)-элементном множестве число подмножеств равно 2k+i. Для доказательства рассмотрим множество М' = (дь д2, д3, ак, д*+1}, которое отличается от М - {д,, д2, д3, ..., ак} добавлением к нему элемента ак+1. Среди искомого числа подмножеств уже есть 2к под­ множеств М, и ни в одном из них ак + , не содержится. Кроме того, подмножествами М' будут являться все те же 2к подмножеств, но с добавленным в каждое элементом ак+ ь и все они будут различ­ ны. Очевидно, что других подмножеств нет. Тогда общее число подмножеств равно их сумме: 2к + 2к = 2к+\ что соответствует на­ шей гипотезе. Поэтому на основании принципа математической индукции делаем вывод о том, что действительно для V« е N число подмножеств «-элементного множества равно 2" , что и требовалось доказать. Задача 32. Найти мощность декартова произведения конечных множеств. Решение. Известно, что число элементов декартова произведе­ ния двух множеств Х х У при | Х\ =т, \ У| = к равно т ■к, т .е . | Х х x Y \ = \X\ - \ Y\ = т- к. Пусть даны множества X = {х,, х2, ..., xm},Y = {уи уъ ..., ук). Тогда X х Y состоит из пар вида (х„ yj), где 1 < /< т, 1 <j< к. Доказательство проведем методом математической индукции. Рассмотрим s множеств Хи X2,...,XS, из которых составлены кор­ тежи длины s: а = <xh х2, ..., х5>, где х, е X] , причем 1 < / < s. Множество, состоящее из таких кортежей, называется декарто­ вым (прямым) произведением s множеств Хи Х2, ..., Xs и обозна­ чается X) х Х2 х ... х Х5. Тогда число элементов такого декартова произведения должно вычисляться по формуле | Ххх Х2х ... х Xs\ = = Ш - \х2\ ■ ... • UI. 10* 275