Говорят, что формула логики предикатов имеет нормальную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отнесена к элементарным формулам.
Очевидно, что, используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной формуле. Например, приведем к нормальной форме формулу:
$$( \exists x P (x) \rightarrow \forall y Q (y)) \rightarrow R (z).$$
Пользуясь равносильными преобразованиями, получим:
$$( \exists x P (x) \rightarrow \forall y Q (y)) \rightarrow R (z) \equiv \overline { \overline { \exists x P (x) } \vee \forall y Q (y) } \vee R (z) \equiv$$
$$\equiv \overline { \overline { \exists x P (x) } } \wedge \overline { \forall y Q (y) } \vee R (z) \equiv \exists x P (x) \wedge \exists y \overline { Q (y) } \vee R (z).$$
Среди нормальных форм формул логики предикатов важное значение имеют так называемые предваренные нормальные формы (п.н.ф.). В них кванторные операции либо полностью отсутствуют, либо они используются после всех операций алгебры логики, то есть предваренная нормальная форма формулы логики предикатов имеет вид:
$$(\sigma x_{1}) (\sigma x_{2}) ... (\sigma x_{n}) A ( x_{1}, x_{2},..., x_{m}) , n \leq m,$$
где под символом \((\sigma x_{i})\) понимается один из кванторов \( \forall x_{i} \) или \( \exists x_{i} \), а формула \(A\) кванторов не содержит.
Теорема. Всякая формула логики предикатов может быть приведена к предваренной нормальной форме.
Доказательство. Будем считать, что формула уже приведена к нормальной форме и покажем, что ее можно привести к предваренной нормальной форме.
Если данная формула является элементарной, то она кванторов не содержит, и, следовательно, уже имеет предваренную форму.
Предположим теперь, что теорема справедлива для формул, содержащих не более \(k\) операций, и докажем, что при этом предположении она будет справедлива и для формул, содержащих ровно \(k+1\) операцию.
Пусть формула \(A\) содержит \(k+1\) операцию и имеет вид \(\sigma x L (x)\), где \(\sigma x\) обозначает один из кванторов.
Так как \(L (x)\) содержит \(k\) операций, и, следовательно, ее можно считать приведенной к предваренной нормальной форме, то у нее все кванторные операции стоят впереди. Но тогда формула \(\sigma x L (x)\), очевидно, имеет предваренную нормальную форму.
Пусть формула \(A\) имеет вид \(\bar{L}\), где формула \(L\) приведена к предваренной нормальной форме и содержит \(k\) операций. тогда с помощью равносильностей отрицание можно ввести под знак кванторов, и это приведет формулу \(A\) к предваренной нормальной форме.
Пусть формула \(A\) имеет вид \(L_{1} \vee L_{2}\), где \(L_{1}\) и \(L_{2}\) приведены к предваренной нормальной форме.
Переименуем в формуле \(L_{2}\) связанные предметные переменные так, чтобы в формулах \(L_{1}\) и \(L_{2}\) все связанные предметными переменными были различными. При этом формулы \(L_{1}\) и \(L_{2}\) могут быть записаны в виде:
$$L_{2} = (\sigma x_{1}) (\sigma x_{2}) ... (\sigma x_{m})\alpha _{1} ( x_{1}, x_{2}, ..., x_{n}) , m\leq n;$$
$$L_{2} = (\sigma y_{1}) (\sigma y_{2}) ... (\sigma y_{p})\alpha _{2} ( y_{1}, y_{2}, ..., y_{n}) , p\leq q.$$
Используя равносильности, запишем формулу \(A\), вводя формулу \(L_{2}\) под знаки кванторов \((\sigma x_{1}), (\sigma x_{2}), (\sigma x_{m})\):
$$A \equiv (\sigma x_{1})(\sigma x_{2}) ... (\sigma x_{m}) (\alpha _{1}(x_{1}, x_{2},...,x_{n}) \vee$$
$$\vee (\sigma y_{1})(\sigma y_{2}) ... (\sigma y_{p}) \alpha _{2}(y_{1}, y_{2},...,y_{q})).$$
Затем введем под знаки кванторов \((\sigma y_{1}),(\sigma y_{2}) , ..., (\sigma y_{p})\) формулу \(\alpha _{1}(x_{1}, x_{2},...,x_{n}).\) Тогда для формулы \(A\) получим предваренную нормальную форму:
\(A \equiv (\sigma x_{1}) (\sigma x_{2}) ... (\sigma x_{m}) (\sigma y_{1}) (\sigma y_{2})... (\sigma y_{p})(\alpha _{1} (x_{1},x_{2}, ...,x_{n})\)\(\vee \alpha _{2} (y_{1}, y_{2}, ...,y_{q})).\)
Аналогично проводится доказательство и в случае, когда формула \(A\) имеет вид \(L_{1} \wedge L_{2}\).
Замечание. Если в процессе приведения формулы логики предикатов к п.н.ф. приходится рассматривать выражение \( \exists x A (x) \vee \exists x B (x) \) или выражение \( \forall x A (x) \wedge \forall x B (x) \), то следует воспользоватся равносильностями.
Пример. Привести к п.н.ф. формулу:
$$A \equiv \forall x \exists y P ( x,y) \wedge \overline { \exists x \forall y Q (x,y) }.$$
Решение. Проводя равносильные преобразования, получим:
$$A \equiv \forall x \exists y P ( x,y) \wedge \forall x \exists y \overline { Q (x,y) } \equiv$$
$$\equiv \forall x ( \exists y P (x,y) \wedge \exists z \overline { Q (x,z) } ) \equiv$$
$$\equiv \forall x \exists y ( P (x,y) \wedge \exists z \overline { Q (x,z) } ) \equiv$$
$$\equiv \forall x \exists y \exists z ( P (x,y) \wedge \overline { Q (x,z) } ).$$
