Уикипедия

Логическо програмиране: Разлика между версии

Интерактивен преглед на историята
← По-стара редакцияПо-нова редакция →
Изтрито е съдържание Добавено е съдържание
ВизуаленУикитекст
м замяна на чужда езикова препратка
м Грешки в статичния код: Остарели HTML-тагове
Ред 7:
 
Правилата са написани във формата на клаузи:
:<ttsamp>H :- B<sub>1</sub>, ..., B<sub>n</sub>.</ttsamp>
Правилото има логически смисъл на импликация, която се чете <ttsamp>"H„H е вярно, ако е вярно B<sub>1</sub>, ..., B<sub>n</sub>"“</ttsamp>:
:<ttsamp>H if B<sub>1</sub> and ... and B<sub>n</sub>.</ttsamp>
Правилата имат глава (следствие) <ttsamp>H</ttsamp> и тяло (опашка, предпоставки) <ttsamp>B<sub>1</sub>, ..., B<sub>n</sub>.</ttsamp>
Правилата дават информация за условията, които са достатъчни за изпълняването на дадена връзка или свойство. Главата на правилото се състои от единствен атом и означава свойството или връзката, която ще е в сила, ако са изпълнени всички предпоставки на правилото. Тялото на правилото се състои от поредица от атоми. Знакът, разделящ тялото и главата, се чете „е вярно, ако“.
 
