Программирование на языке Пролог для задач искусственного интеллекта. Введение в логическое программирование

МИНОБРНАУКИ РОССИИ 
Федеральное государственное бюджетное образовательное 
учреждение высшего образования 
«Российский государственный гуманитарный университет» 

Отделение интеллектуальных систем в гуманитарной сфере 

Кафедра математики, логики и интеллектуальных систем 
в гуманитарной сфере  

Е.А. Ефимова 

Программирование на языке Пролог  
для задач искусственного интеллекта 

Введение 
в логическое программирование 

Учебник 

Для направления подготовки 
 45.04.04 «Интеллектуальные системы 

в гуманитарной сфере» 

Москва
2020 

2-е издание, электронное

УДК 004.8
ББК 32.813
Е91

Утверждено на заседании РИСО 
16 апреля 2018 г., протокол № 3

Е91
Ефимова, Елена Анатольевна.

Программирование на языке Пролог для задач искусственного интеллекта. 
Введение в логическое программирование : учебник / Е. А. Ефимова ; Минобрнауки России, ФГБОУ ВО «РГГУ», Отделение интеллектуальных систем в 
гуманитарной сфере, Кафедра математики, логики и интеллектуальных систем в 
гуманитарной сфере. — 2-е изд., эл. — 1 файл pdf : 411 с. — Москва : Российский государственный гуманитарный университет, 2020. — Систем. требования: 
Adobe Reader XI либо Adobe Digital Editions 4.5 ; экран 10". — Текст : электронный.

ISBN 978-5-7281-2910-3

Рассматриваются основные теоретические понятия логического программирования, а 
также приемы и методы программирования на языке Пролог. Изучаются основы программирования на языке Visual Prolog 9. Изложение сопровождается большим числом примеров 
программ и иллюстраций. Приводятся упражнения для самостоятельной работы.
Для студентов и аспирантов, специализирующихся в области информационных технологий, прикладной математики и информатики, программной инженерии, разработки и анализа интеллектуальных систем, а также программистов и всех интересующихся практическим 
использованием логического программирования.

УДК 004.8 
ББК 32.813

Электронное издание на основе печатного издания: Программирование на языке Пролог 
для задач искусственного интеллекта. Введение в логическое программирование : учебник / 
Е. А. Ефимова ; Минобрнауки России, ФГБОУ ВО «РГГУ», Отделение интеллектуальных систем в гуманитарной сфере, Кафедра математики, логики и интеллектуальных 
систем в гуманитарной сфере. — Москва : Российский государственный гуманитарный университет, 2019. — 408 с. — ISBN 978-5-7281-2300-2. — Текст : непосредственный.

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.

ISBN 978-5-7281-2910-3
© Е. А. Ефимова, 2019
© Российский государственный 
гуманитарный университет, 2020

Содержание 

Предисловие .................................................................................................................... 5 

1. Основы логического программирования

1.1. Декларативная семантика логической программы ...................................... 9 

1.2. Процедурная семантика логической программы ....................................... 22 

Упражнения ........................................................................................................... 30 

2. Создание консольных приложений на языке Visual Prolog ............................. 32 

2.1. Консольное приложение “Hello, World!” .................................................... 32 

2.2. Основные разделы программы ..................................................................... 36 

2.3. Создание модуля ............................................................................................ 40 

2.4. Ввод и вывод в консольных приложениях .................................................. 45 

Упражнения ........................................................................................................... 53 

3. Устройство вычислений в языке Пролог

3.1. Поиск решений в языке Пролог ................................................................... 54 

3.2. Сложные термы ............................................................................................. 62 

3.3. Отрицание в языке Пролог ........................................................................... 66 

3.4. Коллекция решений ....................................................................................... 69 

Упражнения ........................................................................................................... 71 

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

4.1. Отсечение ....................................................................................................... 73 

4.2. Режимы детерминизма. Потоки параметров............................................... 79 

4.3. Логические задачи ......................................................................................... 83 

Упражнения ........................................................................................................... 88 

5. Внутренняя база данных

5.1. Конструкции циклов, управляемых откатом .............................................. 91 

5.2. Создание и изменение внутренней базы данных ....................................... 98 

5.3. Факт-переменная ......................................................................................... 104 

5.4. Контролирующий учебный диалог ............................................................ 111 

Упражнения ......................................................................................................... 117 

6. Рекурсия

6.1. Рекурсивное определение отношений ....................................................... 119 

6.2. Функции ....................................................................................................... 124 

6.3. Рекурсивные алгоритмы ............................................................................. 133 

