Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Теория и практика логического программирования на языке Visual Prolog 7

Учебное пособие для вузов
Покупка
Артикул: 415135.02.01
Рассмотрены теоретические основы логического програм- мирования. Даны примеры и описание предметной области с помощью логических моделей. Показана связь базовых поня- тий логики предикатов и основных конструкций языка логиче- ского программирования Пролог. Изложены основы логиче- ского программирования на примере языка Visual Prolog 7. Рассмотрены структура программы, алгоритм работы интерпре- татора, ввод – вывод, приемы и средства организации интерак- тивных программ, вопросы недетерминированного программи- рования и управления выполнением программы, различные структуры данных и предикаты работы с ними. Книга содер- жит многочисленные примеры, а также контрольные вопросы и практические задания. Пособие будет полезно при изучении курса «Функциональное и логическое программирование». Для студентов высших учебных заведений, программи- стов, специалистов в области искусственного интеллекта и баз данных.
Цуканова, Н. И. Теория и практика логического программирования на языке Visual Prolog 7: Учебное пособие для вузов / Цуканова Н.И., Дмитриева Т.А. - Москва : Гор. линия-Телеком, 2013. - 232 с. (Учебное пособие для высших учебных заведений)ISBN 978-5-9912-0194-0. - Текст : электронный. - URL: https://znanium.com/catalog/product/414543 (дата обращения: 16.06.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Н. И. Цуканова 
Т. А. Дмитриева 
 
 
 
 
 
 
Теория и практика логического 
программирования на языке 
Visual Prolog 7 
 
 
 
Допущено УМО вузов по университетскому 
политехническому образованию в качестве учебного 
пособия для студентов высших учебных заведений, 
обучающихся по специальности 230105 – «Программное 
обеспечение вычислительной техники  
и автоматизированных систем» 
 
 
 
 
 
 
 
Москва 
Горячая линия - Телеком 
2013 

УДК 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 

ПРЕДИСЛОВИЕ 

В последние годы значительно возрос интерес к работам по искусственному интеллекту, особенно к практическому воплощению результатов 
этих работ в экспертных системах. Одной из наиболее важных задач, связанных с проектированием таких систем, является проблема представления знаний о предметной области. Исследования развиваются в двух направлениях: первое связано с выбором формализованных моделей представления знаний; второе – с разработкой и внедрением языков представления знаний, обладающих необходимыми изобразительными средствами. 
В настоящее время большую популярность приобрел язык логического 
программирования Пролог, основанный на самой старой модели представления знаний – исчислении предикатов первого порядка. Само название Пролог есть сокращение, означающее программирование на языке 
логики. 
Пролог предоставляет средства для описания знаний о предметной области в виде фактов и правил вывода. Он понятен экспертамнепрограммистам и даже с успехом может использоваться для обучения 
детей программированию. Пролог способствует формированию стиля программирования, основанного на идеях модульного программирования и 
программирования "сверху вниз". В то время как традиционные языки 
программирования являются процедурно-ориентированными, Пролог основан на описательной или декларативной парадигме в программировании. Это свойство коренным образом меняет программистское мышление 
и делает обучение программированию на Прологе увлекательным занятием, требующим определенных интеллектуальных усилий. 
Пролог применяется при создании приложений в следующих областях: 
• 
разработка быстрых прототипов прикладных программ; 
• 
разработка приложений, связанных с защитой информации; 
• 
управление производственными процессами; 
• 
создание динамических реляционных баз данных; 
• 
перевод с одного языка на другой; 
• 
реализация экспертных систем и оболочек экспертных систем. 
Системы программирования на Прологе эксплуатируются на ЭВМ самых разных типов и приобрели широкую известность благодаря наличию 
таких 
развитых 
версий 
на 
персональных 
компьютерах 
как 
WinProlog, Visual Prolog, Strawberry Prolog и Arity Prolog. В пособии рассматриваются примеры, подготовленные в среде Visual Prolog 5.2, 7.0 –
 7.3, приводятся правила и пример создания законченного приложения с 
