Ще илюстрираме основната идея на логическото програмиране с няколко примера (тези примери ще дадат и известна представа за начина, по който компютрите изпълняват някои прости програми на Пролог).

    Пример 1. Този пример се отнася до търсене на цикли в краен ориентиран граф. Могат да се посочат ред задачи, които водят до такова търсене. Например нека за известен брой събития разполагаме с някаква информация за определени двойки измежду тях кое от двете събития е станало по-рано. Бихме могли да се опитаме въз основа на тази информация да се опитаме да направим заключение за хронологичната подредба на всичките тези събития, взети заедно. Не е изключено обаче наличната информация да съдържа грешки, вследствие на които да не е възможно подреждане, съгласуващо се с нея. Такова положение би било налице тогава, когато за някои събития event₁, event₂, ..., event_n измежду разглежданите при наличната информация се получава такъв цикъл:
        event₁ предхожда event₂,
        event₂ предхожда event₃,
                       .   .   .
        event_n-1 предхожда event_n,
        event_n предхожда event₁.
Тук ще се занимаем с един друг случай, когато също възниква задача за търсене на цикли. Да разгледаме някой от действащите в момента в България закони и да му съпоставим граф с толкова върхове, колкото са членовете на закона, и с ребра-стрелки, изобразяващи препратките от един член към друг. Интересуваме се дали в така получения граф има цикли (ако се окаже, че има, редно е да бъдат анализирани, за да се види дали не се дължат на дефекти на закона). За конкретност нека разглежданият закон да бъде Законът за висшето образование във вида му към началото на 2002 г. Той има над 100 члена (като оставим настрана параграфите от допълнителните, преходните и заключителните разпоредби в края му), но стрелките в съответния граф са по-малко на брой, а именно 42. Да се условим да означаваме чл. 1, чл. 2, чл. 3 и т.н. съответно с a1, a2, a3 и т.н. За да изразим това, че даден член X цитира друг член Y, да приемем да пишем q(X,Y). Лесно е да се съобрази, че когато търсим цикли в споменатия по-горе граф, можем, вместо да работим с всичките 42 препратки, да се ограничим само с препратките към такива членове, които от своя страна цитират други. Оказва се, че препратките от този вид са следните осем:
       q(a26,a50).
        q(a26v,a26).
        q(a46,a78).
        q(a47,a46).
        q(a65a,a64).
        q(a78,a47).
        q(a78,a81).
        q(a79,a47).
Ясно е, че ако в разглеждания граф има цикъл, то сигурно ще е налице и цикъл с брой на последователните препратки, по-голям от 1, но не по-голям от 8. Най-напред се опитваме да намерим цикъл само от две препратки, т.е. да намерим два члена X и Y, такива, че да бъдат изпълнени едновремено условията q(X,Y) и q(Y,X). При терминологията, която се използва при работа с езика Пролог, това се изказва с думите, че се опитваме да удовлетворим целта
        ?- q(X,Y),  q(Y,X).
Тъй като трябва да бъде изпълнено в частност условието q(X,Y), възможните двойки (X,Y) са осемте, които са посочени по-горе - от (a26,a50) до (a79,a47). Лесно се проверява обаче, че за никоя от тях в горния списък от факти не се среща факт q(Y,X). Значи опитът ни да намерим цикъл само от две препратки се оказа неуспешен. Следващата стъпка е да потърсим цикъл от три препратки, т.е. да се опитаме да удовлетворим целта
        ?- q(X,Y), q(Y,Z), q(Z,X).
Отново за двойката (X,Y) имаме споменатите преди малко осем възможности. Започваме да ги разглеждаме последователно. При X=a26, Y=a50 удовлетворяването на поставената цел е равносилно с удовлетворяване на целта
        ?- q(a50,Z), q(Z,a26).
Нейното удовлетворяване обаче е невъзможно, защото в списъка няма факт от вида q(a50,Z). Така първата от осемте възможности отпада. Преминаваме към следващата - X=a26v, Y=a26. В този случай удовлетворяването на поставената цел е равносилно с удовлетворяване на целта
        ?- q(a26,Z), q(Z,a46).
