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

Министерство науки и высшего образования Российской Федерации 

 
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 

 
 
 
 
 

Т.В. АВДЕЕНКО, М.Ю. ЦЕЛЕБРОВСКАЯ 
 
 
 
 
 
 
ВВЕДЕНИЕ В ИСКУССТВЕННЫЙ  
ИНТЕЛЛЕКТ И ЛОГИЧЕСКОЕ  
ПРОГРАММИРОВАНИЕ 

 
ПРОГРАММИРОВАНИЕ  
В СРЕДЕ VISUAL PROLOG 

 
Утверждено Редакционно-издательским советом университета 
в качестве учебного пособия 
 
 
 
 
 
 
 
 
 
 

НОВОСИБИРСК 

2020 

 

УДК 004.8(075.8) 
         А 187 
 
 

Рецензенты: 

М.Г. Зайцев, канд. физ.-мат. наук, доцент 

М.Ш. Муртазина, канд. филос. наук, доцент 

 
 
Работа подготовлена на кафедре ТПИ для студентов III курса ФПМИ  
(направления подготовки 01.03.02, 02.03.03) 

 
Авдеенко Т.В. 
А 187   
Введение в искусственный интеллект и логическое программирование. Программирование в среде Visual Prolog: учебное пособие / Т.В. Авдеенко, М.Ю. Целебровская. – Новосибирск: Изд-во НГТУ, 2020. – 64 с. 

 

ISBN 978-5-7782-4182-4 

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

УДК 004.8(075.8) 
 
 
 
ISBN 978-5-7782-4182-4  
 
 
 
© Авдеенко Т.В., Целебровская М.Ю., 2020 
© Новосибирский государственный 
    технический университет, 2020 

 

1. ОБЩИЕ СВЕДЕНИЯ О ЯЗЫКЕ  
ПРОГРАММИРОВАНИЯ ПРОЛОГ 

В отличие от подавляющего большинства других языков программирования Пролог (Prolog) обычно рассматривается в одном контексте 
с понятием «логическое программирование», которое, в свою очередь, 
является промежуточным этапом развития языков программирования в 
направлении ухода от «процедурности» ко все большей «декларативности», что соответствует основной идее развития методологии искусственного интеллекта (ИИ) [8]. Вероятно, в скором будущем человек, 
решая задачу, не будет задавать последовательность команд на некотором известном языке программирования (чисто процедурный подход), 
а станет описывать ее в совершенно абстрактных логических терминах, 
не оперирующих определениями «байт» или «указатель», т. е. он будет 
создавать модель анализируемой проблемы и пытаться получить положительные или отрицательные результаты этого анализа. Практическим 
результатом такого анализа может быть, например, автоматически генерируемая на основе созданной модели оптимизированная программа на 
процедурном языке (например, C++). 
Таким образом, можно констатировать, что Пролог не является языком программирования в чистом виде. С одной стороны, этот язык 
можно рассматривать как оболочку экспертной системы (ЭС), с другой – как интеллектуальную базу данных и, что самое важное, не реляционную. Математическая модель, лежащая в основе Пролога, довольно сложна, и по мощности системы формирования запросов к базе 
с этим языком не сравнится ни одна из коммерческих СУБД. 
Из сказанного следует, что Пролог является не процедурным, а декларативным языком программирования и относится к группе постобъектно-ориентированных языков – функциональным языкам. Человек 
лишь описывает структуру задачи, а Пролог-машина вывода сама ищет 

