7. Предваренная нормальная форма

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

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

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

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

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

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

Доказательство. Будем считать, что формула уже приведена к нормальной форме и покажем, что ее можно привести к предваренной нормальной форме.

Если данная формула является элементарной, то она кванторов не содержит, и, следовательно, уже имеет предваренную нормальную форму.

Предположим теперь, что теорема справедлива для формул, содержащих не более k операций, и докажем что при этом предположении она будет справедлива и для формул. содержащих ровно k+1 операцию.

Пусть формула А содержит k 1 операцию и имеет вид L( х), гдеобозначает один из кванторов.

Так как L(x) содержит k операций, и, следовательно, ее можно считать приведенной к предваренной нормальной форме, то у нее все кванторные операции стоят впереди. Но тогда формула L(x), очевидно, имеет предваренную нормальную форму.

Пусть формула А имеет вид, где формула L приведена к предваренной нормальной форме и содержит k операций. Тогда с помощью равносильностей 1 и 2 отрицание можно ввести под знак кванторов, и это приведет формулу А к предваренной нормальной форме.

Пусть формула А имеет вид , гдеиприведены к предваренной нормальной форме.

Переименуем в формуле связанные предметные переменные так, чтобы в формулахивсе связанные предметные переменные были различными. При этом формулыимoгyт быть записаны в виде

Используя равносильности 7 и 1, запишем формулу А, вводя формулу под знаки кванторов:

Затем введем под знаки кванторов формулу. Тогда для формулы А получим предваренную нормальную форму:

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

Замечание. Если в процессе приведения формулы логики предикатов к п.н.ф. приходится рассматривать выражение или выражение, то следует воспользоваться равносильностями 5 и 10.

Например, приведем к пред варенной нормальной

форме формулу .