дб - Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д

автоматы используются в компиляторах, которые транслируют исходный код компьютерных языков для синтаксического анализа и разбиения исходного кода на меньшие смысловые единицы, называемые лексемами. В таких приложениях, как компиляторы, транслирующие исходный код в код на языке ассемблера, и программы, применяемые для точного распознавания речи, невозможно обойтись без синтаксического анализа и использования конечных автоматов. А со времени появления языка Java термин компилятор приобрел более широкое значение и стал обозначать средство трансляции исходного кода не только в код ассемблера, но ив независимый от платформы байт-код (эти функции выполняет компилятор javac). Впервые такая возможность появилась с введением в действие программного обеспечения языка Pascal в х годах, поскольку байт-код этого языка мог эксплуатироваться на любом микропроцессоре. Программное обеспечение,
позволяющее преобразовывать код на языке Pascal в байт-код,
правильнее считать интерпретатором, а не компилятором,
поскольку этот байт-код не содержит команд языка конкретного компьютера, подобных командам языка ассемблера. Но интерпретаторы обладают меньшим быстродействием по сравнению с компиляторами, поэтому разработчи-
2.3. Продукции 143 ки языка Pascal решили, что лучшей рекламой для программного обеспечения служит его обозначение как компилятора, а не интерпретатора. С
оперативной демонстрационной версией конечного автомата,
предложенной компанией Xerox, можно ознакомиться по адресу http: //www. xrce. xerox. corn/competencies/content- analysis/fsCompiler/fsinput.html. С примерами таких конечных автоматов, как автомат по продаже безалкогольных напитков,
можно ознакомиться, перейдя по ссылкам, которые представлены по ад f sCompiler/f sexamples html. Практически исчерпывающий

