Previous  Next  Contents
 

СИГНАТУРИ И СТРУКТУРИ

      Често срещан случай в математиката и в информатиката е да се разглежда някое дадено множество с някои дадени функции и предикати в него (вместо предикатите биха могли да са дадени съответните множества на истинност). За да може да се работи в такава ситуация, обикновено се използват някакви означения за дадените функции и предикати. Понятието сигнатура, което сега ще въведем, е предназначено да отрази някои черти на такива означения, но по начин, който е съобразен със синтаксиса на езика Пролог. Съобразяването ще се изразява в избора на думите, които ще бъдат допустими като означения  -  те ще бъдат думи над стандартната основна азбука, започващи с малки латински букви (да припомним, че споменатата азбука се състои от малките и главните латински букви, знака _ и десетте цифри).

      Приемаме да наричаме сигнатура всяка наредена тройка (Φ,Π,ρ), която удовлетворява следните условия:
          а) Φ и Π са непресичащи се множества от думи над стандартната основна азбука, всяка от които започва с малка латинска буква и е различна от думите not, true и fail;
          б) ρ е изображение на обединението на множествата Φ и Π в множеството на неотрицателните цели числа;
          в) съществуват безбройно много думи над стандартната основна азбука, които започват с малка латинска буква, но не принадлежат на никое от множествата Φ и Π.

      Когато е дадена една сигнатура (Φ,Π,ρ), думите от множествата Φ и Π ще наричаме съответно функционални символи и предикатни символи на тази сигнатура, а изображението ρ ще наричаме неин указател за брой на аргументите. Числото, съответстващо чрез ρ на даден функционален или предикатен символ на сигнатурата, ще наричаме брой на аргументите на този символ в дадената сигнатура. Функционалните и предикатните символи с брой на аргументите n ще наричаме съответно n-местни функционални символи и n-местни предикатни символи на дадената сигнатура. Нулместните функционални символи на една сигнатура ще наричаме нейни константи.

      Пример 1. Имайки пред вид пример 3 от встъпителните бележки, уместно е да разгледаме сигнатурата (Φ,Π,ρ), където

Φ = {e,a,b,s},  Π = {d,p},  ρ(e) = 0,
ρ(a) = ρ(b) = ρ(s) = ρ(d) = 1,  ρ(p) = 2.

      Пример 2. В приложенията на логическото програмиране често пъти за функционални и предикатни символи се избират не еднобуквени думи както в горния пример, а по-дълги думи, които насочват към някакво тълкуване на въпросните функционални и предикатни символи. Във връзка с пример 4 от встъпителните бележки е уместно да разгледаме да речем сигнатура (Φ,Π,ρ), където
Φ = {a,b,singleton,union},  Π = {belongs},
ρ(a) = ρ(b) = 0,  ρ(singleton) = 1,  ρ(union) = ρ(belongs) = 2.

      Забележка 1. В т. а) от дефиницията за сигнатура поискахме думите от множествата Φ и Π да бъдат различни от трите думи not, true и fail. Поставихме това изискване, за да можем по-нататък безпроблемно да използваме въпросните три думи за друга цел, а именно като логически символи.

      Забележка 2. Изискването от т. в) на дефиницията за сигнатура очевидно е изпълнено в случаите, когато множествата Φ и Π са крайни. Всъщност най-често ще имаме работа именно със сигнатури, чиито функционални и предикатни символи са крайно много, но все пак има някои теоретични въпроси, за които ограничаването само с такива сигнатури би създало затруднения. Ролята на изискването от т. в) е да гарантира наличието на един безкраен резерв за евентуално разширяване на сигнатурата чрез добавяне на нови функционални или предикатни символи.

      Забележка 3. Ако искаме да използваме една сигнатура в рамките на дадена софтуерна реализация на езика Пролог и това да не води до проблеми, трябва да се погрижим още сред функционалните и предикатните символи на сигнатурата да не се срещат думи, резервирани за вградени предикати на реализацията (когато това условие е изпълнено, ще казваме, че сигнатурата е съгласувана с дадената реализация). Списъкът на въпросните резервирани думи зависи от конкретната реализация и може да бъде намерен в нейната документация. Думите not, true и fail, споменати в т. а) на дефиницията, обикновено влизат в този списък, но освен тях влизат и много такива, за които нашата дефиниция не забранява да бъдат функционални или предикатни символи (например във версия 1.6 на Strawberry Prolog Light има 162 такива други думи).

      Забележка 4. Много от реализациите на Пролог (вкл. Strawberry Prolog) позволяват една и съща дума да се използва в дадена програма и като функционален, и като предикатен символ, а също броят на аргументите, с които тя се използва на различни места в програмата, може да бъде различен (всъщност често даже не се прави разлика между функционални и предикатни символи). С цената на някои технически усложнения бихме могли да отразим тези възможности и в дефиницията за сигнатура, но усложненията не биха били особено оправдани, понеже използването на въпросните възможности при програмирането на Пролог едва ли може да увеличи съществено приложимостта.

      Когато Σ и Σ′ са две сигнатури, ще казваме, че  Σ′ съдържа  Σ  (или че  Σ се съдържа в  Σ′),  ако всеки функционален и всеки предикатен символ на Σ е съответно функционален или предикатен символ на Σ′ със същия брой аргументи (при  Σ=(Φ,Π,ρ)  и  Σ′=(Φ′,Π′,ρ′)  това е равносилно с изискването да имаме съотношенията Φ′⊇Φ и Π′⊇Π, а изображението ρ′ да е продължение на изображението ρ). Благодарение на т. в) от дефиницията за сигнатура, всяка сигнатура се съдържа в безбройно много други. Очевидно отношението между сигнатури, което дефинирахме, е една частична наредба (т.е всяка сигнатура съдържа себе си, две сигнатури, всяка от които съдържа другата, съвпадат и винаги, когато една сигнатура съдържа друга, а тя съдържа трета, първата съдържа третата). При тази чзстична наредба съществува най-малка измежду всички възможни сигнатури (т.е. такава, която се съдържа във всяка сигнатура)  -  това е сигнатурата с празни множества на функционалните и на предикатните символи и с никъде недефиниран указател за брой на аргументите.

      Използването на функционалните и предикатните символи на една сигнатура за означаването на дадени функции и предикати се регламентира чрез дефиницията на понятието структура. Ще наричаме така всяка наредена тройка (Σ,D,I), състояща се от сигнатура Σ, непразно множество D и изображение I със следните свойства:
          а) дефиниционна област на I е множеството на всички функционални символи и всички предикатни символи на Σ;
          б) всеки път, когато φ е n-местен функционален символ на Σ, съответното I(φ) е n-местна функция в D;
          в) всеки път, когато π е n-местен предикатен символ на Σ, съответното I(π) е n-местен предикат в D.

      Трите компоненти Σ, D и I на една структура (Σ,D,I) ще наричаме съответно сигнатура, носител (или универсум) и интерпретиращо съответствие на тази структура. Функционалните и предикатните символи на сигнатурата на една структура ще наричаме още функционални и предикатни символи на структурата; по аналогичен начин ще говорим и за n-местни функционални и предикатни символи на тази структура. Интерпретиращото съответствие на една структура ще наричаме още интерпретация на нейните функционални и предикатни символи. Ако S е една структура с интерпретиращо съответствие I, то за всеки функционален символ φ на S съответната функция I(φ) ще означаваме още с φS и за всеки предикатен символ π на S съответния предикат I(π) ще означаваме още с πS.

      Пример 3. Нека Σ е сигнатурата, която посочихме в пример 1 по-горе. Ще дефинираме структура (Σ,D,I), съответстваща на разглежданията от пример 3 от встъпителните бележки. За тази цел вземаме в качеството на D множеството на всички думи над азбуката, състояща се от буквите a, b и s, и полагаме