Фактът q(a26,Z) се среща в разглеждания списък само в един случай - при Z=a50. Горната цел обаче не се удовлетворява в този случай, защото в списъка не се среща факт q(a50,a46). Така и втората от осемте възможности отпадна. Да разгледаме третата - X=a46, Y=a78. Тогава нашата задача е равносилна с удовлетворяване на целта
        ?- q(a78,Z), q(Z,a46).
Има две възможности за Z, при които фактът q(a78,Z) се среща в списъка - Z=a47 и Z=a81. При първата от тях q(Z,a46) става q(a47,a46), което е факт от списъка. С това показахме, че е налице цикъл от три препратки: q(a46,a78), q(a78,a47), q(a47,a46). Разбира се направените дотук разсъждения не изключват възможността да има и други цикли от три или повече препратки и тези цикли да не могат да се получат от вече намерения чрез циклична пермутация и/или повторение. По-подробно изследване на възможностите позволява да се види, че такива други цикли няма.

    Забележка 1. Ние решихме задачата, която си бяхме поставили, чрез нейното разделяне на две по-лесни. А именно, най-напред измежду всичките 42 препратки от един член към друг подбрахме подходяща част, която се оказа съставена от 8 препратки, и след това фактически потърсихме цикъл в значително по-малкия граф, на който върхове са членовете, срещащи се в тази част от препратките (това търсене би могло да се направи и чрез нагледно изобразяване на споменатия по-малък граф). В случай че използуваме компютър, такова разделяне на задачата обаче едва ли би донесло някаква съществена изгода, особено ако си послужим с някои допълнителни средства на езика Пролог извън илюстрираните чрез горното разглеждане на примера (вж. например приложения текстов файл с програма на Пролог и цел към нея - изпълнението на програмата върху целта решава задачата без нейното разделяне на по-прости; от използваните в програмата допълнителни средства особено заслужава да се отбележи отношението \= , което при изпълнението на тази програма играе ролята на различие между върхове на графа).

    Забележка 2. Намереният цикъл показва, че в разглеждания закон чл. 46 цитира чл. 78, който от своя страна цитира чл. 47, а той пък цитира чл. 46. За щастие този цикъл не се дължи на дефекти на закона - при по-подробното разглеждане на споменатите членове се вижда, че цитирането на чл. 78 от чл. 46 става в една алинея на последния, а пък чл. 47 цитира други алинеи, които при това не я цитират (тъй да се каже, кръгът фактически не се затваря).

    Пример 2. Ще разгледаме отношението между двама души X и Y, което се изразява с думите, че X е потомък на Y. Дефиницията на това отношение всъщност е индуктивна - един човек е потомък на своите родители и на хората, чийто потомък е някой от родителите му. Да се условим да пишем d(X,Y), за да изразим това, че X е потомък на Y. Нека p(Y,X) пък да означава, че Y е родител на X. Тогава за всеки двама души X и Y е вярно, че от p(Y,X) следва d(X,Y), а за всеки трима души X, Y и Z е вярно, че от p(Y,X) и d(Y,Z) следва d(X,Z). Ще запишем тези отношения на следване по приетия в езика Пролог начин - за да изразим, че дадено твърдение Тв₀ следва от други дадени твърдения Тв₁, Тв₂, ..., Тв_m, пишем
        Тв₀ :- Тв₁, Тв₂, ..., Тв_m.
Прието е отношения на следване, записани по такъв начин, да се наричат правила. В конкретния случай получаваме правилата
        d(X,Y) :- p(Y,X).
        d(X,Z) :- p(Y,X), d(Y,Z).
Да предположим сега, че за някои конкретни седем души, които да назовем за краткост c1, c2, c3, c4, c5, c6, c7, разполагаме със следната информация:
        p(c1,c3).
        p(c2,c5).
        p(c3,c5).
        p(c4,c6).
        p(c5,c7).
