- •Ф.К. Алиев, и.А. Юров
- •Введение
- •Основные способы задания двоичных функций
- •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.1. Полнота и замкнутость. Функционально полные системы
Определение 3.1. Для произвольного класса системы двоичных функций множество всех двоичных функций, представимых формулами, над, называется замыканием класса (системы) функцийи обозначается через.
Имеют место следующие свойства замыкания.
Свойство 3.2. .
Свойство 3.3. .
Свойство 3.4. .
Обозначим через множество всех двоичных функций отn переменных, а через множество всех двоичных функций (от произвольного числа переменных).
Определение 3.5. Система функций называется полной, если.
Утверждение 3.6. Система функций является полной системой функций.
Доказательство. Очевидно, что элементарная конъюнкция является формулой над. Отсюда следует, что дизъюнкция любого числа элементарных конъюнкций является формулой над. Отсюда и из равенства (2.5) следует, что любая функция, представима над формулой. Следовательно,.
Утверждение 3.7. Система функций является полной системой функций.
Доказательство. Очевидно, что , из равенстваследует, что. Отсюда и из свойств 3.3 и 3.4 имеем:, т.е.. Таким образом, показано, чтои. Полученные включения означают, что
Утверждение 3.8. Система функций является полной системой функций.
Доказательство. Очевидно, что , из равенстваследует, что. Отсюда и из свойств 3.3 и 3.4 имеем:, т.е.. Таким образом, показано, чтои. Полученные включения означают, что
Утверждение 3.9. Система функций является полной системой функций, где— двоичная функция, называемая штрихом Шеффера, задается табл.3.1.
Доказательство. Очевидно, что . Из равенств и следует, что . Далее доказательство текстуально аналогично доказательству утверждения 3.8 при подстановкевместо |
Таблица 3.1
| ||
0 1 0 1 1 |
1 1 1 0 | ||
|
Утверждение 3.10. Система функций , является полной системой функций.
Доказательство. Очевидно, что . Из равенстваследует, что. Далее доказательство текстуально аналогично доказательству утверждения 3.8 при подстановкевместо
Утверждение 3.11. Система функций является полной системой функций, где— двоичная функция, называемая стрелкой Пирса, задается табл.3.2.
Доказательство. Очевидно, что . Из равенствиследует, что. Далее доказательство текстуально аналогично доказательству утверждения 3.8 при подстановкевместоивместо |
Таблица 3.2
| ||
0 1 0 1 1 |
1 0 0 0 | ||
|
Определение 3.12. Каждая двоичная функция , образующая полную систему, называетсяшефферовой функцией.
Пример 3.13. Функция является шефферовой функцией. Это следует из утверждения 3.9.
Пример 3.14. Функция является шефферовой функцией. Это следует из утверждения 3.11.
Примеры шефферовых функций от большего числа переменных будут приведены ниже, после изложения критерия полноты системы двоичных функций.