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

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

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

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

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

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

· A¹Æ - некоторое множество объектов (область интерпретации)

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

· e(f_j): A´A´…´A®A – функция, определенная для m-местного функционального символа (интерпретация функционального символа)

· e(c_k)ÎA – (интерпретация константы)

Пример.

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

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

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

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

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

· e(a)=Джон

· e(b)=Мэри

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

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

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

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

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

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

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

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

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

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

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

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

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

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

R_i(t₁, … , t_n)

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

b. Пусть j, s, t - предложения языка логики предикатов . Тогда

Øj « j	sÙt « s и t	sÚt « s или t
s®t « s или t	s«t « ( s и t) или ( s и t)
($x)s(x) « $ элемент aÎA такой, что s(c), где сÏ и интерпретация получена из путем добавления элемента e(с)=a
("x)s(x) « " элемента aÎA s(c), где сÎ и интерпретация получена из путем добавления элемента e(с)=a