Упражнения ......................................................................................................... 146 

7. Списки. Полиморфизм

7.1. Обработка списков. Полиморфизм ............................................................ 148 

7.2. Операции преобразования списков ........................................................... 158 

7.3. Недетерминированные предикаты обработки списков ........................... 168 

Упражнения ......................................................................................................... 178 

8. Списки. Анонимные предикаты

8.1. Анонимные предикаты ............................................................................... 180 

8.2. Алгоритмы сортировки списка .................................................................. 195 

8.3. Примеры решения логических задач ......................................................... 204 

8.4. Массивы ........................................................................................................ 213 

Упражнения ......................................................................................................... 222 

9. Графы. Деревья

9.1. Графы ............................................................................................................ 226 

9.2. Корневые деревья ........................................................................................ 240 

9.3. Алгоритмы на графах .................................................................................. 260 

Упражнения ......................................................................................................... 269 

10. Синтаксический анализ

10.1. Порождающие грамматики ...................................................................... 272 

10.2. Синтаксический анализ логических выражений .................................... 278 

10.3. Анализ арифметических выражений ....................................................... 284 

10.4. Язык запросов, близкий к естественному ............................................... 293 

10.5. Пример универсального разбора .............................................................. 299 

Упражнения ......................................................................................................... 310 

11. Анализ игровых позиций 

11.1. Основные стратегии выбора хода игрока ............................................... 312 

11.2. Анализ игры «крестики-нолики» ............................................................. 332 

11.3. Примеры игр .............................................................................................. 352 

Упражнения ......................................................................................................... 358 

12. Графический интерфейс пользователя

12.1. Основные операции рисования ................................................................ 360 

12.2. Меню. События мыши .............................................................................. 372 

12.3. Отображение изображений. Использование таймера ............................ 384 

12.4. Игра «Жизнь» ............................................................................................. 390 

Упражнения ......................................................................................................... 404 

Литература .................................................................................................................. 406 

Предметный указатель ............................................................................................... 407 

Предисловие 
 
Современное декларативное программирование благодаря развитию вычислительной техники все более активно используется в области разработки прикладного программного обеспечения. Декларативные языки программирования, логические и функциональные, 
наиболее близки к человеческому мышлению. Программы на декларативных языках, как правило, не просто короче, чем программы на императивных языках; они также позволяют значительно сократить время разработки компьютерного приложения. В них описывается, что 
нужно сделать, на языке отношений в логических языках или на языке 
функций в функциональных, но не детализируется как. Знание основных принципов логического программирования и умение применять 
их в практике программирования полезно любому программисту.  
Предмет настоящего учебника – логическое программирование 
и его использование для разработки современных компьютерных приложений. 
Учебник предназначен для студентов магистратуры, которые 
изучают методы разработки и анализа интеллектуальных систем. Он 
может быть полезен студентам бакалавриата и специалитета, а также 
аспирантам, которые специализируются в области информационных 
технологий, прикладной математики и информатики, программной 
инженерии и других областях, так или иначе связанных с программированием.  
Цель учебника – изложение основных теоретических положений 
и формирование практических умений по использованию логического 
программирования в профессиональной деятельности, в частности, 
приобретение навыков программирования на языке Пролог – основном языке логического программирования. 
Основу учебника составляет курс «Логическое программирование», который автор в течение многих лет преподавал студентом Российского государственного гуманитарного университета, специализирующимся в области разработки интеллектуальных систем.  
Исторически первым возникло императивное программирование, сначала на языках низкого уровня, затем высокого. Когда предметом активных исследований стали задачи искусственного интеллекта – символьные вычисления, анализ текстов на естественном языке, 
развитие банков данных и знаний, экспертные системы, проблемы 
биоинженерии, создание роботов и многие другие, появилась необходимость разработки специализированных языков программирования 
высокого уровня, удобных для их решения. В результате возникла 
декларативная парадигма программирования. 

