Previous  Next  Contents
 

 

СИГНАТУРИ, СТРУКТУРИ, ТЕРМОВЕ, АТОМАРНИ ФОРМУЛИ

    Оттук нататък ще предполагаме (както направихме това в предходния въпрос) , че е дадена една азбука, наречена базисна, която съдържа измежду своите знаци двете кръгли скоби и запетаята. Ще предполагаме също, че е фиксирано някое такова множество W от думи над базисната азбука, че префиксните изрази над W да имат еднозначен анализ. Сега и в бъдеще обаче ще се занимаваме със случая, когато W е обединение на множество X (множество на променливите), за което ще искаме да е безкрайно, множества F0,F1,F2, ... (множествa съответно на нулместните, едноместните, двуместните и пр. функционални символи), множества P0,P1,P2, ... (множествa съответно на нулместните, едноместните, двуместните и пр. предикатни символи)  и непразно множество L (множество на логическите символи), като при това множествата X и L нямат общи елементи с никое от множествата Fn и Pn, а също и помежду си (други пресичания на множества измежду споменатите се допускат). Нулместните функционални символи ще наричамe още константи. Двойката от редиците F0,F1,F2,... и P0,P1,P2,... ще наричаме сигнатура.

    Пример 1. Горното положение на нещата би могло да се осъществи например по следния начин, подходящ за разглеждане на чисто логическата част на езика Пролог в реализацията му Strawberry Prolog:
        а) базисната азбука съдържа поне главните и малките латински букви, цифрите, знака за подчертаване _ ,  двете кръгли скоби и запетаята;
        б) множеството X се състои от думите, които започват с главна латинска буква или със знак за подчертаване и не съдържат други знаци освен латински букви, знак за подчертаване и цифри, като изключваме обаче еднобуквената дума, състояща се само от знак за подчертаване (анонимната променлива), и думите, започващи с G, следвано от споменатия знак (глобалните променливи);
        в) всяко от множествата Fn и Pn се състои от думи, които започват с малка латинска буква, не съдържат други знаци освен латински букви, знак за подчертаване и цифри и не са резервирани за вградени предикати на Strawberry Prolog.
        г) множеството L съдържа поне думата not, която е една от резервираните думи на Strawberry Prolog (всъщност даже и тя доста дълго време няма да ни е нужна).

    В курса ние няма да ограничаваме разглежданията чрез фиксиране на такъв или друг конкретен пример, а единственото нещо, което ще изискваме винаги, това е да са изпълнени предположенията, изказани в абзаца преди примера (вкл. изискването префиксните изрази над W да имат еднозначен анализ). В по-нататъшните примери  обаче там, където е нужно да бъде фиксиран изборът на множеството W и на споменатите негови подмножества, ще имаме пред вид именно ситуацията от току-що описания пример, конкретизирана чрез подходящ избор на множествата Fn и Pn .

    Както обикновено, за всяко множество C и всяко положително цяло число n ще означаваме с Cn множеството на всички наредени n-орки от елементи на C; това множество се нарича n-та декартова степен на C (множеството C1 ще отъждествяваме със самото множество C). Ако C и Cў са някакви множества (не непременно различни помежду си), то за всяко положително цяло число n ще наричаме n-местни операции от C към Cў изображенията на множеството Cn в множеството Cў, а нулместни операции от C към Cў ще наричаме елементите на Cў. Множеството на всички n-местни операции от C към Cў ще означаваме с On(C,Cў). Под n-местни операции в дадено множество C ще разбираме n-местните операции от C към самото C, а под n-местни предикати в C - n-местните операции от C към двуелементното множество {0, 1}, състоящо се от числата 0 и 1 (когато имаме работа с предикати, интуитивно можем да тълкуваме числото 1 като "истина", а числото 0 - като "лъжа").

    Забележка 1. При описанието на езика Пролог терминът "предикат" често се употребява в по-широк смисъл и например някои от вградените предикати, за които стана дума в пример 1, не са всъщност предикати в горния смисъл.

    Когато C е дадено множество, а n е неотрицателно цяло число, ще наричаме интерпретация в C на n-местните функционални символи кое да е изображение на множеството Fn в множеството On(C,C). С други думи, една интерпретация в C на n-местните функционални символи се определя като на всеки n-местен функционален символ се постави в съответствие някоя n-местна операция в C. Аналогично, под интерпретация в C на n-местните предикатни символи ще разбираме кое да е изображение на множеството Pn в множеството On(C, {0, 1}), т.е. една интерпретация в C на n-местните предикатни символи се определя като на всеки n-местен предикатен символ се постави в съответствие някой n-местен предикат в C.

    Казваме, че е дадена една структура, когато е дадено едно непразно множество C и за всяко неотрицателно цяло число n са избрани по една интерпретация в C на n-местните функционални символи и по една интерпретация в C на n-местните предикатни символи. Самата структура може да се разглежда като наредена тройка с пръв член непразното множество C, втори член редица j0,j1,j2,... и трети член редица p0,p1,p2,..., където за всяко неотрицателно цяло число n jn и pn са съответно интерпретация в C на n-местните функционални символи и интерпретация в C на n-местните предикатни символи. Първият член на така описаната тройка (т.е. множеството C) се нарича носител на структурата.

    Пример 2. Имайки пред вид пример 3 от встъпителните бележки, да конкретизираме сигнатурата от пример 1 по-горе, като положим

