|
дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
Противоположным по отношению к этому предложению является предложение "ни одна собака не является животным",
которое записывается следующим образом 2.14. Квантор всеобщности 183 что Н — предикативная функция, обозначающая людей, а М — функция, обозначающая смертных. В таком случае утверждение, согласно которому все люди смертны, можно записать таким образом:
(Чх)(Н(х) -+ М(х)) IF х — человек THEN х сыертен Рис. Представление утверждения логики предикатов в виде семантической сети Квантор всеобщности может также интерпретироваться как конъюнкция предикатов, относящихся к отдельным экземплярам. Как было указано выше, экземпляром называется конкретный случай. Например, допустим, что собака по имени Спарклер представляет собой конкретный экземпляр класса собак. Эту мысль можно выразить следующим образом) В данном примере Dog — предикативная функция,
а Sparkler — экземпляр. Такое предложение логики предикатов:
(Мх) Р(х) может интерпретироваться в терминах экземпляров а,,
как показано ниже. Р(а) Л P(a>) Л Раз) Л . Л P(a
) В этом случае многоточие указывает, что действие предиката распространяется на все элементы данного класса. Таким образом, в приведенном выше выражении сказано, что предикат применяется ко всем экземплярам класса. В выражениях может использоваться несколько кванторов. Например, как показано ниже, для формулировки закона коммутативности сложения для чисел требуются два квантора. (Чх)(Чу)(х + р = д + х) Это утверждение читается так для всех х, если х — человек, то х смертен. Как показано на рис. 2.16, это предложение логики предикатов может быть также представлено с помощью семантической сети. Кроме того, оно может быть выражено в терминах правил Глава 2. Представление знаний 184 В этом выражении утверждается, что "для каждого хи для каждого у суммах и у равна сумме у их Квантор существования Квантором еще одного типа является квантор существования. Квантор существования определяет утверждение как истинное применительно по крайней мере к одному элементу области определения. Он представляет собой ограниченную форму квантора всеобщности (в котором утверждается, что некоторое выражение является истинным для всех элементов области определения. Квантор существования записывается как символ, за которым следует одна или несколько переменных, например, как показано ниже. (х) (х х = 1) (3x) (elephant(x) Л пате(Сtyde)) существует по меньшей мере один для некоторых иыеется некоторый некоторые В качестве еще одного примера можно привести выражение, в котором указано, что все слоны имеют четыре ноги (Чх) (elephant(x) - four-legged(x) ) А утверждение, что некоторые слоны имеют три ноги, записывается со знаком логической операции AND и квантором существования следующим образом (3x) (elephant(x) Л three- legged(x) ) Также как квантор всеобщности может быть выражен с помощью конъюнкции, квантор существования может быть выражен с помощью дизъюнкции экземпляров, а Р(а,) V Р(а2) V Р(а,) V V P(a) В табл. б в качестве примеров приведены утверждения с кванторами, в которых Р обозначает предложение "слоны — млекопитающие, и их отрицания. В первом из приведенных выше предложений указано, что имеется некоторое число х, результат умножения которого на самого себя равен 1. Во втором выражении сказано, что существует некоторый слон по кличке Клайд. Квантор существования можно прочитать несколькими способами, в частности, таким образом 2.16. Кванторы и множества 185 Числа в круглых скобках обозначают примеры, которые будут рассматриваться в последующем описании. Таблица 2.6. Примеры отрицаемых кванторов Пример Значение (а) (Vx) (Р) Все слоны млекопитающие (Ь) (Зх) ( Р) Некоторые слоны не млекопитающие (а) (Зх) (Р) Некоторые слоны млекопитающие (Ь) (Võ) ( P) Никакие слоны не млекопитающие Кванторы и множества Кванторы и множества могут использоваться для определения подмножеств универсального множества U, как показано в табл. 2.7. Таблица 2.7. Некоторые выражения с множествами и их логические эквиваленты Выражение с множествами Логический эквивалент Чх(х C Ах В) Vx(x C Ах ВАЛ х ЕВА- В Е U (х Е АТ (истинное значение) F (ложное значение) А=В АсВ А 5 В АОВ А' U (универсальное множество) Я (пустое множество) Отношение, согласно которому А является строгим подмножеством В (имеющее вид А<В), означает, что все элементы множества А принадлежат к множеству В, нов свою очередь, в множестве В имеется хотя бы один элемент, не принадлежащий к множеству А. Предположим, что Е обозначает всех слонов, а М всех млекопитающих. В таком случае следующее отношение между множествами представляет собой утверждение, что все слоны — млекопитающие, ноне все Примеры (аи (Ь) являются отрицаниями по отношению друг к другу таковыми являются также примеры (аи (Ь. Обратите внимание на то, что отрицанием выражения с квантором всеобщности из примера (а) становится выражение с отрицанием предложения P с квантором существования, как показано в примере (Ь. Аналогичным образом отрицание выражения с квантором существования из примера (2а) представляет выражение с отрицанием предложения P и квантором всеобщности, как показано в примере (Глава 2. Представление знаний 186 млекопитающие являются слонами (EnGnF) сМ Ниже приведены некоторые примеры предложений с кванторами, в которых используются указанные обозначения. E — слоны R — рептилии С — серые F четырехногие D — собаки М — млекопитающие Никакие слоны не являются рептилиями о Некоторые слоны — серые ЕлСфо Никакие слоны не являются серыми о Некоторые слоны не являются серыми ф о Все слоны являются серыми и четырехногими Ес (GnF) Все слоны и собаки являются млекопитающими (EUD) с М Некоторые слоны являются четырехногими и серыми (EnFnG) фо Обозначив множество животных серого цвета как G, а множество животных с четырьмя ногами — как F, можно записать утверждение, что все серые и четырехногие слоны являются млекопитающими, следующим образом. Ограничения логики предикатов 187 Между формой представления информации с помощью множеств и логической формой имеется еще одна аналогия, которая выражается в виде законов де Моргана, как показано в табл. 2.8. Символ эквивалентности (=), те. знак двусторонней условной операции, означает, что выражение, находящееся слева от него, имеет такое же истинностное значение, как и выражение, находящееся справа. Это означает, что указанные выражения эквивалентны. Таблица 2.8. Законы де Моргана, представленные в форме с использованием множеств и логической форме Форма с использованием множеств Логическая форма (А п В' = Аи В' (Аи В' = А' п В' -р л о) — -ð v -q -(p v q) — -рл-д 2.17 Ограничения логики предикатов Безусловно, логика предикатов применима в ситуациях многих типов, но некоторые типы утверждений невозможно представить на основе логики предикатов с использованием кванторов всеобщности и кванторов существования. Например, в логике предикатов невозможно выразить следующее утверждение Большинство учащихся в классе получили оценки отлично 2.18 Резюме В настоящей главе приведены основные сведения о логике, представлении знаний и некоторых методах представления знаний. Выбор правильного метода представления знаний в экспертных системах имеет очень важное значение. В этом утверждении квантор "большинство" означает "больше половины. Квантор "большинство" не может быть выражен в терминах квантора всеобщности и квантора существования. Для реализации квантора "большинство" в логике должны быть предусмотрены некоторые предикаты, обеспечивающие подсчет количества элементов, что возможно при использовании нечеткой логики, описанной в главе 5. Еще одно ограничение логики предикатов состоит в том, что она не позволяет выражать зависимости, которые могут быть истинными только иногда, ноне всегда. Указанная проблема также может быть решена с помощью нечеткой логики. Однако внедрение в логическую систему средств проведения вычислений влечет за собой также появление дополнительных усложнений к тому же в результате логика начинает в большей степени напоминать математику. Глава 2. Представление знаний 188 Задачи 2.1. Нарисуйте семантическую сеть для классификации компьютеров с использованием связей АКО и А. Рассмотрите такие классы, как микрокомпьютеры мэйнфреймы; суперкомпьютеры; вычислительные системы выделенные компьютеры; компьютеры общего назначения одноплатные компьютеры; компьютеры, реализованные в виде одной микросхемы; однопроцессорные и многопроцессорные компьютеры. Включите данные о конкретных экземплярах. 2.2. Нарисуйте семантическую сеть для классификации средств обеспечения межкомпьютерного взаимодействия с использованием связей АКО и А. Рассмотрите такие классы, как локальные сети, глобальные сети, сети с маркерным кольцом, звездообразные сети, централизованные сети, децентрализованные сети, распределенные сети, сети с модемными линиями связи, телекоммуникационные сети, группы новостей и электронная почта. Включите данные о конкретных экземплярах. Рассматривались также логические ошибки, поскольку для инженера познаниям важно понимать правила предметной области и не путать форму представления знаний с семантикой. Если не заданы формальные правила, то экспертная система может не позволить достичь правильных заключений, что повлечет за собой губительные последствия при эксплуатации таких ответственных систем, от которых зависит жизнь и собственность людей. Сточки зрения логики знания могут классифицироваться многими способами и рассматриваться как априорные, апостериорные, процедурные, декларативные и неявные. К числу методов, широко применяемых в экспертных системах для представления знаний, относятся продукционные правила, объекты, семантические сети, схемы, фреймы и логика. Каждый из указанных подходов имеет свои преимущества и недостатки. Прежде чем приступать к проектированию экспертной системы, необходимо принять решение о том, какой из способов представления знаний может стать основой выбора подхода к решению рассматриваемой задачи. Следует не пытаться применять одно и тоже инструментальное средство для решения всех задача выбирать каждый раз наилучшее средство. Кроме того, в данной главе речь шла о том преимуществе языка CLIPS, что он позволяет представлять знания не только с помощью объектов, но и с помощью правил. Многочисленные ссылки, с помощью которых можно ознакомиться с дополнительной информацией о логике, знаниях и логических ошибках приведены в приложении Ж. В приложениях А — В содержатся полезные справочные сведения об эквивалентностях, кванторах и свойствах множеств. Задачи 189 2.3. Нарисуйте систему фреймов для описания здания, в котором вы проходите обучение. Предусмотрите возможность представить данные об офисах, аудиториях, лабораториях и т.д. Включите данные о конкретных экземплярах с заполненными слотами для одного фрейма каждого типа, такого как офис и аудитория. 2.5. Нарисуйте диаграммы Венна и обозначьте отдельные элементы каждой диаграммы как термы выражений, в которых используются описанные ниже операции с множествами. В приведенных примерах (1, 2) — первое множество, а (2, 3) — второе. а) Результат операции "исключительное ИЛИ" с двумя множествами, Аи В, состоит из всех элементов, которые находятся или водном, или в другом, но не обоих множествах одновременно. Операцию "исключительное ИЛИ" называют также симметрической разностью множеств и обозначают знаком операции (Например (1,2)/(2,3) = (1,3) б) Результат выполнения операции разности множеств с двумя множествами, которая обозначается знаком операции ( — ), состоит из всех элементов первого множества, которые не принадлежат также ко второму множеству. Например (1, 2) — (2, 3) = (1) 2.6. Составьте истинностные таблицы и определите, какие из следующих выражений представляют собой тавтологии, противоречия или контингентные утверждения, и какие не относятся ник одному из этих типов. При выполнении упражнений аи б) вначале представьте рассматриваемые утверждения с помощью логических символов и связок. а) Если я пройду этот курс и получу оценку "отлично, то я пройду этот курс или получу оценку "отлично. б) Если я пройду этот курс, то получу оценку "отлично" и я пройду этот курс и не получу оценку "отлично. в) ((АЛ В (СЛ С) - (А - В. 2.4. Нарисуйте систему фреймов действия, позволяющую узнать, какие действия следует предпринять в случае аппаратного отказа конкретной компьютерной системы. Рассмотрите возможность аварийного отказа диска, источника электропитания, процессора и памяти Глава 2. Представление знаний г) (А — +В)Л( ВVС)Л(АЛ С). д) А - В (контингентное утверждение. 2.7. Два предложения логически эквивалентны тогда и только тогда, когда они имеют одно и тоже истинностное значение. Таким образом, если Аи В любые утверждения, то следующее выражение с двусторонним условным оператором становится истинным при любых значениях утверждений, входящих в его состав, те превращается в тавтологию А — Вили эквивалентность А В Определите, являются ли два приведенных ниже предложения логически эквивалентными, записав их с использованием логических символов, а также определите, показывает ли истинностная таблица двусторонней условной операции с этими предложениями, что полученное выражение представляет собой тавтологию. Если выедите банановый сплит, тоне можете есть торт. Если выедите торт, тоне можете есть банановый сплит. 2.8. Запишите логическое выражение, эквивалентное выражениям с соответствующими операциями разности множеств и симметрической разности множеств. 2.9. Покажите, что следующие эквивалентности соблюдаются для любых множеств А, В, Си пустого множества И. а) (Аи В) = (В и А. б) (А и В) и С = Аи (В и Св) АО И = А. г) АflВ=ВйА. д) АПА'=И. 2.10. Запишите приведенные ниже утверждения в квантифицированной форме. а) Все собаки — млекопитающие. б) Никакая собака не является слоном. в) Некоторые программы содержат ошибки. r) Ни одна из моих программ не содержит ошибок. д) Все ваши программы содержат ошибки. Степенным множеством P(S) множества S называется множество, все элементы которого представляют собой подмножества множества S. Множество P(S) всегда содержит по меньшей мере такие элементы, как пустое множество И и множество S. 191 Задачи а) Найдите степенное множество множества А = (2, 4, 6].. б) Сколько элементов содержит степенное множество множества с N элементами а) Запишите истинностную таблицу для выражений, представленных в табл. 2.9. Таблица Логические выражения, которым могут быть даны осмысленные определения Осмысленное определение Выражение б) Покажите, что (р Vq) Л (рЛ q) р где знак обозначает операцию "исключительное ИЛИ. а) Запишите истинностные таблицы для операций NAND и NOR. б) Докажите, что (Д и (I) — адекватные множества, представив связки , Ли в терминах связки , а затем — связки . Для этого составьте истинностные таблицы, чтобы показать, что следующие выражения представляют собой логические эквивалентности (р л др) -р = рр (uvq) = — (р IS) l (q I q) в) Поскольку р - q=(phq), представьте выражение р — + q с помощью знаков операции . г) Каковы преимущества и недостатки использования адекватных одно- элементных множеств, во-первых, сточки зрения удобства использования системы обозначений, и, во-вторых, конструирования электронных схем для микросхем 2.12. Выполните следующие задания. либо р либо q нирниц р если не q р потому что q никакие р не есть q 2.13. Выполните следующие упражнения. (p v q) л -р л др) чр (рЛq) Л(др) p Глава 2. Представление знаний 192 2.14. Каковы преимущества и недостатки проектирования экспертной системы со знаниями, относящимися к нескольким предметным областям Объясните, почему приходится по-разному кипятить воду в высокогорной местности (например, в Денвере) и на равнине (например, в Хьюстоне, если в процессе кипячения воды готовится яйцо, которое должно быть сварено вкрутую. Относится ли эта задача к проблематике логики или физики. Даны приведенные ниже операторы PROLOG; докажите, что Том — дедушка самого себя. mother(pat,ann). parents(jim,ann,tom). surrogatemother (pat,tom). ; Пэт — мать Энн Джим и Энн — родители Тома ; Пэт — суррогатная мать Тома Глава Методы логического вывода 3.1 Введение Настоящая глава представляет собой вводное описание методов формирования рассуждений о знаниях. При изучении этих методов необходимо отделить смысл слов, используемых в рассуждениях, от самих рассуждений, чтобы иметь возможность рассматривать данную тему на основе формального подхода, обсуждая различные методы логического вывода [83]. В частности, в данной главе будет рассматриваться важный вид рассуждений, применяемый в экспертных системах, в котором заключения логически выводятся из фактов с использованием правиЛ. Такой вид рассуждений имеет особое значение в экспертных системах, поскольку формирование логических выводов — это фундаментальный метод решения задач в экспертных системах [60]. Как было сказано в главе экспертные системы обычно используются в том случае, если отсутствует подходящий алгоритм или алгоритмическое решение. Экспертная система должна построить цепь логических выводов для выработки решения по такому же принципу, как это делают люди, особенно если сталкиваются с неполной или недостающей информацией. Простая компьютерная программа, в которой для решения задачи применяется некоторый алгоритм, просто неспособна выдать ответ, если не заданы все необходимые параметры. С другой стороны, экспертная система вырабатывает наилучшее предположение также, как это делает человек, если ему приходится решать некоторую задачу, а оптимальное решение не может быть определено. Идея состоит в том, что экспертная система должна предложить хотя бы какое-то решение так же, как мог бы сделать человек, в надежде на то, что это решение (к счастью) окажется удачным, а не оставлять задачу вообще нерешенной. Безусловно, полученное решение может лишь на 95'Ы приближаться к оптимальному решению, но это все равно Глава 3. Методы логического вывода 194 лучше, чем полное отсутствие решения. В таком подходе фактически нет ничего нового. Например, в математике для решения задач, не имеющих аналитического решения, уже в течение многих столетий используются числовые расчеты, такие как метод решения дифференциальных уравнений Рунге — Кутта. Примечание. Полезный справочный материал к этой главе содержится в приложениях А — В. 3.2 Деревья, решетки и графы Дерево — это иерархическая структура данных
|
|
|
Скачать 3.73 Mb.