3.6.   Пренексная нормальная форма

 

Определение. Говорят, что формула логики предикатов имеет нормальную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отрицания отнесена к элементарным формулам.

Очевидно, что используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной форме.

Пример 1. Приведем к нормальной форме формулу

.

Пользуясь равносильными преобразованиями, получим

.

Среди нормальных форм формул логики предикатов выделяют так называемую предваренную (префиксную, пренексную) нормальную форму (ПНФ). В ней кванторные операции либо полностью отсутствуют, либо они используются после всех операций алгебры логики, т.е. ПНФ формулы логике предикатов имеет вид

,

где под символом  понимается один из кванторов  или , а формула А кванторов не содержит.

Теорема. Всякая фрмула логики предикатов может быть приведена к предваренной нормальной форме.