F0={e}, F1={a,b,s}, P1={d}, P2={p}
и приемем всички останали множества Fn и Pn да бъдат празни. Нека C е множеството на всички думи над азбуката , състояща се от буквите a, b и s. Ще дефинираме структура с носител C, съответстваща на разглежданията от пример 3 от встъпителните бележки. За тази цел вземаме следните интерпретации j0, j1, p1, p2 в C съответно на нулместните и едноместните функционални символи и на едноместните и двуместните предикатни символи (други функционални и предикатни символи в случая няма, тъй че останалите интерпретации jn и pn ще бъдат с празна дефиниционна област и няма нужда да се грижим за тяхното дефиниране):
j0(e)=e,  j1(a)=a, j1(b)=b, j1(s)=s, p1(d)=d^, p1(p)=p^,
където с e, a, b, s както в споменатия пример от встъпителните бележки са означени съответно празната дума и функциите в C, дефинирани чрез равенствата a(X)=aX,  b(X)=bX,  s(X)=sX, а d^ и p^ са едноместният и двуместният предикат, които представят свойството d и отношението p от същия пример в смисъл, че имаме d^(Y)=1 точно тогава, когато е изпълнено условието d(Y), и имаме p^(X,Y)=1 точно тогава, когато е изпълнено условието p(X,Y).

    Забележка 2.  При описанието на езика Пролог терминът "структура" понякога се употребява в друг смисъл, нямащ нищо общо с горния. Въпросният друг смисъл играе ролята на събирателно понятие за понятията терм и атомарна формула, които след малко ще въведем.

    Нека S е дадена структура. Ако се случи една дума w да принадлежи на точно едно от множествата Fn и Pn, то тя ще бъде в дефиниционната област на точно една от интерпретациите, определящи S. В този случай образът на w при въпросната интерпретация ще означаваме с wS. Например ако S е структурата от пример 2, то ще имаме равенствата

