6.3. СЕМАНТИКА

Для того чтобы п. п. формуле придать «содержаний», ее надо интерпретировать как некоторое утверждение, касающееся рассматриваемой области. Для нас областью может служить некоторое непустое множество (возможно, бесконечное). Им может быть множество целых чисел, или множество всех конфигураций игры в восемь, или множество всех математиков и т. д. Интересующие нас утверждения будут связаны с отношениями между элементами этой области. Например, мы можем захотеть высказать утверждение: «Джон — отец Билла». Тогда областью будет множество людей, а отношением между людьми — бинарное отношение «отцовства».

Полезно также иметь функции на этой области. Если — область, то -местная функция ставит в соответствие каждому набору из элементов области некоторый элемент из этой области. Так, функция плюс отображает пары целых чисел в целые числа в соответствии с хорошо известной операцией сложения.

Именно об этих аспектах области — ее элементах, ее функциях и ее отношениях — мы и хотим говорить на нашем языке исчисления предикатов. Для того чтобы для п. п. формулы сделать утверждение определенного смысла, мы связываем с этой п. п. формулой некоторую непустую область а затем с каждым константным символом в п. п. формуле — некоторый конкретный элемент из с каждой функциональной буквой в п. п. формуле — некоторую конкретную функцию на (я-местные функциональные буквы соответствуют -местным функциям); с каждой предикатной буквой в этой п. п. формуле — некоторое конкретное отношение между элементами из (-местные предикатные буквы соответствуют -местным отношениям).

Конкретизация области и указанных соответствий дает интерпретацию, или модель, нашей п. п. формулы.

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

Рассмотрим в качестве примера атомную формулу

и следующую интерпретацию:

При такой интерпретации наша атомная формула утверждает, что «число 2 больше суммы чисел 4 и 6». Это утверждение неверно, поэтому имеет значение Если интерпретацию изменить так, что а станет числом 11, то будет иметь значение Т. Очевидно, что существует много других интерпретаций, для которых эта атомная формула имеет значение Т, и много таких интерпретаций, для которых она имеет значение но для любой интерпретации будет либо Т, либо и никогда то и другое одновременно.

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

Если формула, то имеет значение Т, когда имеет значение и имеет значение когда имеет значение Т.

Если — любые две п. п. формулы, то значения даются следующей таблицей истинности:

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

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