Next  Contents
 

 

ВСТЪПИТЕЛНИ БЕЛЕЖКИ

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

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

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

      Пример 1. Този пример се отнася до търсене на цикли в краен ориентиран граф. Могат да се посочат ред задачи, които водят до такова търсене. Например нека за известен брой събития разполагаме с някаква информация за определени двойки измежду тях кое от двете събития е станало по-рано. Бихме могли да се опитаме въз основа на тази информация да се опитаме да направим заключение за хронологичната подредба на всичките тези събития, взети заедно. Не е изключено обаче наличната информация да съдържа грешки, вследствие на които да не е възможно подреждане, съгласуващо се с нея. Такова положение би било налице тогава, когато за някои събития event1, event2, …, eventn измежду разглежданите при наличната информация се получава такъв цикъл:

event1 предхожда event2,
event2 предхожда event3,
                .   .   .
eventn-1 предхожда eventn,
eventn предхожда event1.
Тук ще се занимаем с един друг случай, когато също възниква задача за търсене на цикли. Да разгледаме някой от действащите в момента в България закони и да му съпоставим граф с толкова върхове, колкото са членовете на закона, и с ребра-стрелки, изобразяващи препратките от един член към друг. Интересуваме се дали в така получения граф има цикли (ако се окаже, че има, редно е да бъдат анализирани, за да се види дали не се дължат на дефекти на закона). За конкретност нека разглежданият закон да бъде Законът за висшето образование във вида му към началото на 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). Изискването да бъдат изпълнени едновременно няколко условия е пак едно условие. При означенията, които се използват в езика Пролог и с които ще си служим и ние, такова съставно условие се записва чрез последователното написване на отделните условия, разделени със запетаи. И така, можем да кажем, че се опитваме с подходящ избор на членове 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). Ще запишем тези съотношения на следване по приетия в езика Пролог начин - за да изразим, че дадено твърдение statement0 следва от други дадени твърдения statement1, statement2, …, statementm, пишем

statement0 :- statement1, statement2, …, statementm.
Прието е съотношения на следване, записани по такъв начин, да се наричат правила. В конкретния случай получаваме правилата
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). При това положение единствената възможност, която остава, е да се възползваме евентуално от второто правило. Опитът да направим това заменя първоначалното запитване със следното:
?- p(Y,c7), d(Y,c1).
С други думи, пита се дали при някой избор на 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).
Този опит обаче пропада, защото то не се среща в явен вид в наличната информация. Другият опит заменя достигнатото твърдение със следното условие, за което се питаме дали се изпълнява за някой 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).
Тъй като то се среща в наличната информация, ясно е, че отговорът на първоначалния въпрос е положителен.

      Пример 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) за него.

      Пример 2". Да разгледаме и такова изменение на пример 2, при което въпросът е на кои хора е потомък c7. Ще отговорим на този въпрос, като потърсим всички начини да се изпълни условието

d(c7,U)
Тези начини са два вида. Начините от единия вид са чрез изпълняване на условието
p(U,c7)
Веднага се вижда, че наличната информация предоставя точно един такъв начин - в качеството на U да се вземе c5. Начините от втория вид са чрез изпълняване на условието
p(Y,c7),d(Y,U).
Тъй като наличната информация позволява да изпълним подусловието p(Y,c7) само чрез полагането Y=c5, фактически работата сега се свежда до намиране на начините за изпълняване на условието
d(c5,U).
И за това условие има два вида начини за изпълняването му. Едната възможност е чрез изпълняване на условието
p(U,c5).
Това условие може да се изпълни по два начина - чрез полагането U=c2 или чрез полагането U=c3. Другата възможност е чрез изпълняване на условпето
p(V,c5),d(V,U).
Тя се свежда до изпълняване на някое от следните две условия:
d(c2,U).
d(c3,U) .
Работейки по аналогичен начин, лесно се убеждаваме, че наличната информация не дава начин за изпълняване на първото от тях, а за второто тя дава точно един начин - чрез полагането U=c1. И така, наличната информация позволява на поставения въпрос да се дадат отговорите c5, c2, c3 и c1.

      Забележка 4. Струва си да бъде разгледано и изменение на пример 2, при което се търси кои са потомците да речем на c1. Въпросът се свежда до търсене на начините за изпълняване на условието

