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

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

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

Пример 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.51.8. Аксиома индукции ``говорит'' про множества натуральных чисел, а задачи 1.51.8 – про функции из натуральных чисел в натуральные числа, и не существует переменных для таких объектов в языке первого порядка сигнатуры (6). ``Формулы второго порядка'' (не обсуждаемые здесь подробно) дают такую возможность. Кроме объектных переменных, такие формулы могут включать ``предикатные переменные'' и ``функциональные переменные''. Например, аксиома индукции может быть представлена замкнутой формулой второго порядка
" p((p(a) & " x(p(x) Й p(s(x)))) Й " x p(x)), (8)
где p – унарная предикатная переменная.

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

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

h(t1, ... , tn)I = hI (tI1, ... , tIn)
Дополнительное правило в определении значений формул при интерпретации читается следующим образом:

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

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


Назад