Императивная парадигма программирования основана на модели архитектуры ЭВМ, предложенной фон Нейманом в 40-е годы. 
XX в., поэтому программирование в императивном стиле позволяет 
использовать ресурсы компьютера наиболее эффективно. Теоретической моделью императивного программирования является машина 
Тьюринга. Первоначально программы занимались в основном разного 
рода вычислениями. Проблемы искусственного интеллекта стали причиной появления парадигмы функционального программирования. 
Функциональное программирование основано на математических функциях. Теоретической основой функционального программирования является лямбда-исчисление. В функциональных языках имеется возможность отделить определение функции от ее имени; в этом 
случае функция определяется лямбда-выражением. Успехи, достигнутые в области автоматического доказательства теорем, привели к тому, что возникла парадигма логического программирования. 
Логическим программированием называют программирование, 
основанное на продукционных правилах и использующее язык символьной логики. Логическое программирование состоит в описании 
задачи с помощью аксиом и применении автоматического логического вывода на основе этих аксиом. Теоретической основой логического 
программирования является исчисление предикатов первого порядка. 
Современные исследования в области автоматического доказательства теорем начались с создания Г. Фреге исчисления предикатов 
первого порядка (1879). В первой трети XX в. были разработаны процедуры формального доказательства теорем (Ж. Эрбран, Т. Скулем, 
К. Гедель). В середине 50-х годов появились первые попытки программирования процедуры доказательства. В середине 60-х годов 
появился метод резолюций – эффективный метод логического вывода 
(Дж. Робинсон). Примерно в то же время В.Ф. Турчин создал функциональный язык РЕФАЛ, использующий концепции сопоставления с 
образцом и переписывания термов. В основе модели вычислений этого языка лежит нормальный алгоритм Маркова. В конце 60-х годов в 
США К. Хьюитт разработал первый язык логического программирования Planner.  
Язык Пролог был создан в Марселе в начале 70-х годов прошлого 
века Аланом Колмероэ. Первый интерпретатор языка Пролог написал 
Ф. Руссель. После создания в конце 70-х годов в Эдинбурге Д. Уорреном и Ф. Перейрой компилятора языка Пролог, написанного в значительной степени на нем самом, Пролог стал языком практического программирования. Эдинбургский Пролог был положен в основу 
стандарта языка Пролог, опубликованного в 1995 г.  
В начале 80-х годов начался новый этап  развития логического 
программирования, связанный с тем, что язык Пролог был положен 

в Японии в основу проекта ЭВМ пятого поколения. В середине 80-х 
годов XX в. в Копенгагене Л. Йенсен, Ф. Гронсков и Дж. Хофман разработали компилятор Turbo Prolog для персональных компьютеров. 
Статическая типизация, которая использовалась в языке Turbo Prolog, 
позволила транслировать программы непосредственно в машинные 
коды. На этом языке стали разрабатываться крупные коммерческие 
системы. Несмотря на несоответствие стандарту, система Turbo Prolog 
быстро стала популярной во всем мире, в том числе в России. В середине 90-х годов появилась система Visual Prolog. Современная версия 
языка Visual Prolog разрабатывается с начала 2000 годов.  
Система программирования Visual Prolog обладает всеми средствами для быстрой разработки современных приложений. Она предоставляет возможность сочетать логическое, функциональное и объектно-ориентированное программирование. В настоящее время язык 
Visual Prolog используется для создания систем управления ресурсами 
больших комплексов (в частности, аэропортов), обработки текстов на 
естественном языке, экспертных систем, систем медицинской диагностики и многого другого. Для учебных целей предназначена версия 
Personal Edition, для разработки коммерческих приложений – Commercial Edition. 
Содержание учебника соответствует программе курса «Программирование на языке Пролог для задач искусственного интеллекта» магистерской программы «Когнитивное и программное 
обеспечение интеллектуальных роботов и программирование интеллектуальных систем» направления подготовки 45.04.04 «Интеллектуальные системы в гуманитарной сфере» и охватывает все темы курса.  
Первые восемь глав посвящены введению в программирование 
на языке Пролог. В первой главе излагаются основные теоретические 
положения логического программирования. Во второй главе показано, 
как создавать консольные приложения на языке Visual Prolog. Третья 
глава описывает, как устроены вычисления, которые осуществляет 
машина вывода Пролога, в ней обсуждаются механизмы унификации 
и отката, а также предикат отрицания. В четвертой главе рассматриваются основные средства управления процессом вычислений. Пятая 
глава связана с созданием внутренних баз данных. В ней рассматриваются циклы, которые управляются только за счет отката, а также 
средства для написания игр в консоли, в частности, использование 
цвета и событий мыши. Приводятся примеры программ, которые могут использоваться для проверки знаний учащихся. Шестая глава посвящена рекурсии и рекурсивным алгоритмам; рассматривается задача 
о 
ханойской 
башне; 
приводится 
пример 
моделирования 
арифметики с помощью логических программ. Седьмая и восьмая 
главы посвящены технике обработки списков. Вводится понятие  

