Метод на разрешаване
Правила в логическото програмиране.
Логическо програмиране.
Пролог и логическо програмиране.
1.Логическото програмиране е направление в програмирането, базирано на идеите и методите на математическата логика. Терминът логическо програмиране в компютърната литература се тълкува в широк и тесен смисъл.
В широко тълкуване LP включва набор от концепции, методи, езици и системи, които се основават на идеята за описване на проблем с набор от твърдения на някакъв логически език и получаване на решение на проблема чрез конструиране на логическо заключение в някаква формална дедуктивна система. Класовете формули, използвани за описание на проблеми, методите за извод и изчислителните модели, използвани за описване на проблеми, методите за извод и изчислителните модели, използвани в такива системи, са много разнообразни, така че техните различни комбинации формират специфични стилове на програмиране: концептуален, функционален (приложен) и т.н.
Най-големи практически резултати са постигнати в системи за програмиране, където като логически програми се използват специални класове логически формули: клаузи на Хорн, а като начин за тяхното използване се използват специални методи за логически изводи - вариантина метода на разделителна способност.
Програмирането с помощта на такива системи се наричаHorn или резолюция, но най-често -логическо програмиране, прехвърляне на тясното тълкуване на термина към по-широка концепция.
Най-известните системи от този вид са реализации на езика Prolog (програмиране от гледна точка на логиката - Програмиране в логиката). Нека разгледаме основните идеи и концепцията за LP в тесен смисъл.
Неформално, логическа програма описванабор от обекти, набор от функции и отношения на тези обекти. Логическата програма е изградена като набор от изявления за обекти, функции и връзки. Такова описание е статистическо и не уточнява никакъв изчислителен процес, т.е. можем да приемем, че това описание дефинира базата данни, в която се съхраняват обекти и присвоените им функции и връзки, например под формата на графики. Концепцията за заявка (цел) се отнася до конкретно приложение на логическа програма - например каква е стойността на функция, дадена от логическа програма за дадена стойност на аргумент. Изчисляването на отговор на запитване съответства на доказване на съществуването на такъв обект. Пропуските, по които се извършват изчисленията, формират процедурно-оперативната семантика на логическа програма. Успехът на езика Prolog се дължи на факта, че от една страна, с помощта на логическите формули на клаузите на Horn, използвани в тях, могат да бъдат описани много практически задачи, а от друга страна, е намерена простотата на интерпретация на тези формули и е изградена доста ефективна реализация на системата LP.
2.Правилата в Prolog са:
м
където , са атоми, атомът се нарича заглавка, а атомите са тялото на правилото. Тялото може да бъде празно (когато m=0) - такива правила се наричат факти. Атомът има формата
Къде е произволен предикатен символ или име на релация; - условия.
Термин е или име на променлива, или константа, или съставен термин във формата, f е n-имен функционален символ.
Функциите, посочени в логическото програмиране, се представят като релации - функция на n-место y =f (X1,X2…Xn) се представя като (n+1)-локална релация от формата F(X1,X2…Xn,Y).
Заявката (това е целта) изглежда така: С1,С2. Cr, където r>= 0 иC1, C2...Crса атоми.
Всяко правило позволява логично ипроцедурна интерпретация (в семантиката). Логическата интерпретация на правилото-„истината на A0 следва от истинността на a1 .и истината на A2, и истината на Am“ или „Ao е вярно, ако A1,A2, Am са верни“.
Че. правилата се разглеждат като формули на езика на предикатната логика на формата:
Ето общия квантор.
- логически съединител "И".
- логическа връзка "ако, тогава"
В Prolog данните, формулите се записват отзад и се използва друга нотация:
- означава се с "," (запетая) или думата и . v - ";" (точка и запетая) или "или".
- "Аз" или ": -" или ако.
Формула, използваща логически връзки. програми. може да се преобразува в еквивалент, но със съединители (НЕ) и (ИЛИ), формула от вида:
(m> 0).
Такива формули се наричат дизюнкции на Хорн, а стилът на програмиране е Хорн.
3.Метод на разрешаване - след получаване на логическа програма с прикачени към нея заявки под формата на набор от клаузи на Horn, тя се опитва да конструира изход от празна клауза, обозначена със символа "a". Ако успее, целта е разрешена, в противен случай се отхвърля. Методът за разрешаване се прилага с помощта на две правила:
Правилото за разделяне или правилото за залепване, което по време на работа нарича процедурата за обединяване - сравнения.
Обединяването е процес, който получава два термина като вход и намира обединител за тях.
Обединител на два термина е заместване, което прави термините еднакви и ако обединителят съществува, тогава термините се наричат обединени и за тях се намира най-често срещаният обединител, ако не, процедурата за обединяване отчита грешка.
Правило за разрешаване. Позволява от клаузи:
Вземете новклауза:
Тук-е най-общият обединител на термините t и s, гарантира тяхното равенство и означава, че всички замествания на обединителя се правят за всички атоми, включени в клаузи D1 и D2. Клаузите D1 и D2 се наричат родители на клаузата D. Няма двойка в клаузата D
, докато ()=() и двойката е тавтология (идентично вярна) и може да бъде премахната от по-нататъшни изчисления и изпълнява правилото за разрешаване.
Правилото за залепване ни позволява да получим клауза от клаузата A(t)A(s), т.е. свързване на идентични атоми, получени след извършване на обединяващо заместване.
Работа със системата за програмиране Turbo Prolog.