Нека пред нас стои въпросът дали от тази информация и от преди това записаните правила може да се заключи, че c7 е потомък на c1. Един бегъл поглед върху наличната информация позволява бързо да забележим, че отговорът на поставения въпрос е положителен (особено очевидно става това, ако изобразим информацията графично). Ние обаче ще опишем друг начин за установяване на същото, който в случая изглежда неоправдано тромав, но има например такива предимства: а) няма проблеми той да се използва при много по-голям обем на наличната информация; б) работейки по този начин, ще можем да намираме отговор на въпрос от подобен вид и в случаите, когато този отговор е отрицателен. Започваме с това, че записваме поставения въпрос като целта
        ?- d(c7,c1).
Понеже твърдението d(c7,c1) не фигурира в явен вид в наличната информация, единствената възможност да се заключи въз основа на нея, че това твърдение е вярно - това е да се използва някое от записаните две правила заедно със заключение за вярност на твърдението или твърденията в това правило вдясно от знака  :-  . Опитваме най-напред да се възползваме от първото правило. По този начин ние заменяме поставената цел с целта
        ?- p(c1,c7).
Ако от наличните сведения може да се заключи, че твърдението p(c1,c7) е вярно, това би ни дало положителен отговор и на първоначално поставения въпрос. Лесно се вижда обаче, че такова заключение не е възможно - въпросното твърдение нито се среща в явен вид в наличната информация, нито би могло да се получи с използване на някое от двете правила (в ляво от знака  :-  в тях стоят твърдения, започващи с d, а не с p). При това положение единствената възможност, която остава, е да се възползваме евентуално от второто правило. Опитът да направим това заменя първоначалната цел със следната, за която се питаме дали се удовлетворява при някой избор на Y:
        ?- p(Y,c7), d(Y,c1).
Разбира се удовлетворяване на условието p(Y,c7) в тази цел е възможно само чрез такива Y, за които съответното твърдение p(Y,c7) фигурира в явен вид в наличната информация. Има един единствен такъв Y, а именно Y=c5. При това положение първоначалната ни цел се заменя с целта
        ?- d(c5,c1).
Единият опит за получаване на заключение d(c5,c1) ни води до целта
        ?- p(c1,c5).
Този опит обаче пропада, защото твърдението p(c1,c5) не се среща в явен вид в наличната информация. Другият опит заменя достигнатата цел със следната, за която се питаме дали се удовлетворява за някой Y1:
        ?- p(Y1,c5), d(Y1,c1).
Има два възможни Y1, за които съответното твърдение p(Y1,c5) се среща в наличната информация - Y1=c2 и Y1=c3. При Y1=c2 удовлетворяването на горната цел е равносилно с удовлетворяване на целта
        ?- d(c2,c1).
За нея обаче и двата допустими опита за удовлетворяване пропадат. Първият от тях я заменя с целта
        ?- p(c1,c2).
Вторият пък прави удовлетворяването й равносилно с намиране на Y2, който да удовлетворява целта
        ?- p(Y2,c2), d(Y2,c1).
Сред фактите от наличната информация обаче не фигурира никакво твърдение с c2 като втори аргумент. И така, остана единствената възможност - да опитаме с Y1=c3. Тогава въпросът се свежда до удовлетворяване на целта
        ?- d(c3,c1).
Първият от двата възможни пътя за нейното удовлетворяване я заменя с целта
        ?- p(c1,c3).
Тъй като твърдението p(c1,c3) се среща в наличната информация, ясно е, че тази цел се удовлетворява и значи наистина отговорът на първоначалния въпрос е положителен.

    Пример 2'. Нека изменим пример 2 като вместо въпроса дали c7 е потомък на c1 поставим въпроса дали c7 е потомък на c4. Почти всичко, което направихме преди малко, остава в сила при замяна на c1 с c4. Различие се появява едва към края, когато стигаме до цел
        ?- d(c3,c4).
Първият от двата възможни опита за нейното удовлетворяване води до целта
        ?- p(c4,c3).
Другият опит ни довежда до задачата да удовлетворим чрез подходящ Y3 целта
        ?- p(Y3,c3), d(Y3,c4).