d(U,c1).
В този случай опитът да се работи аналогично на по-горе изисква малко повече труд. Например едната от възможностите за изпълняване на това условие е чрез изпълняване на условието
p(Y,U),d(Y,c1).
Първото подусловие на това условие обаче може да бъде изпълнено по 5 различни начина и ще трябва всяка от тези 5 възможности да бъде разгледана поотделно.

    Пример 3. Нека D е множеството на всички думи над една азбука, състояща се от буквите a, b и s. Да дефинираме три изображения a, b и s на множеството D в себе си, както следва:
a(X) = aX,   b(X) = bX,   s(X) = sX.
Да означим още празната дума с e. Всяка от думите, които разглеждаме, може да бъде получена и то по единствен начин от празната дума чрез известен брой прилагания на горните три изображения. Например имаме
bsaa = b(s(a(a(e)))).
Да разгледаме формална граматика Г с терминални символи a и b, с единствен нетерминален символ s, който е и неин начален символ, и с правила s→asb, s→ab. За всеки две думи X и Y нека p(X,Y) изразява твърдението, че X се преобразува в Y чрез еднократно прилагане на някое от правилата на Г. За произволна дума Y нека d(Y) изразява твърдението, че Y е изводима в Г (т.е. Y може да се получи от s чрез някакъв брой прилагания на споменатите правила). Тогава са в сила твърденията и съотношенията на следване, които при означенията на езика Пролог могат да се запишат по следния начин:
p(s(X),a(s(b(X)))).
p(s(X),a(b(X))).
p(a(X),a(Y)) :- p(X,Y).
p(b(X),b(Y)) :- p(X,Y).
p(s(X),s(Y)) :- p(X,Y).
d(s(e)).
d(Y) :- p(X,Y), d(X).
Ето как например с помощта на горните сведения може да се изследва дали е изводима в Г думата aabb. Въпроса представяме чрез запитването
?- d(a(a(b(b(e))))).
Единственият начин условието в това запитване да бъде изпълнено въз основа на споменатите сведения е да се изпълни чрез подходящ избор на дума X условието
p(X,a(a(b(b(e))))), d(X).
Единствената възможност за това пък е да имаме X=a(X1) за някоя дума X1, изпълняваща условието
p(X1,a(b(b(e)))), d(a(X1)).
За това има две възможности. Едната е да имаме X1=s(b(e)) и да бъде вярно твърдението
d(a(s(b(e)))).
Другата възможност е да имаме X1=а(X2) за някоя дума X2, изпълняваща условието
p(X2,b(b(e))), d(a(a(X2))).
Да проучим най-напред първата възможност. Единственият начин тя да се осъществи е за някоя дума X2 да се изпълнява условието
p(X2,a(s(b(e)))), d(X2).
И за това има две възможности. Едната е да имаме X2=s(e) и да бъде вярно твърдението
d(s(e)).
Другата е да имаме X2=a(X3) за някоя дума X3, изпълняваща условието
p(X3,s(b(e))), d(a(X3)).
Тъй като твърдението, споменато при първата от тези две възможности, е един от фактите, с които разполагаме, става ясно, че отговорът на първоначалното запитване е положителен и значи думата aabb е изводима в граматиката Г. При това положение няма защо да се занимаваме с втората от двете възможности. Разбира се няма нужда да се занимаваме и с втората от двете възможности, споменати преди това. Да отбележим обаче, че би ни се наложило да разгледаме изчерпателно всички възможности, ако вместо с думата aabb бяхме се занимали с някоя дума, неизводима в Г.

      Пример 4. В теорията на множествата за всеки неин обект X е дефинирано множество {X} (единично множество за X), на което X е единственият елемент. Освен това за всеки две множества A и B е дефинирано множество A ∪ B (обединение на A и B), на което елементи са елементите на A и елементите на B. Част от информацията, съдържаща се в току-що казаното, би могла да се запише (при използване също на знака за принадлежност ∈ от теорията на множествата) чрез следното твърдение и следните две съотношения на следване:
