1. Прежде всего отметим, что эти алгебры равномощны и обе содержат по элементов т.к. если , то B = , и т.к. все двоичные функции с m переменным определяются вектор-столбцом с компонентами, то таких различных двоичных векторов будет ;
2. Поскольку все множества U одинаковой мощности порождают изоморфные булевы алгебры (B , ) множеств, то эту теорему достаточно доказать для какого-либо конкретного U, удовлетворяющего условию . В качестве такого множества U возьмем множество – двоичных векторов длины m и, следовательно, будем доказывать изоморфизм между булевой алгеброй множеств (B , ) и булевой алгеброй функций ;
3. Обозначим через множество единичных наборов функции f. Тогда набор принадлежит . Соответственно (гомоморфизм отображает f в множество единичных наборов ) – между функциями и их единичными множествами является взаимно однозначным соответствием между и B , поскольку различным функциям соответствуют различные множества, и наоборот.
Определение: Функцию f, единичным множеством которой служит М, называют характеристической функцией множества М.
|
|
4. Покажем, что взаимно однозначное соответствие Г является изоморфизмом. Достаточно проверить выполнение равенств гомоморфизма для всех трех пар операций, которое в данном случае сводится к трем уравнениям:
,
для любых функций f и g от m переменных. Докажем втрое из них.
Пусть ( - двоичный вектор, , f – единичное множество функции ), тогда и, следовательно, или и, значит, или , следовательно, .
Обратно:
или
или
.
Аналогично доказываем остальные свойства.
Замечание: Во избежание путаницы обращаем внимание на различие объектов в доказанных нами теоремах.
1. В теореме 1 фигурировала алгебра со следующим основным множеством:
- - множество произвольной природы и любой конечной мощности n;
- B - множество подмножеств U мощности ;
- - множество двоичных векторов длины n также мощности .
В теореме 2 участвовали:
- тот же множество , но с дополнительным условием (m – любое натуральное число);
- - конкретное множество U с этими же условиями: ;
- множество логических функций m переменных: ;
- B - множество подмножеств : B = .
2. Множества и , хотя и имеют одну и ту же природу (состоят из двоичных наборов), использовались в теореме 1 и теореме 2 по-разному. В теореме 1 была использована структура элементов , благодаря чему над ними оказались возможными поразрядные логические операции. Подмножества не рассматривались. В теореме 2 структура элементов не учитывалась, само было выбрано только для естественности и наглядности, зато рассматривалась B - система
Таблица 1
f | g | ||||||
подмножеств . Теоремы 1 и 2 указывают на тесную связь между множествами и логическими функциями и позволяют переходить от операций над множествами к операциям над функциями и обратно. В частности, они дают возможность непосредственно производить операции над функциями, заданными не формулами, а таблицами или единичными множествами.
|
|
Из теоремы 1 и теоремы 2 следует, что булевы операции над функциями, заданными таблицами, сводятся к поразрядным логическим операциям над столбцами значений функций. Пример, приведенный в таблице, содержащей две функции f и g, и результат булевых операций над ними.
ЛИТЕРАТУРА
1. Кузнецов О. П., Адельсон - Вельский Г. М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1986. - 480 с.
2. Кук Д., Бейз Г. Компьютерная математика: Пер. с англ. - М.: Наука, Гл. ред. физ. - мат. лит., 1990. - 384 с.
3. Москинова Г. И. Дискретная математика в примерах и упражнениях. В 2-х ч. - Кемерово, Изд-во КГУ, 1993.
4.Виленкин Н. Я. Комбинаторика. - М.: Наука, гл. ред. физ.-мат. лит.,1969. – 328 с.
5. Яблонский С. В. Введение в дискретную математику/Учеб. пособие. М.: Наука, 1986. - 384 с.
6. Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по курсу дискретной математики/Учеб. пособие. - М.: Наука, 1992. - 408 с.