Определение. Говорят, что формула логики предикатов
имеет нормальную форму,
если она содержит только
операции конъюнкции, дизъюнкции и кванторные
операции, а операция отрицания отнесена к элементарным формулам.
Очевидно, что
используя равносильности алгебры высказываний и логики предикатов, каждую
формулу логики предикатов можно привести к нормальной форме.
Пример 1. Приведем к нормальной форме формулу
.
Пользуясь равносильными преобразованиями,
получим
.
Среди нормальных форм формул логики
предикатов выделяют так называемую предваренную (префиксную, пренексную)
нормальную форму (ПНФ). В
ней кванторные операции либо полностью отсутствуют,
либо они используются после всех операций алгебры логики, т.е. ПНФ формулы
логике предикатов имеет вид
,
где под символом
понимается один из
кванторов
или
, а формула А кванторов не содержит.
Теорема. Всякая фрмула логики предикатов может
быть приведена к предваренной нормальной форме.