Логическое программировыание Лекция 3 Основные понятия Пролога

Содержание Основные понятия Вводный пример программы Определения согласно нотации БНФ Факты Правила Вопросы Пример – генеалогическое дерево 2

Пример первой программы 3 % Программа: определение специальности (квалификации) студента % факты studied(petya,mathematics). studied(vasya,german). studied(petya,compscience). studied(vasya,literature). studied(petya,english). % правила studied_technical(X) :- studied(X,mathematics). studied_technical(X) :- studied(X,compscience). studied_languages(X) :- studied(X,english). studied_languages(X) :- studied(X,german). speciality(X,tech_translator) :- studied_languages(X), studied_technical(X). speciality(X,programmer) :- studied(X,mathematics), studied(X, compscience). speciality(X,lit_translator) :-studied_languages(X), studied(X,literature). % запросы % ?- speciality(vasya, X). % ?- speciality(X, lit_translator).

Механизм логического вывода 4

Дерево И - ИЛИ 5

Дерево вывода 6

Нормальная форма Бэкуса - Наура ( БНФ ) 3 Символ ::= читается как " по определению "," это ", " есть ". Слева объясняемое понятие, справа - конструкция, разъясняющая его. Пример : ::= Символ | означает в нотации БНФ " или ", он применяется для разделения различных альтернативных растолкований определяемого понятия. Пример : ::= 0|1|2|3|4|5|6|7|8|9 Часть синтаксической конструкции, заключенная в квадратные скобки, является необязательной ( может присутствовать или отсутствовать ); Пример : ::= [-] Символ * обозначает, что часть синтаксической конструкции может повторяться произвольное число раз ( ноль и более ). Пример. ::= [ ]*.

Механизм работы логического интерпретатора 8 Запрос (целевое утверждение) сопоставляется (унифицируется) с головами имеющихся в программе правил и фактов. Начиная с первого найденного правила, целевое утверждение подменяется правой частью правила (с учетом замены переменных) Если встречается неуспех (правило не находится), то происходит откат

Базовые термины Пролога 9 Предложение имеет вид : A:- B 1,..., B n где A называется заголовком или головой предложения, а B 1,..., B n - телом. В математической логике отношения принято называть предикатами. Факт констатирует, что между объектами выполнено некоторое отношение. Он состоит только из заголовка. Т. е. это предложение, у которого тело пустое. Пример : известный нам факт, что Наташа является мамой Даши, может быть записан так : mother('Наташа', 'Даша').

Предикат и его свойства 10 Если воспользоваться нормальной формой Бэкуса - Науэра, то предикат можно определить следующим образом : ::= | ( [, ]*), т. е. предикат состоит либо только из имени, либо из имени и следующей за ним последовательности аргументов, заключенной в скобки. Аргументом или параметром предиката может быть константа, переменная или составной объект. Число аргументов предиката называется его арностью или местностью. Константа получает свое значение в разделе описания констант, а переменная означивается в процессе работы программы.

Правила 11 Правило - это предложение, истинность которого зависит от истинности одного или нескольких предложений. Обычно правило содержит несколько хвостовых целей, которые должны быть истинными для того, чтобы правило было истинным. В нотации БНФ правило будет иметь вид : ::= :- [, ]* Пример. Известно, что бабушка человека - это мама его мамы или мама его папы. Соответствующие правила будут иметь вид : бабушка(X,Y):- мама(X,Z), мама(Z,Y). бабушка(X,Y):- мама(X,Z), папа(Z,Y).

Переменные 12 Переменные - данные, имеющие имя, представляющее собой набор букв и цифр, и обозначающие какой - либо объект / сущность. Имя переменной в Прологе может состоять из букв латинского алфавита, цифр, знаков подчеркивания и должно начинаться с прописной буквы или знака подчеркивания. Свободная переменная - это переменная, которая еще не получила значения. Она не равняется ни нулю, ни пробелу ; у нее вообще нет никакого значения. Такие переменные еще называют неконкретизированными. Переменная, которая получила какое - то значение и оказалась связанной с определенным объектом, называется связанной. Если переменная была конкретизирована каким - то значением и ей сопоставлен некоторый объект, то эта переменная уже не может быть изменена.

Вопросы 13 Вопрос состоит только из тела и может быть выражен с помощью БНФ в виде : ::= [, ]* Вопросы используют для выяснения выполнимости некоторого отношения между описанными в программе объектами. Система рассматривает вопрос как цель, к которой надо стремиться. Ответ на вопрос может оказаться положительным или отрицательным, в зависимости от того, может ли быть достигнута соответствующая цель.

Цели 14 Программа может содержать вопрос в себе ( внутренняя цель ). Если программа содержит внутреннюю цель, то после запуска программы на выполнение система проверяет достижимость заданной цели. Если внутренней цели в программе нет, то после запуска программы система выдает приглашение вводить вопросы в диалоговом режиме ( внешняя цель ). Если цель достигнута, система отвечает, что у нее есть информация, позволяющая сделать вывод об истинности вопроса ("Yes"). При этом если в вопросе содержатся переменные, то система либо выдает их значения, приводящие к решению, если решение существует, либо сообщает, что решений нет ("No solution"). Если достичь цели не удалось, система ответит, что у нее нет положительного ответа ("No").

Пример 15 Факты : mother('Наташа','Даша'). mother('Даша','Маша'). Вопросы : mother('Наташа','Маша'). => No mother(X, 'Даша').=> X='Наташа'; mother(X,Y).=> X='Наташа'; Y='Даша';X='Даша; Y='Маша'; mother(X,_). => X='Наташа'; X='Даша'; mother(_,_).=> Yes Новое правило: granny(X,Y):- mother(X,Z), mother (Z,Y). ?- granny('Наташа', X). X='Маша';

Классический пример … ( для лабоработрной работы 1) 16

Описание отношений родства 17

Пример правила : Отношение « родные брат / сестра » 18

Усовершенствованный пример 19

Отношение предки / потомки 20

Примеры отношений … 21 % Отношение родства – «родитель»; логическое «ИЛИ» rel(parent,X,Y) :- rel(mother,X,Y); rel(father,X,Y). ?- rel(X, nicolas_ii, olga_1). X = father % определяем одно отношение из другого («ребенок»): rel(child,X,Y) :- rel(parent,Y,X). % отчим (неродной отец); лгичекое «НЕ» rel(stepfather,X,Y):- mother(Z,Y), married(X,Z), not(father(X,Y)). % брат; логическое неравенство rel(brother,X,Y) :- rel(mother,A,X), rel(mother,A,Y), rel(father,B,X), rel(father,B,Y), X\=Y. ?- rel(X,nicolas_1,anna). X = brother

Выводы 22 Программы на прологе состоят из фактов и правил вывода новых фактов. Другое название правила (отношения) – Предикат, состоит из заголовка и тела Переменные бывают свободными (неконкретизированными) и связанными (конкретизированными). Освоить базовую технику работу с предикатами можно при решении задачи о родственных связях (л.р. 1) Задание: выполнить упражнение из л.р. 1 согласно своему номеру варианта; дополнить правила предиката rel определяемыми отношениями