И двата опита пропадат, защото сред фактите от наличната информация няма нито един с втори аргумент c3. Това показва, че от тази информация и двете правила, с които разполагаме, не може да се заключи, че c7 е потомък на c4.

    Забележка 3. Ако към наличната информация в пример 2 се добави нова, това разбира се в никакъв случай не може да попречи на заключението, че c7 е потомък на c1. Това, което направихме в пример 2', може обаче да се промени и така разширената информация да позволи да се заключи, че c7 е потомък и на c4. Така би станало например, ако се добави факт p(c4,p7), p(c6,c7) или p(c4,c3). Същото би се случило и ако да речем са налице още един човек c8 и сведения p(c6,c8) и p(c8,c7) за него.

    Пример 3. Нека обектите, с които се занимаваме, да бъдат думите над една азбука, състояща се от буквите a, b и s. В множеството на тези думи да дефинираме функции на един аргумент a, b и s, както следва:

    В следващите лекции предстои да поставим на по-ясна и сигурна основа нещата, които извършвахме в горните примери. Ще разгледаме и ред други въпроси, без разбира се да имаме възможността да изчерпим изключително обширната тематика, отнасяща се до логическото програмиране и езика Пролог. За онези, които биха искали самостоятелно да разширят своите знания в тази насока, посочваме следния източник в Интернет, който съдържа многобройни препратки към други източници на информация по споменатата тематика (повечето от тях също в Интернет):

The WWW Virtual Library: Logic Programming - http://archive.comlab.ox.ac.uk/logic-prog.html

Ще отбележим още, че в студентската читалня на библиотеката на ФМИ могат да бъдат намерени следните книги на български език, имащи близка връзка с тематиката:

Д. Дочев, Х. Дичев, З. Марков, Г. Агре. Програмиране на Пролог. София, 1989.

Л. Стойчев, А. Антонов, И. Филипов. Програмни езици за изкуствен интелект. София, 1995.

М. Тодорова. Езици за функционално и логическо програмиране. II част. Логическо програмиране. София, 1995.

И. Сосков, А. Дичев. Теория на програмите. София, 1996.

Сред книгите на други езици могат да бъдат много полезни например следните:

У. Клоксин, К. Меллиш. Программирование на языке Пролог, "Мир", 1987 (превод на W. Clocksin, C. Mellish. Programming in Prolog, Springer-Verlag, 1981).

Ч. Чень, Р. Ли. Математическая логика и автоматическое доказательство тео-рем, "Наука", 1983 (превод на C.-L. Chang, R. C.-T. Lee. Symbolic Logic and Mechanical Theorem Proving, Academic Press, 1973).

K. R. Apt. Introduction to Logic Programming. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B: Formal Models and Semantics, pages 495-574. Elsevier and The MIT Press, 1990.

U. Nilsson, J. Maluszynski. Logic, Programming and Prolog, 2nd edition, John Wiley & Sons, Ltd., 1995.

L. Sterling, E. Shapiro. The Art of Prolog, The MIT Press, 1989.

Някои упражнения върху Пролог, подготвени от ас. Весела Балева, могат да се намерят на адрес

        http://www.fmi.uni-sofia.bg/fmi/logic/vbaleva/Exercises.htm

В определена насока може да се окаже полезен и следният текст в Интернет, който обаче не е насочен директно към логическото програмиране:

        Д. Скордев. Записки по математическа логика - http://www.fmi.uni-sofia.bg/fmi/logic/skordev/ln/ml/

    Изложението в настоящия курс в по-голямата си част няма да е обвързано с някоя конкретна софтуерна реализация на езика Пролог и ще е посветено на по-общи въпроси. Там, където обаче е уместна по-голяма конкретност в това отношение, ще се съобразяваме с реализацията Strawberry Prolog, разработена от Димитър Димитров Добрев и негови сътрудници (тя се използва и в практикума към курса). В частност примерите за програми на Пролог, които понякога ще даваме, ще бъдат съобразени с нея. Ако разполагате с компютър и желаете да се упражнявате самостоятелно в програмиране на Пролог, добре ще е да вземете текущата версия на Strawberry Prolog от адреса http://www.dobrev.com и да я инсталирате на въпросния компютър, стига операционната му система да позволява  работа с тази  версия (ако случаят не е такъв, например ако компютърът е под Windows 3.11 или 3.1, можете да потърсите подходяща друга реализация, като си послужите с информация от първия от цитираните по-горе Интернет-източници).
 

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

Next  Contents