eS=e,   aS=a,   bS=b,   sS=s,   dS=d^,   pS=p^.

    В ситуацията, описана в началото на настоящия въпрос, индуктивно се дефинира понятието терм: термове са константите, променливите и всички думи от вида f(T1,Т2...,Тn), където n е положително цяло число, f e n-местен функционален символ и T1, Т2,...,Тn са термове. Аналогична, но малко по-проста е и дефиницията на понятието затворен терм: затворени термове са константите и всички думи от вида f(T1,Т2...,Тn), където n е положително цяло число, f e n-местен функционален символ и T1, Т2,...,Тn са затворени термове (в литературата по логическо програмиране затворените термове често се наричат основни термове). Очевидно всички затворени термове са термове, а обратното не е вярно. След като разполагаме с понятието терм, уславяме се да наричаме атомарни формули нулместните предикатни символи и всички думи от вида p(T1,Т2...,Тn), където n е положително цяло число, p e n-местен предикатен символ и T1, Т2, ..., Тn са термове. Действайки аналогично, уславяме се да наричаме затворени атомарни формули (или основни атомарни формули) нулместните предикатни символи и всички думи от вида p(T1,Т2...,Тn), където n е положително цяло число, p e n-местен предикатен символ и T1, Т2, ..., Тn са затворени термове. Разбира се всички затворени атомарни формули са атомарни формули. Ясно е, че всички термове и всички атомарни формули са префиксни изрази над множеството W (има обаче и много други префиксни изрази над това множество, напр. изразите от вида X(T1,Т2...,Тn), къдетo X е променлива, n е положително цяло число и T1, Т2, ..., Тn са термове).

    Пример 3. При условията на пример 2 думата a(s(b(X))) е терм, думата b(s(a(a(e)))) е затворен терм, думата p(X,a(Y)) е атомарна формула, а думите d(a(a(b(b(e))))) и p(e,e) са затворени атомарни формули.

    Това, че термовете и атомарните формули са префиксни изрази над множеството W, заедно с еднозначния анализ на префиксните изрази над W осигурява еднозначното прочитане на термовете и на атомарните формули в следния смисъл: трите случая в дефиницията за терм се изключват взаимно, като в третия от тях числото n, функционалният символ f и термовете T1, Т2, ..., Тn се определят еднозначно по дадения терм, а също двата случая в дефиницията за атомарна формула се изключват взаимно и във втория от тях числото n, предикатният символ p и термовете T1, Т2, ..., Тn се определят еднозначно по дадената атомарна формула.

    Забележка 3. Предположенията, при които работим, не изключват възможността една и съща дума да бъде както терм, така и атомарна формула. Еднозначният анализ на префиксните изрази над W позволява да охарактеризираме думите с това свойство по следния начин: една дума е едновременно терм и атомарна формула точно тогава, когато тя принадлежи на сечението F0ЗP0 или има вида w(T1,T2...,Tn), където n е положително цяло число, w е дума от сечението FnЗPn и T1, T2, ..., Tn са термове.

    За всеки терм T ще дефинираме индуктивно едно множество VAR(T), което ще наричаме множество на променливите на T. А именно:
        а) при cОF0 полагаме VAR(c)=Ж;
        б) при XОX полагаме VAR(X)={X};
        в) когато n е положително цяло число, fОFn и T1, Т2, ..., Тn са термове, полагаме

VAR(f(T1,Т2...,Тn)) =
n
ою
i=1
 VAR(Ti).
Така изказаната дефиниция определя еднозначно множеството VAR(T) за произволен терм T благодарение на еднозначното прочитане на термовете.

    Пример 4. При условията на пример 2 имаме равенството VAR(a(s(b(X))))={X}, а множеството на променливите на терма b(s(a(a(e)))) е празно.

    Като използваме току-що дадената дефиниция и индукция, съобразена с дефиницията за терм, веднага се убеждаваме, че множеството на променливите на кой да е терм е крайно подмножество на множеството X. Пак въз основа на горната дефиниция, но чрез индукция, съобразена с дефиницията за затворен терм, показваме, че множеството на променливите на кой да е затворен терм е празно. Обратното също е вярно - ако множеството на променливите на един терм е празно, то този терм е затворен. В това можем да се убедим, като с помощта на горната дефиниция и на индукция, съобразена с дефиницията за терм, докажем за произволен терм, че той е затворен или множеството на променливите му има поне един елемент.

    За всяка атомарна формула A дефинираме множество VAR(A), което ще наричаме множество на променливите на A. Дефиницията е следната: когато pОP0, полагаме VAR(p)=Ж, а когато n е положително цяло число, pОPn и T1, Т2, ..., Тn са термове, полагаме

VAR(p(T1,Т2...,Тn)) =
n
ою
i=1
 VAR(Ti).
