Логическое программирование

1.

Уфимский государственный авиационный
технический университет
Факультет информатики и робототехники
Кафедра вычислительной математики и кибернетики
Логическое
программирование
Д.т.н., профессор кафедры ВМиК Ризванов Дмитрий Анварович

2. Литература по дисциплине

Д.А. Ризванов, Д.В. Попов, Г.А. Макеев. Функциональное и логическое
программирование. Математические основы и языковая семантика:
учебное пособие. – Уфа: УГАТУ, 2009. – 160 с.
И.Братко. Программирование на языке Пролог для искусственного
интеллекта. М.: Мир. 1990, 2007.
Дж.Стобо. Язык программирования Пролог. "Радио и связь". М.1993.
У.Клоксин, К.Меллиш. Программирование на языке Пролог. "Мир".1987.
Дж.Малпас. Реляционный язык Пролог и его применение.
"Наука".М.1990.
А.Янсон. Турбо-Пролог в сжатом изложении. "Мир". М. 1991
Ц.Ин,Д.Соломон. Использование Турбо-Пролога. "Мир".М.1993.
Язык Пролог в пятом поколении ЭВМ. Сб.статей. "Мир".М.1988
2

3.

Эпиграф

4. Основные конструкции логической программы

ЛП состоит из предложений, которые описывают знания о решаемой задаче.
Предложение конструируется из объектов и отношений между ними.
Объекты.
Конкретное множество объектов образует проблемную область.
Например, для задачи f(x) -> min множество всех чисел образует проблемную область,
если f(x) определена.
Конкретные объекты образуют множество индивидуумов.
Конкретные объекты и конкретные отношения это константы.
Имена констант это атомы.
Различают атомы простые и составные.
Например, «мир» – простой, «студент(петров)» - составной.
В общем виде структура имени имеет вид: f(t1,…,tn) где f – функтор, ti – аргументы.
Отношения.
Рассмотрим запись «сессия(экзамен(мат, физ, прогр), весна)»
В основе представления о смысле имен сессии и экзамена лежат конкретные множества
наборов объектов. Заданием этого множества можно формализовать понятие
«экзамены».
Например, экзамены = { (мат, физ, прогр), (фил, псих, экол), … }
Это пример трехместного отношения. N- местное отношение – это множество кортежей
для фикс. N.
4

5. Основные конструкции логической программы (2)

Предикаты.
В логике отношение называют предикатом.
Имя отношения – предикатный символ.
Запись P(t).
Понимание:
1. Элементы кортежа t принадлежат отношению с именем P или:
2. Высказывание Р верно для элементов кортежа t.
Предложение состоит из:
• Логических связок (и), (или), (не), (если), (тождественно).
• Предикатов.
• Формул:
Каждый предикат – формула.
Если F1, F2 – формулы, то
(F1) – формула.
F1 F2, F1 F2, F1, F1 F2, F1 F2 – тоже формулы.
Например.
Студент-ФИРТ(петров) – формула.
Студент-УГАТУ(петров) Студент-ФИРТ(петров) – формула.
Замечание. «петров» - конкретный объект, поэтому с малой буквы.
5

6. Основные конструкции логической программы (3)

Переменные, термы, предложения.
Логические переменные используются при формулировке утверждения обо
всех объектах данной совокупности.
Имя переменной начинается с заглавной буквы.
Терм – либо константа, либо переменная, либо кортеж, перед которым стоит
функтор.
Предикат – кортеж, перед которым стоит предикатный символ.
Формула – предикат либо одно из выражений (F1), θ F1, где θ – любой из
кванторов.
Предложение – формула, каждое вхождение переменной которой находится в
области действия квантора по ней.
Замечание. Логический терм – единственная структура данных в ЛП.
Предикаты выражают отношения между объектами, а предложения описывают
логические свойства отношений.
6

7. Виды предложений ЛП

1.Факты
2.Правила
3.Вопросы
7

8. Факты

Факт P(t1,…,tn). – простейшее предложение, используемое для того, чтобы
можно было утверждать, что высказывание о принадлежности объекта ti
некоторому отношению P истинно.
Например, факультет-УГАТУ(фирт).
Универсальный факт:
«все студенты МО владеют английским языком»: влад-англ-яз(Студ, мо).
Простейшей ЛП является простейшая БД.
Создание БД начинается с создания реляционной схемы для каждого
отношения.
Например, книга(Автор, Название, Издательство, Год):
книга(братко, программирование-на-языке-пролог, мир, 1990).
8

9. Правила

Правила – предложения вида P(t1,…,tn) a1(t1,…,tr), a2(t1,…,ts), …, am(t1,…,tq).
Например, «некто получает повышенную стипендию, если некто студент,
сдавший все экзамены на отлично»:
получ-повыш-стип(X) сдал-все-экз(X), экз(X,5,5,5,5).
Замечания.
1. Факт – простейший случай правила.
2. В ЛП правила называют аксиомами, а совокупность фактов и правил –
гипотезами.
9

