Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Пусть формулы 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. Теорема о существовании нормальной формы для каждой приведённой формулы логики предикатов.
Теорема: для любой приведённой формулы существует равносильная ей нормальная формула той же длины. Такая формула называется нормальной формой данной приведённой формулы.
Дата публикования: 2014-11-29; Прочитано: 1120 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!