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

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

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

      Забележка 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 (ще ги наричаме съответно интерпретация на φ в S и интерпретация на π в S).

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

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

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

      Пример 5. Нека Σ е сигнатурата с константа the_oldest, едноместни функционален еимвол the_next_after, едноместни предикатни символи is_male, is_female и двуместен предикатен символ is_parent_of. Естествено е да разглеждаме структури с тази сигнатура, получени по следния начин. Вземаме някакъв списък от имена на хора, подредени по датата на раждането. В качеството на носител на структурата вземаме множеството, състоящо се от тези имена и от празната дума ε. Като интерпретация на константата the_oldest вземаме първото име от списъка. Функционалния символ the_next_after интерпретираме чрез функцията, която на всяко име от списъка без последното съпоставя следващото в списъка, а на последното и на празната дума съпоставя празната дума, Предикатните символи is_male и is_female интерпретираме чрез предикатите, на които множествата на истинност се състоят съответно от имената на мъже в списъка и от имената на жени в списъка. Като интерпретация на предикатния символ is_parent_of вземаме предиката с множество на истинност, състоящо се от онези наредени двойки от имена от списъка, за които човекът, именован чрез първия член на двойката, е родител на човека, именован чрез втория. Да приемем за конкретност, че гореспоменатият списък се състои от малките имена на всички членове на семейството, в което се е родил поетът Иван Вазов. В такъв случай списъкът е следният:

      Пример 6. Със сигнатурата от предходния пример (както изобщо с всяка сигнатура) има безбройно много различни структури. Ето една от тях, която е с безкраен носител. Неин носител е множеството на естествените числа 0, 1, 2, 3, …, интерпретация на константата the_oldest е числото 0, функционалният символ the_next_after се интерпретира чрез функцията, която на всяко естествено число k съпоставя числото k+1, интерпретациите на предикатните символи is_male и is_female имат за множества на истинност съответно множеството на четните естествени числа и множеството на нечетните естествени числа, а предикатът, интерпретиращ is_parent_of, има стойност 1 точно за онези наредени двойки естествени числа, в които първият член е 0 или 1, а вторият е по-голям от 1.

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

      Когато S и S′ са две структури, ще казваме, че S′ е обогатяване на S  (или че S е обедняване на S′), ако сигнатурата на S′ съдържа сигнатурата на S, носителите на S и S′ съвпадат, а интерпретиращото съответствие на S′ е продължение на интерпретиращото съответствие на S.

      Пример 7. Нека S е структура от вида, разгледан в пример 5. Да означим със Σ′ сигнатурата, получена от Σ чрез добавяне на константа the_youngest, едноместен функционален символ the_previous_before и двуместен предикатен символ is_born_before. Едно интуитивно приемливо обогатяване на S е структурата S′ със сигнатура Σ′, със същия носител както на S и с интерпретиращо съответствие, получаващо се от интерпретиращото съответствие на S чрез додефинирането му за добавените функционални символи и предикатен символ по такъв начин, че the_youngest^S′ да е последният член на списъка, функцията the_previous_before^S′ да съпоставя на всяко име от списъка без първото неговото предхождащо в списъка, а на първото и на празната дума да съпоставя празната дума, множеството на истинност на предиката is_born_before^S′ да се състои от онези двойки имена от списъка, в които първият член на двойката предхожда втория във списъка.

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

Previous  Next  Contents

Дата на една по-стара версия:	12.08.2004
Дата на настоящата версия:	28.02.2005
(поправена печатна грешка:	22.02.2008)