решение. Более того, здесь вообще не существует понятия последовательности команд, все это скрыто в математической модели языка. Однако заметим, что, хотя в идеальной модели Пролог-машины последовательность целей не играет роли, в ее конкретных реализациях от порядка следования целей зависит не только скорость работы программы, 
но часто и получаемый результат. 
Математическая модель Пролога основана на теории исчисления 
предикатов, в частности на процедурной интерпретации хорновых дизъюнктов, содержащих не более одного заключения, предложенной Робертом Ковальским из Эдинбурга [7]. Алан Колмероэ, автор языка Пролог, начал работы над полноценной компьютерной реализацией трудов 
Ковальского с 1972 года. Он составил алгоритм формального способа 
интерпретации процесса логического вывода и разработал систему автоматического доказательства теорем, которая была написана на Фортране. Она-то и послужила прообразом Пролога. Название «Пролог» произошло от Programmation en Loqicue – ЛОГическое ПРОграммирование. 
Вскоре появились первые компиляторы с этого языка, в частности прекрасная реализация Дэвида Уоррена для компьютера DEC-10 в Эдинбурге, ставшая своего рода стандартом вплоть до сегодняшнего дня. Эффективность этой версии заставила специалистов по искусственному 
интеллекту по-новому взглянуть на Пролог. В некоторых приложениях, 
типичных для Лиспа, таких как обработка списков, Пролог уже не уступал своему конкуренту, что и послужило в дальнейшем стимулом для 
ряда специалистов по логическому программированию к переходу на 
этот язык. 
В качестве типовых данных Пролог использует элементарные единицы данных, так называемые атомы – строки символов и числа. Из атомов составляются списки и бинарные деревья. Сама «программа» строится из последовательности фактов и правил, и затем формулируется 
утверждение, которое Пролог будет пытаться доказать с помощью введенных правил. Таким способом можно описывать очень сложные проблемы, которые будут решаться Прологом автоматически, т. е. алгоритм решения задачи (последовательность действий) строится автоматически в процессе интерпретации логической программы. Это происходит с помощью метода сопоставления и рекурсивного поиска. Рекурсия играет в Прологе большую роль. 
С распространением Пролога появилась возможность создавать интеллектуальные нереляционные базы знаний с иерархической структурой на основе стандартного механизма с гибкой организацией очень 

сложных запросов. Были написаны эффективные программы для решения переборных задач, в частности из области молекулярной биологии 
и проектирования СБИС, где требовалось учитывать либо сложные 
внутренние структуры, либо большое число правил, описывающих организацию объекта. Пролог хорошо зарекомендовал себя в качестве экспертной оболочки и при решении задач грамматического разбора. Что 
весьма характерно, первый высокопроизводительный компилятор этого 
языка (Эдинбургская версия) был написан на самом Прологе. И немудрено, ведь все формальные синтаксические описания грамматик в 
Бэкус-форме прекрасно записываются в терминах Пролога. 
Долгое время среди разработчиков этого языка шла напряженная 
борьба между сторонниками оригинальной семантики Пролога и специалистами, стремившимися пожертвовать ясной структурой языка ради 
повышения эффективности реализации. В частности, свою роль стала 
играть последовательность правил в базе данных. Дело в том, что нередко для получения быстрого ответа целесообразно использовать сначала, например, наиболее простые правила или наиболее эффективные 
с точки зрения человека. Программа на Прологе постепенно стала приближаться к обычным процедурным языкам. Немалую роль в этом сыграло и искусственно введенное понятие отсечения (реализуемое с по- 
мощью предиката «!»), своего рода аналог столь нелюбимого профессором Дейкстром оператора «go to». Теперь программист мог по своему 
усмотрению динамически отсекать бесплодные (по его мнению) ветви 
деревьев перебора, что приводило к многократному (на два-три порядка) повышению скорости работы программ, но при этом существенно нарушалась ясность ее структуры, и возникновению множества проблем, связанных с отладкой. 
К счастью, развитие вычислительной техники в сочетании с уникальной структурой языка дало свои результаты. При появлении первых 
параллельных компьютеров программисты, работающие на Прологе, 
быстро осознали пагубность различных «нововведений» типа оператора 
отсечения, лишавших язык оригинальной чистоты, и вернулись к первоначальной версии языка. Пресловутая последовательность правил перестала играть роль, так как появилась возможность вычислять их параллельно, а поскольку математическая теория Пролога не накладывает 
никаких требований на упорядоченность фактов и правил в базе, скорость работы программы стала линейно пропорциональной числу процессоров. Имеются бесплатные и коммерческие версии Пролога для реализаций на параллельных компьютерах, например, Densitron CS Prolog 

