Содержание.
Введение………………………………….……………………………….3
1. Основные производители……………………………………………..5
2. Историявозникновения и развития языка ПРОЛОГ……….……….6
3. Исчислениевысказываний…………………………………....………9
3.1.Исчисление предикатов…………………………………………….11
3.2.Программирование на ПРОЛОГЕ…………………………………14
3.3.Принцип резолюций……………………………………..…………16
3.4.Поиск доказательства в системе резолюций………………….…..18 Заключение……………………………………………………………….22
Списоклитературы………..…………………………………………..…24
Введение.
Программные средства, базирующиеся натехнологии и методах искусственного интеллекта, получили значительноераспространение в мире. Их важность, и, в первую очередь, экспертных систем инейронных сетей, состоит в том, что данные технологии существенно расширяюткруг практически значимых задач, которые можно решать на компьютерах, и их решениеприносит значительный экономический эффект. В то же время, технологияэкспертных систем является важнейшим средством в решении глобальных проблемтрадиционного программирования: длительность и, следовательно, высокаястоимость разработки приложений; высокая стоимость сопровождения сложныхсистем; повторная используемость программ и т.п. Кроме того, объединениетехнологий экспертных систем и нейронных сетей с технологией традиционногопрограммирования добавляет новые качества к коммерческим продуктам за счетобеспечения динамической модификации приложений пользователем, а непрограммистом, большей «прозрачности» приложения (например, знанияхранятся на ограниченном естественном языке, что не требует комментариев к ним,упрощает обучение и сопровождение), лучших графических средств,пользовательского интерфейса и взаимодействия.
По мнению специалистов, в недалекойперспективе экспертные системы будут играть ведущую роль во всех фазахпроектирования, разработки, производства, распределения, продажи, поддержки иоказания услуг. Их технология, получив коммерческое распространение, обеспечитреволюционный прорыв в интеграции приложений из готовыхинтеллектуально-взаимодействующих модулей.
Среди специализированных систем,основанных на знаниях, наиболее значимы экспертные системы реального времени,или динамические экспертные системы. На их долю приходится 70 процентов этогорынка.
Значимость инструментальных средствреального времени определяется не столько их бурным коммерческим успехом (хотяи это достойно тщательного анализа), но, в первую очередь, тем, что только спомощью подобных средств создаются стратегически значимые приложения в такихобластях, как управление непрерывными производственными процессами в химии,фармакологии, производстве цемента, продуктов питания и т.п., аэрокосмическиеисследования, транспортировка и переработка нефти и газа, управление атомными итепловыми электростанциями, финансовые операции, связь и многие другие.
Классы задач, решаемых экспертнымисистемами реального времени, таковы: мониторинг в реальном масштабе времени,системы управления верхнего уровня, системы обнаружения неисправностей,диагностика, составление расписаний, планирование, оптимизация,системы-советчики оператора, системы проектирования.
Коммерческие успехи к экспертным системами нейронным сетям пришли не сразу. На протяжении ряда лет (с 1960-х годов)успехи касались в основном исследовательских разработок, демонстрировавшихпригодность систем искусственного интеллекта для практического использования.Начиная примерно с 1985 (а в массовом масштабе, вероятно, с 1988-1990 годов), впервую очередь, экспертные системы, а в последние два года и нейронные сетистали активно использоваться в реальных приложениях.
1. Основные производители.
Инструментарий для создания экспертныхсистем реального времени впервые выпустила фирма Lisp Machine Inc в 1985 году.Этот продукт предназначался для символьных ЭВМ Symbolics и носил названиеPicon. Его успех привел к тому, что группа ведущих его разработчиков образовалафирму Gensym, которая, значительно развив идеи, заложенные в Picon, выпустила в1988 году инструментальное средство под названием G2. В настоящий моментработает его третья версия и подготовлена четвертая.
Еще в конце 1970-х годов стала отчетливопросматриваться тенденция к использованию в исследованиях в областиискусственного интеллекта «формальных» методов, т.е. основанных нааппарате математической логики. Эти методы противопоставлялись болееинтуитивным и менее формализованным эвристическим методам, скажем, таким,которые были использованы в системе MYCIN. Для того чтобы стало ясно, что всеэто значит, нужно познакомить вас с логическими языками, а затем показать, каксоотносятся их свойства с теми методами рассуждений, которые должныподдерживать типовые экспертные системы.
Математическая логика является формальнымязыком в том смысле, что в отношении любой последовательности символов онапозволяет сказать, удовлетворяет ли эта последовательность правиламконструирования выражений в этом языке (формулам). Обычно формальным языкампротивопоставляются естественные, такие как французский и английский, в которыхграмматические правила не являются жесткими. Утверждение, что логика являетсяисчислением с определенными синтаксическими правилами логического вывода, означает,что влияние одних членов выражения на другие зависит только от формы выраженияв данном языке и ни коим образом не зависит от каких-либо посторонних идей илиинтуитивных предположений.
Под автоматическим формированием сужденийпонимается поведение некоторой компьютерной программы, которая строитлогический вывод на основании определенных законов. Так, нельзя отнести кклассу программ автоматического формирования суждений программу, котораямоделирует подбрасывание монетки, чтобы определить, следует ли одна формула изнабора других. (В литературе также часто встречается термин автоматическаядедукция, равнозначный по смыслу термину автоматическое формирование суждений.)
При реализации автоматическогоформирования суждений, как правило, стремятся к максимально возможномуединообразию и стандартизации в представлении формул, но в то же время влитературе часто приходится сталкиваться с самыми разнообразными системамиобозначений, относящихся к логике. Основными синтаксическими схемамипредставления выражений являются конъюнктивная нормальная форма (conjunctivenormal form— CNF), полная фразовая форма (full clausal form) и фраза Хорна(Horn clause), последняя является подмножеством полной фразовой формы.
2. История возникновения иразвития языка ПРОЛОГ.
На протяжении многих тысячелетийчеловечество занимается накоплением, обработкой и передачей знаний. Для этихцелей непрерывно изобретаются новые средства и совершенствуются старые: речь,письменность, почта, телеграф, телефон и т. д. Большую роль в технологииобработки знаний сыграло появление компьютеров.
В октябре 1981 года Японское министерствомеждународной торговли и промышленности объявило о создании исследовательскойорганизации — Института по разработке методов создания компьютеров новогопоколения (Institute for New Generation Computer Technology Research Center).Целью данного проекта было создание систем обработки информации, базирующихсяна знаниях. Предполагалось, что эти системы будут обеспечивать простотууправления за счет возможности общения с пользователями при помощиестественного языка. Эти системы должны были самообучаться, использоватьнакапливаемые в памяти знания для решения различного рода задач, предоставлятьпользователям экспертные консультации, причем от пользователя не требовалосьбыть специалистом в информатике. Предполагалось, что человек сможетиспользовать ЭВМ пятого поколения так же легко, как любые бытовыеэлектроприборы типа телевизора, магнитофона и пылесоса. Вскоре вслед заяпонским стартовали американский и европейский проекты.
Появление таких систем могло бы изменитьтехнологии за счет использования баз знаний и экспертных систем. Основная сутькачественного перехода к пятому поколению ЭВМ заключалась в переходе отобработки данных к обработке знаний. Японцы надеялись, что им удастся неподстраивать мышление человека под принципы функционирования компьютеров, априблизить работу компьютера к тому, как мыслит человек, отойдя при этом от фоннеймановской архитектуры компьютеров. В 1991 году предполагалось создать первыйпрототип компьютеров пятого поколения.
Теперь уже понятно, что поставленные целив полной мере так и не были достигнуты, однако этот проект послужил импульсом кразвитию нового витка исследований в области искусственного интеллекта и вызвалвзрыв интереса к логическому программированию. Так как для эффективнойреализации традиционная фон неймановская архитектура не подходила, были созданыспециализированные компьютеры логического программирования PSI и PIM.
В качестве основной методологии разработкипрограммных средств для проекта ЭВМ пятого поколения было избрано логическоепрограммирование, ярким представителем которого является язык Пролог. Думается,что и в настоящее время Пролог остается наиболее популярным языкомискусственного интеллекта в Японии и Европе (в США, традиционно, болеераспространен другой язык искусственного интеллекта — язык функциональногопрограммирования Лисп).
Название языка «Пролог»происходит от слов ЛОГическое ПРОграммирование (PROgrammation en LOGique вофранцузском варианте и PROgramming in LOGic — в английском).
Пролог основывается на таком разделематематической логики, как исчисление предикатов. Точнее, его базис составляетпроцедура доказательства теорем методом резолюции для хорновских дизъюнктов.
В истории возникновения и развития языкаПролог можно выделить следующие этапы.
В 1965 году в работе «A machineoriented logic based on the resolution principle», опубликованной в 12номере журнала «Journal of the ACM», Дж Робинсон представил методавтоматического поиска доказательства теорем в исчислении предикатов первогопорядка, получивший название «принцип резолюции». На самом деле, идеяданного метода была предложена Эрбраном в 1931 году, когда еще не былокомпьютеров. Робинсон модифицировал этот метод так, что он стал пригоден дляавтоматического, компьютерного использования, и, кроме того, разработалэффективный алгоритм унификации, составляющий базис его метода.
В 1973 году «группа искусственногоинтеллекта» во главе с Аланом Колмероэ создала в Марсельском университетепрограмму, предназначенную для доказательства теорем. Эта программаиспользовалась при построении систем обработки текстов на естественном языке.Программа доказательства теорем получила название Prolog (от Programmation enLogique). Она и послужила прообразом Пролога. Ходят легенды, что автором этогоназвания была жена Алана Колмероэ. Программа была написана на Фортране иработала довольно медленно.
Большое значение для развития логическогопрограммирования имела работа Роберта Ковальского «Логика предикатов какязык программирования» (Kowalski R. Predicate Logic as ProgrammingLanguage. IFIP Congress, 1974), в которой он показал, что для того чтобыдобиться эффективности, нужно ограничиться использованием множества хорновскихдизъюнктов. Кстати, известно, что Ковальский и Колмероэ работали вместе втечение одного лета.
В 1976 г. Ковальский вместе с его коллегойМаартеном ван Эмденом предложил два подхода к прочтению текстов логическихпрограмм: процедурный и декларативный. Об этих подходах речь пойдет в третьейлекции.
В 1977 году в Эдинбурге Уоррен и Перейрасоздали очень эффективный компилятор языка Пролог для ЭВМ DEC–10, которыйпослужил прототипом для многих последующих реализаций Пролога. Что интересно,компилятор был написан на самом Прологе. Эта реализация Пролога, известная как«эдинбургская версия», фактически стала первым и единственнымстандартом языка. Алгоритм, использованный при его реализации, послужилпрототипом для многих последующих реализаций языка. Как правило, еслисовременная Пролог-система и не поддерживает эдинбургский Пролог, то в еесостав входит подсистема, переводящая прологовскую программу в«эдинбургский» вид. Имеется, конечно, стандарт ISO/IEC 13211– 1:1995,но его поддерживают далеко не все Прологсистемы.
В 1980 году Кларк и Маккейб в Великобританииразработали версию Пролога для персональных ЭВМ.
В 1981 году стартовал вышеупомянутыйпроект Института по разработке методов создания компьютеров нового поколения.
На сегодня существует довольно многореализаций Пролога. Наиболее известные из них следующие: BinProlog,AMZI-Prolog, Arity Prolog, CProlog, Micro Prolog, МПролог, Prolog-2, QuintusProlog, SICTUS Prolog, Silogic Knowledge Workbench, Strawberry Prolog, SWIProlog, UNSW Prolog и т. д.
В нашей стране были разработаны такиеверсии Пролога как Пролог-Д (Сергей Григорьев), Акторный Пролог (АлексейМорозов), а также Флэнг (А. Манцивода, Вячеслав Петухин).
Стерлинг и Шапиро в книге «Искусствопрограммирования на языке Пролог» пишут: «Зрелость языка означает,что он больше не является доопределяемой и уточняемой научной концепцией, астановится реальным объектом со всеми присущими ему пороками и добродетелями.Настало время признать, что хотя Пролог и не достиг высоких целей логическогопрограммирования, но, тем не менее, является мощным, продуктивным и практическипригодным формализмом программирования».
/>3. Исчисление высказываний.
Исчисление высказываний представляет собойлогику неанализируемых предположений, в которой пропозициональные константымогут рассматриваться как представляющие определенные простые выражения вроде«Сократ — мужчина» и «Сократ смертен». Строчные литеры р,q, r,… в дальнейшем будут использоваться для обозначения пропозициональныхконстант, которые иногда называют атомарными формулами, или атомами.
Ниже приведены все синтаксические правила,которые используются для конструирования правильно построенных формул (ППФ) висчислении высказываний.
(S. U) ЕслиU является атомом, то уявляется ППФ.
(S¬) Если U является ППФ, то —U такжеявляется ППФ.
(S. v) Если U и ф являются ППФ, то (U u ф)также является ППФ.
В этих правилах строчные буквы греческогоалфавита (например, U и ф) представляют пропозициональные переменные, т.е. неатомарные формулы, а любое простое или составное высказывание.Пропозициональные константы являются частью языка высказываний, которыйиспользуется для приложения исчисления пропозициональных переменных кконкретной проблеме.
Выражение -U читается как «неU», а (U v ф) читается как дизъюнкция «U или ф (или оба)». Можноввести другие логические константы — «л» (конъюнкция), «D»(импликация, или обусловленность), "=" (эквивалентность, илиравнозначность), которые, по существу, являются сокращениями комбинации трех приведенныхвыше констант. .
(U ^ ф) Эквивалентно¬(¬U v ф). Читается«U и ф».
(U />ф) Эквивалентно (¬U v ф). Читается«U имплицирует ф».
(U==ф) Эквивалентно (U/>ф)^(ф/>U). Читается «Uэквивалентно ф».
В конъюнктивной нормальной формеисчисления высказываний константы «импликация» и«эквивалентность» заменяются константами «отрицание» и«дизъюнкция», а затем отрицание сложного выражения раскрывается спомощью формул Де Моргана:
¬(U^ф) преобразуется в (¬Uv¬ф), ¬(U v ф)преобразуется в (-U^ф), ¬¬U преобразуется в U .
Последний этап преобразований — внесениедизъюнкций внутрь скобок: (£ v (U ^ф))) заменяется((£vU\(U)^(£vф)).
Принято сокращать вложенность скобочныхформ, отбрасывая в нормальной конъюнктивной форме знаки операций v и л. Нижепредставлен пример преобразования выражения, содержащего импликацию двухскобочных форм, в нормальную конъюнктивную форму.
¬(pvq)/>(-p^A-q) Исходное выражение.
¬¬(pvg)v(-p^- q) Исключение~.
(pvq)v(-p^- q) Ввод — внутрь скобок.
(¬pv(pvq))v(¬pv(pvq)) Занесение v внутрьскобок.
{{-p, р, q}, {¬q, р, q} } Отбрасывание А иv в конъюнктивной нормальной форме.
Выражения во внутренних скобках — это либоатомарные формулы, либо негативные атомарные формулы. Выражения такого типаназываются литералами, причем с точки зрения формальной логики порядоклитералов не имеет значения. Следовательно, для представления множествалитералов — фразы — можно позаимствовать из теории множеств фигурные скобки.Литералы в одной и той же фразе неявно объединяются дизъюнкцией, а фразы,заключенные в фигурные скобки, неявно объединяются конъюнкцией.
Фразовая форма очень похожа наконъюнктивную нормальную форму, за исключением того, что позитивные инегативные литералы в каждой дизъюнкции группируются вместе по разные стороныот символа стрелки, а затем символ отрицания отбрасывается. Например,приведенное выше выражение
преобразуется в две фразы:
p,q
в которых позитивные литералысгруппированы слева от знака стрелки, а негативные справа.
Более строго, фраза представляет собойвыражение вида
в котором p1..., рт q1,..., qn являютсяатомарными формулами, причем т=>0 и п=>0. Атомы в множестве р1,..., ртпредставляют заключения, объединенные операторами дизъюнкции, а атомы вмножестве q1 ..., qn — условия, объединенные операторами конъюнкции.
/>
3.1 Исчисление предикатов
Исчисление высказываний имеет определенныеограничения. Оно не позволяет оперировать с обобщенными утверждениями вроде«Все люди смертны». Конечно, можно обозначить такое утверждениенекоторой пропозициональной константой р, а другой константой q обозначитьутверждение «Сократ — человек». Но из (р л q) нельзя вывестиутверждение «Сократ смертен».
Для этого нужно анализироватьпропозициональные символы в форме предикатов и аргументов, кванторов и квантифщированныхпеременных. Логика предикатов предоставляет нам набор синтаксических правил,позволяющих выполнить такой анализ, набор семантических правил, с помощьюкоторых интерпретируются эти выражения, и теорию доказательств, котораяпозволяет вывести правильные формулы, используя синтаксические правиладедукции. Предикатами обозначаются свойства, такие как «бытьчеловеком», и отношения, такие как быть «выше, чем».
Аргументы могут быть отдельнымиконстантами, или составным выражением «функция-аргумент», котороеобозначает сущности некоторого мира интересующих нас объектов, или отдельнымиквантифицируемыми переменными, которые определены в этом пространстве объектов.Специальные операторы — кванторы — используются для связывания переменных иограничения области их интерпретации. Стандартными являются кванторы общности(V) и существования (3). Первый интерпретируется как «все», а второй— «кое-кто» (или «кое-что»).
Ниже приведены синтаксические правилаисчисления предикатов первого порядка.
Любой символ (константа или переменная)является термом. Если rk является символом k-местной функции и а1 ...,
(S 40
Если Tk является символом k-местногопредиката
и а1 ..., ak являются термами,
то U(а1 ..., ak) является правильнопостроенной формулой (ППФ).
(S. -) и (S. v)
Правила заимствуются из исчислениявысказывании.
(S. V) Если U является ППФ и % являетсяпеременной,
то (любой Х) U является ППФ.
Для обозначения используются следующиесимволы:
U — произвольный предикат;
Г — произвольная функция;
a — произвольный терм;
X — произвольная переменная.
Действительные имена, символы функций ипредикатов являются элементами языка первого порядка.
Использование квантора существованияпозволяет преобразовать термы с квантором общности в соответствии сопределением
(EX)U определено как -(любой X)-U.
Выражение (EХ)(ФИЛОСОФ(Х)) читается как«Кое-кто является философом», а выражение (любой Х)(ФИЛОСОФ(Х))читается как «Любой является философом». Выражение ФИЛОСОФ(Х)представляет собой правильно построенную формулу, но это не предложение,поскольку область интерпретации для переменной X не определена каким-либоквантором. Формулы, в которых все упомянутые переменные имеют определенныеобласти интерпретации, называются замкнутыми формулами.
Как и в исчислении высказываний, висчислении предикатов существует нормальная форма представления выражений, нодля построения такой нормальной формы используется расширенный набор правилсинтаксических преобразований. Ниже приведена последовательность применениятаких правил. Для приведения любого выражения к нормальной форме следуетвыполнить следующие операции.
(1) Исключить операторы эквивалентности, азатем импликации.
(2) Используя правила Де Моргана и правилазамещения (E X)U на -(любой X)-U (а следовательно, и (любой X) U на -(E X)-U),выполнить приведение отрицания.
(3) Выполнить приведение переменных. Приэтом следует учитывать особенности определения области интерпретации переменныхкванторами. Например, в выражении (E Х)(ФИЛОСОФ(Х))&(E Х)(АТЛЕТ(Х))переменные могут иметь разные интерпретации в одной и той же области. Поэтомувынесение квантора за скобки — (E Х)(ФИЛОСОФ(Х))&.(АТЛЕТ(Х))— даствыражение, которое не следует из исходной формулы.
(4) Исключить кванторы существования.Кванторы существования, которые появляются вне области интерпретации любогоквантора общности, можно заменить произвольным именем (его называют константойСколема), в то время как экзистенциальные переменные, которые могутсуществовать внутри области интерпретации одного или более кванторов общности,могут быть заменены функциями Сколема. Функция Сколема— это функция спроизвольным именем, которая имеет следующий смысл: «значение даннойпеременной есть некоторая функция от значений, присвоенных универсальным переменным,в области интерпретации которых она лежит».
(5) Преобразование в префиксную форму. Наэтом шаге все оставшиеся кванторы (останутся только кванторы общности)переносятся «в голову» выражения и таким образом оказываются слева всписке квантифицированных переменных. За ними следует матрица, в которойотсутствуют кванторы.
(6) Разнести операторы дизъюнкции иконъюнкции.
(7) Отбросить кванторы общности. Теперьвсе свободные переменные являются неявно универсально квантифицированнымипеременными. Экзистенциальные переменные станут либо константами, либофункциями универсальных переменных.
(8) Как и ранее, отбросить операторыконъюнкций, оставив множество фраз.
(9) Снова переименовать переменные, чтобыодни и те же имена не встречались в разных фразах./>/>
Исчисление предикатов в упрощенном виде.Там выражение вида
at(робот, комнатаА)
означает, что робот находится в комнате А.Термы робот и комнатаА в этом выражении представляли собой константы, которыеописывали определенные реальные объекты. Но что будет означать выражение вида
at(X, комнатаА) ,
в котором х является переменной? Означаетли оно, что нечто находится в комнате А? Если это так, то говорят, чтопеременная имеет экзистенциальную подстановку (импорт). А может быть, выражениеозначает, что все объекты находятся в комнате А? В таком случае переменнаяимеет универсальную подстановку. Таким образом, отсутствие набора четких правилне позволяет однозначно интерпретировать приведенную формулу.
Перечисленные в этом разделе правила исчисленияпредикатов обеспечивают однозначную интерпретацию выражений, содержащихпеременные.
В частности, фраза
at(X, комнатаА )
«для всех X X находится в комнате А,если X находится в ящике 1». В этой фразе переменная имеет универсальнуюподстановку. Аналогично, фраза
at(X, комнатаА)
Иными словами, это не тот случай, когда некоторыйобъект X находится в комнате А и, следовательно, переменная имеетэкзистенциальную подстановку.
Теперь можно преобразовать фразовую форму,в которой позитивные литералы сгруппированы слева от знака стрелки, анегативные — справа. Если фраза в форме
P1, ..., Рт
для всех x1, ..., хk
p1 или… или pm является истинным, еслиq1 и… и qn являются истинными.
Если п = 0, т.е. отсутствует хотя бы одноусловие, то выражение будет интерпретироваться следующим образом:
для всех x1, ..., xk
p1 или… или рт является истинным.
Если т = 0, т.е. отсутствуют термызаключения, то выражение будет интерпретироваться следующим образом:
для всех x1, ..., xk
не имеет значения, что q1 и… и qnявляются истинными.
Если же т = п = 0, то мы имеем дело спустой фразой, которая всегда интерпретируется как ложная.
3.2 Программирование на ПРОЛОГЕ.
При программировании на Прологе усилияпрограммиста должны быть направлены на описание логической модели фрагментапредметной области решаемой задачи в терминах объектов предметной области, ихсвойств и отношений между собой, а не деталей программной реализации.Фактически Пролог представляет собой не столько язык для программирования, сколькоязык для описания данных и логики их обработки. Программа на Прологе неявляется таковой в классическом понимании, поскольку не содержит явныхуправляющих конструкций типа условных операторов, операторов цикла и т. д. Онапредставляет собой модель фрагмента предметной области, о котором идет речь взадаче. И решение задачи записывается не в терминах компьютера, а в терминахпредметной области решаемой задачи, в духе модного сейчасобъектноориентированного программирования.
Пролог очень хорошо подходит для описаниявзаимоотношений между объектами. Поэтому Пролог называют реляционным языком.Причем «реляционность» Пролога значительно более мощная и развитая,чем «реляционность» языков, используемых для обработки баз данных.Часто Пролог используется для создания систем управления базами данных, гдеприменяются очень сложные запросы, которые довольно легко записать на Прологе.
В Прологе очень компактно, по сравнению симперативными языками, описываются многие алгоритмы. По статистике, строкаисходного текста программы на языке Пролог соответствует четырнадцати строкамисходного текста программы на императивном языке, решающем ту же задачу.Пролог-программу, как правило, очень легко писать, понимать и отлаживать. Этоприводит к тому, что время разработки приложения на языке Пролог во многихслучаях на порядок быстрее, чем на императивных языках. В Прологе легкоописывать и обрабатывать сложные структуры данных.
Прологу присущ ряд механизмов, которыми необладают традиционные языки программирования: сопоставление с образцом, вывод споиском и возвратом. Еще одно существенное отличие заключается в том, что дляхранения данных в Прологе используются списки, а не массивы. В языкеотсутствуют операторы присваивания и безусловного перехода, указатели.Естественным и зачастую единственным методом программирования являетсярекурсия. Поэтому часто оказывается, что люди, имеющие опыт работы напроцедурных языках, медленней осваивают декларативные языки, чем те, ктоникогда ранее программированием не занимался, так как Пролог требует иногостиля мышления, отказа от стереотипов императивного программирования.
Фразы Хорна (Horn clause) представляютсобой подмножество фраз, содержащих только один позитивный литерал. В общемвиде фраза Хорна представляется выражением
В языке PROLOG эта же фраза записывается втаком виде:
р :- q1,...,qn. Такая фразаинтерпретируется следующим образом:
«Для всех значений переменных в фразеp истинно, если истинны q1 и… и qn»,
т.е. пара символов ":-" читаетсякак «если», а запятые читаются как «и».
PROLOG — это не совсем обычный языкпрограммирования, в котором программа состоит в основном из логических формул,а процесс выполнения программы представляет собой доказательство теоремыопределенного вида.
Фраза в форме
р :- q1, ...,qn.
может рассматриваться в качествепроцедуры. Такая процедура предполагает следующий порядок выполнения операций.
(1) Литерал цели сопоставляется слитералом р (унифицируется с р), который называется головой фразы.
(2)Хвост фразы ql, ...,qn конкретизируетсяподстановкой значений переменных (или унификаторов), сформированных врезультате этого сопоставления.
(3) Конкретизированные термы хвостовойчасти образуют затем множество подцелей, которые могут быть использованыдругими процедурами.
Таким образом, сопоставление (илиунификация) играет ту же роль, что и передача параметров функции в других,более привычных языках программирования.
Например, рассмотрим набор фраз языка PROLOG,представленных в листинге 1. Предположим, что a, b и с — какие-то блоки в миреблоков. Две первые фразы утверждают, что а находится на (on) b, a b находитсяна (on) с. Третья фраза утверждает, что X находится выше (above) Y, если Xнаходится на (on) Y. Четвертая фраза утверждает, что X находится выше (above)Y, если существует какой-то другой блок Z, размещенный на (on) Y, и X находитсявыше (above) Y.
Листинг 1. Простая программа на языке PROLOG, определяющаяотношение
on (на)
on(а, b).
on(b, с).
above(X, Y) :- on(X, Y).
above(X, Y) :- on(Z, Y),
above(X, Z).
Очевидно, что от программы требуетсявывести цель above (а, с) из этого множества фраз. Процесс формулировкивыражения цели включает обработку двух процедур above и использование двух фразon. В языке PROLOG используется «интерпретация фраз Хорна для решенияпроблем» Фундаментальный метод доказательства теорем, на которомбазируется PROLOG, называется опровержением резолюций (resolution refutation).
3.3 Принцип резолюций
Мы стараемся упростить синтаксисисчисления таким образом, чтобы уменьшить количество правил влияния,необходимое для доказательства теорем. Вместо дюжины или более правил, которыеиспользуются при доказательстве теорем вручную, системы автоматическогодоказательства для фразовых форм используют единственное правило вывода —принцип резолюций, — впервые описанное Робинсоном ([Robinson, 1965]).
Рассмотрим следующий пример из исчислениявысказываний. В дальнейшем прописными буквами Р, Q, R,… будут обозначатьсяотдельные фразы, а строчными греческими U, ф и £ — пропозициональныепеременные, как и раньше.
Если U и ф представляют две произвольныефразы, которые можно представить в конъюнктивной нормальной форме, и
U={ U1, ..., Ui, ...., Um},
и
ф= {ф1..., фi....., фn}, и
Ui, = ¬фi при 1[i[mm,1 [j [ n,
то новую фразу £ можно вывести изобъединения U' и ф', где
U' = U¬{ Ui} и ф' = ф¬{ф,}.
Фраза £ = U' и ф' называетсярезольвентой шага резолюции, а U и ф являются родительскими фразами. Иногдаговорят, что U и ф «сталкиваются» на паре дополняющих литералов Ui,и фj.
Мощность резолюции обеспечивается тем, чтов ней суммируется множество других правил. Это станет очевидно после того, какобычные правила будут представлены в конъюнктивной нормальной форме.
В левой колонке табл. 1 перечисленынаименования правил вывода, в средней показано, как они выглядят в обычныхобозначениях, а в правой колонке — во фразовой форме. В каждой записи выраженияв верхней части представляют схему предпосылок, а выражения в нижней части —схему заключений. Из этой таблицы видно, что каждое из цитированных выше пятиправил является одним из экземпляров резолюции:
Таблица 1. Обобщение резолюции. Правило вывода Обычная форма Конъюнктивная нормальная форма Modus ponens
(U/>ф,U)/Ф {¬U, Ф},{U}/{ф} Modus fallens
(U/>ф.¬ф)/-U {¬U, ф},{-, ф}/{-U} Сцепление
(U/>ф, ф/>£)(U/>£) {¬U, ф},{¬ф,£}/{¬U,£} Слияние
(U/>ф,¬U />ф)/ф {U, ф},{¬U, ф}/{ф} Reductio (U,¬U)/ | {¬U},{U}/{}
Противоречие в правиле, которое обычнообозначается значком 1, дает в результате пустую фразу— {}. Это означает, чтопредпосылки несовместимы. Если считать, что предпосылки описывают некотороесостояние предметной области, то такой набор предпосылок не может быть реальнообеспечен в ней, т.е. такое состояние невозможно.
Главное, что компонент автоматическогодоказательства теорем, который является основным компонентом большинства системискусственного интеллекта и, в частности, языков программированияискусственного интеллекта, таких как PROLOG, является системой, опровержениярезолюций. Для того чтобы доказать, что р следует из некоторого описаниясостояния (или теории) Т, нужно положить —р и попытаться доказать, что из этогопредположения следует утверждение, противоречащее Т. Если это удастся сделать,то тем самым подтверждается утверждение р, а в противном случае оноопровергается.
В исчислении предикатов использованиерезолюций требует дополнительных усилий, поскольку в этом исчисленииприсутствуют переменные. Основная операция сопоставления в доказательстветеорем с помощью резолюций называется унификацией. При сопоставлениидополняющих литералов отыскивается такая подстановка переменных, котораяпревращает оба выражения в идентичные.
Например, выражения БЕЖИТ_БЫСТРЕЕ_ЧЕМ(Х,улитка) и БЕЖИТ_БЫСТРЕЕ _ЧЕМ (черепаха, Y) превращаются в идентичные приподстановке {Х/черепаха, Y/улитка}. Такая подстановка называется унификатором.Наша цель — отыскать наиболее общую подстановку такого рода.
/>3.4 Поиск доказательства в системе резолюций
Резолюция представляет собой правиловывода, с помощью которого можно вывести новую ППФ (правильно построеннуюформулу) из старой. Однако в приведенном выше описании логической системыничего не говорится о том, как выполнить доказательство. Обратим основноевнимание на стратегические аспекты доказательства теорем.
Пусть р представляет утверждение«Сократ — это человек», a q — утверждение «Сократ смертен».Пусть наша теория имеет вид
Т={{¬р,q}, {р}}.
Таким образом, утверждается, что еслиСократ человек, то Сократ смертен, и что Сократ — человек. {17} выводится изтеории Т за один шаг резолюции, эквивалентной правилу modus ponens. .
Выражения {¬р, q} и {р}«сталкиваются» на паре дополняющих литералов р и ¬р, а {q} являетсярезольвентой. Таким образом, теория Алогически подразумевает д, что записываетсяв форме Т|-q. Теперь можно добавить новую фразу {q} — резольвенту — в теорию Ти получить таким образом теорию
Т'= {{ ¬ip, q}, {p}, {q}}.
Конечно, в большинстве случаев длядоказательства требуется множество шагов. Положим, например, что теория Т имеетвид
В этой теории р и q сохраняют прежнийсмысл, а г представляет утверждение «Сократ — бог». Для того чтобыпоказать, что Т|- ¬r, потребуются два шага резолюции:
{¬q,p},{Р}/{q}
{¬q,-r},{q} / {-r}
Обратите внимание, что на первом шагеиспользуются две фразы из исходного множества Т, а на втором— резольвента {q},добавленная к Т. Кроме того, следует отметить, что доказательство может бытьвыполнено и по-другому, например:
{¬p,q},{¬q,¬r}/{¬p,¬r},
{¬p,¬r},{p}/{¬r}
При таком способе доказательства к Тдобавляется другая резольвента. В связи со сказанным возникает ряд проблем.
Когда множество Т велико, естественнопредположить, что должно существовать несколько способов вывести интересующуюнас конкретную формулу (эта формула является целевой). Естественно, чтопредпочтение следует отдать тому методу, который позволяет быстреесформулировать доказательство.
Множество Т может поддерживать и теправила, которые не имеют ничего общего с доказательством целевой формулы. Какже заранее узнать, какие правила приведут нас к цели?
Потенциально весь процесс подверженопасности комбинаторного взрыва. На каждом шаге множество Г растет, и в нашемраспоряжении оказывается все больше и больше возможных путей продолженияпроцесса, причем некоторые из них могут привести в зацикливанию.
Та схема логического вывода, которой мыследовали до сих пор, обычно называется прямой, или восходящей стратегией. Мыначинаем с того, что нам известно, и строим логические суждения в направлении ктому, что пытаемся доказать. Один из возможных способов преодолениясформулированных выше проблем — попытаться действовать в обратном направлении:от сформулированной целевой формулы к фактам, которые нужны нам длядоказательства истинности этой формулы.
Предположим, перед нами стоит задачавывести {q} из некоторого множества фраз
Т= {...,{ ¬p, q},...}.
Создается впечатление, что это множествонужно преобразовать, отыскивая фразы, включающие q в качестве литерала, а затемпопытаться устранить другие литералы, если таковые найдутся. Но фраза {q} не «сталкивается»с такой фразой, как, например, { —р, q}, поскольку пара, состоящая изодинаковых литералов q, не является взаимно дополняющей.
Если q является целью, то методопровержения резолюции реализуется добавлением негативной формулы цели кмножеству Т, а затем нужно показать, что формула
Т' = Т U {¬q}
является несовместной. Полагая, чтомножество Т непротиворечиво, приходим к выводу, что Т' может бытьпротиворечивым вследствие Т |- q.
Рассмотрим этот вопрос более подробно.Сначала к существующему множеству фраз добавляется отрицание проверяемой фразы{-q}. Затем предпринимается попытка резольвировать {-q} с другой фразой в Т.При этом существуют только три возможные ситуации.
В Т не существует фразы, содержащей q. Вэтом случае доказать искомое невозможно.
Множество Т содержит {q}. В этом случаедоказательство выполняется немедленно, поскольку из {¬q} и {q} можно вывестипустую фразу, что означает несовместность (наличие противоречия).
Множество Т содержит фразу {..., q, ...}.Резольвирование этой фразы с {¬q} формирует новую фразу, которая содержитостальные литералы, причем для доказательства противоречия все они должны бытьудалены в процессе резольвирования.
Эти оставшиеся литералы можнорассматривать в качестве подцелей, которые должны быть разрешены, еслитребуется достичь главной цели. Описанная стратегия получила названиенисходящей (или обратной) и очень напоминает формулирование подцелей в системеMYCIN.
В качестве примера положим, что множествоТ, как и ранее, имеет вид {{¬p,q},{¬q,¬r},{p}}. Мы пытаемся показать, что Т|-¬r. Для этого докажем, что фраза {r} является следствием существующегомножества Т, для чего добавим к этому множеству отрицание фразы ¬r. Поискпротиворечия происходит следующим образом:
[{¬q,¬r},{r}]/{¬q}
[{¬p,q},{¬q}]/{¬q}
[{¬p},{p}]/{}
Этот метод доказательства теорем получилназвание «опровержение резолюции», поскольку, во-первых, ониспользует правило вывода резолюций, а во-вторых, следует стратегии «отпротивного» (стратегии опровержения).
Теперь вернемся к примеру PROLOG-программы,представленному в листинге 1. На рис. 1 показано дерево доказательстваутверждения above(a, с). Дерево строится сверху вниз, и каждая ветвь связываетдве «родительские фразы», в которых содержатся дополняющие литералы,с фразой, которая образуется в результате применения правила резолюции. Ко всемцелям, записанным справа от значка ":-", неявно применяетсяотрицание. В левой части дерева представлены формулы целей, а в правой — фразы,взятые из базы данных.
Корнем дерева является пустая фраза {}.Это означает, что поиск доказательства был успешным. Добавление негативнойфразы :- above (а, с) к исходному множеству (теории) привело к противоречию.Таким образом, можно утверждать, что фраза above (а, с) является логическимследствием из этой теории.
Обратите внимание на роль операцииунификации в этом доказательстве. Цель above (а, с) унифицируется с головнойфразой above(X, Y) с помощью подстановки {Х/а, Y/c}, где выражение Х/а можноинтерпретировать как «X получает значение а». Затем эта подстановкаприменяется к хвостовой части фразы
on(Z, Y), above(X, Z),
из чего следует формулировка подцелей
on(Z, с), above(a, Z).
Следующая подцель on(Z, с) унифицируется сon(b, с) подстановкой {Z/b}. Эта подстановка затем применяется и к оставшейсяподцели, которая таким образом превращается в above (а, b), и так до тех пор,пока не образуется пустая фраза.
/>
Рис. 1. Дерево доказательства методом опровержения резолюций
Восходящий процесс доказательства,использующий в качестве отправной точки утверждение, которое мы стараемсядоказать, позволяет сфокусировать внимание на процессе поиска решения,поскольку анализируемые логические связи по крайней мере потенциально ведут наск цели. Правда, основанный на этой стратегии метод опровержения резолюций непозволяет решить все перечисленные выше проблемы. В частности, этот метод негарантирует, что найденный путь доказательства будет короче других (илидлиннее).
4. Заключение
Тема искусственного интеллекта всегда былав информатике «страной плохишей», населенной массой «неправильных»проблем, не поддающихся решению традиционными способами. Эта область привлеклавнимание прежде всего разносторонних специалистов, которых не испугало ееоткрытое, лишенное всякой организации пространство, — людей, которых влечетзадача узнать, как мы мыслим. Такие исследователи, как Марвин Минский (MarvinMinsky), Джон Мак-Карти (John McCarthy), Герберт Саймон (Herbert Simon), ПатХейес (Pat Hayes), Дональд Мичи (Donald Michie) и Бернард Мельтцер (BernardMeltzer), стали первопроходцами для тех, кто следовал за ними по пути,пролегающем через информатику, психологию и математическую логику.
Не вдаваясь в длительные рассуждения,можно ответить, что нет ничего плохого в использовании для построенияэкспертных систем подходящих традиционных технологий, если это приводит кжелаемому результату. Например, генерация гипотез в системе DENDRAL основана наалгоритме перечисления вершин плоского графа, а в системе MYCIN использованстатистический подход для выбора способа лечения на основе анализа чувствительностиорганизма к тем или иным лекарственным препаратам. Использование методов поискаили языков программирования, характерных для систем искусственного интеллекта,не запрещает инженерам по знаниям применять методики, заимствованные изприкладной математики, исследования операций или других подходящих дисциплин.Для некоторой части рассматриваемой проблемы решение может быть получено чистоалгоритмически или математически, и было бы непозволительной роскошьюотказываться от таких методов, если они способствуют достижению нужногорезультата.
Экспертные системы не смогли бы получитьстоль широкого распространения в настоящее время, если бы в свое время в ихразвитие не внесли существенный вклад идеи искусственного интеллекта. То, чтопредлагает искусственный интеллект, — это множество концепций, технологий иархитектур, пригодных для решения комплексных проблем в тех случаях, когдачисто арифметические или математические решения либо неизвестны, либомалоэффективны.
Правила логического вывода, теория ориентированныхграфов и математическая логика были изобретены задолго до появления такойобласти исследований, как искусственный интеллект. Но именно исследования вэтой области позволили адаптировать формальный аппарат этих теорий к задачампредставления знаний и отыскать высокоэффективные средства их реализации.Развитие современных продукционных, объектно-ориентированных систем и системпроцедурной дедукции в значительной мере определяется такими приложениямиискусственного интеллекта, как проблемы классификации и конструирования.
В прошлом часто высказывалосьпредположение, что использование в процессе разработки более мощныхинструментальных средств будет способствовать упрощению программированияэкспертных систем. Существует, однако, некоторый баланс между«мощностью» инструмента, принимающего решение за разработчика, игибкостью, допускающей возможность выбрать решение, наиболее подходящее дляконкретной системы. Чрезмерное упрощение оболочек зачастую оборачивалосьслишком большими ограничениями для разработчиков прикладных систем, в то времякак смешивание разных парадигм программирования предоставляло такую свободу, скоторой не всякий программист мог разумно управиться. Как показала практика,наиболее эффективным путем оказалось предоставление разработчику тщательнопродуманных готовых модулей, таких как системы анализа правдоподобия, которыеспособны эффективно решать отдельные важные нетривиальные задачи. Применениетаких модулей существенно сокращает сроки разработки прикладных экспертныхсистем.
Список литературы:
1. А.Н. Адаменко, А.М. Кучуков. Логическоепрограммирование и Visual Prolog
СПб.:БХВ—Петербург, 2003.
2. Братко И. Алгоритмы искусственного интеллекта наязыке PROLOG. М.: «Вильямс», 2004.
3. Джексон П. Введение в экспертные системы.-Москва, С.Петербург, Киев: Изд. дом «Вильямс», 2002
4. Дж. Доорс, А. Рейблейн, С. Вадера.Пролог — языкпрограммирования будущего. М.: Финансы и статистика, 1990
5. Дюбуа Д., Прад А. Теория возможностей. Приложения к
представлению знаний. -М.: Радио и связь, 1995
6. Корнеев В.В., Гарев А.Ф., Васюшин СВ., Райх В.В. Базыданных.
Интеллектуальная обработка информации. — М.: Изд-во «Нолидж»,
2000
7. Мендельсон Э. Введение в математическую логику. М.,1976
8. Нечаев В.В., Панченко В.М., Свиридов А.П.Исследование операций
и теория систем. Основы статистической динамики знаний. Учебное
пособие.-М.: МИРЭА, 2000
9. Новиков П. С. Элементы математической логики. М.,1959
10. Попов Э.В. Экспертные системы реального времени. В:Открытые
системы, N2 (10), 1995
11. Хоггер К. Введение в логическое программирование М.:Мир, 1988
12. Черч А. Введение в математическую логику, т. I. М.1960