полиморфизма, рассматриваются элементы функционального программирования, появляются анонимные предикаты и предикаты высших порядков. Кроме того, рассматриваются примеры порождения 
комбинаторных соединений, алгоритмы сортировки списков, а также 
методы решения логических задач с помощью списков, в частности 
создается универсальный решатель задач, аналогичных «головоломке 
Эйнштейна»; приводятся примеры использования бинарных и двумерных массивов. Девятая глава связана с графами и корневыми деревьями. Рассматриваются основные алгоритмы поиска путей на графах и методы обработки деревьев, в том числе красно-черных и 
цифровых деревьев. Глава 10 посвящена порождающим грамматикам 
и синтаксическому анализу текстов; в ней создается язык запросов к 
базе данных, близкий к естественному языку, а также приводится 
пример универсального разбора. В главе 11 обсуждаются проблемы, 
связанные с программированием игр; рассматриваются методы минимакса, альфа-бета отсечения и ван Эмдена для реализации хода игрока-компьютера; проводится анализ позиций и партий для игры «крестики-нолики». Глава 12 посвящена методам разработки графического 
интерфейса пользователя; в частности, в ней рассматривается пример 
построения графа, а также реализация игры «Жизнь» Джона Конвея.  
По окончании каждой главы приводится список упражнений, 
которые предназначены для закрепления и более глубокого усвоения 
материала, а также для приобретения навыков программирования на 
языке Пролог и создания приложений в среде Visual Prolog. 
Завершают учебник список литературы и предметный указтель. 
Язык Visual Prolog является объектно-ориентированным, тем 
не менее основное внимание в учебнике уделяется логическому и 
функциональному стилям программирования. Исключением является 
глава 12, где эти стили программирования сочетаются с объектным 
стилем.   
Автор выражает глубокую признательность д-ру физ.-мат. наук, 
проф. Е.М. Бениаминову, д-ру физ.-мат. наук, проф. О.М. Аншакову и 
д-ру физ.-мат. наук Д.В. Виноградову за полезные обсуждения, а также представителям компании Prolog Development Center (Дания) – Лео 
Йенсену (Leo Schou-Jensen), Томасу Линдеру Пулсу (Thomas Linder 
Puls), Карстену Келеру Холсту (Carsten Kehler Holst) — и ее отделения 
в Санкт-Петербурге – канд. техн. наук В.А. Юхтенко, С.В. Мухину и 
А.Б. Доронину за предоставление версии Visual Prolog Commercial 
Edition и за внимание к работе. 

1. Основы логического программирования 
 
Основная идея логического программирования состоит в том, 
чтобы решение задачи сводить к описанию множества исходных утверждений на некотором формальном логическом языке, из которого 
можно было бы получать необходимые заключения с помощью некоторой системы логического вывода. В качестве формального языка в 
логическом программировании используется язык логики предикатов, 
так что логическая программа представляет собой последовательность 
формул. В классическом логическом программировании эти формулы 
являются хорновскими дизъюнктами. В языках логического программирования также используются внелогические средства, к которым относятся, например, операции ввода и вывода. Наиболее известным языком логического программирования является язык 
Пролог. 
В настоящей главе вводятся основные понятия классического 
логического программирования. Рассматриваются декларативная и 
процедурная семантика логической программы.  
 

1.1. Декларативная семантика логической программы 
 
Логическая программа – это последовательность предложений, 
которые с помощью формул логики предикатов описывают отношения между некоторыми элементами, или объектами.  
 
1.1.1. Язык логики предикатов первого порядка 
 

Определение. Алфавит языка логики предикатов состоит из 
следующего набора символов: 

1) переменные – символы, которые в языке Пролог пишутся  
с прописной буквы, например X, Y, Z, …; 

2) константы, например «программирование» и 25; 

3) функциональные символы арности n, которые в языке Пролог 
называют функторами, например f, g, h, …;  

4) предикатные символы арности n, например p, q, r, …; 

5) логические связки – символы & (конъюнкция), (дизъюнкция), 
(отрицание), или (импликация), (эквиваленция); 

6) кванторы (общности) и (существования); 

7) вспомогательные символы, такие как скобки, запятая, точка, 
точка с запятой. 

Арность предикатного или функционального символа – это неотрицательное целое число, указывающее количество аргументов, с 
которыми будет использоваться этот символ. Предикатные символы и 
функторы арности n будут обозначаться в виде p/n или f/n (с синтаксической точки зрения обозначения одинаковы). Символы p и f называются также именами предикатов или функторов.  

Пусть A – алфавит языка логики предикатов.  
Объекты, между которыми описываются отношения в программе, представляются термами. Понятие терма определяется индуктивно. 

