Предваренная нормальная форма (ПНФ)

Формула логики предикатов имеет нормальную форму если она содержит только операции. ()

ПНФ – это такая форма где кванторные операции отсутствуют, либо используются после всех операция. Т.е.

Теорема: все формулы логики предикатов (ЛП) м/б приведены к ПНФ

Доказательство: пусть формула имеет нормальную форму.

Если формула элементарная => она квадратов не содержит => она сама по себе является в ПНФ.

1. Пусть формула A содержит k+1 операцию и , где L(x) – cодержит к-операций изходя из условия L(x) находиться в пнф. Поскольку кванторы записаны впереди данной формулы то A находиться в пнф.

2. Пусть A=L где L находиться в ПНФ тогда с помощью равносильностей

1 и 2 отрицание можно внести под знак кванторов, тогда А будет в пнф

3. Пусть А=L1 V L2; где L1 L2 в пнф. Переименуем в L2 связанные предметные переменные так, чтобы они были различными.

Используя равносильности 7 и 1

Запишем формула А используя формулу L2 под знаки квантора:

Получается что

Далее ведем под знаки кванторов

формулу L1.

Получаем:

Т.о А находиться в ПНФ

Дата добавления: 2015-04-24