Предваренные нормальные формы

В логике высказываний вводятся две нормальные формы - дизъюнктивная нормальная форма и конъюнктивная нормальная форма. В логике предикатов также имеется предваренная нормальная форма (ПНФ).

Определение 3.1. Формула Ф в логике первого порядка находится в предваренной нормальной форме, если формула Ф имеет вид:

() … () (F),

где каждое , i= 1,..., n, есть " или $ , и F - формула, не содержащая кванторов. () … () называется префиксом формулы F.

Формула (" х) (" у) ($ z)(Q (х, y)® R (z)) находится в предваренной нормальной форме.

Рассмотрим метод преобразования формулы в предваренную нормальную форму. Для этого приведем основные пары эквивалентных формул логики предикатов. Две формулы и эквиваленты тогда и только тогда, когда истинностные значения и одни и те же при любой интерпретации. Сначала вспомним эквивалентности исчисления высказываний:

Кроме них, существуют другие пары эквивалентных формул, содержащих кванторы. Чтобы подчеркнуть, что свободная переменная х входит в формулу F, формулу F представим в виде F [ x ], ниже формула G, не содержит переменной х. Выполняются следующие пары эквивалентных формул.

Законы 3 и 4 истины, т.к. G не содержит х и может быть внесена в область действия квантора Q. Законы 1,2 нетрудно доказать, рассматривая произвольные интерпретации I с областью D и различные варианты истинности для соответствующих формул. Пусть F [ x ], H [ x ] - две формулы, содержащие х тогда:

Квантор всеобщности и квантор существования можно распределять по и соответственно.

Пример 3.1. F [ x ] - четное число х, H [ x ]- нечетное число х, тогда левая часть 5а) ложна, а правая истинна. Для 6а) левая часть истинна, а правая ложна.

В случаях подобных 5а), 6а) формула преобразуется в ПНФ специальным образом. Т.к. каждая связанная переменная в формуле может рассматриваться как место для подстановки, какой угодно переменной, то каждую связанную переменную х можно переименовать в z и формула перейдет в , т.е. = . Тогда, если z - переменная, которая не встречается в F [ x ], то

Алгоритм преобразования формул в пренексную нормальную форму.

Шаг 1. Исключаем и эквивалентность из формул.

Шаг 2. Знак отрицания вносим внутрь формулы. Для этого используем законы двойного отрицания, де Моргана и 1),2).

Шаг 3. Переименовываем связанные переменные, если это необходимо.

Шаг 4. Используем 3),4),5),6),7),8).

Пример 3.2. Привести в ПНФ формулу (" x) P (x)®$ xQ (x).