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



страница2/22
Дата01.06.2017
Размер2.18 Mb.
1   2   3   4   5   6   7   8   9   ...   22

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

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


при n > 0, n-местна функция в M наричаме тотално изображение на Mn в M;

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


при n > 0, n-местен предикат в M наричаме тотално изображение на Mn в { 0, 1};

при 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 започват с малка латинска буква и се състоят от латински букви (малки и големи), цифри и подчертаване;

двойката редици , наричаме сигнатура;

поставяме следните изисквания nn = , 0  , 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 е непразно множество – достатъчно е да се използва, че 0  ;
нека S е структура, M е нейният носител и 0, 1, …; 0, 1, …; са съответните интерпретации на функционалните и предикатните символи в M;

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

ако p  Пn, то често вместо n (p) пишем pS;

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


пример: нека M е множеството от всички хора в семейството на Иван Вазов – самият Иван Вазов, бащата Минчо Вазов, майката Съба Вазова и другите им девет деца;

определяме сигнатура 0 = { ivan, mincho, syba}, 1 = { next, prev}, 2 = , 3 = , …;

0 = , 1 = { male, female}, 2 = { parent, distinct}, 3 = ,

4 = , …;

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

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

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

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

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

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

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

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

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

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

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

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

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

1   2   3   4   5   6   7   8   9   ...   22


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница