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

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

Определение 17. Интерпретация формулы F логики первого порядка состоит из непустой (предметной) области D и указания значения всех констант, функций и предикатов, встречающихся в F.

1. Каждой константе мы ставим в соответствие некоторый элемент из D.

2. Каждой n - местной функции мы ставим в соответствие отображение из Dⁿ в D (заметим, что Dⁿ = {(x₁, x₂,…,x_n)з x₁О D, x₂О D,…, x_nО D}).

3. Каждому n - местному предикату мы ставим в соответствие отображение Dⁿ в {И, Л}.

Для каждой интерпретации формулы из области D формула может получить значение И или Л согласно следующим правилам:

1. Если заданы значения формул F и G, то истинностные значения формул Ш(F), (F Ъ G), (F Щ G), (F ® G), (F «G) получаются с помощью таблиц истинности соответствующих логических связок.

2. (" x) F получает значение И, если F получает значение И для каждого x из D, в противном случае она получает значение Л.

3. ($ x) F получает значение И, если F получает значение И хотя бы для одного x из D, в противном случае она получает значение Л.

Отметим, что формула, содержащая свободные переменные, не может получить истинностное значение. Поэтому, в дальнейшем, будем считать, что формула либо не содержит свободных переменных, либо свободные переменные рассматриваются как константы.

Пример 3. Рассмотрим формулы (" x) P(x) и ($x) ШP(x).

Пусть интерпретации такова: область - D={1,2};

Оценка для P:P(1) =И, P(2) =Л.

В таком случае (" x) P(x) есть Л, а ($x) ШP(x) есть И в данной интерпретации.

Пример 4. Рассмотрим формулы (" x) ($y) P(x, y).

Пусть интерпретации такова: область - D={1,2};

Оценка для P: P(1,1) =И, P(1,2) =Л, P(2,1) =Л, P(2,2) =И.

При x=1 существует y=1, что P(x, y) =И.

При x=2 существует y=2, что P(x, y) =И.

Следовательно, в указанной интерпретации, для каждого x из D существует такой y, что P(x, y)=И, то есть (" x) ($y) P(x, y) есть И в данной интерпретации.

Определение 18: Формула является непротиворечивой (выполнимой) тогда и только тогда, когда существует такая интерпретация I, что G имеет значение И в I. В этом случае говорят, что I удовлетворяет G.

Определение 19: Формула является противоречивой (невыполнимой) тогда и только тогда, когда не существует интерпретации, которая удовлетворяет G.

Определение 20: Формула G является общезначимой тогда и только тогда, когда не существует никакой интерпретации, которая не удовлетворяет формуле G.

Определение 21: Формула G есть логическое следствие формул F₁, F₂,…, F_n тогда и только тогда, когда для каждой интерпретации I, если F₁ Щ F₂ Щ …F_n истинна в I, то G также истинна в I.

Теоремы 1 и 2 верны также и для логики предикатов первого порядка.

Пример 5. Рассмотрим формулы:

F1: (" x) (P(x)® Q(x)),

F2: P(a).

Докажем, что Q(a) есть логическое следствие формул F1 и F2.

Рассмотрим любую интерпретацию I, которая удовлетворяет (" x) (P(x)® Q(x))Щ P(a). Конечно, в этой интерпретации P(a) есть И. Пусть Q(a) есть Л в данной интерпретации, тогда P(a)® Q(a) есть Л в данной интерпретации по определению операции импликации. Это значит, что (" x) (P(x)® Q(x)) есть Л в I, что невозможно. Следовательно, Q(a) должна быть И в каждой интерпретации, которая удовлетворяет (" x) (P(x)® Q(x))Щ P(a). Это означает, что Q(a) есть логическое следствие из F1 и F2.

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

Дата добавления: 2015-06-27