графическим интерфейсом в среде Visual Prolog 7.0 – 7.3. Эти версии являются в настоящее время наиболее развитыми промышленными версиями, работающими в среде ОС Windows. 

 
Логическое программирование на языке Visual Prolog 

 4 

Пособие делится на одиннадцать глав. В гл. 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. 
Авторы выражают благодарность рецензентам, сделавшим ряд ценных 
замечаний при подготовке данного пособия. 

Глава 1. ВВЕДЕНИЕ В ТЕОРЕТИЧЕСКИЕ ОСНОВЫ 
ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ 

Язык Пролог разрабатывался как язык систем искусственного интеллекта, и в 1984 году в проекте вычислительных систем пятого поколения был объявлен как базовый язык [3]. 
Система искусственного интеллекта содержит два обязательных 
элемента – базу знаний (БЗ) и машину вывода [2], которые тесно связаны между собой положенной в их основу моделью представления 
знаний. 
Процесс работы системы искусственного интеллекта упрощенно 
можно описать следующим образом. На вход системы поступает вопрос пользователя B . Машина вывода, опираясь на хранимые в БЗ 
знания общего характера о предметной области 
1
A , 
2
A , …, 
n
A  и на 
данные, вводимые пользователем, осуществляет вывод ответа на поставленный вопрос. 
Для представления знаний о предметной области используются 
различные модели [2]. Одна из них – это логическая модель представления знаний [1]. В соответствии с ней знания о предметной области 
описываются логическими формулами 
1
A , 
2
A , …, 
n
A  и считаются 
истинными утверждениями – аксиомами. Эти формулы хранятся в базе 
знаний. Вопрос пользователя или цель решения задачи также выражается логической формулой B , которая является гипотезой, истинность 
или ложность ее доказывается машиной вывода. Машина вывода в 
процессе своей работы доказывает логическое следование B  из истинности 
1
A , 
2
A , …, 
n
A . 
Для того чтобы знания описывать на языке логики в наиболее естественной форме для пользователя-непрофессионала, был разработан 
язык Пролог. Для написания программы на этом языке надо знать и 
понимать всего три конструкции: факт, правило, вопрос. С их помощью можно описать все базовые логические операции: конъюнкцию, 
дизъюнкцию, импликацию и отрицание. Кроме того, Пролог позволяет 
писать программу на близком к естественному для пользователя языке 
(например, на русском языке). В основе языка Пролог лежит исчисление предикатов первого порядка, а именно, логические конструкции, 
приводимые к Хорновским дизъюнктам. Чтобы понять выразительные 
возможности основных утверждений языка, как работает машина вывода и что такое Хорновские дизъюнкты, вам следует внимательно 
прочитать эту первую главу. В ней рассматриваются теоретические 
основы языка Пролог. 

 
Логическое программирование на языке Visual Prolog 

 6 

1.1.  Формальная система 

В формальной логике разрабатываются методы правильных рассуждений, представляющих собой цепь умозаключений. Для описания 
рассуждений и лежащих в их основе закономерностей используются 
логические модели, базирующиеся на понятии формальной системы. 
Формальная система задаётся четвёркой вида 
>
=< T, P, A, B
M
 
Множество T  есть множество базовых элементов различной 
природы, например слов из некоторого ограниченного словаря, студентов некоторой группы, звуков определённого инструмента и т.д. 
Важно, что для множества T  существует некоторый способ определения принадлежности или не принадлежности произвольного элемента 
к этому множеству. Процедура такой проверки может быть любой, но 
за конечное число шагов она должна давать положительный или отрицательный ответ на вопрос, является ли x  элементом множества T . 
Обозначим эту процедуру П(Т). 
Множество P  есть множество синтаксических правил. С их помощью из элементов T  образуют синтаксически правильные совокупности (правильно построенные формулы – ППФ). Например, из 
слов ограниченного словаря строятся синтаксически правильные фразы и т.д. Декларируется существование процедуры П(P), с помощью 
которой за конечное число шагов можно получить ответ на вопрос, 
является ли совокупность X  синтаксически правильной. 
В множестве синтаксически правильных совокупностей (ППФ) выделяется некоторое множество A . Элементы A  называются аксиомами. Как и для других составляющих формальной системы, должна 
существовать процедура П(А) , с помощью которой для любой синтаксически правильной совокупности (ППФ) можно получить ответ на 
вопрос о принадлежности её к множеству A . 
Множество B  есть множество правил вывода. Применяя их к элементам A , можно получить новые синтаксически правильные совокупности, к которым снова можно применить правила из B . Так формируется множество выводимых в данной формальной системе совокупностей ППФ. Если имеется процедура П(B) , с помощью которой 
можно определить для любой синтаксически правильной совокупности (ППФ), является ли она выводимой, то соответствующая формальная система называется разрешимой. Это показывает, что именно правила вывода являются наиболее сложной составляющей формальной 
системы. 

 
Глава 1. Введение в теоретические основы логического программирования 
 
 7 