справочник по конечным автоматам приведен по адресу http:
//odur. let. rug.nl/ alfa/fsa stuff/. Безусловно, конечные автоматы успешно действуют применительно к грамматике с сокращенным множеством символов, например, если в число этих символов входят цифры от О доили буквы алфавита, но при их использовании в таких областях, как распознавание речи,
где могут обнаруживаться неоднозначности, возникают проблемы. Например, рассмотрим следующие два предложения (1) No one has let us read и (2) No one has lettuce red В предложении (1) группа людей жалуется, что им не дают возможности читать, а в предложении (2) говорится о том, что ни у кого нет красного салата. Водном из удобных способов,
позволяющих однозначно отличить друг от друга такие похожие слова и словосочетания, как "lettuce" и "let us", "read" и "используется скрытая марковская машина (Hidden Markov
Machine— HMM), в которой вероятности присваиваются действиям, осуществимым в конечном автомате. Скрытая марковская машина позволяет рассмотреть всю структуру предложения или проанализировать дополнительные предложения, чтобы выявить правильный контекст (либо прочитав всю книгу, в которой встретилось предложение, либо проведя поиск названий овощей в каталогах овощных магазинов. Безусловно, экспертные системы не являются наиболее подходящим вариантом программного обеспечения, с помощью которого могла бы быть создана скрытая марковская машина, но они могут использоваться в качестве внешнего интерфейса для системы распознавания речи, для того чтобы в дальнейшем такая экспертная система, как CLIPS, могла применяться для инициирования соответствующих правил. В
действительности в языке CLIPS предусмотрена возможность легко связывать с помощью интерфейса код на языке С или
С++, поэтому программное обеспечение скрытой марковской машины, написанное на С или Сможет вызываться полностью аналогично любой другой функции, определяемой ключевым словом языка CLIPS. Одной из сильных сторон языка является то

Глава 2. Представление знаний 144 2.4 Семантические сети
Семантические сети, или просто сети, — это классический способ представления пропозициональной информации,
используемый в искусственным интеллекте (http: //www. pcai.
corn/web/T6110H2/R6. ol h8/pcai. htm), поэтому семантические сети иногда называют пропозициональными сетями. Как было описано выше, пропозициональным утверждением (или высказыванием) называется предложение, которое может быть либо истинным, либо ложным, такое как "все собаки млекопитающие" и "треугольник имеет три стороны".
Высказывания имеют форму декларативных знаний, поскольку в них утверждаются факты. Сточки зрения математики семантическая сеть представляет собой помеченный ориентированный граф. Высказывание всегда является либо истинным, либо ложными называется атомарным, так как его истинностное значение не подлежит дальнейшей декомпозиции.
Здесь термин атомарный применяется в классическом смысле,
который применялся для обозначения неделимого объекта в трудах древнегреческих ученых. В отличие от этого, нечеткие утверждения, описанные в главе 5, не должны обязательно быть только истинными или только ложными. Семантические сети впервые были разработаны для исследований в области искусственного интеллекта как способ описания человеческой памяти и языка Квиллианом (Quillian) в 1968 году. Квиллиан использовал семантические сети для анализа смысла слов в предложениях. (Обратите внимание на то, что выявление смысла предложения не сводится к синтаксическому анализу и разбиению предложения на лексемы и лексические структуры по такому принципу, который осуществляется с использованием конечных автоматов и скрытых марковских ма- что этот язык расширяемый, и пользователь может легко вводить новые ключевые слова на этапе компиляции для достижения наибольшей эффективности. Кроме того, благодаря наличию объектно-ориентированных средств языка COOL для расширения возможностей языка CLIPS с использованием всей

мощи средств множественного наследования могут применяться объекты. Другое программное обеспечение, такое как искусственные нейронные системы, генетические алгоритмы и прочие программы, написанные на С или Сможет вводиться либо в левые части правил, для инициирования правил, либо в правые части правил, для обеспечения вывода. Из программы на языке CLIPS можно, например, обращаться к синтезатору речи, эффекторами актюаторам робота, определив с помощью ключевых слов соответствующие функции. Исходный код языка представлен в общее пользование, а это означает, что компиляция вызовов новых ключевых слов в программе может осуществляться без потери быстродействия, которое обнаруживается при использовании других экспертных инструментальных средств, для которых исходный код не предоставлен. Семантические сети 145 шин, рассматриваемых в предыдущем разделе) С тех пор семантические сети успешно применялись для решения многих задач, связанных с представлением знаний. Понимание смысла, достигаемое с помощью семантических сетей, позволяет выйти за рамки возможностей программного обеспечения простых экспертных систем или искусственного интеллекта для устранения неоднозначности. В следующей главе, посвященной логическому выводу, будет показано, как экспертные системы выводят из фактов заключения, которые могут использоваться другими правилами вцепи логического вывода до тех пор, пока не будет достигнуто действительное заключение. А если не учитывается семантика, то работа экспертных систем может оканчиваться неудачей, как и размышления человека, сбитого столку из-за обнаружившейся неоднозначности. Структура семантической сети отображается графически с помощью узлов и соединяющих их дуг. Узлы иногда именуются объектами а дуги связями, или ребрами. Связи в семантической сети применяются для представления отношений, а узлы, как

правило, служат для представления физических объектов,
концепций или ситуаций. На риса показана обычная сеть
(фактически ориентированный граф, в которой связи обозначают авиационные маршруты, проложенные между городами. Узлы обозначены кружками, а связи — линиями,
соединяющими узлы. Стрелки показывают направление, или ориентацию, самолетов, совершающих полеты (именно поэтому граф, на котором указаны направления, называется ориентированным. На рис. 2.4, б связи показывают отношения между членами некоторой семьи. Отношения имеют для семантических сетей исключительно важное значение,
поскольку предоставляют базовую структуру для организации знаний. Знания, заданные без учета отношений, превращаются просто в коллекцию несвязанных фактов. А если заданы отношения, то знания приобретают связную структуру,
исследование которой позволяет выводить логическим путем другие знания. Например, на основании рис. 2.4, б можно сделать вывод, что Анна и Билл — бабушка и дедушка Джона,
даже несмотря на то, что на этом рисунке нет явно заданной связи, обозначенной как "grandf ather — о f". Семантические сети иногда называют ассоциативными сетями, поскольку одни узлы в таких сетях ассоциированы, или связаны, с другими. В
действительности в оригинальной работе Квиллиана человеческая память моделировалась как ассоциативная сеть, в которой понятия были представлены в виде узлов, а связи показывали, как соединены эти понятия друг с другом. Согласно указанной модели, если происходит стимуляция одного узла в результате чтения слов в предложении, то происходит активизация связей этого узла с другими узлами, и такая активность распространяется посети. Если же достаточную активизацию получает другой узел, тов обладающем сознанием разуме всплывает концепция, представленная этим узлом.
Например, очевидно, что человек знает тысячи слов

146 Глава 2. Представление знаний Чикаго Сан-Фр Нью-Йорк
Лос-А а) Сеть общего вида sister-of John б) Семантическая сеть
Рис. 2.4. Примеры двух типов сетей нов его сознании отражаются только слова того конкретного предложения,
которое он читает. Как оказалось, во многих разных способах представления знаний особенно полезными являются отношения определенных типов. Поэтому при изучении различных задач принято использовать именно эти типы, а не определять каждый раз новые отношения. К тому же применение общепринятых типов позволяет другим людям проще понять, что описано в незнакомой для них сети 2.4. Семантические сети 147 Рис. 2.5. Семантическая сеть со связями Аи А (АКО) (3, eggs, blue, tires, art) К двум таким связям широко используемых типов относятся связи Аи А (связь последнего типа иногда записывается как
АКО). На рис. 2.5 показана семантическая сеть, в которой используются такие связи. На данном рисунке связь IS-А
означает "является экземпляром" данного класса и указывает на конкретный экземпляр некоторого класса. В этом контексте понятие класса близко к математическому понятию множества,
поскольку служит для обозначения группы объектов. Тем не менее множество может содержать элементы любого типа, а объекты в классе связаны определенными отношениями друг с другом, те. не могут быть взяты произвольно. Например, может быть определено множество, состоящее из следующих элементов Глава 2. Представление знаний Но элементы этого множества не связаны какими-либо обычными отношениями. С
другой стороны, в семантической сети может быть задан класс,
состоящий из самолетов, поездов и автомобилей. Объекты этого класса связаны друг с другом, поскольку все они представляют собой некоторые средства транспорта. В данном случае связь

АКО используется для обозначения отношения одного класса с другим. Связь АКО не может служить для обозначения отношений конкретных объектов для этого предназначена связь
IS-А. Связь АКО определяет отношение между отдельным классом и родительским классом (или классами),
применительно к которому этот отдельный класс является дочерним. Указанные отношения можно трактовать итак, что связь АКО определяет отношение между одними родовыми узлами и другими родовыми узлами, а связь А определяет отношение между экземпляром, или отдельным объектом, иродовым классом. Следует отметить, что на рис. 2.5 более общие классы находятся в верхней части, а более конкретные классы — в нижней части. Более общий класс, на который указывает стрелка АКО, называется суперклассом. Если суперкласс имеет связь АКО, указывающую на другой узел, то он вместе стем представляет собой класс суперкласса, на который указывает стрелка АКО. Иной способ представления таких отношений заключается в том, что связь АКО направлена от подкласса к классу. Вместо связи АКО иногда используется связь ARE, в которой ARE читается как обычное слово "есть. Все объекты класса должны иметь один или несколько общих атрибутов. Каждый атрибут имеет значение. Комбинация атрибута и значения называется свойством. Например,
дирижабль имеет такие атрибуты, как размеры, вес, форма и цвет. Значением атрибута формы является эллипсоид. Иными словами, дирижабль имеет такое свойство, как эллипсоидальная форма. В семантических сетях можно также найти связи других типов. Связь А определяет значение.
Например, самолет, на котором летает Президент, приобретает атрибут "Самолета ВВС номер один. А если Президент летит на вертолете, такой вертолет А (является) "Вертолетом ВВС
номер один. Связь CAUSE выражает причинные знания.
Например, горячий воздух CAUSE (становится причиной) того,
что воздушный шар поднимается. Рекламный дирижабль компании Goodyear является дирижаблем, а дирижабли имеют эллипсоидальную форму из этого следует, что дирижабль является эллипсоидальным. Повторение

характеристик узла в его потомках называется наследованием.
Если нет более определенного свидетельства, позволяющего утверждать обратное, то предполагается, что все элементы некоторого класса наследуют все свойства суперклассов этого класса. Например, воздушные шары имеют круглую форму. Но класс дирижаблей имеет связь, указывающую на узел,
обозначающий эллипсоидальную форму, поэтому явно заданная связь рассматривается как имеющая более высокий приоритет.
Наследование представляет собой полезное средство в представлении знаний, поскольку позволяет избавиться от. Тройки "объект-атрибут-значение" 149 необходимости повторно указывать общие характеристики. Связи и наследование являются основой эффективных способов представления знаний, поскольку дают возможность показывать многие сложные отношения с помощью нескольких узлов и связей. Ниже в этой главе будут описаны объектно- ориентированные возможности языка CLIPS, которые реализуются с использованием встроенного в него языка Эти два языка позволяют создавать экспертные системы,
используя правила, объекты или комбинации правили объектов,
связанных полноценными отношениями множественного наследования. 2.5 Тройки "объект — атрибут — значение" Одна из проблем, связанных с применением семантических сетей,
состоит в том, что не предусмотрены стандартные определения для имен связей. Например, в некоторых книгах связи IS-А
используются для представления и общих, и индивидуальных отношений. Это означает, что связь А применяется для представления такого же смысла, какой представляют обычные слова "is а" (является, а также может применяться вместо связи
АКО. Еще одной широко применяемой связью является HAS-А,
которая устанавливает отношение между классом и подклассом.
Связь А направлена в сторону, противоположную по отношению к связи АКО, и часто используется для обозначения отношения между одним объектом и частью другого объекта

например, как показано ниже. автомобиль А двигатель автомобиль А шины автомобиль А автомобиль производства компании Ford Более определенно можно указать,
что связь А устанавливает отношение между значением и атрибутом, а связь А — между объектом и атрибутом.
Такие три понятия, как обьект, атрибут и значение, встречаются вместе настолько часто, что иногда обнаруживается возможность создать упрощенную семантическую сеть с использованием только этих понятий. Чтобы охарактеризовать всезнания, представленные в семантической сети, можно воспользоваться тройкой "объект — атрибут — значение — OAV), или просто триплетом такие триплеты использовались в экспертной системе предназначенной для диагностирования инфекционных заболеваний. Представление в виде тройки OAV является удобным способом оформления списка имеющихся знаний в форме таблица также позволяет легко преобразовать полученную таблицу в компьютерный код по методу индукции правил. Пример таблицы стройками показан в табл. Индукция — это мощный логический метод, который часто используется неправильно. В качестве классического примера можно указать такую ситуацию, когда нерадивого программиста спрашивают, по Глава 2. Представление знаний чему он не создает резервные копии данных, хранящихся на жестком диске своего компьютера. Обычно лентяи дают при этом ошибочный индуктивный ответ, состоящий в том, что жесткий диск на этом компьютере еще никогда не ломался, поэтому по индукции такая авария никогда не произойдет. (Такой способ "рассуждений"
широкой публики очень нравится биржевым маклерам.)
Дополнительные сведения об индуктивном логическом программировании приведены в [5]. Таблица 2.1. Таблица со списком троек "объект — атрибут — значение" (OAV) Атрибут color Значение red mcintosh type quantity color 100 red seedless

type quantity 500 Тройки "объект — атрибут — значение" лежат в основе особенно полезного способа представления фактов и шаблонов, применяемых для согласования с фактами в антецеденте правила. Семантическая сеть для подобной системы состоит из узлов, представляющих объекты, атрибуты и значения, соединенных связями Аи А. Если должен быть представлен только один объект и применять отношения наследования не требуется, то может оказаться приемлемым еще более простое представление, называемое парой "атрибут значение" (attribute-value — AV), или просто парой. 2.6 Языки семантические сети Семантические сети могут быть легко преобразованы в программу на языке Например, ниже приведены операторы PROLOG, которые представляют некоторую часть отношений из семантической сети, приведенной на рис. 2.5. Обратите внимание на то, что конец оператора PROLOG обозначается точкой (.). Объект apple apple apple grapes grapes grapes is a(goodyear blimp, blimp). is a(spirit of st louis, special). has shape(blimp, ellipsoidal). has shape(balloon, round).
2.6. Языки семантические сети 151 Основные сведения о языке PROLOG Каждый из приведенных выше операторов PROLOG представляет собой предикативное выражение (или просто предикат, поскольку эти операторы основаны на логике предикатов. Однако PROLOG нельзя назвать настоящим языком логики предикатов, поскольку он является компьютерным языком с исполняемыми операторами.
В языке PROLOG предикативное выражение состоит из имени предиката, такого как is a, за которым следуют от нуля или больше параметров, заключенных в круглые скобки и разделенных запятыми. Ниже приведены некоторые примеры предикатов PROLOG. Комментарии обозначаются точками с запятой и игнорируются машиной PROLOG. color(red).
mother(pat,ann). parents (jim,ann,tom) surrogatemother (pat,tom). то, что цвет — красный, является фактом ; Пэт — мать Энн ;

Джим и Энн — родители Тома ; Пэт — суррогатная мать Тома is a(red,color). has a(john, father). has a(john, mother). has a(john,
parents). Обратите внимание на то, что эти предикаты has a не выражают тот же смысл, как и раньше, поскольку отец, мать ив целом родители Джона явно не Назначение предикатов с двумя параметрами проще понять, представив себе, что они состоят из имени предиката, за которым следует первый параметр. С
другой стороны, смысл предикатов, имеющих больше двух параметров, необходимо определять явно, как показано в примере предиката parents. А при использовании семантических сетей возникает другая сложность, поскольку они позволяют представлять в основном только двоичные отношения в силу того, что линия, обозначающая связь, имеет только два конца.
Таким образом, предикат parents нельзя представить графически с помощью одного ориентированного ребра,
поскольку в определении предиката имеются три параметра. А
попытка реализовать идею, согласно которой Томи Энн должны быть представлены водном родительском узле, а Джим — в другом, приводит к новым осложнениям. Дело в том, что при этом исключается возможность использовать родительский узел для определения других бинарных отношений, таких scarc mother — of, поскольку Тома никак нельзя считать матерью.
Предикаты могут быть также представлены с помощью таких отношений, как Аи А, например, следующим образом:
Глава 2. Представление знаний 152 названы. Для того чтобы указать имена отца, материи отдельно каждого из роди- телей,
необходимо добавить несколько дополнительных предикатов,
как показано ниже. is a(tom,father). isa(susan, mother). is a(tom,parent). is a(susan, parent). Но даже эти дополнительные предикаты не выражают тот же смысл, что и первоначальные предикаты. Например, мы знаем, что Джон имеет отца, а Том является отцом, но из этого не следует, что Том — отец Джона.
Все приведенные выше операторы фактически представляют собой описания фактов в языке PROLOG. Программы на языке

PROLOG состоят из фактов и правил, заданных в общей форме целей р. р) p2) р Именно поэтому предикаты, подобные следующим, рассматриваются как факты, следовательно,
должны быть истинными color(red). has a(john, father). В этом операторе терм р представляет собой голову правила, а термы р выполняют роль подцелей. Как правило, выражение,
применяемое в форме такого оператора, является хорновским выражением, которое утверждает, что цель р, заданная в голове выражения, выполняется тогда и только тогда, когда выполнены все подцели. Исключение из этого правила возникает только в том случае, если используется специальный предикат,
обозначающий отказ. Предикат с обозначением отказа является удобным, поскольку в классической логике нелегко доказать истинность отрицания, а язык PROLOG основан на классической логике. Отрицание рассматривается как невозможность найти доказательство, и поэтому процесс выполнения программы может оказаться очень длинными сложным, если количество потенциальных согласований достаточно велико. Благодаря использованию оператора отсечения и специального предиката failure процесс доказательства истинности отрицания становится более эффективным, поскольку процедура поиска доказательства сокращается. Запятые, разделяющие подцели,
представляют логическую операцию AND, а символ интерпретируется как знак операции IF. Если в операторе задана только голова выражения, а правая часть отсутствует (как в приведенном ниже примере, то считается, что голова выражения имеет истинное значение. Языки семантические сети 153 parent(X, У- father(X, Y). parent(X, Y):- пюйег(Х, У. Эти правила означают, что
Х является родителем У, если Х — отец У или если Х — мать У.
Аналогичным образом, предикат grandparent (дедушка или бабушка) может быть определен таким образом У — parent(X, Z),parent(Z, УС другой стороны, предикат ancestor (предок) можно определить, как показано ниже. (1)

ancestor(X, У — parent(X, У. (2) ancestor(X, У — ancestor(X,
Z),ancestor(Z, У. Как принято в настоящей книге, обозначения) и (2) используются для идентификации отдельных компонентов примера. Обеспечение поискав языке Как правило, в системе, предназначенной для выполнения операторов PROLOG, применяется интерпретатор, хотя в некоторых системах может вырабатываться откомпилированный код. Общая структура системы PROLOG показана на рис. 2.б.
Пользователь взаимодействует с системой PROLOG, вводя запросы в форме предикатов и получая ответы. Предикативная база данных содержит предикаты, представленные в виде правили фактов, которые были в нее введены ив результате сформировали базу знаний. Интерпретатор предпринимает попытки определить, следует ли предикат запроса, введенный пользователем, из базы данных. Если запрос сформулирован как факт и этот факт находится в базе данных, интерпретатор возвращает ответа если этот факт в базе данных отсутствует — возвращает ответ по. С другой стороны, если запрос сформулирован в виде правила, то интерпретатор предпринимает попытки выполнить подцели этого правила,
проводя поиск в глубину, как показано на рис. 2.7. Для сравнения на этом рисунке показан также ход поискав ширину,
хотя такой режим работы в системе PROLOG обычно не применяется. Еще один способ трактовки понятия факта состоит в том, что факт рассматривается как безусловное заключение,
которое не зависит от чего-либо иного, поэтому для его определения операция IF (или) не требуется. В отличие от этого, правила PROLOG требуют применения операции поскольку представляют собой условные выражения,
истинность которых зависит от одного или нескольких условий.
В качестве примера можно привести следующие правила определения предиката parent:
Глава 2. Представление знаний 154 Рис. 2.6. Общая организация системы PROLOG (3) parent(ann,mary). (4)

parent(ann,susan). (5) parent(mary,ЬоЬ). (6) parent(susan john). А
теперь допустим, что системой PROLOG передан следующий запрос для определения того, является ли Энн предком Сьюзен:
:- ancestor(ann,susan). Признаком того, что это — запрос,
является отсутствие в правиле головы. Это означает, что система PROLOG должна доказать данное условие. Тремя типами хорновских выражений, применяемых в системе, являются факты, правила и запросы. Условие может быть доказано, только если оно представляет собой заключение некоторого экземпляра выражения. Безусловно, для этого должно быть доказуемым самовыражение, и такое доказательство осуществляется путем доказательства условий выражения. При поиске в глубину поиск в дереве начинается от корня, продолжается настолько далеко, насколько это возможно,
после чего происходит возврат. Еще одна отличительная особенность поискав системе PROLOG состоит в том, что он происходит слева направо. А поиск в ширину предусматривает полную обработку узлов на текущем уровне перед переходом наследующий, более низкий уровень. В качестве примера поиска цели в системе PROLOG рассмотрим, как происходит обработка приведенных выше правили, относящихся к предикату ancestor. Предположим, что на данном этапе введены следующие факты 2.6. Языки семантические сети 155 Рис. 2.7. Поиск в глубину и поиск в ширину применительно к дереву произвольной формы После того как система PROLOG принимает этот входной запрос, начинается поиск выражения, голова которого согласуется с входным шаблоном ancestor(ann,susan). Такая процедура называется сопоставлением с шаблоном и полностью аналогична сопоставлению с шаблоном, в котором участвуют факты и антецеденты продукционного правила. Поиск начинается с первого введенного оператора, (1), который находится вначале списка операторов, и происходит в направлении к последнему оператору, (6), находящемуся в

конце списка. При этом обнаруживается возможность согласования с первым правилом предиката ancestor, с правилом (1). Переменная Х согласуется с апп, а переменная Глава 2. Представление знаний Ус. Поскольку теперь голова предиката согласована, система предпринимает попытку согласовать тело правила (1), что приводит к созданию подцели parent(ann,susan). Затем система осуществляет попытку согласовать эту подцель с другими выражениями ив конечном итоге согласует ее с фактом, parent(ann,susan). На этом все цели, подлежащие согласованию, исчерпываются, и система PROLOG отвечает "yes", поскольку первоначальный запрос является истинным. В
качестве еще одного примера предположим, что введен следующий запрос : — апсейог(ашцоЬп). Согласуется правило) предиката ancestor, в результате чего переменной Х
присваивается значение апп, а переменной У — значение После этого система PROLOG предпринимает попытки согласовать тело правила (1), parent(ann john), с каждым из операторов parent. Однако все попытки согласования оканчиваются неудачей, поэтому обнаруживается, что тело правила (1) не может быть истинным. Поскольку тело правила) не является истинным, голова этого правила также не может быть истинной. Поскольку правило (1) не может быть истинным,
система PROLOG затем предпринимает попытку проверить истинность правила (2) предиката ancestor. Переменной Х
присваивается значение апп, а переменной У — значение Система PROLOG осуществляет попытки доказать, что голова правила (2) является истинной, доказывая то, что обе подцели правила (2) являются истинными. Это означает, что требуется доказать истинность обеих подцелей, ancestor(ann,Z) и ancestor(Z, john). Система PROLOG предпринимает попытки согласования подцелей в направлении слева направо, начиная с подцели ancestor(ann, Z). Проходя по списку выражений,
начиная сверху, система PROLOG обнаруживает, что эта первая

подцель согласуется с правилом (1), и поэтому пытается доказать истинность тела правила (1), parent(ann, Z). А после того как поиск снова начинается с верхней части списка,
обнаруживается первое согласование этого тела с оператором, поэтому система PROLOG присваивает переменной значение mary. Теперь система PROLOG пытается согласовать вторую подцель правила (2), представленную в виде ancestor(mary,ohn). Эта подцель согласуется с правилом (1), и поэтому PROLOG пытается выполнить тело этого оператора. Однако в операторах от (3) доб) факт parent(mary,ohn) отсутствует, поэтому данная попытка поиска оканчивается неудачей. Затем система пересматривает свое предположение, согласно которому переменной Z должен быть присвоено значение mary. Поскольку этот вариант оказался неприменимым, система пытается найти приемлемое значение. Еще одна возможность осуществляется с помощью правила (4), согласно которому переменной присваивается значение susan. Показанный здесь метод возврата в целях опробования другого пути поиска, после того как предыдущая попытка. Трудности, связанные с использованием семантических сетей 157 :- ancestor(ann john) Обратите внимание на то, что управляющая структура PROLOG относится к типу марковского алгоритма, в котором последовательность поискав ходе сопоставления с шаблонами обычно определяется тем, в каком порядке введены хорновские выражения. В этом состоит отличие системы PROLOG от экспертных систем, основанных на правилах, которые обычно следуют принципу Поста (согласно этому принципу, ход поиска не зависит оттого, в каком порядке введены правила. Система PROLOG обладает многими другими особенностями и возможностями, которые не упоминаются в настоящей книге. Сточки зрения разработчиков экспертных систем, особенно важными возможностями являются перебор с возвратами и сопоставление с шаблонами

К тому же важно то, что язык PROLOG имеет декларативный характер, поскольку это означает, что в качестве исполняемой программы непосредственно применяется спецификация программы. 2.7 Трудности, связанные с использованием семантических сетеи Безусловно, семантические сети могут оказаться весьма полезным средством представления знаний,
но они имеют целый ряд ограничений, в частности, связанных с отсутствием стандартов именования связей, о чем было сказано выше. В результате возникают затруднения при попытке понять,
для чего фактически была создана какая-то конкретная сеть, и действительно ли эта сеть была создана правильно. С
указанной проблемой именования связей сопряжена проблема именования узлов. Например, если в сети имеется узел,
обозначенный как "chair" (кресло, остается неизвестным,
обозначает ли это слово одно из указанных ниже понятий, или что-то другое. данное конкретное кресло класс всех кресел воспользоваться некоторым путем окончилась неудачей,
называется перебором с возвратами и часто используется для решения задач. После выбора варианта присваивания переменной Z значения susan система PROLOG предпринимает попытку доказать, что выражение ancestor(susan john) является истинным. Согласно правилу (1), для этого необходимо доказать истинность тела parent(susan john). И действительно, факт (согласуется, поэтому указанный запрос обозначается как истинный, так как доказано, что его условия являются истинными Глава 2. Представление знаний понятие кресла кресло председателя собрания Семантическая сеть может применяться для представления категорических знаний (те. знаний, которые определены однозначно) только притом условии, что строго определены сами имена связей и узлов. Безусловно,
аналогичные проблемы обнаруживаются и при использовании языков программирования. Но, к счастью, указанная задача уже решена с введением в действие расширяемого языка разметки

(eXtensible Markup Language — XML) и онтологий. Язык ХМЬ
проявил себя как бесценное средство реализации стандартного способа условного представления формальной семантики в виде конструкций языков всех возможных типов. Кроме того,
разработана версия ХМЬ, основанная на правилах, а также созданы языки разметки для математики, музыки, пищевой промышленности и многих других областей, в которых для обработки информации применяются компьютеры. Благодаря использованию языка ХМЬ и онтологий система World Wide сокращенно WWW, или W3) постепенно превращается из хранилища данных в коллекцию информации, доступной для чтения с помощью компьютера, имеющую гораздо более широкую область применения. В связи с этим Web теперь все чаще именуют семантической системой Web (Semantic Web), а непросто системой Web, поскольку в этой системе в настоящее время реализуются новые способы представления смыслового значения информации. Еще одна проблема, связанная с использованием семантических сетей, состоит в том, что при осуществлении поиска узлов возникает комбинаторный взрыв,
особенно если ответ на запрос является отрицательным. Дело в том, что если запрос должен выработать отрицательный результат, то может оказаться, что требуется выполнить поиск по многим или даже по всем связям в сети. А как показано в описании задачи коммивояжера, приведенном в главе количество связей равно факториалу от количества узлов в сети за вычетом единицы, если все узлы сети связаны друг с другом.
Безусловно, такая степень связности встречается не во всех представлениях задач, но возможность комбинаторного взрыва нельзя исключить. Семантические сети были первоначально предложены для использования в качестве модели ассоциативной памяти человека. В этой модели каждый узел имеет связи с другими узлами и выборка информации происходит в результате распространения активности по узлам сети. Нов мозгу человека должны также быть предусмотрены другие механизмы, поскольку для него не требуется много времени, чтобы ответить на вопрос "Есть ли футбольная команда на Плутоне" В мозгу человека имеется

приблизительно 1011 нейронов и примерно 1015 связей. Если бы все его знания были представлены только с помощью семантической сети, то потребовалось бы чрезвычайно продолжительное время для формулировки отрицательного ответа на вопросы, подобные указанному выше вопросу о футбольной. Схемы 159 2.8 Схемы Семантическая сеть может служить примером поверхностной структуры знаний. Поверхностность знаний в семантической сети обусловлена тем, что всезнания в ней представлены в виде связей и узлов. Структура знаний аналогична структуре данных в том, что составляет упорядоченную коллекцию знаний, а непросто разрозненные данные. С другой стороны, глубокую структуру знаний имеют причинные знания, которые объясняют, почему происходит то или команде, поскольку для поиска ответа пришлось бы ввести в действие все 1015 связей. Кроме того, семантические сети не соответствуют требованиям логики, поскольку не позволяют применять для определения знаний такие способы, которые являются применимыми к логике. Как будет описано ниже в данной главе, логические способы представления позволяют определить какое-то конкретное кресло, некоторые кресла, все кресла, отсутствие кресел и т.д. Еще одна проблема состоит в том, что семантические сети остаются неприменимыми для эвристических методов, поскольку в сети невозможно представить эвристическую информацию, касающуюся того, как можно эффективно провести поиск в сети. Эвристикаэто эмпирическое правило, которое может помочь найти решение,
но, в отличие от алгоритма, не гарантирует нахождение решения. В искусственном интеллекте возможность применения эвристик очень важна, поскольку типичные задачи искусственного интеллекта настолько сложны, что алгоритмическое решение для них не существует или слишком неэффективно для практического использования. Единственной стандартной стратегией управления, встроенной в сеть, которая

может помочь в решении задач, является наследование, ноне все задачи могут быть представлены с использованием такой структуры. Для устранения недостатков, присущих семантическим сетям, было опробовано много подходов.
Некоторые введенные в них усовершенствования были основаны на логике, а другие усовершенствования, в которых предпринимались попытки закрепления процедур за узлами,
были основаны на использовании эвристик. Такие процедуры должны были вызываться на выполнение после того, как узел становится активизированным. Но созданные в результате системы позволяли достичь лишь незначительного расширения возможностей за счет ухудшения естественной выразительности семантических сетей. По результатам анализа всех этих усилий был сделан вывод, что семантические сети, как и любые другие инструментальные средства, должны использоваться в тех областях, для которых они приспособлены в наибольшей степени, те. для представления бинарных отношений, поэтому не следует их загромождать, пытаясь превратить в универсальное инструментальное средство Глава 2. Представление знаний иное событие. Например,
может быть создана медицинская экспертная система на основе поверхностных знаний, содержащая примерно такие правила у пациента иыеется высокая температура THEN пациент должен принять аспирин Нов подобной системе отсутствует фундаментальные знания о биохимии человеческого организма и о том, почему прием аспирина влечет за собой снижение температуры. Это правило вполне могло быть определено следующим образом IF у одного из присутствующих имеется розовая обезьяна THEN он должен принять в подарок холодильник Иными словами, знания в такой экспертной системе являются поверхностными, поскольку они основаны на синтаксисе, а не на семантике, а в этой синтаксической конструкции любые два словесных выражения могут быть заменены на Хи У, как в следующем правиле IF у какого-то

человека иыеется (Х) THEN он должен принять (Y) Обратите внимание на то, что в этом правиле Хине переменные,
а подстановочные символы, заменяющие любые два словесных выражения. С другой стороны, врачи обладают причинными знаниями, поскольку учились много лет в медицинском институте и приобрели опыт лечения пациентов. Если же способ лечения, применяемый как обычно, оказывается неэффективным, врачи могут использовать свои способности к рассуждению, чтобы найти вариант, альтернативный по отношению к выбранному с помощью обычно применяемого ими метода, основанного на прецедентах. Иными словами, эксперт знает, когда можно нарушить правила. Структура семантической сети слишком проста, поэтому с ее помощью невозможно представить знания многих типов, применяемые в реальном мире. Для лучшего представления сложных структур знаний требуются более сложные структуры представления. В
искусственном интеллекте для описания более сложных структур знаний, чем семантические сети, используется термин схема (schema). Термин схема заимствован из психологии, где он обозначает непрерывную организацию знаний или реакций живого существа, вырабатываемых в ответ на стимулы. Это означает, что живые существа, изучая причинные отношения между стимулом и результатом, стремятся повторно испытать приятные стимулы и избежать неприятных. Например, при осуществлении таких действий, как еда и пить, складываются сенсорно-двигательные схемы, окрашенные ощущениями удовольствия, которые обеспечивают координацию информации, полученной от органов чувств, с необходимыми моторными (мускульными) движениями, с помощью которых осуществляется процесс еды и питья. Человек не обязан задумываться над этими. Схемы 161 неявными знаниями, чтобы узнать, как выполнять эти действия, к тому же очень трудно точно объяснить, как они осуществляются, вплоть до уровня

управления мускулами. А еще более значительные затруднения возникают при попытке объяснить схему, которой подсознательно руководствуется человек вовремя езды на велосипеде. Попробуйте объяснить словами чувство равновесия Еще одним важным типом схем являются концептуальные схемы, с помощью которых в мозгу человека складываются концепции. Например, допустим, что человек овладел концептуальным представлением о том, что такое животное. Но большинство людей, которых просят объяснить,
что представляет собой животное, скорее всего, будут описывать его в таких терминах, что животное — существо с четырьмя ногами, заросшее мехом. К тому же, безусловно,
сложившаяся у человека концепция животного будет зависеть оттого, выросли он в сельской местности, в городе или на берегу реки. Тем не менее все люди имеют в своем сознании,
складывающемся из концепций, определенные стереотипы.
Безусловно, в обыденной речи термин стереотип может иметь отрицательную окраску, нов искусственном интеллекте он обозначает типичный пример. Поэтому для большинства людей стереотипом животного может быть собака. Концептуальная схема — это абстракция, в которой конкретные объекты классифицируются по их общим свойствам. Например, если вы увидите рисунок с надписью "Искусственный фрукт, на котором изображен небольшой круглый объект красного цвета с зеленым черенком, то, по-видимому, распознаете его как искусственное яблоко. Этот объект обладает свойствами принадлежности к яблокам, которые могут быть поставлены в соответствие с концептуальной схемой яблока. Концептуальная схема настоящего яблока может охватывать такие общие свойства яблок, как размеры, цвет, вкус, назначение и т.д. Эта схема не будет включать подробных сведений о том, где именно было сорвано яблоко, на каком грузовике оно доставлено в супермаркет и как зовут человека, положившего его на полку.
Эти подробности не имеют значения при анализе тех свойств, из которых складывается абстрактная концепция яблока. Кроме того, следует учитывать, что, например, слепой человек может иметь совсем другую концептуальную схему яблока, в которой

наибольшую важность имеет текстура поверхности и запах.
Сосредоточение на общих свойствах объекта позволяет упростить проведение рассуждений об этих свойствах,
поскольку при этом не приходится отвлекаться на незначащие подробности. Как правило, схемы имеют структуру, внутреннюю по отношению к применяемым в них узлам, а семантические сети не имеют такой структуры. Всезнания о некотором узле,
применяемом в семантической сети, заключены в надписи на этом узле. Семантическая сеть аналогична такой структуре данных, применяемой в компьютерных науках, в которой ключ поиска одновременно представляет собой данные, хранящиеся в узле. А схема аналогична структуре данных, в которой узлы содержат записи. Каждая запись может содержать данные,
записи или указатели на другие узлы Глава 2. Представление знаний 2.9 Фреймы Одним из типов схем, который используется во многих приложениях искусственного интеллекта, является фрейм. Еще один тип схемы представляет собой сценарий, который по существу является упорядоченной во времени последовательностью фреймов. Фреймы предложены для использования в качестве метода понимания особенностей зрения, естественных языков и других областей и предоставляют удобную структуру для описания объектов, типичных для какойто конкретной ситуации,
в частности, стереотипов объектов. Фреймы являются особенно полезным средством моделирования знаний, основанных на здравом смысле, а эта область знаний с большим трудом поддается освоению с помощью компьютеров. Безусловно,
семантические сети по существу можно рассматривать как двумерное представление знаний, а фреймы добавляют третье измерение, поскольку позволяют использовать узлы, имеющие внутреннюю структуру. В качестве таких структур могут применяться простые значения или другие фреймы. Основная характерная особенность фрейма состоит в том, что он представляет взаимосвязанные знания по узкой теме

значительная часть которых — это знания, заданные по умолчанию. Система фреймов может оказаться весьма подходящей для описания механического устройства, например автомобиля. Такие компоненты автомобиля, как двигатель,
корпус, тормозная система и т.д., должны рассматриваться в сочетании, чтобы можно было получить общее представление о связях между этими компонентами. Дополнительные сведения о компонентах могут быть получены с помощью изучения структуры фреймов. Безусловно, автомобили разных моделей отличаются друг от друга, но большинство автомобилей, как правило, имеют такие аналогичные компоненты, как колеса,
двигатель, корпус и передаточный механизм. В этом состоит отличие фрейма от семантической сети, поскольку сеть, как правило, используется для общего представления знаний. Тем не менее, как ив случае семантических сетей, стандарты определения систем на основе фреймов отсутствуют. Для работы с фреймами создан целый ряд языков специального назначения, таких как FRL, SRL, KRL, КЕЕ, HP-RL; кроме того,
предусмотрены такие усовершенствованные средства работы с фреймами языка LISP, как LOOPS и FLAVORS. Фрейм аналогичен структуре записи на языке высокого уровня, таком как С, или атому со списком свойств в языке LISP. В свою очередь, полями значениям записи соответствуют такие компоненты фрейма, как слоты и заполнители слотов. Фрейм по существу представляет собой группу слотов и заполнителей,
которые определяют объект, рассматриваемый в качестве стереотипа. Фрейм с описанием автомобиля показан на рис. В терминах представления в виде тройки "объект атрибут значение" автомобиль — это объект, имя слота — атрибута заполнитель значение 163 2.9. Фреймы Рис. 2.8. Фрейм с описанием автомобиля
Большинство фреймов не являются настолько простыми, как показано на рис. 2.8. Фреймы обнаруживают свою значимость в составе иерархических систем фреймов ив условиях

применения наследования. Использование фреймов в виде заполнителей слотов и ввод в действие отношения наследования позволяет создавать очень мощные системы представления знаний. В частности, как оказалось, экспертные системы на основе фреймов являются очень полезным средством представления причинных знаний, поскольку хранимая в них информация организована с учетом причини следствий. В отличие от этого, экспертные системы, основанные на правилах, обычно опираются на неорганизованные знания,
которые не являются причинными. Некоторые инструментальные средства, основанные на фреймах, такие как
КЕЕ, позволяют хранить в слотах самые разнообразные элементы. В частности, слоты фреймов могут хранить правила,
графику, комментарии, отладочную информацию, вопросы для пользователей, гипотезы, касающиеся той или иной ситуации,
или другие фреймы. Фреймы обычно применяются для представления либо универсальных, либо специальных знаний.
На рис. 2.9 показан универсальный фрейм, предназначенный для представления концепции собственности, которой может владеть человек. Заполнителями могут быть значения, такие как название собственности в слоте пате, или ряд значений,
например, как в слоте types. Сами слоты могут также содержать процедуры, закрепленные за слотами и называемые процедурными вложениями. Сами процедуры, как правило,
подразделяются натри типа. Процедура типа if-needed выполняется, если требуется значение заполнителя, но первоначально это значение не присутствует в слоте или является неприменимым значение default, предусмотренное по умолчанию. Во фреймах значения 164 Глава 2. Представление знаний Рис. 2.9. Универсальный фрейм, предназначенный для описания концепции собственности предусмотренные по умолчанию, являются исключительно важными, поскольку позволяют моделировать некоторые аспекты функционирования мозга. Применяемые по

умолчанию значения соответствуют ожиданиям человека в отношении некоторой ситуации, которые складываются на основании опыта. А после того как обнаруживается новая ситуация, осуществляется модификация наиболее подходящего фрейма, что позволяет проще приспособиться к ситуации. Люди не начинают с пустого места, сталкиваясь с каждой новой ситуацией. Вместо этого они модифицируют в существующих фреймах заданные по умолчанию значения или другие заполнители. Заданные по умолчанию значения часто используются для представления знаний, основанных на здравом смысле. Знания, основанные на здравом смысле, могут рассматриваться как общеизвестные знания. Мы используем здравый смысл, если недоступны знания, более соответствующие конкретной ситуации. Процедура типа if-added вызывается на выполнение, если в слот должно быть введено какое-либо дополнительное значение. Например, в слоте types процедура if — added вызывает на выполнение в случае необходимости процедуру ADD — PROPERTY для добавления собственности нового типа. Например, эта процедура может быть вызвана после приобретения драгоценностей, телевизора,
стереомагнитофона или собственности другого типа, поскольку указанные значения не содержатся в слоте types. Процедура типа if-removal вызывается на выполнение каждый раз, когда возникает необходимость удалить из слота какое-либо значение.
В частности, проце-
2.9. Фрей мы 165 Рис. 2.10. Фрейм с описанием автомобиля универсальный субфрейм с описанием типа собственности
Системы фреймов проектируются таким образом, чтобы более универсальные фреймы находились ближе к вершине иерархии.
Предполагается, что специализация фреймов применительно к конкретным случаям может осуществляться путем модификации применяемых по умолчанию значений и создания более конкретных фреймов. С помощью фреймов может быть предпринята попытка моделировать объекты реального мира

используя универсальные знания для описания большинства атрибутов того или иного объекта и более конкретные знания для описания частных случаев. Например, обычно принято рассматривать птиц как теплокровных, покрытых перьями живых существ, способных летать. Но некоторые птицы, такие как пингвины и страусы, не могут летать. Эти типы представляют более конкретные классы птица их характеристики могут обнаруживаться на более низких уровнях иерархии фреймов по сравнению с такими птицами, как канарейки или дура такого типа выполняется, если данные, представленные каким-то значением, устаревают. Заполнители слотов могут также содержать отношения по такому же принципу, который применяется при специализации слотов. На рис. 2.9 — показано, как используются отношения аи а для создания иерархических связей между фреймами. Фреймы,
представленные на рис. 2.9 и 2.10, являются универсальными, а фрейм, приведенный на рис. 2.11, является конкретным,
поскольку представляет собой экземпляр фрейма с описанием определенного автомобиля. Разрабатывая эти фреймы, мы руководствовались соглашением, что отношения а — kind — о являются универсальными, а отношения is — а конкретными Глава 2. Представление знаний 166 Рис. 2.11. Экземпляр фрейма с описанием определенного автомобиля дрозды. Иными словами, верхние уровни в иерархии фреймов с описанием птиц представляют характеристики, в большей степени относящиеся ко всем птицам, а нижние уровни обозначают нечеткие границы между объектами реального мира. Объект, обладающий всеми типичными характеристиками, принято называть прототипом;
этот термин буквально означает первичный тип. Кроме того,
классификация фреймов может проводиться на основании того,
в какой области они применяются. Ситуативные фреймы содержат знания о том, чего можно ожидать в какой-то конкретной ситуации, например, на вечеринке по случаю дня

рождения. С другой стороны, фреймы действия содержат слоты,
которые определяют действия, подлежащие выполнению в какой-то конкретной ситуации. Это означает, что заполнителями слотов являются процедуры, предназначенные для выполнения определенных действий, таких как удаление дефектной детали с конвейера. Фрейм действия представляет процедурные знания.
А для описания причинно-следственных отношений могут применяться фреймы причинных знаний, представляющие собой сочетания ситуативных фреймов и фреймов действия. На практике были созданы очень сложные системы фреймов,
предназначенные для решения самых различных задач. Одной из наиболее впечатляющих систем, продемонстрировавшей широкие возможности применения фреймов для творческого открытия математических понятий, стала программа АМ
(Automated Майе — автоматизированный математик)
Дуга Лената (Doug Lenat). В классической системе АМ Лената создавались, а затем исследовались сочетания интересных новых понятий. Эта система предложила некоторые совершенно новые математические доказательства для целого ряда теорем.
Другие многочисленные 2ЛО. Трудности, связанные с использованием фреймов примеры программ для доказательства теорем и систем совершения открытий приведены в том разделе приложения Ж,
который относится к данной главе. 2.10 Трудности, связанные с использованием фреймов Рис. 2.12. Фрейм elephant На первый взгляд создается впечатление, что фрейм elephant представляет собой приемлемое общее описание слонов. Однако предположим, что существует конкретный трехногий слон по кличке Клайд. Возможно, Клайд потерял ногу изза несчастного случая на охоте или просто притворяется, что у него нет одной ноги, чтобы попасть на страницы настоящей книги. Но важно то,
что во фрейме elephant содержится утверждение, будто любой слон имеет четыре ноги, а не три. Поэтому мы не можем рассматривать фрейм elephant как действительное определение

любого слона. Первоначально фреймы предназначались для использования в качестве способа представления стереотипных знаний. Важной особенностью любого стереотипа является то,
что он имеет вполне определенные характеристики, поэтому позволяет предоставить для многих своих слотов значения,
заданные по умолчанию. Наглядным примером стереотипов,
вполне подходящих для представления в виде фреймов,
являются математические понятия. Подход на основе фреймов имеет интуитивную привлекательность, поскольку обеспечиваемое сего помощью упорядоченное представление знаний, вообще говоря, в большей степени доступно для понимания по сравнению с логическими или продукционными системами, в которых для той же цели применяется целый ряд правил [51]. Тем не менее при использовании систем фреймов обнаруживаются существенные недостатки, связанные с тем,
что в этих системах допускается неограниченная модификация или уничтожение слотов. Классическим примером этой проблемы является фрейм elephant с описанием слонов,
который приведен на рис. 2.12.
168 Глава 2. Представление знаний Безусловно, этот фрейм можно модифицировать таким образом, чтобы он допускал в качестве исключения наличие трехногих, двуногих, одноногих или даже безногих слонов. Нов результате этого определение становится не очень качественным. Дополнительные проблемы могут возникать и при использовании других слатов.
Предположим, что Клайд переболел желтухой в тяжелой форме и его кожа стала желтой. Но разве из-за этого он перестал быть слоном Альтернативным по отношению к использованию фрейма в качестве определения является вариант, в котором фрейм рассматривается как описание, например, типичного слона. Но такой подход приводит к возникновению других проблем, связанных с наследованием. Обратите внимание на то, что во фрейме elephant указано, что слон относится к категории (а — kind — of) млекопитающих. А поскольку теперь

фреймы интерпретируются как описания типичных представителей, то наша система фреймов указывает, что типичный слон представляет собой типичное млекопитающее.
Тем не менее, хотя слон — млекопитающее, его, повидимому,
нельзя считать типичным млекопитающим. Судя по количеству особей, вероятно, название типичного млекопитающего с большим правом могут претендовать люди, коровы, крысы и овцы. В большинстве систем фреймов не предусмотрены способы определения неизменных слотов. А поскольку в связи с этим может подвергнуться изменениям любой слот, то свойства,
наследуемые одним фреймом от другого, могут быть изменены или исключены на любом уровне иерархии. Это означает, что любой фрейм по существу является примитивным, исходным фреймом, так как нет никаких гарантий того, что заданные в нем свойства будут общими. Каждый фрейм складывается из собственных правили поэтому каждый фрейм является изначальным. В такой неограниченной системе нив чем действительно нельзя быть уверенными поэтому невозможно формулировать общезначимые утверждения, подобные тем,
которые были сделаны при определении понятия слон. Кроме того, нет возможности достаточно надежно создавать сложные объекты на основании более простых определений, например,
описывать слона стремя ногами исходя из определения обычного слона. Проблемы подобного типа возникают и при использовании семантических сетей с наследованием. Если разрешено вносить изменения в свойства любого узла, тони в чем нельзя быть уверенным. Однако есть и другой способ трактовки фреймов, который является очень полезным. Если понятие фрейма будет расширено таким образом, чтобы оно охватывало свойства объектов, то появляется возможность рассматривать как фрейм любой объект. В язык CLIPS встроен полный объектно-ориентированный язык, называемый поэтому CLIPS может рассматриваться как расширение языка,
основанного на фреймах. С тех пор как в язык CLIPS был включен язык COOL, стали доступными все преимущества объектов. Поэтому на языке CLIPS могут создаваться объектно- ориентированные экспертные системы, позволяющие

использовать правила (рассматриваемые как небольшие фрагменты знаний) и вместе. Логика и теория множеств 169 2.11 Логика и теория множеств Кроме правил, фреймов и семантических сетей, для представления знаний могут использоваться символы логики
(логика изучает правила формирования неопровержимых рассуждений. Важной частью процесса формирования рассуждений является логический вывод заключений из посылок. Развитие способов применения компьютеров для осуществления рассуждений привело к созданию логического программирования и к разработке таких языков, основанных на логике, как PROLOG. Кроме того, логика играет чрезвычайно важную роль в экспертных системах, поскольку в таких системах применяются машины логического вывода, проводящие рассуждения от фактов к заключениям. В действительности для обозначения систем логического программирования и экспертных систем используется общий описательный термин автоматизированные системы формирования рассуждений.
Самая ранняя система формальной логики была разработана древнегреческим философом Аристотелем в IV веке до н.э.
Аристотелевская логика основана на понятии силлогизма.
Аристотель изобрел четырнадцать типов силлогизмов, а еще пять типов были предложены во времена Средневековья.
Силлогизмы имеют две посылки и одно заключение, которое вытекает из посылок. Классический пример силлогизма приведен ниже. Посылка. Все люди смертны Посылка. Сократ человек Заключение. Сократ сыертен В силлогизме посылки служат в качестве свидетельств, из которых должно обязательно следовать заключение. Силлогизм — это один из способов представления знаний. Еще одним таким способом являются диаграммы Венна (рис. 2.13). Внешний круг представляет все смертные создания, а внутренний круг, обозначающий людей,
изображается полностью внутри круга, представляющего смертных, для указания на то, что все люди смертны. Поскольку

Сократ — человек, то представляющий его круг полностью находится внутри круга, представ- стем предоставляющие возможность организовывать более крупные фрагменты знаний в виде объектов в целях упрощения разработки и сопровождения. Правила могут применяться для работы с фактами или объектами, и поэтому CLIPS обладает всеми преимущества двух категорий инструментальных средств экспертных систем — основанных на правилах и основанных на объектах. Благодаря применению объектов в языке становится проще создавать, эксплуатировать и сопровождать крупные базы знаний по сравнению с такими системами, в которых предпринимаются попытки представить всезнания в тысячах отдельных правили фактов Глава 2. Представление знаний 170 Рис. 2.13. Диаграмма
Венна ляющего людей. Строго говоря, круг, представляющий
Сократа, должен выглядеть как точка, поскольку подразумевается, что круг обозначает класс. Но для удобства мы будем использовать круги при обозначении любых объектов.
Заключение, что Сократ смертен, следует из того факта, что его круг находится внутри круга смертных созданий, поэтому он также должен быть смертным. Сточки зрения математики любой круг на диаграмме Венна представляет множество, т.е.
коллекцию объектов. Объекты, принадлежащие множеству,
называются элементами множества. Некоторые примеры множеств приведены ниже. А = (1,3,5) ВСЕ) В этих примерах три точки, ..., называемые троеточием, указывают, что перечень термов продолжается до бесконечности. Символ в виде греческой буквы эпсилон (Е)
указывает, что некоторый элемент принадлежит к множеству.
Например, выражение 1 Е А означает, что число 1 — элемент ранее определенного множества А. Если элемент не принадлежит к множеству, то для обозначения этого используется символ ф, как в примере 2 ф А. Если два

произвольных множества, допустим, Хи У, определены так, что каждый элемент Х является элементом У, то Х является подмножеством У это утверждение записывается в математической форме, как Х СУ, или У а Х 2.11. Логика и теория множеств 171 C — — À Ã1 Â Рис. Пересечение множеств Здесь символ fl представляет операцию пересечения множеств. Еще один способ записи этого утверждения может быть сформулирован в терминах элементов х следующим образом С = (х Е U (х с А) Л (х Е В) Из указанного определения подмножества следует, что каждое множество является подмножеством самого себя. А
подмножество, не совпадающее с самим множеством,
называется строгим подмножеством. Например, множество Х,
которое определено выше, является строгим подмножеством множества У. Входе рассуждений о множествах удобно считать рассматриваемые множества подмножествами универсального множества. При смене темы обсуждения изменяется и само универсальное множество (универсум. На рис. 2.14 показано подмножество, сформированное в результате пересечения двух множеств в универсуме всех автомобилей. А при обсуждении целых чисел универсумом являются все целые числа.
Универсум отображается как прямоугольник, окружающий свои подмножества. Универсальные множества используются не только для удобства. Неразборчивое использование условий для определения множеств может приводить к логическим парадоксам, а универсальные множества позволяют избежать таких парадоксов. Допустим, что А — множество всех синих автомобилей, В — множество всех автомобилей с ручной передачей, а С — множество всех синих автомобилей с ручной передачей. В таком случае можно записать следующее Глава 2. Представление знаний В этом выражении обозначает универсальное множество. Символ читается

такой, что. Вместо символа иногда используется двоеточие. Символ Л обозначает логическую операцию Приведенное выше выражение, определяющее множество Считается так С состоит из элементов х универсума U, таких, что х является элементом Аи х является элементом В. Логическая связка AND впервые была определена в булевой алгебре.
Выражение, состоящее из двух операндов, связанных знаком логической операции AND, является истинным тогда и только тогда, когда оба операнда являются истинными. Если множества
А и Вне имеют общих элементов, то А П В = И, где греческая буква фи (И) представляет пустое множество, или множество меры нуль, ), которое не содержит элементов. Иногда для обозначения пустого множества используется греческая буква лямбда (Л. В качестве других обозначений для универсального множества применяется цифра 1, а пустого множества — цифра
О. Хотя пустое множество не имеет элементов, оно все еще остается множеством. В качестве примера можно привести ресторан с множеством клиентов. Если в ресторан никто не пришел, то множество клиентов пусто, но ресторан из-за этого не перестает существовать. К другим операциям с множествами относится обьединение, которое представляет собой множество всех элементов, принадлежащих либо множеству А, либо множеству В, либо обоим множествам одновременно Аи В = (x e U i (x е Ас В) А' = (x c U i -(x c А) В этом выражении штрих (') обозначает дополнение множества. Символ тильды ( представляет логический оператор NOT. Диаграммы Венна,
представляющие основные операции над множествами,
показаны на рис. 2.15. 2.12 Пропозициональная логика
Старейшим и одним из простейших типов формальной логики является силлогизм. Термин формспьный означает, что логика, к которой он относится, распространяется только на форму логических утверждений, ноне учитывает их значения. Иными словами, в формальной логике рассматривается только синтаксис утверждений, а не их семантика. Такое свойство логики становится чрезвычайно важным при создании экспертных системах, поскольку позволяет отделить В этом выражении символ U представляет операцию объединения

множеств. Символ V обозначает логическую операцию Дополнением множества А является множество всех элементов,
не принадлежащих к А 2.12. Пропозициональная логика 173 Рис. 2.15. Диаграммы
Венна, представляющие основные операции с множествами знания от рассуждений. Дело в том, что иногда высказывания,
которые внешне выглядят как рассуждения, могут представлять собой знания. Например, утверждение "Президент всегда прав,
поскольку он никогда не бывает неправ" внешне напоминает рассуждение в связи с наличием в нем слова "поскольку",
которое связывает две части предложения. Но фактически утверждение подобного типа представляет собой тавтологию,
поскольку, в отличие от фактов, которые могут быть в реальном мире истинными или не истинными, тавтология всегда в чисто логическом смысле истинна, так как ссылается для доказательства на саму себя. В действительности в этой тавтологии утверждается "Х есть Х. Но если вы не принадлежите к той же политической партии, что и Президент, то можете не согласиться с этим утверждением исходя из его семантики, а не формы, и предпочесть другую тавтологию:
"Президент всегда неправ, поскольку он никогда не бывает прав. Безусловно, для многих термин формальная логика звучит устрашающе, но логика не сложнее, чем алгебра. В
действительности алгебра фактически пред Глава 2. Представление знаний ставляет собой формальную логику чисел. Например, предположим, что вас попросили решить такую задачу в школе имеются компьютеров с общим количеством микросхем памяти, равным. В некоторых компьютерах имеется две микросхемы памяти,
в других — четыре. Каково количество компьютеров того и другого типа Решение этой задачи может быть записано алгебраически следующим образом 25=Х+У 60 = Х -+- У

Посылка. Все сквиги являются ыуфаыи Посылка. Джон — сквиг
Заключение. Джон — муф Безусловно, слова сквиг и муф не имеют смысла и значения, но форма приведенного выше доказательства из-за этого не перестает быть правильной. Это означает, что рассматриваемое доказательство остается действительным, независимо оттого, какие слова в нем используются, поскольку применяемый в нем силлогизм имеет действительную форму. Фактически действительным является любой силлогизм в следующей форме, независимо от того,
какие слова будут подставлены вместо Х, У и Z: Посылка. Все Х
суть Y Посылка. Z есть Х Заключение. Z есть Y Этот пример показывает, что в формальной логике смысл не учитывается и имеет значение только форма или внешнее представление.
Логика становится После чего эту систему уравнения можно легко решить и получить Хи У = 5. А теперь рассмотрим следующую задачу. На скотном дворе имеется 25 животных с общим количеством ног, равным 60. Некоторые из этих животных имеют две ноги, а другие — четыре. (Примечание.

дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д