- •Ф.К. Алиев, и.А. Юров
- •Введение
- •Основные способы задания двоичных функций
- •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-полнота
- •Список Литературы
9.4. Использование равносильностей для упрощения формул
Равносильности 1-26 (см. табл.9.1) зачастую используются также для преобразования формул к равносильным им формулам нужного вида.
В качестве примеров рассмотрим преобразование формул алгебры предикатов к так называемым приведённым и предваренным формулам.
Определение 9.12. Формула алгебры предикатов называется приведенной, если в ней не используется операция «», а отрицание или не используется совсем, или относится лишь к элементарным формулам.
Определение 9.13. Предваренной (или нормальной, или пренексной) формулой алгебры предикатов называется любая формула вида
, (9.4)
где δ1, …, δk — кванторы, а А — приведенная формула, не содержащая кванторов.
Теорема 9.14. Для всякой формулы А алгебры предикатов существует равносильная ей приведенная формула. Докажем теорему индукцией по рангу r(А) формулы А. Если r(А) = 0, то утверждение верно. Пусть r(А) > 0. Тогда по определению формулы А совпадает с одной из формул вида
A1 A2, A1 A2, δxA1, A1 A2, .(9.5)
Доказательство. По предположению индукции формулы А1, А2 равносильны приведенным формулам. Заменив ими в (9.5) формулы А1, А2, мы в трех первых случаях сразу получим приведенные формулы. А так как A1 A2 А1 А2 (см. п.24 табл.9.1), то остается рассмотреть случай, когда . ЕслиА1 элементарна, то А — приведенная формула. Если же А1 не элементарна, то она может иметь вид B1 B2, B1 B2, δxB1, B1 B2,B1, где r(Bi) < r(A) –2. Тогда по свойствам равносильности 11, 12, 20, 21, 24, 14 (см. табл.9.1) формула А равносильна одной из формул:
B1 B2, B1 B2, δ*xB1, B1 B2, B1. (9.6)
Остается применить предположение индукции к формулам B1,B1,B2 и заменить их в (9.6) приведенными формулами.
Теорема 9.15. Для всякой формулы алгебры предикатов существует равносильная ей предваренная формула.
Доказательство. По теореме 9.14, не теряя общности, можно считать, что А — приведенная формула. Снова применим индукцию по r(А). Для r(А) = 0 утверждение верно. Пусть r(А) > 0. Тогда формула А может иметь вид
1) A1 A2,
2) A1 A2,
3) δxA1,
4)A1.
Причем в случае 4 А1 — элементарная формула и для нее утверждение теоремы верно. Рассмотрим случаи 1-3.
1. A = A1 A2. По предположению индукции Аi равносильна предваренной формуле Bi, i = 1, 2, причем согласно равносильности 26 (см. табл.9.1) связанные переменные любой из формул В1, В2 можно считать отличными от всех переменных другой формулы. Таким образом, A = B1 B2, где можно считать B1 = δ1x1…δkxkC1, B2 = δk + 1xk + 1…δnxnC2, где x1, …, xk не входят в С2, а xk + 1, …, xn не входят в С1, и формулы С1, С2 не содержат кванторов. Отсюда, используя равносильность 25, получим
A δ1x1…δkxkδk + 1xk + 1 … δnxn(C1 C2).
2. Для A = A1 A2, рассуждения двойственны.
3. A = δxA1. По предположению индукции А1 равносильна приведенной формуле A δ1x1…δkxkB, причем можно считать, что x x1, …, xk. Возможны два случая:
а) В содержит свободные вхождения х. Тогда А равносильна предваренной формуле δxδ1x1…δkxkB;
б) В не содержит свободных вхождений х. Тогда из равносильности 4 (см. табл.9.1) следует, что значения формулы А1 не зависят от значений переменной х, а потому А А1 и теорема доказана.