1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50

1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50

^ 1.2. Математическая база языка Пролог
Программка на Прологе содержит в себе постанову задачки в виде огромного количества формул логики предикатов первого порядка и описания цели – формулировку аксиомы, которую необходимо обосновать, исходя из огромного 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 количества фактов и правил, содержащихся в этой постановке.

Формализм исчисления предикатов первого порядка оказался комфортным для описания постановки задачки на языке, близком к естественному.

Таким макаром, язык Пролог имеет четкую математическую базу. В базе языка 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 лежит исчисление предикатов первого порядка, и в этом смысле язык является подмножеством формальной логики. Но Пролог включает не все формальное исчисление, а только некое его подмножество, представленное хорновскими дизъюнктами.

Дадим несколько 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 определений.

Пусть имеется некое огромное количество объектов, называемое предметной областью. Выражение P(X1, X2, …, Xn), где Xi, i=1,…,n – так именуемые предметные переменные, а P воспринимает значения 0 либо 1, именуется логической функцией либо предикатом 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50. Предикат от n переменных именуют n-местным.

Предикат P(X1, X2, …, Xn) задает отношение меж элементами X1,X2,…,Xn и обозначает выражение, что «X1,X2,…,Xn находятся меж собой в отношении P 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50». К примеру, если отношение родитель(X,Y) значит, что X является родителем для Y (но не напротив!), то выражение родитель(«царь Петр I», «царевич Алексей») является настоящим, а отношение 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 родитель(«царь Петр I», «царевна Софья») – неверным. Принципиально осознавать, что имена отношений и их размерность («арность») произвольны и зависят только от целей их использования.

Из подобного рода простых отношений при помощи логических связок образуют более 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 сложные дела, которые в свою очередь являются предикатами, другими словами могут принимать те же значения – «истина» либо «ложь». В качестве связок употребляются конъюнкция (логическое И), дизъюнкция (логическое Либо), импликация (логическое 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 следование), отрицание, эквивалентность.

Разглядим традиционный пример рассуждений с внедрением логических связок. Пусть имеются последующие рассуждения на естественном языке (в этом случае – теоремы):

^ Все люди смертны.

Сократ – человек.

Аксиома, логически вытекающая из этих 2-ух 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 аксиом:

Сократ смертен.

Эти теоремы можно переписать так (в определениях исчисления предикатов):

^ Для всех X, если X – человек, то смертен X

И человек( Сократ )

Соответственно наш пример можно перевести на Пролог (еще 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 пока без учета синтаксиса версии PDC Prolog):

смертен( Х) :- человек ( Х ).

человек( сократ ).

Тут собственное имя «Сократ», представляющее строковую константу, записано с малеханькой буковкы, так как во всех версиях Пролога 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 с большой буковкы записывается имя переменной. При работе этой маленький программки можно задать системе вопрос: является ли Сократ смертным, и система ответит «Да»:

? смертен( сократ ).

Да

Это обычный пример, но его довольно, чтоб показать необходимость 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 использования Пролога для реализации различного рода рассуждений, так как можно задать огромное количество фактов и правил, Система, построенная при помощи Пролога, без помощи других сделает томную работу, пробираясь по цепочке через факты 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 и правила в поисках логического вывода.

Есть отличия синтаксиса логики предикатов от языка PDC Prolog. Соответствие можно созидать в таблице 1.

Заглавие операции

Обозначение в логике предикатов

Обозначение в языке PDC Prolog

и

&

запятая

либо

v

точка с запятой 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 либо точка

если

=>

:-

не

~

not


В языке Пролог исчисление предикатов ограничено особыми выражениями, именуемыми хорновскими дизъюнктами. Хорновской дизъюнкт имеет вид:

~P1 v ~P2 v … v ~ Pm v Pn,

где P1, P2, … Pm, Pn – предикаты (термы, логические 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 формулы). В данной записи предикатов мы акцентировали внимание на наружном представлении дизъюнкта в виде структуры, состоящей из предикатов, без перечисления их вероятных аргументов. Как мы лицезрели на примерах выше, предикат имеет аргументы, что, вообщем 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 говоря, в Прологе необязательно. (В математической логике предикат без аргументов именуется выражением.)

В последнем выражении только формула Pn без отрицания, и в этом основная особенность хорновского дизъюнкта. Это выражение может быть переписано 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 в виде:

P1 & P2 & … & Pm => Pn ,

и оно имеет последующую интерпретацию:

из P1 и P2 и … и Pm следует Pn.

Последнее выражение как и раньше именуется дизъюнктом, хотя от 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 символов отрицания и дизъюнкции перебежали к импликации и конъюнкции. Особенность хорновского дизъюнкта: справа от знака следования стоит только одно следствие из некого огромного количества дизъюнктов, записанных слева.

В синтаксисе Пролога последнее выражение записывается:

Pn :- P 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 501, P2, … , Pm.

Принципиально уяснить, что следствие оказалось записанным слева, а так как Пролог базируется на хорновских дизъюнктах, в левой части импликации (заключения) содержится единственный литерал. Последнюю запись утверждения Пролога можно трактовать 2-мя 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 методами:

  1. Декларативный смысл: Pn поистине, если сразу истинны P1, P2, … , Pm.

  2. Процедурный смысл: для того, чтоб выполнить Pn, нужно поочередно выполнить P1, P2, … , Pm.

Логика хорновских дизъюнктов эквивалентна полной 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 теории предикатов первого порядка, используемой для подтверждения на базе опровержения. Механизм логического вывода употребляет способ резолюций, применяющийся для автоматического подтверждения теорем, который был предложен Робинсоном (1965 г.) 1. Процесс поиска подтверждения на базе способа резолюции и составляет 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 сущность выполнения программки на Прологе. Но познание этих понятий очевидно необязательно для того, чтоб начать программировать на Прологе. Потому мы сосредоточимся на прагматическом нюансе программирования на Прологе, опуская теоретическое обоснование, которое 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 довольно тщательно изложено в литературе.
^ 1.2. Организация вычислительного процесса
Программка на Прологе включает набор процедур, любая из которых представляет собой определенный предикат. Предикат имеет общую форму:

А :– В1, В2, ... , Вn. ,

которая интерпретируется 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 : "А является настоящим, если В1, В2, ..., Вn являются настоящими". Таким макаром, значок “ :- “ соответствует обозначению «если». Предикат, содержащий условия истинности, является правилом. Когда n=0, т.е. молвят, что отсутствуют условия истинности, то такое предложение 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 выражает факт, и это записывается "А." (точка в конце записи предиката неотклонима). Так как факт не содержит критерий истинности, в Прологе факт всегда является настоящим.

В данной форме записи часть выражения, стоящая слева 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 от знака “ :- “, именуется головой дизъюнкта (в нашем примере "А"), а выражение, стоящее после чего значка, именуется телом дизъюнкта, т.е. В1, В2, ... , Вn – это тело, либо хвост дизъюнкта.

Пролог-программа 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 обязана иметь цель, так как вычисление таковой программки всегда начинается от цели. Достигнуть цели всегда значит, что она логически следует из правил программки. Можно рассматривать программку как запись аксиом, а цель – аксиому, которую следует 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 обосновать. Если получен запрос (т.е. цель, которую необходимо удовлетворить), Пролог пробует найти его истинность 2-мя методами. Во-1-х, цель удачно удовлетворяется (т.е. считается настоящей), если она сопоставляется 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 с имеющимся фактом (потому что факты всегда являются настоящими). Во-2-х, цель считается настоящей, если она сопоставляется с головой “А” правила " А, если В1, ... , Вn " и если подцели В1, ... , Вn могут быть завершены удачно. В 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 случае удачного сравнения Пролог выдает ответ "yes", т.е. цель согласована. Термин «сопоставление» обозначает совпадение цели с головой факта либо правила и относится к одному из 2-ух базисных устройств 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 логического вывода. Другой базисной операцией является унификация.

Унификация она применяется в этом случае, если предикат имеет аргументы.

Если попытка сравнить подцель с фактами в базе данных заканчивается неудачей и остаются другие (еще не 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 применявшиеся правила либо факты), Пролог будет производить возврат и использовать эти кандидатуры. Если все кандидатуры закончились безуспешно, то считается, что исходная цель неудовлетворительна. В данном случае выдается ответ "no".
^ 1.2.2. Внедрение переменных
В 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 Пролог-программе нет никаких выражений, не считая предикатов, и цель тоже представляет собой некий предикат (либо последовательность предикатов). В качестве аргументов цель может содержать константы либо переменные. Переменная представляет собой неконкретизированную величину, которую Пролог 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 должен конкретизировать, т.е. отыскать объекты-константы, которые при их подстановке заместо переменных обеспечивают достижение цели. Неконкретизированная переменная считается свободной, а если выполнена подстановка константой, то связанной. После того 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50, как цель, содержащая переменные, будет согласована, Пролог выдаст значения, которыми будут изменены переменные, входящие в цель.

