- •Ф.К. Алиев, и.А. Юров
- •Введение
- •Основные способы задания двоичных функций
- •1.1. Табличный способ задания
- •1.2. Геометрический способ задания
- •1.3. Задание двоичных функций формулами
- •Основные способы задания двоичных функций (продолжение)
- •2.1. Нормальные формы двоичных функций
- •2.2. Многочлен Жегалкина и действительный многочлен двоичной функции
- •2.3. Теорема о разложении в ряд Фурье
- •Полнота и замкнутость. Критерий полноты системы. Функционально полные системы. Замкнутые классы булевых функций
- •3.1. Полнота и замкнутость. Функционально полные системы
- •3.2. Замкнутые классы булевых функций
- •3.3. Критерий полноты системы булевых функций
- •4.1. Псевдобулевы функции
- •4.2. Функции k-значной логики
- •5.1 Минимизация двоичных функции
- •5.2. Геометрическая интерпретация минимизации днф
- •6.1. Метод Квайна — Мак-Класки нахождения сокращённой днф двоичной функции
- •6.2. Метод нахождения тупиковых днф
- •6.3. Метод Петрика нахождения тупиковых днф
- •Алгебраические системы
- •7.1. Алгебраические системы. Булевы алгебры
- •7.2. Изоморфизм алгебраических систем
- •Алгебры высказываний. Предикаты и операции над ними
- •8.1. Основные логические операции и их свойства
- •8.2. Предикаты и операции над ними
- •Исчисление предикатов
- •9.1. Общее понятие о логическом исчислении
- •9.2. Формулы алгебры предикатов
- •9.3. Равносильность формул. Основные отношения равносильности
- •9.4. Использование равносильностей для упрощения формул
- •9.5. Построение исчисления предикатов
- •9.6. Выводимость и доказуемость формул
- •9.7. Семантика исчисления предикатов
- •Понятие о теории моделей
- •Элементы теории алгоритмов
- •11.1. Основные требования к алгоритмам
- •11.2. Машина Тьюринга и функции, вычислимые по Тьюрингу
- •11.3. Машины произвольного доступа и вычислимые функции
- •Частично рекурсивные функции и их вычислимость
- •Вычислимость суперпозиции
- •Вычислимость рекурсии
- •Вычислимость минимизации
- •Нумерация наборов чисел и слов
- •Нормальные алгоритмы
- •Нумерация алгоритмов
- •1. Нумерация машин Тьюринга
- •2. Нумерация мпд-программ
- •Универсальные функции
- •Алгоритмически неразрешимые проблемы
- •16.1. Алгоритмически неразрешимые проблемы
- •16.2. Примечательные алгоритмически неразрешимые проблемы
- •Характеристики сложности вычислений
- •Характеристика сложности вычислительных задач
- •18.1. Классы сложности p и np и их взаимосвязь
- •18.3. Основные np-полные задачи. Сильная np-полнота
- •Список Литературы
3.2. Замкнутые классы булевых функций
Определение 3.15. Класс булевых функций называется замкнутым, если он совпадает со своим замыканием, т.е..
Замечание 3.16. Полное описание всех замкнутых классов было дано американским математиком Э. Постом. В частности, он доказал, что множество всех замкнутых классов булевых функций счетно и в каждом замкнутом классе можно выделить конечную подсистему, порождающую, т.е. имеющую своим замыканием класс, т.е..
Определение 3.17. Булева функция называется функцией,сохраняющей константу 0, если .
Класс всех булевых функцией, сохраняющих константу 0, обозначим .
Определение 3.18. Булева функция называется функцией,сохраняющей константу 1, если .
Класс всех булевых функцией, сохраняющих константу 1, обозначим .
Определение 3.19. Булева функция называетсялинейной, если , такие, что
.
Класс всех булевых линейных функций обозначим через .
Определение 3.20. Булева функция называетсяаффинной функцией, если , такие, что.
Обозначим через класс всех булевых аффинных функций.
Определение 3.21. Булева функция называетсясамодвойственной функцией, если
. (3.1)
Класс всех булевых самодвойственных функций обозначим через S.
Далее определим понятие монотонной функции. Для этого нам необходимы некоторые дополнительные сведения. Изложим их. На множестве введем отношение, положив для наборови:
,
где отношение напонимается как неравенство на множестве чисел {0, 1}.
Несложно доказать, то отношение рефлексивно, транзитивно и антисимметрично, т.е. является отношением частичного порядка.
Определение 3.22. Булева функция называетсямонотонно возрастающей или монотонной, если для любых наборов выполняется условие:.
Замечание 3.23. Нульместные функции 0 и 1 также естественно считать монотонными.
Класс всех булевых монотонных функций обозначим через М.
Утверждение 3.24. Классы булевых функций иявляются замкнутыми классами булевых функций.
Для доказательства данного утверждения нам необходимо определить понятие ранга формулы над классом.
Определение 3.25. Число всех символов функций из , встречающихся в формуленад, называется рангом формулыи обозначается через.
Замечание 3.26. Понятие ранга формулы над классомне следует путать с понятием ранга элементарной конъюнкции из определения 2.1.
Доказательство утверждения 3.24. Замкнутость перечисленных в утверждении 3.24 шести классов функций доказывается по одной и той же схеме. Проделаем это для какого-нибудь одного класса, например S.
Согласно определениям замыкания (определение 3.1) и замкнутого класса (определение 3.15) нам необходимо доказать, что любая функция, представимая формулой над S, принадлежит S. Докажем это индукцией по рангу формулыА, представляющей функцию .
Если , то, и утверждение очевидно, так как.
Пусть утверждение верно для всех , таких что, где.
Докажем, что утверждение верно и при . Если, тоА имеет вид: , гдеи— формулы меньших рангов, чем, т.е.. По предположению индукции формулыпредставляют булевы функции. Тогда для любыхимеем:
Следовательно, удовлетворяет условию (3.1), т.е