10. Вопросы

Вопросы – служат для извлечения информации из ЛП.
Различают простые и конъюнктивные.
Вид: ? P(t). Здесь Р – цель, поэтому вопросы еще называют целевыми
утверждениями.
Конъюнктивные: ? поэт(ломоносов), химик(ломоносов), спортсмен(ломоносов).
Процедура поиска ответа на простой вопрос состоит в отыскании факта
P(t1,…,tn). Поиск состоит в том, чтобы определить, является ли вопрос
логическим следствием программы.
При поиске ответа на простой вопрос используются простейшие правила
вывода. Правила основаны на теореме “из Р выводимо Р”. Если факт,
тождественный вопросу, найден, то ответ “да” иначе “нет”.
Если получен ответ “нет”, то это означает, что факт Р не содержится в БД.
При этом возможно, что информация в факте Р верная.
Например, ? книга(агафонов, логическое-программирование,наука, 1988) БД,
хотя информация верная.
10

11. Вопросы (2)

Вопросы с переменными служат для представления совокупности вопросов.
Например, ? книга(X, Y, Z, 1990).
Поиск ответа на вопрос заключается в определении, существуют ли такие
значения переменных, при которых вопрос будет логическим следствием
программы. Такие вопросы называются экзистенциональными.
Понятие вопроса связано с понятием общих переменных.
Общие переменные – переменные, входящие в две или более различные цели
вопроса.
Например, likes("Саша",X) likes("Зина",X), likes("Нина",X).
11

12. Программирование на языке Пролог

В отличие от алгоритмических, процедурных языков
программирования, Пролог относится к логическим, декларативным языкам.
При использовании языков первой группы программист задает
машине способ решения поставленной задачи, называемый алгоритмом.
Программы на Прологе содержат только описания (декларации)
отношений между объектами, которые необходимы для решения задачи.
Способ решения задачи выбирает сама машина. Поэтому программы на
Прологе бывают понятнее и много короче, чем на алгоритмических языках
программирования.
12

13. Структура логической программы

Domains
% название раздела типов данных
name = symbol
Predicates
% название раздела с описанием предикатов
likes(name, name)
Сlauses
% название раздела с фактами и правилами
likes("Зина", "мороженое").
likes("Зина", "чтение").
likes("Нина", "мороженое").
likes("Нина", "чтение").
likes("Саша", Х) :- likes("Зина", Х), likes("Нина", Х).
Goal
% название раздела с вопросом
likes("Саша",Y), write(Y), nl.
13

14. Дерево родственных отношений

14

15. Программа «Дерево родственных отношений»

Predicates
Родитель(name, name).
Run.
Clauses
Родитель(пам, боб).
Родитель(том, боб).
Родитель(том, лиз).
Родитель(боб, энн).
Родитель(боб, пат).
Родитель(пат, джим).
Run :- Родитель(боб, пат).
Goal
Run.
Ответ
Yes
15

16. Программа «Дерево родственных отношений»

Predicates
Родитель(name, name).
Run.
Clauses
Родитель(пам, боб).
Родитель(том, боб).
Родитель(том, лиз).
Родитель(боб, энн).
Родитель(боб, пат).
Родитель(пат, джим).
Run :- Родитель(лиз, пат).
Goal
Run.
Ответ
No
16

17. Программа «Дерево родственных отношений»

Вопрос: «Кто является родителем родителя Джима»
17

18. Программа «Дерево родственных отношений»

Вопрос: «Кто является родителем родителя Джима»
Predicates
Родитель(name, name).
Run.
Run(name, name).
Clauses
Родитель(пам, боб).
Родитель(том, боб).
Родитель(том, лиз).
Родитель(боб, энн).
Родитель(боб, пат).
Родитель(пат, джим).
Run :- Родитель(боб, пат).
Run :- Родитель(лиз, пат).
Run(X,Y) :- Родитель(Y, джим), Родитель(X, Y).
Goal Run(X,Y).
Ответ
X=боб, Y=пат.
18

19. Цели в Пролог-программе

• Внутренние
• Пролог находит только первое решение с полученными значениями
переменных
• Внешние
• Пролог находит все достижимые цели
19

20. Управление откатом

Предикат cut
!
Этот предикат, вычисление которого всегда завершается успешно, заставляет
внутренние программы сопоставления «забыть» все указатели отката,
установленные во время попыток вычислить предыдущие подцели.
pr:- a, b, !, c.
При вычислении подправилa а, затем b осуществляется последовательный
поиск решений с откатами до тех пор, пока не будут удовлетворены эти
подцели; далее произойдет успешное завершение предиката отсечения !;
затем начнется вычисление подцели с, но здесь откаты возможны только при
поиске решений для с и благодаря отсечению становятся невозможными
откаты для нового поиска альтернативных решений для подцелей a и b.
20