Разглядим вышеприведенный пример:

родитель(«царь Петр I», «царевич Алексей»).

Спросим эту маленькую программку, чьим родителем является правитель Петр 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 I:

? родитель( «царь Петр I», X ).

Чтоб ответить на вопрос, необходимо заместо X подставит константу «царевич Алексей». В данном случае переменная X конкретизируется константой. В этом примере имела место унификация. Понятие унификации 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 пришло из математической логики, где ему соответствует подстановка значений заместо переменных при выводе логической формулы. В Прологе унификация представляет собой универсальный механизм сравнения с прототипом для передачи характеристик2. В итоге унификации переменная 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 Х получила конкретное значение.

Внутренние механизмы использования переменных в Прологе очень различаются от таких в алгоритмических языках. В процедурном программировании акцент делается на применение оператора присваивания для перемещения данных из 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 фиксированных, поименованных мест их в памяти. Эти поименованные места являются переменными программки.

Программки символьного языка употребляют переменные, которые есть быстрее виртуально в стеке компьютера, а не фиксированных местах памяти. Управление данными осуществляется средством 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 сопоставления с прототипом, и в итоге этого сопоставления переменная может получить конкретное значение (конкретизироваться), пока работает предикат. Если переменная получила свое значение, то все вхождения таковой переменной в некий предикат получают одно и 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 то же значение и уже не могут переконкретизироваться Можно сказать, что все переменные в Прологе локальные. Переменная может переконкретизироваться только при возврате к поиску других решений (бэктрекинге). Так как программки искусственного 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 ума подразумевают таковой возврат, переменная может неоднократно переконкретизироваться с целью вычисления всех наборов значений аргументов.

Мало о присваивании. Читатель уже сообразил, что один из методов придать значение переменной – передать ее как параметр 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 (аргумент) предиката. Другой метод похож на традиционное присваивание, так как употребляет символ равенства. Но все-же следует держать в голове, что в Прологе нет оператора присваивания, а есть схожий на него предикат логического 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 сопоставления, обозначаемый знаком равенства. Потому понятно, что сравнение вида N = N + 1 глупо: величина никогда не может быть равной самой для себя, увеличенной на единицу. Нужно использовать другую переменную: N1= N 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 + 1, но зато можно записать: N + 1 = N1.

Разглядим, как производится сравнение в последнем случае. Пусть N конкретизировано числом 3, N1 – числом 4. В данном случае сравнение завершится «истинно». Если N конкретизировано этим же числом, а N1 не конкретизировано 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50, то в итоге сравнения N1 получит значение 4, и предикат тоже закончится «истинно». Нетрудно сообразить, какие конкретизации переменных дадут неверное сравнение.

Отметим также, что так как в Прологе отсутствуют глобальные переменные, одни 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 и те же имена переменных можно употреблять в почти всех правилах программки, при всем этом меж такими переменными будет отсутствовать какая-либо связь.
^ 1.2.1. Синтаксис фактов и правил
Для того, чтоб 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 начать писать Пролог-программу, следует обусловиться, какие дела (предикаты) в ней будут. Имена предикатов избираем согласно смыслу программки. В синтаксисе Пролога предикат имеет последующий вид:

functor(d1,d2,...) :– cond1, cond2,... .

Тут functor – имя предиката;

functor 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50(d1,d2,...) – голова дизъюнкта;

d1, d2,... – аргументы предиката;

cond1, cond2,... – условия истинности дизъюнкта (в свою очередь, предикаты), где запятые обозначают связку “ И ”;

":–" - обозначение "ЕСЛИ".

Принципиально осознавать, что имена предикатов 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 и их размерность («арность») произвольны и зависят только от целей их использования.

Разглядим конкретное предложение:

P :- Q, R.

