5. Интерпретация и истинность формул в логике предикатов (PrL)

В логике предикатов определение истинностных значений формул основано на понятии интерпретации.

Определение (интерпретации) Пусть имеется язык логики предикатов

={R₀, R₁, … , f₀, f₁, … , c₀, c₁, …}

где R_i – n-местный предикатный символ, f_j – m-местный функциональный символ, c_k – константа. Интерпретацией языка называется следующая совокупность элементов

={A, (R₀), (R₁), … , (f₀), (f₁), … , (c₀), (c₁), …}, где

• A - некоторое множество объектов (область интерпретации)

• (R_i) – n-местное отношение (интерпретация предиката)

• (f_j): AA…AA – функция, определенная для m-местного функционального символа (интерпретация функционального символа)

• (c_k)A – (интерпретация константы)

Пример.

Пусть ={Q, f, a, b} – язык логики предикатов. Рассмотрим интерпретацию языка

={A, ребенок(x,y), мать(x), Джон, Мэри}, где

• A – множество всех людей

• (Q) – двухместное отношение ребенок(x,y) «x является ребенком y»

• (f): AA – функция одного аргумента мать(x) «x является матерью»

• (a)=Джон

• (b)=Мэри

Рассмотрим предложение (замкнутую формулу) S: Q(a, f(a))  (x)(Q(b, x))

Вопрос: как эта формула звучит в интерпретации ?

«Джон является ребенком матери Джона или существует некто (человек), чьим ребенком является Мэри»

Формула S в интерпретации является истинной!

Определение (интерпретация основного терма). Пусть

={R₀, R₁, … , f₀, f₁, … , c₀, c₁, …} – язык логики предикатов и

={A, (R₀), (R₁), … , (f₀), (f₁), … , (c₀), (c₁), …} – его интерпретация.

Интерпретацией основного терма t (не содержащего переменных) называется элемент (t)A, причем

• Если t=c (константа) то (t)=(c) (интерпретация терма совпадает с интерпретацией константы)

• Если t= f(t₁, … , t_n), где t_i – основные термы, то (t)= (f)((t₁), … , (t_n)) (интерпретация терма – есть интерпретация функции от интерпретаций аргументов)

Определение (истинность предложения в данной интерпретации). Пусть

={R₀, R₁, … , f₀, f₁, … , c₀, c₁, …} – язык логики предикатов и

={A, (R₀), (R₁), … , (f₀), (f₁), … , (c₀), (c₁), …} – его интерпретация.

1. Предложение R_i(t₁, … , t_n) истинно в интерпретации

R_i(t₁, … , t_n)

тогда и только тогда, если интерпретации термов (t₁), … , (t_n) удовлетворяют отношению (R_i)

2. Пусть , ,  - предложения языка логики предикатов . Тогда

  	   и 	   или 
   или 	  (  и ) или (  и )
(x)(x)   элемент aA такой, что (c), где с и интерпретация получена из путем добавления элемента (с)=a
(x)(x)   элемента aA (c), где с и интерпретация получена из путем добавления элемента (с)=a

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

Определение. Предложение  языка выполнимо тогда и только тогда, если существует интерпретация языка , в которой предложение  истинно.

Определение. Множество предложений S непротиворечиво, если существует интерпретация языка , в которой все предложения S истинны.

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