Определение. Терм над алфавитом A – это переменная, константа или выражение вида f(t1, t2, …, tn), где f/n – функциональный 
символ и t1, t2, …, tn – термы над алфавитом A.  

Определение. Константы и переменные называются простыми 
термами, остальные термы – сложными, или составными.  

Определение. Терм, не содержащий переменных, называется 
основным термом.  

Пусть T – множество термов над алфавитом A. 

Определение. Формула определяется индуктивно: 

1) выражение p(t1, t2, …, tn), где p/n – предикатный символ из A 
и t1, t2, …, tn – термы из T, является формулой; 

2) каждое из выражений (F & G), (F G), (F), (F G), (G 
F), (F G), (F), где F и G – формулы, является формулой; 

3) выражения X(F) и X(F), где X – переменная из A и F – 
формула, являются формулами.  

Ниже скобки иногда будут опускаться. Кроме того, используются следующие приоритеты относительно символов логических связок 
и кванторов: сначала , , затем , затем &, затем , после этого () и, наконец, . 

Определение. Подвыражение, входящее в формулу F и являющееся формулой, называется ее подформулой.  

Определение. Формула, не содержащая переменных, называется 
основной формулой.  

Определение. Формула вида p(t1, t2, …, tn), где p – имя предиката, 
а t1, t2, …, tn – термы, называется атомарной формулой.  

Определение. Атомарная формула или ее отрицание называются 
литералом. 

Атомарная формула называется также положительным литералом, а ее отрицание – отрицательным литералом. 

Определение. Вхождение переменной X в формулу F называется связанным, если она входит только в ее подформулы вида X(G) 
или X(G), где G – формула. Если переменная в формуле не связана 
квантором, то она называется свободной.  

Определение. Формула, не содержащая свободных переменных, 
называется замкнутой. 

Определение. Предложение – это замкнутая формула. 

Пусть F – формула и X1, X2, …, Xn – все ее свободные переменные. Тогда формула X1X2 …Xn F будет коротко записываться 
в виде F. Формула F называется универсальной формулой. 

Очевидно, что формула F является замкнутой. 

Определение. Терм t называется свободным для переменной X   
в формуле F, если после замены всех свободных вхождений X на t все 
свободные переменные терма t остаются свободными.  

Определение. Пусть F – множество всех формул над алфавитом A. Языком логики предикатов первого порядка называется подмножество множества F. 

Пример 1. Утверждения «Лебедь – это птица» и «Каждая птица – это животное» на языке логики предикатов первого порядка над 
алфавитом A = {"swan", bird/1, animal/1} можно записать соответственно следующим образом: 

bird("swan"); 

X(bird(X) animal(X)). 

Здесь "swan" – константа, а bird и animal – имена унарных предикатных символов. 

1.1.2. Семантика формул 

Рассмотрим семантику формул. Аналогично тому, как утверждения естественного языка, описывающие реальный мир, могут быть 
истинными или ложными в этом мире, значение логической формулы 

также интерпретируется как истинное или ложное в некотором абстрактном мире, который представляется алгебраической системой. Таким образом, интерпретация определяет соответствие между множеством формул и некоторой алгебраической системой. Непустую 
область интерпретации называют доменом. 

Определение. Интерпретацией алфавита A называется пара, 
состоящая из домена D и функции, которая ставит в соответствие: 

1) константе c – элемент (c) из D; 

2) функциональному символу f/n – функцию (f): Dn D; 

3) предикатному символу p/n – отношение (p) Dn. 

Пример 2. Пусть A = {"swan", bird/1, animal/1}, D = {лебедь, 
воробей, слон} и – функция, такая что  

("swan") = лебедь; 

(bird) = {лебедь, воробей}; 

(animal) = {лебедь, воробей, слон}, 

где (bird) и (animal) – унарные отношения на D. Тогда пара (D, ) 
является интерпретацией алфавита A. 

Значением формулы является элемент множества {true, false}, 
который называется истинностным значением. Если значение формулы F в интерпретации равно true, то используют обозначение ; если оно равно false, то пишут F. Ясно, что значение 
основных формул зависит только от интерпретации. 
Будем использовать символы и как метасимволы, означающие соответственно «тогда и только тогда» и «влечет».  

Определение. Значение замкнутой формулы определяется следующим образом: 

1) p(t1, t2, …, tn) ((t1), (t2), …, (tn)) (p); 

2) F & G F и G; 

F G F или G; 

F F; 

F G G или F; 

F G F и G, либо F и G,