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

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

Определение 2.1. Интерпретация формулы Ф первого порядка состоит из непустого универса D и указания значения всех констант и предикатных символов, встречающихся в Ф.

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

2. Каждому п- местному предикатному символу ставится в соответствие отображение ® {0,1}.

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

Пример 2.1. Рассмотрим формулу ( $ х) Ø Р (х). Зададим интерпретацию: область D = {1,2}, оценка для Р:

Т.к. Ø Р (2) = t в этой интерпретации, то ( $ х) Ø Р (х) истинна в этой интерпретации.

Пример 2.2. Рассмотрим формулу (" х) ($ y) (Р (х) Ù Q (х, y)). Зададим интерпретацию I: область D = {1,2}, оценки для Р и Q:

Если х =1, то Р (1) = f, следовательно Р (х) Ù Q (х, y) = f для y = 1 и для y = 2. Т.к. существует х =1, такое что ($ y) (Р (х) Ù Q (х, y)) ложно, то формула

(" х) ($ y) (Р (х) Ù Q (х, y)) ложна при интерпретации I.

Определение 2.2. Формула Ф непротиворечива (выполнима), если существует такая интерпретация I, что Ф имеет значение t в I. Тогда говорят, что I - модель формулы Ф и I удовлетворяет Ф.

Определение 2.3. Формула Ф противоречива (невыполнима), если не существует интерпретации I, которая удовлетворяет Ф.

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

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