Предикатов. Правила эквивалентных преобразований формул исчисления

Правила эквивалентных преобразований формул исчисления

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

В связи с этим дополнительно вводятся ряд правил, позволяющих исключить указанные кванторы из формул. Эти правила делятся на две группы:

1) Правила образования предваренных нормальных форм (ПНФ);

2) Правила образования Скулемовских стандартных форм (ССФ).

Рассмотрим эти формы и правили их образования.

Формула F находится в предваренной нормальной форме (ПНФ), тогда и только тогда, когда она имеет вид:

где каждое 1,n есть или ), или , и есть формула, не содержащая кванторов. называется префиксом, а - матрицей формулы F.

Например, в формуле

префикс предваряет матрицу

Рассмотрим правила эквивалентных преобразований формул, содержащих кванторы.

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

1a)

1b)

2a)

2b)

3a)

3b)

4a) (

4b)

Используя правила эквивалентных преобразований формул логики высказываний и указанные восемь правил, всегда можно преобразовать любую формулу в ПНФ. Рассмотрим пример.

Приведем формулу к ПНФ. Используя правило исключения связки импликации, получим:

.

По правилу 2a имеем:

.

Наконец, используя правило 3b, получим:

.

Формула в правой части последнего соотношения представлена в ПНФ.

Скулемовская стандартная форма – это ПНФ, в префиксе которой отсутствуют кванторы существования , а матрица является ПКНФ. Из этого определения становится очевидным, что скулемовские преобразования формул направлены на исключение кванторов существования из предваренных нормальных форм. Рассмотрим эти правила преобразования.

Пусть формула находится в предваренной нормальной форме, где есть ПКНФ. Положим, что есть квантор существования в префиксе .

Если никакой квантор всеобщности не стоит в префиксе левее , то выберем новую константу , отличающуюся от других констант, входящих в , заменим все , встречающиеся в , на константу и вычеркнем из префикса. Если - список всех кванторов всеобщности, встречающихся левее , то выберем новый местный функциональный символ , отличающийся от других функциональных символов, заменим все в на и вычеркнем из префикса. Затем этот процесс применяем для всех кванторов существования в префиксе; последняя из полученных формул есть ССФ – скулемовская стандартная форма. Константы и функции, используемые для замены переменных квантора существования, называют скулемовскими константами и функциями. Рассмотрим пример.

Получим ССФ для формулы:

Здесь левее нет никаких кванторов всеобщности, левее стоят и , а левее стоят , и . Следовательно, заменим переменную на константу , переменную на двухместную функцию , переменную на трехместную функцию . Таким образом, после указанных замен и изъятия кванторов существования получим следующую стандартную форму для написанной выше формулы:

Рассмотренные правила эквивалентных преобразований дают возможность представить любую теорему логики предикатов в скулемовской стандартной форме. Так как префикс в этой форме содержит только кванторы всеобщности, то это означает, например, для что форма получает значение И, если истинно для каждого из области (а в противном случае получает значение Л), то это дает право рассматривать как простое высказывание и квантор всеобщности, связывающий , вычеркнуть из префикса. В равной мере этот вывод относится и к кванторам всеобщности, связывающим другие переменные. Поэтому для доказательства теорем в логике предикатов можно использовать только матрицы, находящиеся в ПКНФ.

В логике предикатов доказана также следующая теорема.

Пусть - множество дизъюнктов, которые представляют ПКНФ в скулемовской стандартной форме некоторой формулы (теоремы) . Тогда формула противоречива в том и только в том случае, когда множество противоречиво.

Механизм применения метода резолюций, который использовался для доказательства теорем в логике высказываний, может быть применен и в логике предикатов. Однако при этом возникают три существенных вопроса:

1) как найти контрарные пары для дизъюнктов, содержащих переменные?

2) как вычислить резольвенту из дизъюнктов, содержащих переменные?

3) Как извлечь максимальную пользу из обратной дедукции с целью повышения эффективности метода резолюций?

Ответы на эти вопросы вносят некоторую специфику в алгоритм метода резолюций. Вернуться

Дата добавления: 2014-01-04