[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3]

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

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

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

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

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

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

Предположим теперь, что теорема справедлива для формул, содержащих не более k операций, и докажем, что при этом предположении она будет справедлива и для формул, содержащих ровно k+1 операцию.
Пусть формула А содержит k+1 операцию и имеет вид σх L(x) , где σх обозначает один из кванторов.
Так как L(x) содержит k операций, и, следовательно, ее можно считать приведенной к предваренной нормальной форме, то у нее все кванторные операции стоят впереди. Но тогда формула σx L(x) , очевидно, имеет предваренную нормальную форму.
Пусть формула А имеет вид ¬L , где формула L приведена к предваренной нормальной форме и содержит k операций. Тогда с помощью равносильностей 1 и 2 отрицание можно ввести под знак кванторов, и это приведет формулу А к предваренной нормальной форме.
Пусть формула А имеет вид L₁ v L₂ , где L₁ и L ₂ приведены к предваренной нормальной форме.
Переименуем в формуле L₂ связанные предметные переменные так, чтобы в формулах L _l и L₂ все связанные предметные переменные были различными. При этом формулы L₁ и L₂ могут быть записаны в виде

Используя равносильности 7 и 1, запишем формулу А, вводя формулу L₂ под знаки кванторов
(σx₁), (σx₂), (σx_n):

Затем введем под знаки кванторов (σy₁), (σy₂),..., (σy_р) формулу α₁(x₁,x₂,...,x_n). Тогда для формулы А получим предваренную нормальную форму:

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

Замечание
Если в процессе приведения формулы логики предикатов к п.н.ф. приходится рассматривать выражение хА(х) хВ(х) или выражение xA(x)& xB(x), то следует воспользоваться равносильностями 5 и 10.

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

[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3]