КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Например, если , , получаем .Теорема 1. . Доказательство. Пусть , , тогда каждый элемент множества образует пар с различными элементами множества , значит, всего получаем упорядоченных пар, что и требовалось доказать. Множество называется прямым произведением множеств. Теорема 2. . Теорема доказывается методом математической индукции. Множество называется n-ой прямой степенью множества A и обозначается через . Следствие. . Например, если , то построим за два шага: 1) ; 2) . – множество всех подмножеств множества A или булева степеньмножества A. Например, для множества получаем . Заметим, что множество всех подмножеств множества A можно задать в “параметрическом виде”: , т.к. для любого . Теорема 3. . Доказательство. Если , т.е. , то его единственное подмножество есть . . Допустим, что при теорема справедлива. Пусть и . Подсчитаем число элементов множества . Обозначим , тогда . Заметим, что каждый элемент множества либо является подмножеством , либо получен из подмножества добавлением элемента . Число элементов каждого типа равно числу подмножеств , причем по предположению индукции получаем , тогда , что и требовалось доказать. Пример 1. Доказать, что . Решение. Пусть , тогда по определению . Получаем, что и , откуда и . Значит, . Пусть , тогда и , т.е. и , откуда , т.е. . Значит, . Окончательно получаем, что . Кардинальная степень – множество всех функций с областью определения B и областью значений A, т.е. . Отображение f таково, что каждому элементу ставится в соответствие единственный элемент . Теорема 4. . Доказательство. Пусть , , тогда отображение f можно задать упорядоченным набором длины k: , где . Число всех таких наборов равно в силу следствия теоремы 2, следовательно . Теорема доказана. Пример 2. Найти , если , . Решение. Если , тогда f задаётся двоичным упорядоченным набором длины 3. Так как число таких наборов равно , то получаем 8 различных функций, которые сведены в таблице (рис.1), .
Рис. 1 Функция от n переменных, принимающих значения из множества B, и имеющая в качестве области значений множество A, отображает множество в A , т.е. . Таким образом, из теоремы 4 вытекает Теорема 5. Число всех функций от n переменных с областью определения B и областью значений A равно . Пусть . Рассмотрим функции от n переменных с областью определения и множеством значений . Обозначим это множество функций через , т.е. = . Функция называется булевой функцией или функцией алгебры логики от n переменных. Теорема 6. . Множество всех булевых функций от n переменных, которые на нулевом (на единичном) наборе принимают нулевое (единичное) значение, обозначим через .
Пример 3. Найти . Решение. Пусть , тогда значения функции можно произвольно выбирать на всех двоичных наборах, кроме нулевого и единичного, т.е. на наборах. Такой выбор осуществляется способами. Ответ: = .
|