Фактите могат да се третират като правила без тяло, т.е. безусловни правила. Те имат следната форма:
:<ttsamp>H.</ttsamp>
В най-простия случай, когато <ttsamp>H, B<sub>1</sub>, ..., B<sub>n</sub></ttsamp> са атомарни формули, тези клаузи се наричат [https://en.wikipedia.org/wiki/Horn_clause клаузи на Хорн]. Съществуват редица вариации на този случай, например, когато тялото е съставено от отрицанията на атомарни формули (отрицателни Хорнови клаузи).
<br>
В ASP и Datalog, програмите се характеризират само с [https://en.wikipedia.org/wiki/Declarative_programming декларативно] четене и тяхното изпълнение се извършва с помощта на процедури за „доказателство“, чието поведение не е под контрола на програмиста. За разлика от това, в Пролог-базираните езици, програмите се характеризират с т.н. процедурна интерпретация:
:<ttsamp>за да се реши H, трябва да се реши B<sub>1</sub> и ... и B<sub>n</sub>.</ttsamp>
Например, нека имаме следната клауза:
:<ttsamp>fallible(X) :- human(X).</ttsamp>
базирана на пример, използван от [https://en.wikipedia.org/wiki/Terry_Winograd Terry Winograd]<ref>{{cite journal|author= T. Winograd (1972).|title= Understanding natural language |journal= Cognitive Psychology |volume=3| issue = 1 – 191|doi=10.1016/0010 – 0285(72)90002 – 3}}</ref>, за да илюстрира програмния език [https://en.wikipedia.org/wiki/Planner_(programming_language) Planner]. Като клауза в една логическа програма, може да се използва, както като процедура, която проверява дали X е склонен да греши, като се провери дали X е човек, така и като процедура за намирането на човек X, който е склонен на греши, чрез намирането на X, който да е човек. Дори фактите имат процедурна интерпретация. Например, клаузата:
:<ttsamp>human(socrates).</ttsamp>
може да се изпозва едновременно като процедура, която показва, че socrates е човек, и като процедура, която намира X, който е човек, чрез определянето на socrates за човек.
 
Ред 64:
 
За повечето практически приложения, както и за приложения, които изискват не-еднообразни разсъждения в изкуствения интелект, логическите програми, които използват Хорнови клаузи, трябва да бъдат разширени до нормални логически програми с отрицателни условия. Една ''клауза'' в нормална логическа програма има формата:
:<ttsamp> H :- A<sub>1</sub>, …, A<sub>n</sub>, not B<sub>1</sub>, …, not B<sub>n</sub>.</ttsamp>
и се чете декларативно като логическа импликация:
:<ttsamp> H if A<sub>1</sub> and … and A<sub>n</sub> and not B<sub>1</sub> and … and not B<sub>n</sub>.</ttsamp>
където <ttsamp>H</ttsamp> и всички <ttsamp>A<sub>i</sub></ttsamp> и <ttsamp>B<sub>i</sub></ttsamp> са атомни формули. Отрицанието в негативните литерали <ttsamp>not B<sub>i</sub></ttsamp> обикновено се отнася като " [[:en:Negation_as_failure|отрицание като провал]] ", защото в повечето приложения, в които се имплементира, отрицателното условие <ttsamp>not B<sub>i</sub></ttsamp> демонстрира, че положителното условие <ttsamp>B<sub>i</sub></ttsamp> не успява да се задържи. Например:
<source lang="prolog">
canfly(X) :- bird(X), not abnormal(X).
Ред 79:
:- canfly(X).
</source>
Има две възможни решения, които решават първата подцел <ttsamp>bird(X)</ttsamp>, а именно <ttsamp>X = john</ttsamp> и <ttsamp>X = mary</ttsamp>. Втората подцел <ttsamp>not abnormal(john)</ttsamp> от първото възможно решение се проваля, тъй като <ttsamp>wounded(john)</ttsamp> успява и поради това <ttsamp>abnormal(john)</ttsamp> успява. Въпреки това втората подцел <ttsamp>not abnormal(mary)</ttsamp> на второто възможно решение успява, тъй като <ttsamp>wounded(mary)</ttsamp> се проваля, и затова <ttsamp>abnormal(mary)</ttsamp> се проваля. Ето защо, <ttsamp>X = mary</ttsamp> е единственото решение на първоначално поставената цел.
 
Micro-Planner е имал конструкция наречена „thnot“, която, когато се прилага към израз, връща стойността истина ако (и само ако) оценката на израза не успее. Подобен оператор обикновено е вграден и в съвременните [[:en:Prolog|Prolog]] реализации. Обикновено се изписва като <code>not( ''Goal'' )</code> или <code>\+ ''Goal''</code> , където<code>''Goal''</code> е някаква цел (твърдение), което да бъде доказано от програмата. Този оператор се различава от отрицанието в първия ред логика: отрицание като <code>\+ X == 1</code> се проваля, когато променливата <code>X</code> е свързана към атома <code>1</code> , но тя успява във всички останали случаи, включително когато <code>X</code> е неконсолидиран. Това прави разсъждението Prolog е [https://en.wikipedia.org/wiki/Non-monotonic_logic не-еднозначно] : <code>X = 1, \+ X == 1</code> винаги се проваля, докато <code>\+ X == 1, X = 1</code> може да успее, свързвайки <code>X</code> към <code>1</code> , в зависимост от това дали <code>X</code> първоначално е обвързан (имайте предвид, че стандартния Prolog изпълнява твърдения от ляво на дясно).
 
Логическият статус на отрицанието като провал е неразрешено, докато Кийт Кларк [1978] показа, че при определени естествени условия, то е вярно (а понякога и пълно) изпълнение на класическото отрицание по отношение на целостта на програмата. Целостта се отнася приблизително до настройване на всички програмни клаузи с едни и същи предикати от лявата страна:
: <ttsamp>Н: - – Body 1.
: ...
: Н: - – Body к.</ttsamp>
като определение на предиката
: <ttsamp>H iff (Body<sub>1</sub> or … or Body<sub>k</sub>)</ttsamp>
където <ttsamp>"iff"„iff“</ttsamp> означава <ttsamp>"ако„ако и само ако"ако“</ttsamp>. Изписването на цялото изисква изричното използване на равнопоставени предикати и включване на набор от подходящи аксиоми за равенство. Въпреки това, прилагането на отрицанието чрез провал се нуждае само от половинките IF-на определенията без аксиоми на равенство.
 
Например, завършването на програмата горе е:
:<ttsamp> canfly(X) iff bird(X), not abnormal(X).</ttsamp>
:<ttsamp> abnormal(X) iff wounded(X).</ttsamp>
:<ttsamp> bird(X) iff X = john or X = mary.</ttsamp>
:<ttsamp> X = X.</ttsamp>
:<ttsamp> not john = mary.</ttsamp>
:<ttsamp> not mary = john.</ttsamp>
Представата за завършеност е тясно свързана с [https://en.wikipedia.org/wiki/Circumscription_(logic) определението на МакКарти] за разсъждение по подразбиране и, че по презумпция едно твърдение е вярно, ако за него е известно, че е вярно – [https://en.wikipedia.org/wiki/Closed-world_assumption допускането на затворен свят].
 
Като алтернатива на семантиката на завършване, отрицанието като провал може да се тълкува и познавателно, както в [https://en.wikipedia.org/wiki/Stable_model_semantics семантиките на стабилен модел] на [https://en.wikipedia.org/wiki/Answer_set_programming програмирането с редица отговори]. В тази интерпретация <ttsamp>not(B<sub>i</sub>)</ttsamp> означава буквално, че <ttsamp>B<sub>i</sub></ttsamp> не е известно. Познавателното тълкуване има предимството, че може да се комбинира с класическото отрицание, както в "разширеното логическо програмиране", да се формализират фрази като „противоположното не може да се докаже“, където „противоположното“ е класическо отрицание, и „не може да се докаже“ е познавателна интерпретация на отрицанието като провал.
 
=== Представяне на знания ===
Ред 111:
През лятото и есента на 1972 година двамата отново работили заедно и разработили процесуално тълкуване на последиците. Чрез декларативно-процесуалната интерпретация, по-късно образували нотацията на програмният език Пролог,
 
:<ttsamp>H :- B<sub>1</sub>, …, B<sub>n</sub>.</ttsamp>
 
която може да бъде четена и използвана, както декларативно така и процесуално.
Ред 120:
[https://en.wikipedia.org/wiki/Abductive_logic_programming Абдуктивното логическо програмиране] е разширение на обикновеното логическо програмиране, което позволява някои предикати, декларирани като абдуктивни, да бъдат „отворени“ или неопределени. Клаузата в абдуктивната логическа програма има следната формула:
 
:<ttsamp>H :- B<sub>1</sub>, …, B<sub>n</sub>, A<sub>1</sub>, …, A<sub>n</sub>.</ttsamp>
 
където <ttsamp>H</ttsamp> е атомна формула, която не е абдуктивна, всички <ttsamp>B<sub>i</sub></ttsamp> са литерали, чиито предикати също не са абдуктивни, а <ttsamp>A<sub>i</sub></ttsamp> са предикати, чиито литерали са абдуктивни. Абдуктивните предикати могат да бъдат ограничени от ограничения за интегритет, които могат да имат следният вид:
 
:<ttsamp>false :- B<sub>1</sub>, …, B<sub>n</sub>.</ttsamp>
 
където <ttsamp>Bi</ttsamp> са произволни литерали (дефинирани или индуцирани и атомни или отрицателни). Например:
<source lang="prolog">
canfly(X) :- bird(X), normal(X).
Ред 136:
където предиката принципно е абдуктивен.
 
Решаването на проблеми се постига чрез извличане на хипотези, изразени по отношение на абдуктивните предикати. Тези проблеми могат да бъдат или наблюдения, които трябва да бъдат обяснени (както в [https://en.wikipedia.org/wiki/Abductive_reasoning класическата абдукция]) или задачи, които да бъдат решени (както е в обикновената логика на програмиране). Например хипотезата <ttsamp>normal(mary)</ttsamp> обяснява наблюдението <ttsamp>canfly(mary)</ttsamp>. Освен това, същата хипотеза предполага, че единственото решение <ttsamp>X = mary</ttsamp> намира нещо, което може да лети:
<source lang="prolog">
:- canfly(X).
Ред 149:
solve(A):- clause(A,B),solve(B).
</source>
където вярно представлява празена връзка. <ttsamp>(A,B)</ttsamp> означава, че има клауза за обектно-ниво на форма <ttsamp>A:-B</ttsamp>. Металогичното програмиране позволява на представители от обектното и от мета нивото да бъдат комбинирани, като на естествен език. Той може да бъде използван за осъществяване на всяка логика, която следва заключителните правила.
 
=== Ограничително логическо програмиране ===
Ред 155:
 
[[:en:Constraint_logic_programming|Ограничително логическо програмиране]] съчетава Horn логика на програмиране с [[:en:Constraint_solving|решенията за ограничение]]. Тя разширява Horn клаузите, като позволява на някои предикати, декларирани като ограничаващи предикати, да се появят като литерали в тялото на клаузи. Програмата с ограничителна логика е набор от клаузи във формат:
:<ttsamp>H :- C<sub>1</sub>, …, C<sub>n</sub> B<sub>1</sub>, …, B<sub>n</sub>.</ttsamp>
където <ttsamp>H</ttsamp> и всички <ttsamp>B<sub>i</sub></ttsamp> са атомни формули, а <ttsamp>C<sub>i</sub></ttsamp> са ограниченията. Декларативно, такива клаузи се четат като обикновени логически импликации:
:<ttsamp>H if C<sub>1</sub> and … and C<sub>n</sub> and B<sub>1</sub> and … and B<sub>n</sub>.</ttsamp>
Въпреки това, като се има предвид, предикатите в главите на клаузи са определени от програмата с ограничителна логика, предикатите в ограниченията са предварително определени от някои домейн-специфицирана моделно-теоретична структура или теория. Процедурно подцелите, чиито предикати са определени от програмата, са решени чрез цел намаляване, както в обикновеното логическо програмиране, но ограниченията са проверени за удовлетворяване на специфично ограничение от домейна, с което се прилага семантиката на предикатите. Първоначалният проблем е решен като го сведе до задоволителна връзка между ограниченията.
 
Следната програмата с ограничителна логика представлява измислена времева база данни от историята на Джон като учител :
:<ttsamp>teaches(john, hardware, T) :- 1990 ≤ T, T < 1999.</ttsamp>
:<ttsamp>teaches(john, software, T) :- 1999 ≤ T, T < 2005.</ttsamp>
:<ttsamp>teaches(john, logic, T) :- 2005 ≤ T, T ≤ 2012.</ttsamp>
:<ttsamp>rank(john, instructor, T) :- 1990 ≤ T, T < 2010.</ttsamp>
:<ttsamp>rank(john, professor, T) :- 2010 ≤ T, T < 2014.</ttsamp>
Тук <ttsamp>≤</ttsamp> и <ttsamp><</ttsamp> са ограничителни предикати с тяхнота обичайна семантика. Следната заявки в базата данни има за цел да разберете, кога Джон едновременно учи логика и е професор:
:<ttsamp>:- teaches(john, logic, T), rank(john, professor, T).</ttsamp>
Решението е: <ttsamp>2010 ≤ T, T ≤ 2012</ttsamp>.
 
Ограничително логическо програмиране е използвано за решаване на проблеми в сфери като [[:en:Civil_engineering|гражданско строителство]], [[:en:Mechanical_engineering|машиностроене]], проверка [[:en:Digital_circuit|на цифрова схеми]], [[:en:Automated_timetabling|автоматизирано изготвяне на разписание]], [[:en:Air_traffic_control|контрол на въздушното движение]] и финанси. Тя е тясно свързана с [[:en:Abductive_logic_programming|абдуктивното логическо програмиране]].
Ред 176:
 
Конкурентното логическо програмиране интегрира концепции от логическото програмиране в [//en.wikipedia.org/wiki/Concurrent_programming конкурентно програмиране]. Неговото развитие е дало голям тласък през 1980 г. от избора на езика за програмиране на [[:en:Fifth_generation_computer|Japanese Fifth Generation Project (FGCS)]].<ref>{{cite journal|author= T. Winograd (1972).|title= Understanding natural language |journal= Cognitive Psychology |volume=3| issue = 1 – 191|doi=10.1016/0010 – 0285(72)90002 – 3}}</ref>.Програмата с конкурираща логика е набор от пазените [[:en:Horn_clauses|Horn clauses]] на формата :
:<ttsamp>H :- G<sub>1</sub>, …, G<sub>n</sub> | B<sub>1</sub>, …, B<sub>n</sub>.</ttsamp>
Съединението <ttsamp>G<sub>1</sub>, …, G<sub>n</sub></ttsamp> се нарича [[:en:Guard_(computing)|гард]] на клаузата, а <ttsamp>|</ttsamp> е операторът. Декларативно, пазената Horn клауза се чете като обикновена логическа импликация:
:<ttsamp>H if G<sub>1</sub> and … and G<sub>n</sub> and B<sub>1</sub> and … and B<sub>n</sub>.</ttsamp>
Въпреки това, процедурно, когато има няколко клаузи, чиито начала <code>H</code> съвпадат с дадена цел, тогава всички клаузи се изпълняват паралелно, проверявайки дали тяхната охрана <ttsamp>G<sub>1</sub>, …, G<sub>n</sub></ttsamp> задържа. Ако охраната на повече от една клауза задържи, се извършва избор се от една от клаузите, и изпълнение продължава с подцели <ttsamp>B<sub>1</sub>, …, B<sub>n</sub></ttsamp> на избраната клауза. Тези подцели могат да се извършат и паралелно. По този начин конкурентното логическо програмиране прилага форма на „не ми пука недетерминизъм“, а не „Не знам недетерминизъм“
 
Например, следната програма с конкурентна логика определя предикат <ttsamp>shuffle(Left, Right, Merge)</ttsamp>, който може да се използва, за да разбъркате два списъка <ttsamp>Left</ttsamp> и <ttsamp>Right</ttsamp>, комбинирайки ги в един списък <ttsamp>Merge</ttsamp>, който запазва подредбата на двата списъка <ttsamp>Left</ttsamp> and <ttsamp>Right</ttsamp>:
<source lang="prolog">
shuffle([], [], []).
Ред 193:
shuffle(Left, Rest, ShortMerge).
</source>
Тук, <ttsamp>[]</ttsamp> представлява празен списък, а <ttsamp>[Head | Tail]</ttsamp> представлява списък с първия елемент <ttsamp>Head</ttsamp> последван от списък <ttsamp>Tail</ttsamp>. Програмата може да се използва, например, за да разбъркате списъците <ttsamp>[ace, queen, king]</ttsamp> и <ttsamp>[1, 4, 2]</ttsamp>, като се позовава на клаузата за цел:
<source lang="prolog">
shuffle([ace, queen, king], [1, 4, 2], Merge).
</source>
Програмата ще генерира недетерминистично единично решение – например <ttsamp>Merge = [ace, queen, 1, king, 4, 2]</ttsamp>.
 
Може да се каже, че конкурентното логическо програмиране се основава на предаването на съобщения и следователно е предмет на същата неопределеност като други конкурентни системи за предаване на съобщения, също като [[:en:Actor_model|Actors]] (виж [[:en:Indeterminacy_in_concurrent_computation|Indeterminacy in concurrent computation]]). Carl Hewitt твърди, че конкуриращо логическо програмиране не се основава на логиката затова, че изчислителни стъпки не могат да бъдат логически изведени.
Взето от „https://bg.wikipedia.org/wiki/Логическо_програмиране“.