Благодарение на еднозначното прочитане на атомарните формули тази дефиниция определя еднозначно множеството VAR(A) за произволна атомарна формула A. При това, като използваме забележка 3, лесно се убеждаваме, че дефиницията за множество на променливите на терм и току-що дадената дефиниция не влизат в конфликт, когато прилагаме тези две дефиниции към дума, представляваща едновременно терм и атомарна формула.

    Пример 5. При условията на пример 2 имаме равенството VAR(p(X,a(Y)))={X,Y}, а множеството на променливите на атомарната формула d(a(a(b(b(e))))) е празно.

    Като използваме установените преди малко твърдения във връзка с множество на променливите на терм, веднага можем да заключим, че множеството на променливите на коя да е атомарна формула е крайно подмножество на множеството X и че една атомарна формула е затворена точно тогава, когато множеството на нейните променливи е празно.

    Да предположим сега, че е дадена една структура S с носител C, на която вторият и третият член са двете редици от интерпретации j0,j1,j2,... и p0,p1,p2,... За всеки затворен терм T дефинираме елемент TS на множеството C, който ще наричаме стойност на 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 е затворена атомарна формула, уславяме се да пишем SA, за да изразим, че A е вярна в S (за да изразим противното, ще пишем SA). При това уславяне дефиницията е следната: ако pОP0, считаме, че Sp точно тогава, когато p0(p)=1,а ако n е положително цяло число, pОPn и T1, Т2,...,Тn са затворени термове, считаме, че Sp(T1,Т2...,Тn) точно тогава, когато
pn(p)(T1S,Т2S,...,ТnS)=1.
(по повод на еднозначността на тази дефиниция следва разбира се да се позовем на еднозначното прочитане на атомарните формули).

    Пример 6. Ако S е структурата от пример 2, то b(s(a(a(e))))S=bsaa,  Sd(a(a(b(b(e))))),  S p(e,e).

    Ще дадем подобни дефиниции и за случая на произволни термове и произволни атомарни формули. За тази цел обаче първо ще дефинираме едно друго понятие, а именно - ако S е дадена структура и C е нейният носител, то ще наричаме оценка в S на променливите всяко изображение на множеството X в множеството C. Интуитивното предназначение на променливите (т.е. на думите от X) е да им се дават като стойности елементи на носителя на разглежданата структура и една оценка в смисъл на дадената дефиниция може да се тълкува именно като такова даване на стойности.

    Да предположим сега, че освен структурата S е дадена и една оценка v в S на променливите. Тогава за всеки терм T ще дефинираме елемент TS,v на C, който ще наричаме стойност на 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, което ще означаваме с S,vA (противното ще означаваме с S,vA). Дефиницията е следната: ако pОP0, считаме, че S,vp точно тогава, когато p0(p)=1, а ако n е положително цяло число, pОPn и T1, Т2, ...,Тn са термове, считаме, че S,vp(T1,Т2...,Тn) точно тогава, когато
pn(p)(T1S,v,Т2S,v,...,ТnS,v)=1
(разбира се и тук е уместна бележка във връзка с еднозначността на дадените дефиниции).

    Пример 7. Нека S е структурата от пример 2, а v е такава оценка в S на променливите, че да са в сила равенствата v(X)=s(e) и v(Y)=b(e). Тогава a(s(b(X)))S,v=asbs и S,vp(X,a(Y)).

    Чрез индукция, съобразена с дефиницията за затворен терм, се доказва, че за всеки затворен терм T имаме равенството TS,v=TS при произволна оценка v в S на променливите, следователно стойността на затворен терм в дадена структура е частен случай на стойност на терм в дадена структура при дадена оценка на променливите. Оттук веднага получаваме също, че за произволна затворена атомарна формула A и произволна оценка v в S на променливите условието 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) и следователно ще имаме равенството 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), то условието S,vA е равносилно с условието S,vўA.

    За една атомарна формула A ще казваме, че е тъждествено вярна в дадена структура S, ако A е вярна в S при всяка оценка в S на променливите.

    Пример 8. Нека S е структурата от пример 2. Тогава атомарните формули p(s(X),a(b(X))) и p(s(X),a(s(b(X)))) са тъждествено верни в S.

    Ясно е, че ако A е затворена атомарна формула, то A е тъждествено вярна в S точно тогава, когато A е вярна в S. По тази причина за произволна атомарна формула A се уславяме да пишем SA, за да изразим, че A е тъждествено вярна в S.
 

Последно изменение: 15.08.2001 г.
 
 Previous  Next  Contents