Символы и интерпретации

Вернемся к синтаксису языка. Нетерпеливый читатель может найти полное описание формальной грамматики логики первого порядка в листинге.

Синтаксис логики первого порядка с оператором равенства, заданный в форме Бэкуса—Наура. В этом синтаксисе предусмотрены строгие правила применения круглых скобок; примечания, касающиеся круглых скобок и предшествования операторов, приведенные на, равным образом относятся и к логике первого порядка

Sentence —> AtomicSentence

                | ( Sentence Connective Sentence )

                | Quantifier Variable, ... Sentence

                | —(Sentence

AtomicSentence —> Predicate {Term, ...) | Term = Term

        Term —> Function (Term, ...)

                   | Constant

                   | Variable

Connective —> => | a | v | <=>

  Quantifier —> V | 3

    Constant —> A | X\ | John | ...

    Variable —> a | x \ s | ...

   Predicate —> Before \ HasColor \ Raining | ...

    Function —> Mother | LeftLeg | ...

Основными синтаксическими элементами логики первого порядка являются символы, которые обозначают объекты, отношения и функции. Поэтому сами символы подразделяются на три типа: константные символы, которые обозначают объекты; предикатные символы, которые обозначают отношения, и функциональные символы, которые обозначают функции. Примем соглашение, что имена этих символов будут начинаться с прописных букв. Например, могут использоваться константные символы Richard и John; предикатные символы Brother, OnHead, Person, King и Crown и функциональный символ LeftLeg. Как и применительно к пропозициональным символам, выбор имен этих символов полностью предоставляется пользователю. Каждый предикатный и функциональный символ характеризуется арностью, которая определяет количество формальных параметров.

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

  • Символ Richard обозначает Ричарда Львиное Сердце, а символ John — злого короля Джона.
  • Символ Brother обозначает отношение родства между братьями, т.е. множество кортежей объектов; символ OnHead обозначает отношение "быть на голове", которое установлено между короной и королем Джоном; символы Person, King и Crown относятся к множествам объектов, представляющих собой людей, королей и короны.
  • Символ LeftLeg относится к функции "быть левой ногой", т.е. к отображению.

Может быть также много других возможных интерпретаций, связывающих эти символы с данной конкретной моделью. Например, одна интерпретация отображает символ Richard на корону, а символ John — на левую ногу короля Джона. В этой модели имеется пять объектов, поэтому существует 25 возможных интерпретаций только для константных символов Richard и John.

Обратите внимание на то, что не все объекты имеют имя, например, в данной намеченной интерпретации не предусмотрены имена для короны или для ног. Возможно также, чтобы один объект имел несколько имен; примером такой интерпретации была бы интерпретация, в которой и символ Richard, и символ John относились бы к короне.

Если читатель находит, что такая возможность приводит к путанице, напомним, что в пропозициональной логике вполне допустимо иметь модель, в которой высказывания Cloudy (пасмурно) и Sunny (солнечно) одновременно являются истинными; задача исключения из рассмотрения моделей, несовместимых с нашими знаниями, возлагается на базу знаний.

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

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

Даже если количество рассматриваемых объектов ограничено, количество их комбинаций может быть очень большим. Например, при использовании символов, рассматриваемых в данном примере, существует приблизительно 1025 комбинаций для проблемной области с пятью объектами.