Равносильность формул логики предикатов. Правила перехода к равносильным формулам в логике предикатов, совпадающие с аналогичными правилами в логике высказываний

Пусть формулы F и G имеют одно и то же множество свободных переменных (в частности, пустое).

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

Формулы F и G равносильны на множестве M, если они равносильны во всех интерпретациях, заданных на множестве M.

Формулы F и G равносильны (в логике предикатов), если они равносильны во всех множествах (тогда будем писать F G).

Укажем несколько правил перехода от одних формул к другим, им равносильным (во всех интерпретациях). Для формул ЛП сохраняются все равносильности и правила равносильных преобразований логики высказываний. Кроме того, существуют следующие правила:

1. Перенос квантора через отрицание. Пусть A – формула ЛП, содержащая свободную переменную x. Тогда справедливы равносильности

( x) A(x) ( x) A(x);

( x) A(x) ( x) A(x).

Поскольку кванторов всего два, то можно считать их противоположными друг другу. Тогда это правило можно формулировать и так: при переносе квантора через отрицание он меняется на противоположный.

2. Вынос квантора за скобки. Пусть формула A(x) содержит свободную переменную x, формула B не содержит переменной x и нет переменных, свободных в одной из них и связанных в другой. Тогда

( x) (A(x) & B) ( x) A(x) & B;

( x) (A(x) & B) ( x) A(x) & B;

( x) (A(x) B) ( x) A(x) B;

( x) (A(x) B) ( x) A(x) B.

3. Перестановка одноименных кванторов:

( x) ( y) A(x, y) ( y) ( x) A(x, y);

( x) ( y) A(x, y) ( y) ( x) A(x, y).

4. Переименование связанных переменных. Заменяя связанную переменную формулы A другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора, получаем формулу, равносильную A. Это правило применяется при составлении формул ЛП из формул A и B, если есть переменные, свободные в одной из них и связанные в другой. Такую связанную переменную заменяем другой переменной, не входящей в эти формулы.

16. Теорема о существовании приведённой формы для каждой формулы логики предикатов.

Теорема: для любой формулы существует равносильная ей приведённая формула, причём множества свободных и связанных переменных этих формул совпадают. Такая приведённая формула называется приведённой формой данной формулы.

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

Теорема: для любой приведённой формулы существует равносильная ей нормальная формула той же длины. Такая формула называется нормальной формой данной приведённой формулы.