Н. И. Цуканова
Т. А. Дмитриева
Теория и практика логического
программирования на языке
Visual Prolog 7
Допущено УМО вузов по университетскому
политехническому образованию в качестве учебного
пособия для студентов высших учебных заведений,
обучающихся по специальности 230105 – «Программное
обеспечение вычислительной техники
и автоматизированных систем»
Москва
Горячая линия - Телеком
2013
Стр.1
УДК 004.434:004.8
ББК 32.973.26-018.1
Ц85
Рец енз ен т : доктор техн. наук, профессор И. В. Солодовников
Цуканова Н. И., Дмитриева Т. А.
Ц85
Теория и практика логического программирования
на языке Visual Prolog 7. Учебное пособие для вузов. –
М.: Горячая линия – Телеком, 2013. – 232 с.: ил.
ISBN 978-5-9912-0194-0.
Рассмотрены теоретические основы логического программирования.
Даны примеры и описание предметной области
с помощью логических моделей. Показана связь базовых понятий
логики предикатов и основных конструкций языка логического
программирования Пролог. Изложены основы логического
программирования на примере языка Visual Prolog 7.
Рассмотрены структура программы, алгоритм работы интерпретатора,
ввод – вывод, приемы и средства организации интерактивных
программ, вопросы недетерминированного программирования
и управления выполнением программы, различные
структуры данных и предикаты работы с ними. Книга содержит
многочисленные примеры, а также контрольные вопросы
и практические задания. Пособие будет полезно при изучении
курса «Функциональное и логическое программирование».
Для студентов высших учебных заведений, программистов,
специалистов в области искусственного интеллекта и баз
данных.
ББК 32.973.26-018.1
Цуканова Нина Ивановна, Дмитриева Татьяна Александровна
Теория и практика логического программирования
на языке Visual Prolog 7
Учебное пособие для вузов
Обложка художника В. Г. Ситникова
Подписано в печать 01.01.2013. Формат 60х90/16. Гарнитура Times. Усл.печ. л. 14,5. Тираж 1000 экз. (2-й завод 100 экз.)
ООО «Научно-техническое издательство «Горячая линия-Телеком»
ISBN 978-5-9912-0194-0
© Н. И. Цуканова,
Т. А. Дмитриева, 2011, 2013
© Издательство «Горячая линия – Телеком», 2013
Стр.2
ПРЕДИСЛОВИЕ
В последние годы значительно возрос интерес к работам по искусственному
интеллекту, особенно к практическому воплощению результатов
этих работ в экспертных системах. Одной из наиболее важных задач, связанных
с проектированием таких систем, является проблема представления
знаний о предметной области. Исследования развиваются в двух направлениях:
первое связано с выбором формализованных моделей представления
знаний; второе – с разработкой и внедрением языков представления
знаний, обладающих необходимыми изобразительными средствами.
В настоящее время большую популярность приобрел язык логического
программирования Пролог, основанный на самой старой модели представления
знаний – исчислении предикатов первого порядка. Само название
Пролог есть сокращение, означающее программирование на языке
логики.
Пролог предоставляет средства для описания знаний о предметной области
в виде фактов и правил вывода. Он понятен экспертамнепрограммистам
и даже с успехом может использоваться для обучения
детей программированию. Пролог способствует формированию стиля программирования,
основанного на идеях модульного программирования и
программирования "сверху вниз". В то время как традиционные языки
программирования являются процедурно-ориентированными, Пролог основан
на описательной или декларативной парадигме в программировании.
Это свойство коренным образом меняет программистское мышление
и делает обучение программированию на Прологе увлекательным занятием,
требующим определенных интеллектуальных усилий.
Пролог применяется при создании приложений в следующих областях:
разработка быстрых прототипов прикладных программ;
разработка приложений, связанных с защитой информации;
управление производственными процессами;
создание динамических реляционных баз данных;
перевод с одного языка на другой;
•
•
•
•
•
•
реализация экспертных систем и оболочек экспертных систем.
Системы программирования на Прологе эксплуатируются на ЭВМ самых
разных типов и приобрели широкую известность благодаря наличию
таких
развитых версий
на персональных компьютерах как
WinProlog, Visual Prolog, Strawberry Prolog и Arity Prolog. В пособии рассматриваются
примеры, подготовленные в среде Visual Prolog 5.2, 7.0 –
7.3, приводятся правила и пример создания законченного приложения с
графическим интерфейсом в среде Visual Prolog 7.0 – 7.3. Эти версии являются
в настоящее время наиболее развитыми промышленными версиями,
работающими в среде ОС Windows.
Стр.3
4
Логическое программирование на языке Visual Prolog
Пособие делится на одиннадцать глав. В гл. 1 описываются теоретические
основы логического программирования: вводится понятие формальной
системы, затем рассматриваются такие формальные системы как исчисление
высказываний и исчисление предикатов, а также алгоритм вывода,
основанный на принципе резолюции. В гл. 2 рассматриваются базовые
понятия языка логического программирования, структура программы на
Прологе и правила составления программ. В гл. 3 описывается алгоритм
работы интерпретатора Пролога. Подробно рассматривается каждая фаза
циклического процесса доказательства текущей цели. Предлагается для
анализа выполнения программы использовать схему в виде И-ИЛИдерева.
В гл. 4 вводится понятие встроенного предиката, затем рассматриваются
встроенные предикаты ввода-вывода термов, а также арифметические
выражения и предикаты сравнения термов.
Пятая, шестая и седьмая главы посвящены способам управления выполнением
программы на Прологе. В гл. 5 рассматриваются способы организации
ветвления и повторяющихся процессов. Гл. 6 посвящена рекурсии
как одному из основных методов программирования на Прологе. В
гл. 7 описывается управление процессом возврата с помощью встроенного
предиката "отсечение".
Гл. 8–10 посвящены различным структурам данных в языке Пролог. В
гл. 8 рассматриваются списки, их структура и приводятся примеры наиболее
часто используемых предикатов работы со списками. В гл. 9 уделяется
внимание строкам, для работы с ними в языке Visual Prolog разработано
много встроенных предикатов. В гл. 9 рассматриваются структуры. Гл. 11
посвящена описанию среды Visual Prolog 7.0 – 7.3 и правилам создания в
этой среде законченного приложения с использованием графического интерфейса.
В
конце каждой главы приведены вопросы для самоконтроля и задания
для самостоятельной работы, рассматривается пример выполнения одного
из заданий.
Для читателя этой книги можно дать следующие рекомендации. Если
читателю знаком язык Пролог и его цель познакомиться с правилами работы
в новой среде Visual Prolog 7, то ему лучше сразу перейти к гл. 11.
Если читатель – новичок и только начинает изучение языка, но теоретические
основы его не интересуют, ему следует обратиться к гл. 2. А если
читатель специалист по представлению знаний в интеллектуальных системах
и его интересуют логические модели, а также если он очень любознательный,
то рекомендуем ему прочитать гл. 1.
Авторы выражают благодарность рецензентам, сделавшим ряд ценных
замечаний при подготовке данного пособия.
Стр.4
СОДЕРЖАНИЕ
ПРЕДИСЛОВИЕ............................................................................... 3
ГЛАВА 1. ВВЕДЕНИЕ В ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ...................................... 5
1.1. ФОРМАЛЬНАЯ СИСТЕМА............................................................ 6
1.2. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ КАК ФОРМАЛЬНАЯ СИСТЕМА .. 9
1.3. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ ПЕРВОГО ПОРЯДКА КАК
ФОРМАЛЬНАЯ СИСТЕМА......................................................................... 14
1.4. ЛОГИЧЕСКИЕ СЛЕДСТВИЯ........................................................ 20
1.5. ПРЕОБРАЗОВАНИЕ ЛОГИЧЕСКИХ ФОРМУЛ К МНОЖЕСТВУ
ПРЕДЛОЖЕНИЙ – ДИЗЪЮНКТОВ.............................................................. 22
1.6. ПРИНЦИП РЕЗОЛЮЦИИ ............................................................ 25
1.7. ТЕХНОЛОГИЯ РЕШЕНИЯ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ
ЛОГИЧЕСКИХ МОДЕЛЕЙ.......................................................................... 31
1.8. СТРАТЕГИИ УПРАВЛЕНИЯ........................................................ 32
1.9. ХОРНОВСКИЕ ДИЗЪЮНКТЫ ..................................................... 36
КОНТРОЛЬНЫЕ ВОПРОСЫ............................................................... 38
КОНТРОЛЬНЫЕ ЗАДАНИЯ................................................................ 39
ГЛАВА 2. ОПИСАНИЕ ПРЕДМЕТНОЙ ОБЛАСТИ С
ПОМОЩЬЮ ПРОГРАММЫ НА ПРОЛОГЕ................................... 42
2.1. ФАКТЫ..................................................................................... 44
2.2. ВОПРОСЫ ИЛИ ЦЕЛЕВЫЕ УТВЕРЖДЕНИЯ................................. 46
2.3. ПЕРЕМЕННЫЕ .......................................................................... 47
2.4. ПРАВИЛА ................................................................................. 47
2.5. КОНЪЮНКЦИЯ ЦЕЛЕВЫХ УТВЕРЖДЕНИЙ ................................ 50
2.6. ПОПОЛНЕНИЕ БАЗЫ ЗНАНИЙ ................................................... 51
2.7. СТРУКТУРА ПРОГРАММЫ НА ЯЗЫКЕ VISUAL PROLOG............. 52
2.8. РЕЛЯЦИОННЫЙ ЯЗЫК ПРОЛОГ................................................. 56
ЗАКЛЮЧЕНИЕ ................................................................................. 58
ПРИМЕР ВЫПОЛНЕНИЯ КОНТРОЛЬНОГО ЗАДАНИЯ......................... 59
КОНТРОЛЬНЫЕ ВОПРОСЫ............................................................... 62
КОНТРОЛЬНЫЕ ЗАДАНИЯ................................................................ 62
ГЛАВА 3. ОБЩАЯ СХЕМА ВЫПОЛНЕНИЯ ПРОГРАММЫ
НА ЯЗЫКЕ ПРОЛОГ............................................................................. 69
3.1. ОБЩИЕ СВЕДЕНИЯ ................................................................... 69
3.2. МОДЕЛЬ В ВИДЕ И-ИЛИ ДЕРЕВА ПРОЦЕССА ДОКАЗАТЕЛЬСТВА
ЦЕЛЕВОГО ЗАПРОСА ............................................................................... 70
Стр.228
Содержание
229
3.3. АЛГОРИТМ РАБОТЫ ИНТЕРПРЕТАТОРА.................................... 72
КОНТРОЛЬНЫЕ ВОПРОСЫ............................................................... 77
КОНТРОЛЬНЫЕ ЗАДАНИЯ................................................................ 77
ГЛАВА 4. АРИФМЕТИЧЕСКИЕ ВЫРАЖЕНИЯ.
ПРЕДИКАТЫ ВВОДА И ВЫВОДА ТЕРМОВ.................................. 78
4.1. ТЕРМЫ ..................................................................................... 78
4.2. КОНСТАНТЫ ............................................................................ 78
4.3. ПЕРЕМЕННЫЕ .......................................................................... 78
4.4. АРИФМЕТИЧЕСКИЕ ВЫРАЖЕНИЯ............................................. 80
4.5. ПРЕДИКАТЫ СРАВНЕНИЯ ЗНАЧЕНИЙ АРИФМЕТИЧЕСКИХ
ВЫРАЖЕНИЙ........................................................................................... 80
4.6. ВВОД И ВЫВОД ........................................................................ 81
КОНТРОЛЬНЫЕ ВОПРОСЫ............................................................... 82
ГЛАВА 5. УПРАВЛЕНИЕ ВЫПОЛНЕНИЕМ
ПРОГРАММЫ........................................................................................ 83
5.1. ЦЕПОЧКА ................................................................................. 83
5.2. ВЫБОР СРЕДИ АЛЬТЕРНАТИВ................................................... 83
5.3. ИСПОЛЬЗОВАНИЕ FAIL ДЛЯ ОРГАНИЗАЦИИ ПОВТОРЯЮЩЕГОСЯ
ПРОЦЕССА (ЦИКЛА) ................................................................................ 86
5.4. ПРЕОБРАЗОВАНИЕ БАЗЫ ЗНАНИЙ ............................................ 88
5.5. НАКОПЛЕНИЕ СУММЫ............................................................. 91
5.6. СОЗДАНИЕ БЕСКОНЕЧНЫХ АЛЬТЕРНАТИВ ПРИ ПОМОЩИ
REPEAT.................................................................................................... 93
5.7. ВВОД И ВЫВОД ФАКТОВ ДИНАМИЧЕСКОЙ БАЗЫ ДАННЫХ ...... 95
ПРИМЕР ВЫПОЛНЕНИЯ КОНТРОЛЬНОГО ЗАДАНИЯ......................... 98
КОНТРОЛЬНЫЕ ВОПРОСЫ............................................................. 103
КОНТРОЛЬНЫЕ ЗАДАНИЯ.............................................................. 104
ГЛАВА 6. РЕКУРСИЯ................................................................. 106
6.1. ВВЕДЕНИЕ В РЕКУРСИЮ ........................................................ 107
6.2. КАК ПИСАТЬ РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ .......................... 108
6.3. НИСХОДЯЩАЯ РЕКУРСИЯ...................................................... 109
6.4. ВОСХОДЯЩАЯ РЕКУРСИЯ ...................................................... 111
КОНТРОЛЬНЫЕ ВОПРОСЫ............................................................. 114
КОНТРОЛЬНЫЕ ЗАДАНИЯ.............................................................. 114
ГЛАВА 7. ОТСЕЧЕНИЕ.............................................................. 117
7.1. ВВЕДЕНИЕ В ОТСЕЧЕНИЕ ....................................................... 117
7.2. ВОЗДЕЙСТВИЕ ОТСЕЧЕНИЯ НА ПРОЦЕСС ВЫПОЛНЕНИЯ........ 117
Стр.229
230
Логическое программирование на языке Visual Prolog
7.3. ИСПОЛЬЗОВАНИЕ ОТСЕЧЕНИЯ............................................... 118
7.4. ЛОВУШКИ ОТСЕЧЕНИЯ .......................................................... 120
КОНТРОЛЬНЫЕ ВОПРОСЫ............................................................. 122
КОНТРОЛЬНЫЕ ЗАДАНИЯ.............................................................. 122
ГЛАВА 8. СПИСКИ ..................................................................... 123
8.1. ВВЕДЕНИЕ В СПИСКИ............................................................. 123
8.2. ОПИСАНИЕ СПИСКОВ В ЯЗЫКЕ VISUAL PROLOG ................... 123
8.3. ГОЛОВА И ХВОСТ СПИСКА..................................................... 124
8.4. УНИФИКАЦИЯ СПИСКОВ КАК АРГУМЕНТОВ ПРЕДИКАТОВ.... 125
8.5. ПРИНАДЛЕЖНОСТЬ ЭЛЕМЕНТОВ СПИСКУ.............................. 126
8.6. ВВОД, ВЫВОД СПИСКА КАК ТЕРМА........................................ 128
8.7. ИСПОЛЬЗОВАНИЕ ПРЕДИКАТА ПРИСОЕДИНИТЬ .................... 129
8.8. ИСПОЛЬЗОВАНИЕ ПРЕДИКАТА ПРИСОЕДИНИТЬ ДЛЯ
РАЗДЕЛЕНИЯ СПИСКА........................................................................... 131
8.9. ОПЕРАЦИИ СО СПИСКАМИ..................................................... 133
8.10. СОСТАВНЫЕ СПИСКИ........................................................... 136
ПРИМЕР ВЫПОЛНЕНИЯ КОНТРОЛЬНОГО ЗАДАНИЯ В КОНСОЛЬНОМ
РЕЖИМЕ................................................................................................ 137
ПРИМЕР ВЫПОЛНЕНИЯ КОНТРОЛЬНОГО ЗАДАНИЯ В РЕЖИМЕ
ГРАФИЧЕСКОГО ИНТЕРФЕЙСА.............................................................. 140
КОНТРОЛЬНЫЕ ВОПРОСЫ............................................................. 150
КОНТРОЛЬНЫЕ ЗАДАНИЯ.............................................................. 150
ГЛАВА 9. СТРОКИ, СИМВОЛЫ И СИМВОЛИЧЕСКИЕ
ИМЕНА................................................................................................... 151
9.1. СТРОКИ.................................................................................. 151
9.2. ВСТРОЕННЫЕ ПРЕДИКАТЫ ОБРАБОТКИ СТРОК ...................... 152
9.3. СРАВНЕНИЕ СИМВОЛОВ, СТРОК И СИМВОЛИЧЕСКИХ ИМЕН.. 156
ПРИМЕР ВЫПОЛНЕНИЯ КОНТРОЛЬНОГО ЗАДАНИЯ....................... 156
КОНТРОЛЬНЫЕ ВОПРОСЫ............................................................. 158
КОНТРОЛЬНЫЕ ЗАДАНИЯ.............................................................. 158
ГЛАВА 10. СТРУКТУРЫ............................................................ 160
10.1. ВВЕДЕНИЕ В СТРУКТУРЫ..................................................... 160
10.2. ОПИСАНИЕ СМЕШАННЫХ ОБЛАСТЕЙ ДАННЫХ ................... 164
10.3. ОПИСАНИЕ ОБЛАСТИ С МНОЖЕСТВЕННЫМ ТИПОМ
ДАННЫХ................................................................................................ 165
КОНТРОЛЬНЫЕ ВОПРОСЫ............................................................. 165
КОНТРОЛЬНЫЕ ЗАДАНИЯ.............................................................. 165
Стр.230
Содержание
231
ГЛАВА 11. СОЗДАНИЕ ПРИЛОЖЕНИЙ В СРЕДЕ VISUAL
PROLOG 7.0-7.3..................................................................................... 166
11.1. СОЗДАНИЕ КОНСОЛЬНЫХ ПРИЛОЖЕНИЙ............................. 166
11.2. СОЗДАНИЕ ПРИЛОЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ
ГРАФИЧЕСКОГО ИНТЕРФЕЙСА. УПРАВЛЕНИЕ С ПОМОЩЬЮ МЕНЮ
ГЛАВНОГО ОКНА ЗАДАЧ........................................................................ 172
11.2.1. Создание проекта...................................................... 176
11.2.2. Создание модального диалога................................... 178
11.2.3. Изменение меню......................................................... 184
11.2.4. Изменение панели инструментов............................. 187
11.2.5. Ввод основного кода в программу............................. 189
11.2.6. Инкапсуляция интерактивного кода........................ 191
11.3. СОЗДАНИЕ ПРИЛОЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ
ГРАФИЧЕСКОГО ИНТЕРФЕЙСА. УПРАВЛЕНИЕ С ПОМОЩЬЮ ЭЛЕМЕНТОВ
ФОРМЫ. СОЗДАНИЕ НОВОГО КЛАССА. ................................................. 199
11.4. ТЕХНОЛОГИЯ СОЗДАНИЯ ПРОГРАММЫ В РЕЖИМЕ РАБОТЫ С
ГРАФИЧЕСКИМ ИНТЕРФЕЙСОМ............................................................. 215
ЗАКЛЮЧЕНИЕ ............................................................................... 217
КОНТРОЛЬНЫЕ ВОПРОСЫ............................................................. 217
ЗАДАНИЕ....................................................................................... 218
ПРИЛОЖЕНИЕ 1. ЧТО НОВОГО В VISUAL
PROLOG 7.0........................................................................................... 219
СПИСОК ЛИТЕРАТУРЫ........................................................... 227
СОДЕРЖАНИЕ............................................................................. 228
Стр.231