Интерпретация. Модель

Интерпретацию будем считать заданной, если:

1. Задано непустое множество M, называемое областью интерпретации.

2. Заданы следующие соответствия:

a) предикатным буквам поставлены в соответствие некоторые n - местные

предикаты (отношения) в M; niA

b) функциональным буквам поставлены в соответствие некоторые n -

аргументные функции, отображающие M nifn в M;

c) каждой предметной постоянной поставлен в соответствие некоторый

(фиксированный) элемент из M;

d) символам , ⇒, ∀ x, ∃ x поставлен в соответствие их обычный смысл.

3. Считается, что предметные переменные пробегают всё множество M.

Например, чтобы задать интерпретацию для формулы ∀ x(x, y, b31A1A1), нужно

задать множество M - область интерпретации (область изменения

переменных x, y). Из этой области M будем брать некоторый элемент,

соответствующий предметной постоянной b1. Далее нужно задать 3-х

местный предикат на M, соответствующей предикатной букве. Так, можно

положить, что M =[0, ∞); предметной постоянной b31 поставить в соответствие

1, а (x, y, z) поставить в соответствие предикат x + y ≥ z. Тогда формула

∀ x(x, y, b31A31A1) в заданной интерпретации запишется:

∀ x(x + y ≥ 1)

и означает, что для любого x (x ∈ [0, ∞)) сумма x + у больше или равна 1.

Очевидно, что это отношение истинно при некоторых у (у ≥ 1) и ложно при

других значениях у (0≤ у< 1). Если предметной постоянной b1 поставить в

соответствие 0, а не 1, то утверждение ∀ x(x +y ≥ 0) будет истинно при любом

значении свободной переменной у.

Легко видеть, что для той же формулы ∀ x(x, y, b31A1) можно построить

бесчисленное множество других интерпретаций, выбирая различные

множества M, выбирая из M, каким-то образом элемент, соответствующий b1,

и задавая различным образом на M трехместный предикат. Так, можно за M

взять множество всех студентов Казани, за b1 студента Иванова, а (x, y, z)

поставить в соответствии предикат: «x и у учатся в той же группе, что и z».

Тогда исходная формула ∀ x(x, y, b31A31A1) в этой интерпретации означает

утверждение: ∀ x(x и у учатся в той же группе, что и Иванов). Это утверждение

является ложным при каждом у, ибо не может быть, чтобы любой x и

некоторый у учились в той же группе, что и Иванов.

При данной интерпретации всякая формула без свободных переменных

(замкнутая формула) представляет собой высказывание, которое истинно

либо ложно, а всякая формула со свободными переменными выражает

некоторое отношение на M, которое может быть истинно для одних значений

из M и ложно для других.

Формула называется выполнимой в данной интерпретации, если она

принимает значение И хотя бы для одной совокупности возможных значений

её свободных переменных (если они есть). Если формула не содержит

свободных переменных, то она называется выполнимой в том случае, если

принимает значение И в этой интерпретации.

Формула называется истинной в данной интерпретации, если она принимает

значение И для всех возможных значений её свободных переменных (если

они есть). Если же свободных переменных нет, то формула называется

истинной, когда она принимает значение И в этой интерпретации.

Формула называется ложной в данной интерпретации, если она принимает

значение Л для всех возможных значений её свободных переменных (если

они есть). Если же свободных переменных нет, то формула называется

ложной, когда она принимает значение Л в этой интерпретации. Очевидно,

что формула ложна в данной интерпретации тогда и только тогда, когда она

не выполнима в этой интерпретации. Так же ясно, что формула A выполнима

в данной интерпретации тогда и только тогда, когда она не является ложной в

этой интерпретации.

Данная интерпретация называется моделью для множества формул G, если

каждая формула из G истинна в этой интерпретации.