Лекции по логическо програмиране

Функции и предикати

нека M е множество; ако n е цяло число, n > 0, под Mⁿ ще разбираме n-тата декартова степен на M, т.е. множеството от всички наредени n-торки с елементи от M; ще считаме, че M¹ = M;

при n = 0, под 0-местна функция ще разбираме фиксиран елемент на M; 0-местните функции още наричаме константи;

при n = 0, под 0-местен предикат разбираме числото 0 или 1;

под множество на истинност на даден предикат разбираме всички наредени n-торки, върху които предикатът има стойност 1;
за определеност, азбуката която разглеждаме е азбуката от езика PROLOG - всички малки и големи латински букви, десетичните цифри, подчертаване - _, кръглите скоби - (, ),

запетая - ,, двоеточие - :, точка и запетая - ;; единствен ляв ограничител е лявата скоба, единствен десен ограничител е дясната скоба, разделители са запетаята, двоеточието и точката със запетая;

• 
  множеството  от всички променливи; под променлива разбираме дума, започваща с главна латинска буква или с подчертаване и състояща се само от латински букви (малки и главни), цифри и подчертаване; изключваме думата _ и думите, които започват с G_ (поради спецификата на PROLOG); ясно е, че  е изброимо безкрайно множество;
  
• 
  множество от логически знаци – думата not, празната дума, думата true (знак за истинност), думата fail (знак за неистинност), думата for_all (квантор за общност), думата for_some (квантор за съществуване);
  
• 
  ще предполагаме, че за всяко цяло n  0 е избрано множество от думи _n на n-местните функционални символи и множество от думи _n на n-местните предикатни символи; за всяко n  0 думите във _n и _n започват с малка латинска буква и се състоят от латински букви (малки и големи), цифри и подчертаване;
  

поставяме следните изисквания _n  _n = , ₀  , _i  = ,

_i  = ; ясно е, че думите от редиците в сигнатурата и променливите не могат да съвпадат;
в езика PROLOG е поставено още едно изискване – функционалните и предикатните символи да не са резервирани думи на езика; от логическите знаци празната дума и думите за кванторите не са от езика на PROLOG;

Структури на сигнатури

нека е дадена сигнатура, и M е множество;

за всяко n  0:

под интерпретация на думите от _n в M разбираме съответствие, което съпоставя n-местна функция в M на всяка дума от _n;

под интерпретация на думите от _n в M разбираме съответствие, което съпоставя n-местен предикат на всяка

дума от _n;

под интерпретация на дадена сигнатура, в M разбираме редиците , , където за n = 0, 1, …_n е интепретация на _n в M и _n е интерпретация на _n в M;

под структура на дадена сигнатура разбираме двойка от множество M, което се нарича носител на сигнатурата и интерпретация на сигнатурата в M;

лесно може да се покаже, че във всяка структура M е непразно множество – достатъчно е да се използва, че ₀  ;
нека S е структура, M е нейният носител и ₀, ₁, …; ₀, ₁, …; са съответните интерпретации на функционалните и предикатните символи в M;

ако f  Ф_n, то често вместо _n (f) пишем f ^S;

ако p  П_n, то често вместо _n (p) пишем p^S;

въведеното означение не е съвсем точно – например една дума може да е едновременно функционален и предикатен символ (на различен брой аргументи); затова понякога е удобно да се въведе допълнително ограничение - всяка дума от  да попада най-много в едно от множествата Ф_n и П_n, n = 0, 1, …, но ние засега няма да въвеждаме такова ограничение – ще считаме, че интерпретацията се подразбира от контекста;

определяме сигнатура ₀ = { ivan, mincho, syba}, ₁ = { next, prev}, ₂ = , ₃ = , …;

₀ = , ₁ = { male, female}, ₂ = { parent, distinct}, ₃ = ,

₄ = , …;

след това определяме интерпретациите на функционалните и предикатните символи в M:

₀ (ivan) = Иван Вазов,

₀ (mincho) = Минчо Вазов,

₀ (syba) = Съба Вазова,

₁ (next) (A) = A, ако A е Минчо Вазов, Съба Вазова или Иван Вазов (най-голямото дете); иначе, ₁ (next) (A) = B, където B е следващото по големина дете след А;

₁ (prev) (A) = A, ако A е Минчо Вазов, Съба Вазова или

най-малкото дете; иначе, ₁ (prev) (A) = B, където B е предното по големина дете преди А;

₁ (male) (A) = 1  A e мъж, A  M,

₁ (female) (A) = 1  A e жена, A  M,

₂ (parent) (A, B) = 1  A е родител на B, A, B  M,

₂ (distinct) (A, B) = 1  A не е B, A, B  M;

няма нужда да се дефинират останалите интерпретации, тъй като те имат празни дефиниционни области;

с това определихме структура S с носител M – семейството на Иван Вазов;