Исчисление предикатов
Как и в исчислении высказываний, в исчислении предикатов существует нормальная форма представления выражений, но для построения такой нормальной формы используется расширенный набор правил синтаксических преобразований. Ниже приведена последовательность применения таких правил. Для приведения любого выражения к нормальной форме следует выполнить следующие операции.
- (1) Исключить операторы эквивалентности, а затем импликации.
- (2) Используя правила Де Моргана и правила замещения (E X)U на – (любой X)-U (а следовательно, и (любой X) U на – (E X)-U), выполнить приведение отрицания.
- (3) Выполнить приведение переменных. При этом следует учитывать особенности определения области интерпретации переменных кванторами. Например, в выражении (E Х)(ФИЛОСОФ(Х))&(E Х)(АТЛЕТ(Х)) переменные могут иметь разные интерпретации в одной и той же области. Поэтому вынесение квантора за скобки – (E Х)(ФИЛОСОФ(Х))&.(АТЛЕТ(Х)) – даст выражение, которое не следует из исходной формулы.
- (4) Исключить кванторы существования. Кванторы существования, которые появляются вне области интерпретации любого квантора общности, можно заменить произвольным именем (его называют константой Сколема), в то время как экзистенциальные переменные, которые могут существовать внутри области интерпретации одного или более кванторов общности, могут быть заменены функциями Сколема. Функция Сколема– это функция с произвольным именем, которая имеет следующий смысл: "значение данной переменной есть некоторая функция от значений, присвоенных универсальным переменным, в области интерпретации которых она лежит".
- (5) Преобразование в префиксную форму. На этом шаге все оставшиеся кванторы (останутся только кванторы общности) переносятся "в голову" выражения и таким образом оказываются слева в списке квантифицированных переменных. За ними следует матрица, в которой отсутствуют кванторы.
- (6) Разнести операторы дизъюнкции и конъюнкции.
- (7) Отбросить кванторы общности. Теперь все свободные переменные являются неявно универсально квантифицированными переменными. Экзистенциальные переменные станут либо константами, либо функциями универсальных переменных.
- (8) Как и ранее, отбросить операторы конъюнкций, оставив множество фраз.
- (9) Снова переименовать переменные, чтобы одни и те же имена не встречались в разных фразах.
Снова о роботах и комнатах
В главе 3 мы уже упоминали об исчислении предикатов в упрощенном виде. Там выражение вида: at(робот, комнатаА) означало, что робот находится в комнате А. Термы робот и комнатаА в этом выражении представляли собой константы, которые описывали определенные реальные объекты. Но что будет означать выражение вида: at(X, комнатаА), в котором х является переменной? Означает ли оно, что нечто находится в комнате А? Если это так, то говорят, что переменная имеет экзистенциальную подстановку (импорт). А может быть, выражение означает, что все объекты находятся в комнате А? В таком случае переменная имеет универсальную подстановку. Таким образом, отсутствие набора четких правил не позволяет однозначно интерпретировать приведенную формулу.
Перечисленные в этом разделе правила исчисления предикатов обеспечивают однозначную интерпретацию выражений, содержащих переменные.
В частности, фраза: at(X, комнатаА)<-at (X, ящик1) интерпретируется как: "для всех X X находится в комнате А, если X находится в ящике 1".
В этой фразе переменная имеет универсальную подстановку. Аналогично, фраза: at(X, комнатаА) <- интерпретируется как "для всех X X находится в комнате А".
А вот фраза: ← at(X, комнатаА) интерпретируется как "для всех XX не находится в комнате А".
Иными словами, это не тот случай, когда некоторый объект X находится в комнате А и, следовательно, переменная имеет экзистенциальную подстановку.
Теперь можно преобразовать фразовую форму, в которой позитивные литералы сгруппированы слева от знака стрелки, а негативные – справа. Если фраза в форме: P1,…, Рт ← q1,…qn содержит переменные х1,…, хk, то правильная интерпретация имеет следующий вид: для всех x1,…, хk p1 или… или pm является истинным, если q1 и… и qn являются истинными.
Если n = 0, т.е. отсутствует хотя бы одно условие, то выражение будет интерпретироваться следующим образом: для всех x1 ,…, xk p1 или… или рт является истинным.
Если т = 0, т.е. отсутствуют термы заключения, то выражение будет интерпретироваться следующим образом: для всех x1,…, xk не имеет значения, что q1 и… и qn являются истинными.
Если же т = п = 0, то мы имеем дело с пустой фразой, которая всегда интерпретируется как ложная.