Для знаний, входящих в базу знаний (БЗ), можно считать, что множество A  образуют все информационные единицы, которые введены 
в базу знаний извне (экстенсиональная БЗ), а с помощью правил вывода из них выводятся новые производные знания (интенсиональная БЗ). 
Формальная система представляет собой генератор порождения новых 
знаний, образующих множество выводимых в данной системе знаний. 
Это позволяет хранить в БЗ лишь те знания, которые образуют множество A , а все остальные получать путём вывода. 
Формальное доказательство 
Формальное доказательство [1] определяется как конечная последовательность формул ППФ 
1
M , 
2
M , …, 
r
M , такая, что каждая формула 
i
M  либо является аксиомой, либо при помощи одного из правил 

вывода выводима из предшествующих ей формул 
j
M , где 
i
j < . Фор
мула t  называется теоремой, если существует доказательство, в котором она является последней, т.е. 
t
M =
r
. В частности, всякая аксиома 
является теоремой. Если t  есть теорема, то этот факт обозначается 

t
− , а знак −  является символом выводимости (получения) некоторой 

ППФ с помощью правил вывода [1]. 
Интерпретация 
Формальные системы (ФС) используются как модели некоторой 
реальности. Интерпретация представляет собой распространение исходных положений какой-либо формальной системы на реальный мир 
(см. рис. 1.1). 

 

Рис. 1.1. Интерпретация формальной системы 

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

 
Логическое программирование на языке Visual Prolog 

 8 

для каждой формальной системы всегда существовала, по крайней 
мере, одна интерпретация, в которой каждая теорема ФС была бы истинной. Чем больше интерпретаций, тем богаче ФС [1]. 
Доказательство и истинность 
Имеются 4 варианта (рис. 1.2) взаимоотношений между доказательством и значением истинности, поскольку формула, с одной стороны, 
может быть теоремой (Т) либо не теоремой (НТ), а с другой стороны, 
её интерпретация может быть истинной (И) или ложной (Л). 
 

 

Рис. 1.2. Связь между свойствами выводимости и истинности ППФ 

Если для любой интерпретации соблюдаются первый и четвертый 
варианты, то выбранная ФС хорошо описывает предметную область. 
Но это не всегда возможно. 
Второй вариант, когда формула доказуема и соответствует определенной интерпретации, значение которой ложно, говорит о том, что 
нет соответствия между ФС и предметной областью. Следует либо 
заменить ФС, либо исключить данную интерпретацию из рассмотрения. 
Наиболее сложный случай – третий. Ситуацию (НТ, И) трудно 
идентифицировать, т.к. не всегда есть процедура, позволяющая установить, что формула, описывающая истинную интерпретацию, не выводима в данной ФС. 
Свойства формальных систем 
1. Разрешимость. Если существует процедура 
)
(B
П
, позволяющая для любой ППФ установить, выводима ли она в данной ФС (является теоремой), то такая система называется разрешимой. 
2. Полнота в широком смысле слова. ФС называется полной в 
широком смысле слова, если любая выводимая ППФ общезначима 
(т.е. истинна в любой интерпретации) и, наоборот, любая общезначи
 
Глава 1. Введение в теоретические основы логического программирования 
 
 9 

мая ППФ является теоремой данной формальной системы (случай 
(Т, И)). 
3. Полнота в узком смысле слова. ФС называется полной в узком 
смысле слова, если присоединение к аксиомам не выводимых в ФС 
ППФ приводит к противоречию (случай (НТ, И)). 
4. Непротиворечивость. Любое логическое исчисление называется 
непротиворечивым, если в нём не выводимы никакие две ППФ, из которых одна является отрицанием другой. 
5. Независимость аксиом. Таким свойством обладает ФС, у которой все аксиомы независимы, т.е. не выводимы с помощью правил 
вывода из других аксиом.  
Пример формальной системы 
Пример 1.1. Формальная система ДН. 
Алфавит: M , I , U . 
Синтаксис: ППФ – это любая последовательность символов данного алфавита. 
Одна аксиома: MI . 
Правила вывода: 
 
правило 1: 
mIU
mI →
; 
правило 2: 
Mmm
Mm →
; 
 
правило 3: 
U
III →
; 
правило 4: 
→
UU
; 
где m  – ППФ. 
Примеры теорем: 
а) MI  (аксиома); 
б) MII  (правило 2 применено к а); 
в) MIII  (правило 2 применено к б);  
г) MIIIU  (правило 1 применено к в); 
д) MIUU  (правило 3 к применено г); 
е) MI  (правило 4 к применено д). 

1.2.  Исчисление высказываний 
как формальная система 

Исчисление высказываний (ИВ) 
В исчислении высказываний рассматриваются формулы, составленные из элементарных формул, соединённых некоторыми связками. 
Элементарные формулы интерпретируются как простые высказывания, записанные в виде повествовательных предложений естественного языка и принимающие два значения: истина (И) или ложь (Л). Если 
простое высказывание X  истинно, то говорят, что X  принимает значение И, если X  ложно – то Л. Символы И и Л называются истинностными значениями [1]. 

 
Логическое программирование на языке Visual Prolog 

 10 

Сложное высказывание имеет истинностное значение, однозначно 
определяемое истинностными значениями простых высказываний, из 
которых оно составлено. Например: "Если студент ложится поздно 
спать и пьет на ночь кофе, то утром он встает в дурном расположении 
духа или с головной болью". Это сложное высказывание состоит из 
следующих простых высказываний: 
"Студент ложится поздно спать"; 
"Студент пьет на ночь кофе"; 
"Утром студент встает в дурном расположении духа"; 
"Утром студент встает с головной болью". 
Обозначим сложное высказывание через X , а простые – соответственно через Y , Z , U , V . Тогда сложное высказывание запишется в 
виде X  = если Y  и Z , то U  или V . 
Для обозначения используемых в этом примере связок введем специальные символы: "если…то" → , "и" & , "или" ∪ . Тогда в символическом виде высказывание X  запишется так: 
→
=
)
&
(
Z
Y
X
 
)
(
V
U ∪
→
. 
Каждую логическую связку можно рассматривать как операцию, 
которая образует новое высказывание – сложное высказывание из более простых высказываний. Рассматриваются следующие логические 
связки (операции): 

• 
отрицание X ; X  истинно, когда X  ложно, и ложно, когда X  
истинно; 
• 
конъюнкция 
Y
X &
; 
Y
X &
истинно, когда X  и Y  оба истинны, 
в противном случае 
Y
X &
ложно; 
• 
дизъюнкция 
Y
X ∪
; 
Y
X ∪
ложно, когда X  и Y  оба ложны, в 
противном случае 
Y
X ∪
истинно; 
• 
импликация 
Y
X →
; 
Y
X →
 ложно, когда X  истинно, а Y  ложно, в противном случае 
Y
X →
истинно (
Y
X →
 читается, как "если 

X , то Y " или " X влечет Y "); 
• 
эквивалентность 
Y
X ↔
; 
Y
X ↔
 истинно, когда X  и Y  имеют 
одинаковые истинностные значения, в противном случае 
Y
X ↔
ложно. 
Всякое сложное высказывание можно записать в виде некоторой 
формулы, содержащей логические связки и символы, которые обозначают простые высказывания, называемые атомами. Для того чтобы 
узнать, истинно или ложно сложное высказывание, достаточно узнать 
истинностные значения всех атомов, из которых оно составлено. Для