Семантика

Семантика пропозициональных формул определяет, какое истиностное значение F^I назначается пропозициональной формуле F интерпретацией I. Наша следующая цель – расширить это определение до предикатных формул. Сначала нам надо расширить определение интерпретации до предикатных сигнатур.

Интерпретация I предикатной сигнатуры s состоит из

• непустого множества |I|, называемого пространством I,
• элементов c^I из |I| (для каждой объектной константы c из s),
• элементов R^I из множества {л,и} (для каждой пропозициональной константы R из s),
• функций R^I из |I|ⁿ в {л,и} (для каждой предикатной константы R из s арности n > 0).

Пример интерпретации. Теперь замечания, предшествующие упражнениям по переводу с русского языка, могут рассматриваться как определение интерпретации сигнатуры (4). Для этой интерпретации I

|I| = w, aI = 10, PI(n) = м и, если n простое , н о л, иначе , QI(m, n) = м и, если m < n, н о л, иначе,

(5)



Семантика логики предикатов, вводимая ниже, определяет истиностное значение F^I только для случая, когда F – предложение. Как и в логике высказываний определение рекурсивно. Для пропозициональных констант, определять нечего: истиностное значение R^I является частью интерпретации I. Для других атомарных предложений, мы можем определить

R(t1, ... , t_n)^I = R^I(t^I1, ... , t^I_n) (Так как R(t1, ..., t_n) – предложение, каждый терм t_i является объектной константой, и, следовательно, t^I_i – часть I). Для пропозициональных связок, мы можем использовать те же правила, что и в логике высказываний. Но случай кванторов представляет сложность.

Рассмотрим интерпретацию I предикатной сигнатуры s. Для каждого элемента c из пространства |I|, выберем новый символ c^* и добавим его в s в качестве объектной константы. Например, если s есть (4) и I есть (5), тогда расширенная сигнатура –

{a, 0^*, 1^*, 2^*, ... , P, Q}

Интерпретация I может быть расширена до новой сигнатуры с помощью определения

(c^*)^I = c для всех c О |I|.

Мы определим рекурсивно истиностное значение F^I, которое назначается F интерпретацией I для каждого предложения F расширенной сигнатуры, которая включает, в частности, каждое предложение сигнатуры s . Для любой пропозициональной константы R, R^I является частью интерпретации I. Иначе, мы определяем:

• R(t1, ... , t_n)^I = R^I(t^I1, ..., t^I_n),
• (¬F )^I = ¬(F^I),
• (F Д G)^I = Д(F^I, G^I) для каждой бинарной связки Д,
• " w F(w)^I = и тогда и только тогда, когда для всех c О |I|: F (c^*)^I = и,
• $ w F(w)^I = и тогда и только тогда, когда для некоторого c О |I|: F (c^*)^I = и.

Как и в логике высказываний, мы говорим, что F истинно при I и пишем I |= F, если F^I = и.

3.13 Покажите, что $ x Q(x, a) истинно при интерпретации (5).

3.14 Пусть F(x) является формулой, дающей ответ на задачу 3.5 выше. Покажите, что для любого n О w, при интерпретации (5) F(n^*) истинно тогда и только тогда, когда n < 2.

---

Назад