СЕМАНТИКА НА ТЕРМОВЕТЕ И АТОМАРНИТЕ ФОРМУЛИ
Когато D е дадено множество, а n е
неотрицателно цяло число, ще наричаме интерпретация в D на n-местните функционални символи кое да е изображение на множеството Fn в множеството Fn(D). С други думи, една интерпретация в D на n-местните функционални символи се определя като на всеки n-местен функционален символ се постави в съответствие някоя n-местна функция в D. Аналогично, под интерпретация в D на n-местните предикатни символи ще разбираме кое да е изображение на множеството Pn в множеството
Pn(D), т.е. една интерпретация в D на n-местните предикатни символи се определя като на всеки n-местен предикатен символ се постави в съответствие някой n-местен предикат в D.
Казваме, че е дадена една структура, когато е дадено едно непразно множество D и за всяко неотрицателно цяло число n са избрани по една интерпретация в D на n-местните функционални символи и по една интерпретация в D на n-местните предикатни символи. Самата структура може да се разглежда като наредена тройка с пръв член непразното множество D, втори член редица j0,j1,j2,...
и трети член редица p0,p1,p2,...,
където за всяко неотрицателно цяло число n jn и pn са съответно интерпретация в D на n-местните функционални символи и интерпретация в D на n-местните предикатни символи. Първият член на така описаната тройка (т.е. множеството D) се нарича носител (а също универсум или област на данните) на структурата.
Забележка 1. Когато за дадено неотрицателно цяло число n и дадено непразно множество D се окаже, че е възможна само една интерпретация в D на n-местните функционални символи, и ние искаме да определим някоя конкретна структура с носител D, ще подразбираме, че за въпросното n е избрана именно тази интерпретация на n-местните функционални символи, без да я споменаваме изрично. Аналогично ще постъпваме и по отношение на предикатните символи. Споменатото положение да е възможна само една интерпретация в D на n-местните функционални символи възниква в два случая. Единият е онзи, когато множеството Fn е празно (тогава единствената възможна интерпретация в D на n-местните функционални символи е изображението с празна дефиниционна област). Другият случай е при положение, че множеството D има само един елемент (тогава съществува само една n-местна функция в D и единствената възможна интерпретация в D на n-местните функционални символи е онази, която на всеки от тях съпоставя въпросната функция). Положението да е възможна само една интерпретация в D на n-местните предикатни символи възниква единствено в случая, когато множеството Pn е празно.
Пример 1. Имайки пред вид пример 3 от встъпителните бележки, да конкретизираме сигнатурата от пример 1 от предходния въпрос, като положим
F0 = {e}, F1 = {a,b,s}, P1 = {d}, P2 = {p}
и приемем всички останали множества Fn и Pn да бъдат празни. Нека D е множеството на всички думи над азбуката, състояща се от буквите a, b и s. Ще дефинираме структура с носител D, съответстваща на разглежданията от пример 3 от встъпителните бележки. За тази цел вземаме следните интерпретации j0 и j1 в D съответно на нулместните и едноместните функционални символи:
j0(e) = e,
j1(a) = a,
j1(b) = b,
j1(s) = s,
където, както в споменатия пример от встъпителните бележки, e, a, b, s означават съответно празната дума и едноместните функции в D, дефинирани за всяка дума w от D чрез равенствата a(w) = aw, b(w) = bw, s(w) = sw. Интерпретации p1 и p2 в D на едноместните и двуместните предикатни символи определяме като полагаме p1(d) и p2(p) да бъдат съответно едноместният и двуместният предикат, представящи свойството d и отношението p от същия пример в смисъл, че p1(d) приема стойност 1 точно за онези думи от D, които имат свойството d, a p2(p) приема стойност 1 точно за онези двойки от думи от D, които удовлетворяват условието p. Разбира се за останалите интерпретации в D, участващи в определението на конкретната структура, няма нужда да споменаваме, имайки пред вид казаното в забележката по-горе.
Забележка 2. В описанията на езика Пролог терминът "структура" понякога се употребява в друг смисъл, нямащ нищо общо с горния (въпросният друг смисъл играе, грубо казано, ролята на събирателно понятие за понятията терм и атомарна формула).
Нека S е дадена структура. Ако се случи една дума W да принадлежи на точно едно от множествата Fn
и Pn, то тя ще бъде в дефиниционната област на точно една от интерпретациите, определящи S. В този случай образът на W при въпросната интерпретация ще означаваме с WS. Например ако S е структурата от пример 1, то ще имаме равенствата
eS = e, aS = a,
bS = b,
sS = s.
Допустимо е използване на означението WS и в случаи, когато W може да принадлежи на повече от едно измежду множествата Fn
и Pn, но от контекста е ясно коя от приложимите към W интерпретации се има пред вид.
Да предположим сега, че е дадена една структура S
с носител D, на която вторият и третият член са двете редици от
интерпретации j0,j1,j2,...
и p0,p1,p2,...
За всеки затворен терм T дефинираме елемент TS
на множеството D, който ще наричаме стойност на T в S. Дефиницията
е индуктивна: при cОF0
полагаме cS=j0(c),
a когато n е положително цяло число, fОFn
и T1, Т2,...,Тn
са затворени термове, полагаме
f(T1,Т2...,Тn)S = jn(f)(T1S,Т2S,...,ТnS).
Разбира се еднозначността на тази дефиниция произтича от еднозначното прочитане
на термовете. Сега ще дефинираме и стойност в S на коя да е затворена атомарна формула A, като тази стойност ще означаваме с AS и тя ще бъде някое от числата 0 и 1. А именно, ако pОP0, полагаме pS=p0(p), а ако n е положително цяло число, pОPn
и T1,
Т2,...,Тn
са затворени термове, то полагаме
p(T1,Т2...,Тn)S = pn(p)(T1S,Т2S,...,ТnS)
(по повод на еднозначността на тази дефиниция следва разбира се да се позовем
на еднозначното прочитане на атомарните формули). За една затворена атомарна формула A ще считаме, че е вярна в S, и ще пишем S 
A, ако AS=1 (за да изразим противното, ще пишем S 
A).
Пример 2. Ако S е структурата от пример 1, то
b(s(a(a(e))))S = bsaa, S d(a(a(b(b(e))))),
S p(e,e).
Ще дадем подобни дефиниции и за случая на произволни
термове и произволни атомарни формули. За тази цел обаче първо ще дефинираме
едно друго понятие, а именно - ако S е дадена структура и D
е нейният носител, то ще наричаме оценка в S на променливите (или по-кратко оценка в S) всяко изображение на множеството X в множеството D (когато структурата S се подразбира, понякога ще пропускаме частта "в S" на въведения термин). Интуитивното предназначение на променливите (т.е. на думите от X) е да им се дават като стойности елементи на носителя на разглежданата структура и една оценка в смисъл на дадената дефиниция може да се тълкува именно като такова даване на стойности.
Да предположим сега, че освен структурата S
е дадена и една оценка v в S на променливите. Тогава за всеки
терм T ще дефинираме елемент TS,v
на D, който ще наричаме стойност на T в S при
оценка v. Дефиницията е пак индуктивна: при cОF0
полагаме cS,v=j0(c),
при XОX полагаме XS,v=v(X),
a
когато n е положително цяло число, fОFn
и T1, Т2,...,Тn
са термове, полагаме
f(T1,Т2...,Тn)S,v
= jn(f)(T1S,v,Т2S,v,...,ТnS,v).
За произволна атомарна формула A ще дефинираме нейната стойност в S при оценка v, като тази стойност ще означаваме с AS,v и тя ще бъде някое от числата 0 и 1. А именно, ако pОP0, полагаме pS,v=p0(p), а ако n е положително цяло число, pОPn
и T1,
Т2,...,Тn
са термове, то полагаме
p(T1,Т2...,Тn)S,v = pn(p)(T1S,v,Т2S,v,...,ТnS,v)
(по повод на еднозначността на тази дефиниция следва разбира се да се позовем
на еднозначното прочитане на атомарните формули). За една атомарна формула A ще считаме, че е вярна в S при оценката v, и ще пишем S,vA, ако AS,v=1 (за да изразим противното, ще пишем S,vA).
Пример 3. Нека S е структурата от пример 1, а v е такава оценка в S на променливите, че да са в сила равенствата v(X) = sa и v(Y) = ba. Тогава
a(s(b(X)))S,v = asbsa,
S,v p(X,a(Y)).
Чрез индукция, съобразена с дефиницията за затворен
терм, се доказва, че за всеки затворен терм T имаме равенството
TS,v=TS,
следователно стойността на затворен терм в дадена структура е частен случай
на стойност на терм в дадена структура при дадена оценка на променливите.
Оттук веднага получаваме, че и за произволна затворена атомарна формула
A имаме равенството
AS,v=AS, следователно условието S,vA е равносилно с условието SA.
Близко е до ума, че при дадена структура S
и даден терм T стойността TS,v
няма да зависи от това как е дефинирана оценката v за променливите,
които не принадлежат на множеството VAR(T). Това ще го докажем във
вид на следното твърдение:
Лема за базисна роля на променливите на един терм.
Нека S е дадена структура. Тогава за произволен терм T имаме,
че ако две оценки v и vў в
S на променливите съвпадат върху множеството VAR(T), то е в сила равенството
TS,v=TS,vў.
Доказателство. Ще използваме индукция, съобразена
с дефиницията за терм. Ако разглежданият терм е константа или променлива,
проверката на твърдението е непосредствена. Нека сега термът T да
има вида f(T1,Т2...,Тn),
където n е положително цяло число, f e n-местен
функционален символ и T1, Т2,...,Тn
са термове, притежаващи доказваното свойство. Тогава и термът T
ще има това свойство, защото ако две оценки v и vў в S на променливите съвпадат върху множеството VAR(T), то при i=1,...,n те ще съвпадат също върху подмножеството VAR(Ti) на VAR(T) и следователно ще имаме равенството TiS,v=TiS,vў,
а оттук получаваме, че
TS,v=jn(f)(T1S,v,Т2S,v,...,ТnS,v)=jn(f)(T1S,vў,Т2S,vў,...,ТnS,vў)=TS,vў.
ї
Като следствие от горната лема лесно се получава аналогично твърдение за атомарни формули, а именно:
Лема за базисна роля на променливите на една атомарна формула. Нека S е дадена структура. Тогава за произволна атомарна формула A имаме, че ако две оценки v и vў в
S на променливите съвпадат върху множеството VAR(A), то е в сила равенството
AS,v=AS,vў.
За една атомарна формула A ще
казваме, че е тъждествено вярна в дадена структура S, ако
A е вярна в S при всяка оценка в S на променливите.
Пример 4. Нека S е структурата от пример
1. Тогава атомарните формули p(s(X),a(b(X)))
и p(s(X),a(s(b(X)))) са тъждествено верни в S.
Ясно е, че ако A е затворена
атомарна формула, то A е тъждествено вярна в S
точно тогава, когато A е вярна в S. По тази
причина за произволна атомарна формула A се уславяме
да пишем SA,
за да изразим, че A е тъждествено вярна в S.
Последно изменение: 18.02.2002 г.