X ∈ {X}.
X ∈ A ∪ B  :-  X ∈ A.
X ∈ A ∪ B  :-  X ∈ B .
Поставяме си въпроса дали от тази информация може да се извлече заключение, че за произволни два дадени обекта a и b на теорията на множествата може да се намери множество C, изпълняващо условието a и b да принадлежат на C. Не е трудно да се види, че отговорът на този въпрос е положителен. И наистина, да наречем за краткост трите реда по-горе със записана информация съответно първа, втора и трета клауза. Прилагайки първата клауза веднъж с a и втори път с b в качеството на X, заключаваме, че a ∈ {a} и b ∈ {b}. Оттук, прилагайки втората клауза с a и {a} в качеството съответно на X и A, виждаме, че a ∈ {a} ∪ B при всеки избор на множеството B. Аналогично, прилагайки третата клауза с с b и {b} в качеството съответно на X и B, виждаме, че b ∈ A ∪ {b} при всеки избор на множеството A. Следователно условията a и b да принадлежат на C сигурно ще бъдат изпълнени, ако в качеството на C вземем множеството {a} ∪ {b}. Все пак за да се достигне до разсъжденията, които направихме, нужно е известно, макар и малко досещане. Поради това ще изложим и друг начин, който е всъщност начинът на действие на Пролог и който, макар и малко по-дълъг, не изисква досещане, а само акуратност и изчерпателност при търсенето на възможности. Преди всичко нека запишем поставения въпрос като запитване
?- a ∈ C, b ∈ C.
За да изпълним това условието в това запитване, трябва да намерим множество C, изпълняващо и двете подусловия. Започваме с опит да изпълним първото подусловие и след това да видим дали този опит не може да се осъществи така, че да се изпълни и второто. Първата клауза дава само една възможност да се изпълни първото подусловие и тази възможност е да вземем в качеството на C множеството {a}. Ако постъпим така, нашето условие се свежда до условието
b ∈ {a}.
Веднага се вижда обаче, че никоя от трите клаузи не дава възможност за неговото изпълняване. Втората клауза показва, че ако вземем в качеството на C множество от вида A ∪ B, то първоначалното условие сигурно ще бъде изпълнено, ако множествата A и B са такива, че да изпълняват условието
a ∈ A, b ∈ A ∪ B.
Благодарение на първата клауза ние можем да изпълним първото от горните подусловия като вземем множеството {a} в качеството на A и при това положение остава да изпълним чрез подходящ избор на B условието
b ∈ {a} ∪ B.
Неговото изпълняване с помощта на първата клауза не е възможно, а опитът за изпълняване с помощта на втората клауза свежда горноти условие до условие, за което вече отбелязахме, че не може да бъде изпълнено с помощта на никоя от трите клаузи. Остава да опитаме да извършим изпълняването с помощта на третата клауза. Това ни довежда до условието
b ∈ B.
То очевидно може да бъде изпълнено с помощта на първата клауза, вземайки {b} в качеството на B. Сега да си спомним, че ние първо взехме в качеството на C множество от вида A ∪ B, и след това в качеството на A - множеството {a}. В крайна сметка виждаме, че първоначалното условие се изпълнява, ако в качеството на C вземем множеството {a} ∪ {b}.

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

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

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

Съществена информация по един от принципните въпроси на логическото програмиране може да бъде намерена в гл. 9 на книгата
И. Сосков, А. Дичев. Теория на програмите. София, 1996.
Някои упражнения върху Пролог, подготвени от Весела Балева, могат да се намерят на адрес
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, можете да потърсите подходяща друга реализация, като си послужите с информация от първия от цитираните по-горе Интернет-източници).
 

Последно изменение: 25.03.2004 г.
 
 Next  Contents