Семантика пропозициональных формул определяет, какое истиностное значение FI назначается пропозициональной формуле F интерпретацией I. Наша следующая цель – расширить это определение до предикатных формул. Сначала нам надо расширить определение интерпретации до предикатных сигнатур.
Интерпретация I предикатной сигнатуры s состоит из
Пример интерпретации. Теперь замечания, предшествующие упражнениям по переводу с русского языка, могут рассматриваться как определение интерпретации сигнатуры (4). Для этой интерпретации I
| (5) |
Семантика логики предикатов, вводимая ниже, определяет истиностное значение FI только для случая, когда F – предложение. Как и в логике высказываний определение рекурсивно. Для пропозициональных констант, определять нечего: истиностное значение RI является частью интерпретации I. Для других атомарных предложений, мы можем определить
Рассмотрим интерпретацию I предикатной сигнатуры s. Для каждого элемента c из пространства |I|, выберем новый символ c* и добавим его в s в качестве объектной константы. Например, если s есть (4) и I есть (5), тогда расширенная сигнатура –
Интерпретация I может быть расширена до новой сигнатуры с помощью определения
Мы определим рекурсивно истиностное значение FI, которое назначается F интерпретацией I для каждого предложения F расширенной сигнатуры, которая включает, в частности, каждое предложение сигнатуры s . Для любой пропозициональной константы R, RI является частью интерпретации I. Иначе, мы определяем:
Как и в логике высказываний, мы говорим, что F истинно при I и пишем I |= F, если FI = и.
3.13 Покажите, что $ x Q(x, a) истинно при интерпретации (5).
3.14 Пусть F(x) является формулой, дающей ответ на задачу 3.5 выше. Покажите, что для любого n О w, при интерпретации (5) F(n*) истинно тогда и только тогда, когда n < 2.