Необходимо
соотнести формулы логики предикатов первого порядка и предикаты. Как и в логике
высказываний подобное соотнесение осуществляет функция, называемая
интерпретацией.
Определение. Интерпретацией на непустом множестве М называется функция, заданная
на сигнатуре FÈR, которая
1) константе
ставит в соответствие элемент из М;
2) символу n-местной функции ставит в
соответствие некоторую n-местную
функцию, определенную на множестве М;
3) символу n-местного предиката ставит в
соответствие n-местный
предикат, заданный на М.
В результате
любая формула F
получает в соответствие предикат, местность которого равна числу свободных
переменных формулы F.
Приведем
примеры. Пусть сигнатура состоит из символа одноместного предиката P и двухместного предиката D, M={2,3,6,9,12,15} и
F=(P(x)&("y)(P(y)®D(x,y))
Поставим в соответствие
(проинтерпретируем) P(x) предикат «x – простое число», D(x,y) – предикат «x
меньше или равно y».
Тогда формула F получит
в соответствие предикат «x=2».
На этом же множестве можно рассмотреть и другую интерпретацию: P(x) ставится в соответствие «x – нечетное число», D(x,y) – предикат «x
делит y». В таком
случае, формула F
получает в соответствие предикат «x=3». Если j
– интерпретация, то предикат, соответствующий формуле F будем обозначать через j(F).
Одним из
основных типов задач этой темы являются задачи, связанные с использованием
выразительных возможностей языка логики предикатов. В качестве примера
рассмотрим задачу перевода на язык логики предикатов следующего рассуждения.
«Каждый первокурсник знаком с кем-либо из спортсменов. Никакой первокурсник не
знаком ни с одном любителем подледного лова. Следовательно, никто из
спортсменов не является любителем подледного лова». Для удобства ссылок это
рассуждение условимся называть рассуждением о первокурсниках. Выберем следующую
сигнатуру:
П(х): «х –
первокурсник»,
С(х): «х –
спортсмен»,
Л(х): «х – любитель
подледного лова»,
З(x,y): «х знаком с y».
Тогда
рассуждение запишется в виде следующей последовательности формул.
Н1=("x)[П(х)®($y)(C(y)&З(x,y))],
H2=("x)("y)[П(x)&Л(y)®ØЗ(x,y)],
H3=("x)(C(x)®ØЛ(x))
Мы установили,
что выразительных средств логики предикатов достаточно, чтобы записать
рассуждение о первокурсниках. Естественно далее поставить вопрос, логично ли
оно? Будет ли третье предложение следствием первых двух? На этот вопрос мы
ответим в §5.
|