ТЕРМОВЕ И АТОМАРНИ ФОРМУЛИ
Оттук нататък ще предполагаме (както направихме това в един предходен въпрос), че е дадена една азбука, наречена базисна, която съдържа измежду своите знаци двете кръгли скоби и запетаята. Ще предполагаме също, че е фиксирано някое такова множество W от думи над базисната азбука, че префиксните изрази над W да имат еднозначен анализ. Сега и в бъдеще обаче ще се занимаваме със случая, когато W е обединение на множества F0, F1, F2, ... (множествa съответно на нулместните, едноместните, двуместните и пр. функционални символи), множества P0, P1, P2, ... (множествa съответно на нулместните, едноместните, двуместните и пр. предикатни символи), множество X (множество на променливите) и множество L (множество на логическите символи). Думите от обединението на множествата F0, F1, F2, ... ще наричаме с общото име функционалние символи, а думите от обединението на множествата P0, P1, P2, ... - с общото име предикатни символи. Нулместните функционални символи ще наричамe още константи. Ще предполагаме, че множеството X е безкрайно, а множеството L се състои от пет различни думи, които ще означаваме с not, and, or, for_all и for_some (ще ги нариыаме съответно знак за отрицание, знак за конюнкция, знак за дизюнкция, квантор за общност и квантор за съществуване). За множествата X и L ще искаме още да нямат общи елементи помежду си, а също и с никое от множествата Fn и Pn, n = 0, 1 ,2, ... (пресичания на множества от последните два вида обаче се допускат, а също се допуска произволно много такива множества да бъдат празни). За да избегнем някои технически усложнения при по-нататъшните разглеждания, ще направим още следните допълнителни предположения: а) множеството F0 не е празно и б) за всяко неотрицателно цяло число n сечението на множествата Fn и Pn е празно.
Двойката от редиците F0,F1,F2,... и P0,P1,P2,... ще наричаме сигнатура. Интуитивно погледнато, n-местните функционални и предикатни символи ще служат за означаване съответно на дадени n-местни функции и дадени n-местни предикати в някое непразно множество, с променливите ще могат да се означават произволни елементи на това множество, а петте логически символи ще представят, грубо казано, строенето на едни съждения от други с помощта на "не", "и", "или", "за всяко", "за някое".
Забележка 1. Интуитивните разяснения от последното изречение по-горе ще бъдат уточнени в някои от следващите въпроси с помощта на точни математически дефиниции.
Пример 1. Предположенията, които направихме, биха могли да бъдат изпълнени например по следния начин, подходящ за разглеждане на чисто логическата част на езика Пролог в реализацията му Strawberry Prolog:
а) базисната азбука съдържа
поне главните и малките латински букви, цифрите, знака за подчертаване
_ , двете кръгли скоби и запетаята;
б) множеството X се състои от думите, които започват с главна латинска буква или със знак за подчертаване и не съдържат други знаци освен латински букви, знак за подчертаване и цифри, като изключваме обаче еднобуквената дума, състояща се само от знак за подчертаване (анонимната променлива), и думите, започващи с G, следвано от споменатия знак (глобалните променливи);
в) множеството L се състои от думата not (тя всъщност е една от думите на Strawberry Prolog, резервирани за вградени предикати) и от думите and, or, for_all и for_some;
г) всяко от множествата
Fn и Pn се състои от думи, които започват с малка латинска буква, не съдържат други знаци освен латински букви, знак за подчертаване и цифри, не са резервирани за вградени предикати на Strawberry Prolog и не принадлежат на множеството L.
Забележка 2. В курса ние няма да ограничаваме разглежданията чрез фиксиране на такъв или друг конкретен пример, а единственото нещо, което ще изискваме винаги, това е да са изпълнени предположенията, изказани в първия абзац на настоящия въпрос (вкл. изискването префиксните изрази над W да имат еднозначен анализ). В по-нататъшните примери обаче там, където е нужно да бъде фиксиран изборът на множеството W и на споменатите негови подмножества, ще имаме пред вид именно ситуацията от току-що описания пример, конкретизирана чрез подходящ избор на множествата Fn и Pn.
Пример 2. Имайки пред вид пример 3 от встъпителните бележки, да конкретизираме сигнатурата от пример 1 по-горе, като положим
F0 = {e}, F1 = {a,b,s}, P1 = {d}, P2 = {p}
и приемем всички останали множества Fn и Pn да бъдат празни (константата e ще служи за означаване на празната дума e, функционалните символи a, b и s - за означаване на изображенията a, b и s от споменатия пример, а предикатните символи d и p - за означаване на предикати, представящи дефинираните там свойство d и отношение 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 и с равенството F0 З X = Ж осигурява
еднозначното прочитане на термовете и на атомарните формули в следния смисъл:
трите случая в дефиницията за терм се изключват взаимно, като в третия
от тях числото n, функционалният символ f и термовете T1, Т2, ..., Тn се определят еднозначно по дадения терм, а също двата случая в дефиницията за атомарна формула се изключват взаимно и във втория от тях числото n, предикатният символ p и термовете T1, Т2, ..., Тn се определят еднозначно по дадената атомарна формула.
Забележка 3. Предположенията, при които работим, изключват възможността една и съща дума да бъде както терм, така и атомарна формула. И наистина, понеже никоя променлива не е нулместен предикатен символ, еднозначният анализ на префиксните изрази над W позволява да твърдим, че ако една дума би била едновременно терм и атомарна формула, то за някое неотрицателно цяло число n съответните множества Fn и Pn биха имали общ елемент. Ние обаче изключихме тази възможност чрез допълнителното предположение б).
За всеки терм 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)) като същото обединение както в точка в) от дефиницията за множество на промeнливите на терм. Благодарение на еднозначното прочитане на атомарните формули току-що дадената дефиниция определя еднозначно множеството VAR(A) за произволна атомарна формула A.
Пример 5. При условията на пример 2 имаме равенството VAR(p(X,a(Y)))={X,Y}, а множеството на променливите на атомарната формула d(a(a(b(b(e))))) е празно.
Като използваме установените преди малко твърдения
във връзка с множество на променливите на терм, веднага можем да заключим,
че множеството на променливите на коя да е атомарна формула е крайно подмножество на множеството X и че една атомарна формула е затворена точно тогава, когато множеството на нейните променливи е празно.
Последно изменение: 18.02.2002 г.