где P, Q, R – некие предикаты. Для выяснения истинности P следует поначалу узнать истинность Q, потом истинность 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 R. Таким макаром, запятая меж целями обозначает конъюнкцию целей. Но в Прологе вероятна и дизъюнкция целей: должна быть настоящей по последней мере, одна из целей. Дизъюнкция обозначается точкой с запятой:

P 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 :- Q; R.

Смысл такового предложения тот же, что и смысл последующей пары предложений:

P :- Q.

P :- R.

Таким макаром, логическая функция «ИЛИ» может быть записана 2-мя методами.

Для обозначения логических связок можно также 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 использовать более обычные: if, and, or, но в данном случае запись программки получится длиннее.

Если опущены условия, то functor(d1,d2,...) обрисовывает факт.

В качестве первого примера разглядим последующую 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 задачку. Опишем мир увлечений некого круга лиц. Последующим утверждениям на британском языке:

^ Ellen likes reading.

John likes football.

Tom likes baseball.

Eric likes reading.

Mark likes tennis.

соответствуют факты Пролога:

likes( ellen, reading ).

likes 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50( john, football ).

likes( tom, baseball ).

likes( eric, reading ).

likes( mark, tennis ).

Имена людей записали строчными знаками, чтоб отличить их от имен переменных, которые в Прологе начинаются с строчный буковкы. Очевидно, как 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 будет видно дальше, в Прологе есть возможность записывать имена как они того заслуживают. Некое огромное количество фактов, задающих объекты и дела меж ними, уже образует ординарную программку на Прологе. Таким макаром, вопрос: "Что 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 любит Джон?" сводится к поиску объекта X, который отношение likes (нравится) связывает с Джоном; этот объект и будет служить ответом на запрос:

? likes( john, X ).

X = football.

(В языке ^ PDC 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 Prolog заместо знака вопроса, обозначающего цель, записывается ключевое слово Goal).

Отметим, что при определении дела меж объектами существенен порядок, в каком эти объекты входят в отношение:

likes( john, football ) отличается от likes 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50( football, john ).

Факты – принципиальная часть программки искусственного ума, без их нельзя достигнуть цели. Можно сказать, что любая цель опирается на свои факты. После записи фактов обычно следуют правила. Правило всегда выражает некий общий 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 закон. Попробуем добавить один таковой закон: «Всякий Х, любящий читать – умный». Его запись в виде правила:

clever ( X ) :- likes ( X, reading ).

Если значением факта всегда является «истина», то правило содержит условие истинности 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50, записанное в его правой части. Если задаться целью отыскать всех умных людей посреди имеющихся фактов, введем запрос:

? clever (X).

Система отыщет два решения:

^ X=ellen

X= eric

Правило Пролога можно представить как маленькую функцию с 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 локальными переменными. Основное отличие таковой процедуры от процедуры, написанной на процедурном языке: предикат может делать несколько функций, зависимо от состояния аргументов (конкретизированы они либо нет). Одно и то же отношение может быть 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 применено несколькими методами: если его аргументы известны, то проверяется выполнимость дела на этих аргументах; если же некие аргументы неопознаны. То рассчитывается огромное количество наборов значений этих переменных, которые удовлетворяют отношению. К примеру, если 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 имеется предикат square («площадь»), связывающий длину и высоту геометрической фигуры с третьим значением (к примеру, площадью прямоугольника):

square( A, B, S ),

то совсем необязательно этот предикат всегда будет вычислять только 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 площадь S:

? square( 5, 4, S ),

Можно задавать и другие цели:

? square( X, 4, S ),

? square( X, Y, 20 ).

Очевидно, должны быть запрограммированы все кандидатуры вычислений, т.е. при всем этом каждому такому состоянию аргументов соответствует своя статья 1.2. Математическая основа языка Пролог - Программы классификации 49 9 Программа классификации с обратной цепочкой рассуждений 50 предиката.


12-obshie-svedeniya-o-zemle-kak-planete-v-g-galalu-inzhenernaya-geologiya-i-pochvovedenie.html
12-ocenka-i-razvitie-modeli-kompetencij-specialista-po-rabote-s-molodezhyu-centr-patrioticheskogo-vospitaniya.html
12-ohrana-okruzhayushej-sredi-generalnij-plan-municipalnogo-obrazovaniya-gorodskoe-poselenie-gorod-sol-ileck-sol-ileckogo.html