16 4_Классическая семантика ЛП
.rtfКлассическая семантика логики предикатов
Интерпретация:
I=< M, f, g, h,…, P, Q, R , ...>
M - произвольное множество.
Интерпретационные функции для функциональных и предикатных символов:
Если f(n)(x1,…, xn) , то f : MM…M→M или Nf ={<a1,…, an, b>| f(a1,…, an)=b}
Если P(m)(x1,…, xm), то P : MM…M→{0,1}или NP={< a1,…, an >|P(a1,…, an)=1}
Определим истинность формулы в интерпретации I:
-
I(t)M (индукцией по определению терма),
б) I(P(t1, …, tn))=1 <I(t1),…, I(tn)> Np или p(I(t1),…, I(tn))=1
в) I(F&G) = I(F)&I(G)
I(FG) = I(F) I(G)
I(FG) = I(F) I(G)
I(FG) = I(F) I(G)
I(FG) = I(F) I(G)
г) I(F)= I(F)
д) I(x F(x))=1 aM I(F(a))=1
I(x F(x))=1 aM I(F(a))=1
Формула F считается тождественно истинной или общезначимой тогда и только тогда, когда в каждой интерпретации I она истинна.
╞ F I I(F)=1
Формула F называется k- общезначимой тогда и только тогда, когда она истинна во всех интерпретациях, мощность множества MI которых меньше или равна k.
╞k F I(F)=1 |MI| k
Критика.
-
Понятие множества М не определено. В наивной трактовке оно заведомо противоречивое.
-
Если М- бесконечное, то нет возможности проверить, истинна ли формула в данной интерпретации.
Пусть М={1,…,k} и предикатный символ P(x1, …, xn). Число интерпретационных функций для Р:
|
|
|
|
наборов – число интерпретационных
функций для Р.
Случай: n=2, k=8 (изобретение шахмат).