I(e) = e,   I(a) = a,   I1(b) = b,   I(s) = s,
където, както в споменатия пример от встъпителните бележки, e, a, b, s означават съответно празната дума и едноместните функции в D, дефинирани за всяка дума X от D чрез равенствата a(X) = aX,  b(X) = bX,  s(X) = sX. Полагаме още I(d) и I(p) да бъдат съответно едноместният и двуместният предикат, представящи свойството d и отношението p от същия пример в смисъл, че множеството на истинност на I(d) се състои точно от онези думи от D, които имат свойството d, a на множеството на истинност на I(p) принадлежат точно онези двойки от думи от D, които удовлетворяват условието p.

      Пример 4. Нека Σ е сигнатурата от пример 2 по-горе. Като имаме пред вид пример 4 от встъпителните бележки, да разгледаме някое непразно множество D от множества, което притежава следните две свойства:
          а) за всяко множество X, принадлежащо на D, единичното множество {X} също принадлежи на D;
          б) обединението на две множества, принадлежащи на D, винаги принадлежи на D.
При това положение можем да разгледаме такава структура със сигнатура Σ и с носител D, че функционалните символи singleton и union и предикатният символ belongs да се интерпретират съответно с едноместната функция в D, съпоставяща на всяко X от D съответното единично множество {X}, с двуместната функция в D, съпоставяща на всяка двойка от множества, принадлежащи на D, тяхното обединение, и с двуместния предикат в D, чието множество на истинност се състои от наредените двойки (X,Y) от D2, удовлетворяващи условието X да бъде елемент на Y (дори и след като сме избрали множеството D, такива структури може да има много, защото в току-що казаното не сме фиксирали с кои точно елементи на D да се интерпретират константите a и b).

      Забележка 5. На пръв поглед изглежда естествено в горния пример да вземем в качеството на D множеството на всички възможни множества и по този начин да осигурим наличието на свойствата а) и б). За съжаление обаче теорията на множествата не допуска разглеждането на такова множество (ако се приеме, че такова множество съществува, теорията става противоречива). Непразни множества D от множества със споменатите две свойства все пак съществуват - такова множество D може да се построи например по следния начин: вземаме произволно непразно множество от множества D0 и добавяме към него всички други множества, които могат да се получат от множества, принадлежащи на D0, чрез някакъв брой образувания на единично множество и на обединение на две множества.

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

      Когато S и S′ са две структури, ще казваме, че S′ е обогатяване на S  (или че S е обедняване на S′), ако сигнатурата на S′ съдържа сигнатурата на S, носителите на S и S′ съвпадат, а интерпретиращото съответствие на S′ е продължение на интерпретиращото съответствие на S. Ясно е, че така дефинираното отношение между структури е една частична наредба. При тази частична наредба съществува най-малка измежду структурите с даден носител  -  това е онази от тях, която няма никакви функционални и никакви предикатни символи.
 

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