Функциональные символы и равенство: семантика

Чтобы обобщить понятие интерпретации на случай произвольной сигнатуры, нам надо сказать, как разрешено интерпретировать функциональную константу арности n > 0. Такой символ может быть интерпретирован как произвольная тотальная функция n переменных, чьи аргументы и значения принадлежат пространству интерпретации.

Определение 30 (Интерпретация сигнатуры логики пре\-ди\-ка\-тов). Интерпретация I сигнатуры s состоит из

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

Пример 1. Рассмотрим сигнатуру арифметики первого порядка

{ a, s, f, g },

(6)

где a – объектная константа (предназначенная для представления 0), s – унарная функциональная константа (для функции следования), и f, g – бинарные функциональные константы (для сложения и умножения). Так как эта сигнатура не включает предикатных констант, единственными атомарными формулами являются равенства. Интерпретация I сигнатуры (6) определяется следующим образом:

|I| = w, aI= 0, sI(n) = n + 1, fI(m, n) = m + n, gI(m, n) = m · n.

(7)



3.24 Выразите аксиому 1 части 1 и утверждения задач 1.1 и 1.16 замкнутыми формулами первого порядка.

Заметим, что синтаксис логики первого порядка не позволяет представить аксиому индукции и утверждения некоторых других задач из части 1, в частности, задачи 1.5–1.8. Аксиома индукции ``говорит'' про множества натуральных чисел, а задачи 1.5–1.8 – про функции из натуральных чисел в натуральные числа, и не существует переменных для таких объектов в языке первого порядка сигнатуры (6). ``Формулы второго порядка'' (не обсуждаемые здесь подробно) дают такую возможность. Кроме объектных переменных, такие формулы могут включать ``предикатные переменные'' и ``функциональные переменные''. Например, аксиома индукции может быть представлена замкнутой формулой второго порядка

" p((p(a) & " x(p(x) Й p(s(x)))) Й " x p(x)),

(8)

где p – унарная предикатная переменная.

3.25 Представьте следующие предложения формулами первого порядка:

• Существует не более одного x такого, что P(x).
• Существует в точности один x такой, что P(x).
• Существует по крайней мере два x таких, что P(x).
• Существует не более двух x таких, что P(x).
• Существует в точности два x таких, что P(x).

Чтобы определение F^I было применимо в случае присутствия функциональных констант арности > 0, нам надо расширить обозначение t^I с объектных констант до произвольных свободных от переменных термов сигнатуры s^I, и добавить правило для равенства. Значение t^I, назначенное интерпретацией I терму t, определено рекурсивно формулами

h(t1, ... , t_n)^I = h^I (t^I1, ... , t^I_n) Дополнительное правило в определении значений формул при интерпретации читается следующим образом:

• (t1 = t2)^I = и тогда и только тогда, когда t^I1 = t^I2.

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

3.26 Для каждого из следующих предложений определите, является ли оно выполнимым:

• a = b,
• " xy (x = y),
• " xy (x № y).

---

Назад