Интерпретация в логике первого порядка

Необходимо соотнести формулы логики предикатов первого порядка и предикаты. Как и в логике высказываний подобное соотнесение осуществляет функция, называемая интерпретацией.

Определение. Интерпретацией на непустом множестве М называется функция, заданная на сигнатуре 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».

Тогда рассуждение запишется в виде следующей последовательности формул.

Н₁=("x)[П(х)®($y)(C(y)&З(x,y))],

H₂=("x)("y)[П(x)&Л(y)®ØЗ(x,y)],

H₃=("x)(C(x)®ØЛ(x))

Мы установили, что выразительных средств логики предикатов достаточно, чтобы записать рассуждение о первокурсниках. Естественно далее поставить вопрос, логично ли оно? Будет ли третье предложение следствием первых двух?