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

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

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

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

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

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

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

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

      Използването на функционалните и предикатните символи на една сигнатура за означаването на дадени функции и предикати се регламентира чрез дефиницията на понятието структура. Ще наричаме така всяка наредена тройка (Σ,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′ да се състои от онези двойки имена от списъка, в които първият член на двойката предхожда втория във списъка.

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

Последно изменение: 2.06.2010 г.