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

Определение 1.Формула логики предикатов называется выполнимой в области М, если существуют значения переменных, входящих в эту формулу и отнесенных к области М, при которых формула принимает истинные значения.

Определение 2. Формула А называется выполнимой, если существует область, на которой эта формула выполнима.

Определение 3. Формула логики предикатов называется тождественно истинной в области М, если она принимает истинные значения для всех значений переменных , входящих в эту формулу и отнесенных к этой области.

Определение 4. Формула А называется общезначимой, если она тождественно истинная во всякой области.

Определение 5. Формула А называется тождественно ложной в области М, если она принимает ложные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

Из приведенных определений следует:

1. Если формула общезначима, то она и выполнима на всякой области.
2. Если формула тождественно истинна в области, то она выполнима в этой области.
3. Если формула невыполнима, то она тождественно ложна в любой области.

Пример 1. Доказать, что формула

выполнима.

Решение.Для доказательства выполнимости формулы A достаточно найти область определения двухместного предиката P(x,y) и такое его значение, что в этой области формула принимает истинное значение. Такой областью определения предиката, в зависимости, будет множеством М=N*N. Действительно, если P(x,y) – предикат «y:x», то формула A тождественно истинна в области М, и, следовательно, выполнима в этой области. Однако, если в качестве предиката P(x,y) взять предикат «y<x»,то формула А будет тождественно ложной в области М, и, следовательно, невыполнимой в М. При этом ясно, что формула А не общезначима.

Пример 2.Доказать, что формула

является общезначимой.

Решение.Считая, что формула А определена на любой области М, проведем равносильные преобразования:

т.е. формула А тождественно истинная для любых одноместных предикатов P(x) и Q(x) и в любой области.

Пример 3.Доказать, что формула

тождественно логична.

Решение.Так как формула

,

а формула , очевидно, тождественно ложна, то тождественно ложна и формула А.

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

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

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

Пример 4.Привести к п.н.ф. формулу

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