для транспьютеров, или Paralogic. В японском проекте компьютера пятого поколения все программное обеспечение создавалось на Прологподобном языке. 
Большинство свободно распространяемых версий Пролога для 
обычных однопроцессорных компьютеров сегодня или является усеченными подмножествами коммерческих продуктов, или поставляется бесплатно только для учебных и научных организаций. 
Перечислим некоторые из них: SWI-Prolog, Amzi!-Prolog. Знакомый 
многим программистам TurboProlog, разрабатывавшийся ранее фирмой 
Borland, теперь выступает под маркой PDC Prolog и реализован для 
DOS, Windows, OS/2 и UNIX. Правда, как недостатки (например, несовместимость с подавляющим большинством других диалектов этого 
языка), так и его достоинства (такие как удобная среда разработчика и 
быстрый компилятор) сохранились. Есть специальная версия для визуальной разработки Visual Prolog. На нем написана маленькая, простая и 
удобная Пролог-машина Prolog-Interface-Engine-PIE32. Именно на 
Visual Prolog рекомендуется выполнять практические задания, предлагаемые в настоящем учебном пособии. 
Современные профессиональные Пролог-системы обеспечивают 
скорость работы, не уступающую скорости выполнения аналогичных 
программ, написанных на Си (конечно, если не решать на Прологе задачи, подобные Фурье-преобразованию). 
В силу всех изложенных выше причин для знакомства студентов с 
функциональными языками рекомендуется язык Пролог. Общепризнано, что это наиболее простой для изучения язык и в то же время 
очень мощный инструмент для построения интеллектуальных систем. 
Все исследователи практически единогласно утверждают, что будущее – за функциональными языками. Примеры и задачи, описанные в 
учебном пособии, позволят студентам ознакомиться с наиболее перспективным на сегодняшний день направлением информатики, изучающим принципы функционирования и построения систем искусственного интеллекта. 

1.1. ВВЕДЕНИЕ В ПРОЛОГ 

Как было сказано выше, теоретической основой Пролога послужил 
раздел математической логики, называемый исчислением предикатов. 
Прологу присущ ряд свойств, которыми не обладают традиционные 
языки программирования: 
 механизм вывода с поиском и возвратом, 

 встроенный механизм сопоставления с образцом, 
 простая структура представления данных с возможностью их динамического изменения. 
Процесс разработки программы на языке Пролог представляет для 
программиста запись знаний о предметной области в виде фактов и правил в терминах языка и формулировку цели-вопроса, позволяющего после выполнения программы получить ответ на него в форме «доказано – 
не доказано». В отличие от традиционных процедурных языков программирования Пролог не дает возможности записывать в программе 
последовательность команд, обязательных для исполнения. Роль исполнителя со стандартными алгоритмами работы берет на себя встроенный 
механизм Пролога, который в зарубежной литературе называется Engine – движок Пролога (интерпретатор логической программы). Ниже 
мы рассмотрим алгоритмы работы движка, так как четкое понимание 
этих алгоритмов является залогом создания правильно и эффективно работающей программы на Прологе. 
После завершения работы Пролог-программы (доказательства цели) 
могут возникнуть только два состояния: «доказано – не доказано» [6]. 
Иногда они называются состояниями «Истинно» и «Ложно». Доказанное утверждение обычно является истинным, но это не обязательно, так 
как доказательство зависит от известных фактов и сделанных на их основе выводов. Итак, введены новые термины. 

1. Факт – утверждение, которое определяется как доказанное (всегда истинное). Например, факт «Мухтар – это собака» считается доказанным по определению. Но ответ на вопрос «Является ли Джек собакой?» не будет дан, так как утверждение «Джек – собака» не может быть 
доказано с помощью известных фактов. Отрицательный ответ системы 
Пролог означает вовсе не то, что утверждение «Джек – собака» ложно, 
а лишь то, что в Пролог-программе нет фактов о том, что Джек является 
собакой. Такой вид отрицания в Прологе называется отрицанием через 
неуспех. 

2. Вывод. Имея множество фактов, мы можем определять новые 
свойства описанных в них объектов, т. е. допускается вывод свойств из 
фактов. 
Вернемся к факту «Мухтар – это собака». Предположим, что мы хотим на основе известных фактов выявить все объекты, обладающие 
свойством «быть собакой». Задав вопрос «Кто является собакой?», получим ответ «Мухтар – это собака». Это тривиальный пример вывода. 
Введем некоторую дополнительную информацию: