Системы искусственного интеллекта. Тематический план
 Скачать 1.4 Mb.
|
|
ТЕМА 2.2 КРАТКОЕ ВВЕДЕНИЕ В ИСЧИСЛЕНИЕ ПРЕДИКАТОВ И ДОКАЗАТЕЛЬСТВО ТЕОРЕМ Высказывание — это логическое утверждение, которое может быть истинным или ложным. Оно состоит из объектов и отношений между ними. Символьную логику (symbolic logic) можно использовать для решения трех основных задач формальной логики: для выражения высказываний, выражения отношений между высказываниями и описания способов вывода новых высказываний из других высказываний, считающихся истинными. Объекты в высказываниях логического программирования представляются простыми термами, являющимися либо константами, либо переменными. Константа — это символ, представляющий некий объект. Переменная — это символ, который может представлять разные объекты в разное время, хотя в некотором смысле переменная в этом контексте намного ближе к математическому пониманию переменной, чем к переменным в императивных языках программирования. Простейшие высказывания, называемые атомарными высказываниями, состоят из составных термов. Составной терм — это элемент математического отношения, формально записанного в виде математической функции. Составной терм состоит из двух частей: функтора (functor), представляющего собой функциональный символ, называющий отношение, и упорядоченного списка параметров. Примеры: человек (Джек) любит (Боб, стейк) Высказывания можно формулировать двумя способами: в первом случае высказывание считается истинным, а во втором истинность высказывания требуется установить. Иными словами, высказывания можно формулировать либо как факты, либо как запросы. Высказывания в примерах, приведенных выше, могут представлять собой как факты, так и запросы. Исчисление предикатов дает нам метод для выражения совокупностей высказываний. Использовать совокупности высказываний — это означает определять, можно ли вывести из них какие-нибудь интересные или полезные факты. Последнее аналогично работе математиков, старающихся открыть новые теоремы, которые можно вывести из уже известных аксиом и теорем. В 1950-х — начале 1960-х гг. процессу автоматического доказательства теорем уделялось большое внимание. Одним из крупных научных достижений в этой области было открытие принципа резолюции (resolution) Аланом Робинсоном (Alan Robinson) из Сиракузского университета. Резолюция (resolution) — это правило логического вывода, позволяющее вычислять выводимые высказывания по заданным высказываниям, обеспечивая таким образом метод, имеющий потенциальные приложения в области автоматического доказательства теорем. Резолюция была изобретена для применения к высказываниям в дизъюнктивной форме. Концепция резолюции заключается в следующем. Предположим, что нам даны два высказывания в следующих формах: Старше (Джоанна, Джек) => мать (Джоанна, Джек) мудрее (Джоанна, Джек) => старше (Джоанна, Джек) По этим высказываниям, используя резолюцию, можно построить новое высказывание: мудрее (Джоанна, Джек) => мать (Джоанна, Джек) Механизм этой резолюции прост: термы в левых частях этих двух высказываний объединяются с помощью логической операции «И», образуя левую часть нового высказывания. Затем точно так же формируется правая часть нового высказывания: Старше (Джоанна, Джек) И мудрее (Джоанна, Джек) => => мать (Джоанна, Джек) И старше (Джоанна, Джек) Далее терм, появляющийся в обеих частях нового высказывания, удаляется из них («сокращается»): Мудрее (Джоанна, Джек) => мать (Джоанна, Джек) Этот процесс применим и тогда, когда высказывания содержат составные термы в одной или в обеих частях. Левая часть нового выведенного высказывания вначале содержит все термы левых частей двух заданных высказываний; новая правая часть также конструируется аналогично. Затем термы, появляющиеся в обеих частях нового высказывания, удаляются. В действительности резолюция представляет собой более сложный процесс, чем показано в этом простом примере. В частности, наличие переменных в высказываниях требует выполнять в процессе резолюции поиск значений этих переменных, что приводит к процессу поиска соответствий. Этот процесс определения полезных значений переменных называется унификацией, а временное присваивание значений переменным с целью унификации называется конкретизацией. Обычно во время резолюции переменная конкретизируется неким значением, не полностью удовлетворяющим требуемому соответствию, а затем следует отменить последнее действие и конкретизировать эту переменную новым значением. Крайне важное свойство резолюции — ее способность обнаруживать любое противоречие в заданной совокупности высказываний. Это свойство позволяет использовать резолюцию для доказательства теорем следующим образом. В терминах исчисления высказываний мы можем представить себе доказательство теоремы как заданную совокупность соответствующих высказываний, в которых отрицание теоремы само по себе формулируется в виде нового высказывания. Таким образом, теорема отрицаема, так что можно использовать резолюцию для доказательства этой теоремы, обнаружив противоречие. Это — доказательство от противного. Обычно исходные высказывания называются гипотезами, а отрицание теоремы — целью. ТЕМА 2.3 ПРОЦЕСС ЛОГИЧЕСКОГО ВЫВОДА В ЯЗЫКЕ PROLOG Для эффективного использования языка Prolog требуется, чтобы программист точно знал, что именно делает система языка Prolog с его программой. Запросы в Prolog называются целями (goal). Когда цель представляет собой составной оператор, каждый из входящих в нее фактов (структур) называется подцелью (subgoal). Для доказательства того, что цель истинна, процесс логического вывода должен найти цепочку правил логического вывода и/или факты в базе данных, которые связывают цель с одним или несколькими другими фактами в базе данных. Так как доказательство подцели осуществляется с помощью поиска соответствия между высказываниями, иногда его называют сопоставлением. Рассмотрим следующий запрос: man(bob). Эта цель имеет простейший вид. Она относительно проста для того, чтобы резолюция определила, истинно ли это высказывание или ложно: образец этой цели сравнивается с фактами и правилами в базе данных. Если факт man(bob). содержится в базе данных, то доказательство является тривиальным. Допустим, однако, что в базе данных содержатся приведенные ниже факт и правило логического вывода: father (bob). man(X) :- father(X). Тогда можно потребовать, чтобы система языка Prolog нашла два эти утверждения и использовала их для логического вывода истинности цели. Это может привести к необходимости выполнить унификацию, чтобы временно конкретизировать переменную X значением bob. Рассмотрим теперь цель man(X). В этом случае система языка Prolog должна сравнить заданную цель с высказываниями, хранящимися в базе данных. Первое обнаруженное высказывание, имеющее форму указанной цели с любым объектом в качестве параметра, приведет к конкретизации переменной X значением этого объекта. Если же в базе данных нет высказываний, имеющих форму указанной цели, то система отмечает, что цель не может быть достигнута, отвечая «No». Существуют два противоположных подхода к сравнению заданной цели и факта в базе данных. Система может начать поиск с фактов и правил, хранящихся в базе данных, и попытаться найти последовательность совпадений, ведущую к цели. Этот подход называется резолюцией снизу вверх, или прямым выводом (forward chaining). Альтернативный подход заключается в том, что система, наоборот, начинает поиск с цели и пытается найти последовательность соответствующих высказываний, ведущую к некоторому множеству исходных фактов, хранящихся в базе данных. Этот подход называется резолюцией сверху вниз, или обратным выводом (backward chaining). Обратный вывод хорошо работает, когда существует небольшой набор возможных ответов. Прямой же вывод работает лучше, когда количество возможных правильных ответов велико; в этой ситуации при обратном выводе для получения ответа может потребоваться очень большое количество сопоставлений. Существующие реализации языка Prolog используют для резолюции обратный вывод, предположительно потому, что их разработчики думали, будто обратный вывод подходит для более широкого класса задач, чем прямой вывод. Снова рассмотрим тот же пример запроса: man(bob). Предположим, что база данных содержит следующий факт и правило вывода: father(bob). man(X) :- father(X). При прямом выводе система должна отыскать первое высказывание. Тогда логический вывод цели осуществляется следующим образом: переменная X конкретизируется значением bob, первое высказывание сопоставляется с правой частью второго правила father(X), а затем левая часть второго высказывания сопоставляется с целью. При обратном же выводе следует сначала сопоставить цель с левой частью второго высказывания man(X), конкретизировав переменную X значением bob. Тогда на последнем этапе система должна сопоставить правую часть второго высказывания father(bob) с первым высказыванием. Еще одна сложность, относящаяся к разработке языка, возникает всякий раз, когда цель имеет несколько структур (как в примере, приведенном выше). В этом случае вопрос заключается в том, как именно надо выполнять поиск, — сначала в глубину или в ширину? При поиске сначала вглубь (depth-first search) система находит полную цепочку высказываний (доказательство) для первой подцели раньше, чем приступить к работе над остальными подцелями. При поиске сначала вширь (breadth-first search) система работает над всеми подцелями параллельно. Разработчики языка Prolog выбрали в качестве основного способа поиск сначала вглубь, поскольку он требует меньше компьютерных ресурсов, тогда как поиск сначала вширь требует реализации параллельных вычислений и может потребовать наличия большого объема памяти. Последнее свойство механизма резолюции в языке Prolog, которое нам следует обсудить, — бэктрекинг (backtracking). При обработке цели с несколькими подцелями, если система не способна доказать истинность одной из подцелей, то она отказывается от обработки этой подцели, которую не способна доказать. Вместо этого система заново рассматривает предыдущую подцель (если она является единственной) и пытается найти ее альтернативное решение. Это восстановление предшествующего состояния цели для пересмотра ранее доказанной подцели и называют «бэктрекингом» («откатом»). Новое решение отыскивается в результате поиска, предпринятого с того места, где остановился предыдущий поиск для этой подцели. Множественность решений для подцели является результатом наличия различных конкретизаций ее переменных. Следует заметить, что бэктрекинг требует больших затрат времени и объема памяти, поскольку он может найти все возможные решения для каждой подцели. К тому же эти доказательства подцелей могут оказаться недостаточно организованными, чтобы минимизировать объем времени, которое требуется для поиска окончательного решения, что еще больше обостряет проблему. Чтобы укрепить наше понимание бэктрекинга, рассмотрим следующий пример. Пусть в базе данных есть совокупность фактов и правил, а в системе языка Prolog представлена следующая составная цель: male(X), parent(X, "Shelley"). В этой цели спрашивается, существует ли какая-либо конкретизация переменной X, определяющая, что X является мужчиной (male) и родителем (parent) некоего Шелли (Shelley). Система языка Prolog сначала должна найти в базе данных первый факт с функтором male. Затем она конкретизирует переменную X параметром найденного факта (скажем, параметром Mike) и далее пытается доказать, что высказывание parent("Mike","Shelley") является истинным. Если же это не удается сделать, то она возвращается к первой подцели male(X) и пробует снова удовлетворить ее с помощью некоторой альтернативной конкретизации переменной X. Может оказаться, что, выполняя процесс резолюции, система должна будет просмотреть каждого мужчину в базе данных, прежде чем она найдет одного из них, являющегося родителем Шелли. Более того, система обязательно должна просмотреть в базе всех мужчин, чтобы доказать, что цель не может быть удовлетворена. Заметим, однако, что наш пример цели можно решить более эффективно, если порядок следования двух подцелей поменять местами: только после того, как система с помощью резолюции найдет родителя Шелли, пытаться найти лицо с подцелью male. Этот способ эффективен, если у Шелли меньше родителей, чем мужчин в базе данных, — что, конечно же, вполне правдоподобно. Система языка Prolog всегда выполняет поиск в базе данных в направлении от первого элемента к последнему. ТЕМА 2.4 СТРУКТУРА ПРОГРАММЫ НА ЯЗЫКЕ PROLOG Программа, написанная на языке Prolog, состоит из следующих разделов: описание доменов, база данных, описание предикатов, описание цели и описание утверждений. Начала этих разделов отмечают ключевые слова domains, database, predicates, goal и clauses. Назначение указанных разделов: - раздел domains содержит определения доменов, которые описывают различные классы объектов, используемых в программе; - раздел database содержит утверждения базы данных, которые являются предикатами динамической базы данных; если программа не требует наличия такой базы данных, то этот раздел может быть опущен (возможности использования динамической базы данных будут рассмотрены позже); - раздел predicates служит для описания используемых программой предикатов; - в разделе goal формулируется назначение создаваемой программы; составными частями при этом могут являться некие подцели, из которых формируется единая цель программы; - в раздел clauses заносятся факты и правила, известные априорно; о содержимом этого раздела можно говорить как о данных, необходимых для работы программы. Заметим, что большинство программ не обязательно содержит все пять названных разделов. Язык Prolog также обеспечивает возможность включения в программу комментариев, которые обрамляются символами /* и */. Приведем пример описания доменов и предикатов. Рассмотрим отношение «любит» между двумя объектами (пусть это будут имя человека и название вещи, которую любит этот человек). Ранее уже приводилось несколько примеров использования предиката likes, например, likes("Mary", apples). Здесь likes является предикатом (термом предиката), а Mary и apples — объектами этого предиката. Prolog требует указания типов объектов для каждого предиката программы. Некоторые из этих объектов могут быть, к примеру, числовыми данными, а другие — символьными строками. Поэтому в разделе predicates необходимо задать тип объектов каждого из предикатов: predicates likes (symbol, symbol) Это описание означает, что оба объекта предиката likes относятся к типу symbol, который является одним из базисных типов в Prolog (другие базисные типы будут рассмотрены ниже). В некоторых случаях, однако, представляется необходимым иметь возможность несколько большей конкретизации типа используемого предикатом объекта. Например, в предикате likes объекты имеют смысл «тот, кто любит» и «вещь, которую любят». Для этого язык Prolog позволяет конструировать свои собственные типы объектов из базисных типов доменов. Например, в разделе программы domains могут появиться такие описания: domains person, thing = symbol predicates likes (person, thing) Имена person и thing при этом будут обозначать некие совокупности (домены) значений. Рассмотрим, например, следующие три утверждения: likes("John",camera). likes("Tom",computer). likes("Kathy",computer). Термы John, Tom и Kathy принадлежат здесь к домену person, а термы camera и computer — к домену thing. Все три эти утверждения восходят к одному и тому же предикату — likes, отличие же состоит лишь в значениях, которые принимают объекты. Другими словами, все три утверждения являются вариациями одного и того же предиката. Вернемся к описанию доменов. Prolog имеет несколько встроенных типов доменов: символы (все возможные отдельные символы), целые числа, действительные числа, строки (последовательности символов), символические имена (последовательности букв, цифр и знаков подчеркивания, где первый символ — строчная буква, либо последовательности любых символов, заключенных в кавычки) и файлы. Тип каждого из доменов должен быть объявлен в разделе программы domains. Ранее было отмечено, что в раздел clauses заносятся факты и правила, причем каждый факт завершается символом «точка». Примеры: clauses likes ("John", camera). Likes ("Tom", computer). Likes ("Kathy", computer). Рассмотрим особенности использования целей. Далеко не каждая из программ на языке Prolog содержит внутри себя описание своей цели (внутреннюю цель), — часто цель задается в процессе работы программы, т. е. является внешней. Внутренние цели — это цели поиска, которые задаются в самой программе. Цель при этом может состоять из нескольких подцелей, разделенных запятой (логический союз «И») или точкой с запятой (логический союз «ИЛИ»). Завершается цель точкой. Для вывода на экран во внутренних целях используется встроенный предикат write, аргументами которого могут быть строковые константы (заключенные в кавычки) и имена переменных; такие аргументы можно произвольно комбинировать. Примеры: write ("Любимые вещи:"), write (X), nl, write (Y, "любит", Z) Встроенная операция nl при этом позволяет осуществлять перевод курсора на новую строку. Внешние цели. В формулировке запроса к программе можно использовать несколько переменных. Тогда программа выдаст все возможные комбинации значений переменных (предикат write для этого использовать не надо). Пример: /* Демонстрация структуры программы */ domains person, thing = symbol predicates likes (person, thing) clauses likes ("John", camera). likes ("Tom", computer). likes ("Kathy", computer). goal write ("Что же любит Tom?"), nl, likes ("Tom", X), write ("Tom любит", X). Запросы строятся из предикатов, содержащих условия, которые ограничивают пути поиска желаемых результатов, причем в случае, когда какой-либо запрос нужно повторить несколько раз, разумно предусмотреть возможность не задавать всякий раз одни и те же условия. Полезно также для получения ответов из базы данных не использовать факты из базы данных. В языке Prolog эта задача решается конструированием правил, не содержащих в себе данных, т. е. правил нулевой арности. Пример. Представим некую гипотетическую семью, где Фрэнк и Мэри являются мужем и женой, их сына зовут Сэмом, а дочку — Дебби. Ниже приведен диалог, касающийся этой семьи. Вопрос: Кем приходятся друг другу Дебби и Сэм? Ответ: Дебби — сестра Сэма. Вопрос: Из чего вы это заключили? Ответ: У Дебби и Сэма одни и те же родители, Дебби — девочка. Таким образом, Дебби — сестра Сэма. Второй из этих вопросов является разговорной формулировкой правила, которое будет использоваться для ответа на запрос. Это правило можно перефразировать таким образом: Дебби — сестра Сэма, если Дебби — существо женского пола и родители Дебби есть родители Сэма. Эта фраза включает в себя условие «если» (if, может быть обозначено комбинацией символов :- ), которое логически связывает оба утверждения. Утверждение, предшествующее «если», называется заключением, или логическим следствием, а утверждение, следующее за «если», — допущением, или предпосылкой. Правило, задающее отношение «брат – сестра», тогда выглядит следующим образом: sister (Sister, Brother) if female (Sister), parents (Sister, Father, Mother), parents (Brother, Father, Mother). Пример программы: /* Демонстрация конструкции правила */ domains person = symbol predicates male(person) female(person) parents(person, person, person) sister(person, person) who_is_the_sister goal who_is_the_sister. clauses male ("Frank"). Male ("Sam"). Female ("Mary"). Female ("Debbie"). Parents ("Sam", "Frank", "Mary"). Parents ("Debbie", "Frank", "Mary"). who_is_the_sister if sister (Sister, Brother), write(Sister, "is the sister of", Brother,"."), nl. Sister (Sister, Brother) :female (Sister), parents (Sister, Father, Mother), parents(Brother, Father, Mother). Использование составных объектов Рассмотрим факт student ("Иванов", 14, 05, 1980). При таком задании факта оказывается непонятным назначение последних трех объектов. На самом деле они представляют собой дату рождения студента Иванова. Более определенно описать этот объект можно следующим образом: student ("Иванов", birthday (14, 05, 1980)). Объект, представляющий собой другой объект или совокупность объектов, называется составным объектом. Пример: /* Описание составного объекта */ domains date = birthday (integer, integer, integer) predicates student (symbol, date) clauses student ("Иванов",birthday (14, 05, 1980)). student ("Петров",birthday (30, 12, 1981)). student ("Сидоров",birthday (29, 05, 1981)). goal student ("Иванов", X), write("Дата рождения Иванова: ",X). Если необходимо определить только год рождения студента, то цель будет выглядеть так: student ("Иванов", birthday (_,_,Y)), write("Год рождения Иванова: ",Y). Обратите внимание, что переменная, в определении значения которой нет необходимости, называется анонимной переменной и обозначается знаком подчеркивания. Использование альтернативных доменов Представление данных часто требует наличия большого числа структур. В Prolog эти структуры должны быть описаны с помощью альтернативного описания доменов. Пример: /* Использование альтернативных доменов. Для разделения альтернативных доменов применена точка с запятой (;) */ domains thing = misc_thing(whatever); book(author,title); record(artist,album,type) person, whatever, author, title, artist, album, type = symbol predicates owns (person, thing) clauses owns ("Иванов", misc_thing("Piano")). owns ("Петров", book("J.R.R. Tolkien", "Return of the Ring")). owns ("Сидоров", record("Elton John", "Ice Fair", "popular")). |