дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
Наш трехногий слон Клайд находится в Африке, а не на этом скотном дворе) Сколько имеется животных каждого типа?вызванных семантикой. В качестве аналогии для формальной логики может рассматриваться алгебра, в которой правильность таких выражений, как Х + Х = Х, остается неоспоримой, независимо оттого, обозначает ли Х целое число, количество яблок или аэропланов. Аристотелевы силлогизмы оставались фундаментом логики до 1847 года, пока английский математик Джордж Буль (George Вооlе) опубликовал первую книгу с описанием символической логики. Безусловно, Лейбниц) разработал свою собственную версию символической логики в XVII веке, но эта версия таки не получила широкого распространения. Одним из новых понятий, предложенных Булем, явилась модификация аристотелева представления, называемого экзистенциальным значением, согласно которому субъект рассуждений должен существовать. В соответствии с классическими аристотелевыми взглядами такое высказывание, как "все русалки хорошо плавают, не может использоваться как посылка или следствие, поскольку русалки не существуют. А булевы представления, получившие теперь название современных представлений, ослабляют указанное ограничение. Важность современных представлений состоит в том, что они позволяют рассуждать о пустых классах объектов. Например, такое высказывание, как "все жесткие диски, которые отказывают, являются дешевыми, не может использоваться в аристотелевом силлогизме, если мы не можем вести речь хотя бы об одном фактически отказавшем диске. Еще один вклад, сделанный Булем, состоял в том, что этот ученый дал определение понятия множества аксиом. Формулировки аксиом состоят из символов, применяемых для представления объектов и классов, а также алгебраических операций, применяемых для манипулирования этими символами. Аксиомы представляют собой фундаментальные определения, на основании которых создаются сами логические системы, такие как математика и логика. А используя лишь одни аксиомы, можно создавать теоремы. Теорема — это утверждение, которое может быть доказано путем демонстрации того, что оно следует из аксиом. В период между 1910 и 1913 годами Уайтхед (Whitehead) и Расселл (Russell) опубликовали свою монументальную трехтомную работу Principia Mathematica, состоящую из страниц, в которой было показано, что формальная логика может служить основанием математики. Публикация указанной работы была признана важной вехой в развитии математики, поскольку Уайтхед и Расселл показали в ней, как перенести всю математику на твердое основание (а не прибегать к интуиции), полностью отказавшись от смыслового толкования арифметики и вместо этого сосредоточившись на внешних формах и манипуляциях сними. По этой причине Глава 2. Представление знаний 176 Таблица 2.2. Типы предложений Тип Пример Сделайте то, что я вам говорю Что это Повелительные Вопросительные Восклицательные Это великолепно Повествовательные Квадрат имеет четыре равные стороны В пропозициональной логике рассматриваются подмножества предложений, представляющих собой повествовательные предложения, которые могут подразделяться на истинные или ложные. Очевидно, что предложение "Квадрат имеет четыре равные стороны" обладает истинностным значением истина, а предложение "Джордж Вашингтон был вторым по счету президентом США" обладает истинностным значением ложь. Предложение, истинностное значение которого математику иногда в шутку называют "способом нанесения на бумагу бессмысленных знаков. В году знаменитый математик Гёдель (Godel) доказал, что не всегда возможно обосновать внутреннюю согласованность и отсутствие противоречий в формальных системах, основанных на аксиомах. Доказательство Гёделя вызвало значительное замешательство среди математиков, которые надеялись на то, что когда-либо удастся рази навсегда доказать истинность арифметики. Но это не означает, что (как могло бы показаться неосведомленному человеку) мы фактически не можем быть уверены в правильности арифметических расчетов (следует отметить, что любой профессиональный математик, читая эти разглагольствования, найдет их весьма забавными). Пропозициональная логика, иногда называемая пропозициональным исчислением, — это символическая логика, применяемая для манипулирования высказываниями. В частности, пропозициональная логика может использоваться для манипулирования логическими переменными, обозначающими высказывания. Безусловно, большинство людей считают, что исчисление есть нечто подобное математическим системам, которые изобретены Ньютоном и Лейбницем, но этот термин имеет более общий смысл. Аналог термина исчисление в английском языке (calculus) произошел от латинского слова, которое обозначало маленький камешек, используемый при выполнении расчетов. В своем наиболее общем смысле термин исчисление обозначает специальную систему манипулирования символами. С другой стороны, для обозначения пропозициональной логики применяются также такие термины, как исчисление утверждений и исчисление высказываний. Вообще говоря, в пропозициональной логике рассматривается определенный тип предложений естественного языка, асами эти предложения, как показано в табл. подразделяются на четыре основных типа 2 12. Пропозициональная логика Таблица 2.3. Широко применяемые логические связки Значение Связка конъюнкция OR; дизъюнкция NOT; отрицание если. то...; условная операция если и только если двусторонняя условная операция Строго говоря, знак операции отрицания — это не связка, поскольку отрицание представляет собой унарную операцию, применяемую к одному операнду, следующему за знаком этой операции, те. фактически знак операции отрицания ничего не связывает. Операция отрицания имеет более высокий приоритет по сравнению может быть определено, называется утверждением, или высказыванием. Высказывание принято называть также закрытым предложением, поскольку его истинностное значение не подлежит обсуждению. Если бы авторы снабдили настоящую книгу предисловием, в котором было бы сказано "все, что содержится на этих страницах ложно, такое предложение нельзя было бы рассматривать никак истинное, никак ложное. Если бы оно было истинным, то сказанное в предисловии было бы истинным, а это невозможно. Если же такое предложение не является истинным, то все, что содержится в книге, должно быть истинными это означает, что высказанное предложение ложно, а это также не может быть истинным. Предложения подобного типа известны как формулировки парадокса лжеца. Предложения, на которые невозможно дать однозначный ответ, называются открытыми предложениями. Например, открытым является предложение "Шпинат имеет превосходный вкус, поскольку оно является истинным для одних людей и ложным для других. Предложение "Он имеет высокий рост" также является открытым, поскольку в нем содержится местоимение "она не указан конкретный человек. Истинностное значение не может быть присвоено открытому предложению до тех пор, пока не станет известно конкретное лицо (или персонаж, на которое указывает это местоимение. Еще одно затруднение, возникающее при анализе рассматриваемого предложения, состоит в определении смысла выражения "высокий рост. Человек, который для одних кажется высоким, другим может не показаться таковым. С подобной неоднозначностью понятия "высокий рост" невозможно справиться с помощью пропозициональной логики или логики предикатов, но такие проблемы легко решаются с использованием нечеткой логики, которая рассматривается в главе 5. Путем применения логических связок к отдельным высказываниям могут быть сформированы составные высказывания. Наиболее широко применяемые логические связки показаны в табл. 2.3. 178 Глава 2. Представление знаний с другими операциями, поэтому нет необходимости задавать круглые скобки вокруг выражения, в котором она применяется. Таким образом, выражение р Л q означает тоже, что и выражение (р) Л Условная операция аналогична стрелке продукционных правил в том, что также может быть представлена в форма IF — Например, следующее выражение IF идет дождь THEN захвати с собой зонтик может быть представлено в такой форме РЧ в которой применяются следующие обозначения р — идет дождь q — захвати с собой зонтик Иногда вместо символа - используется символ . Для обозначения условной операции применяется также другой термин — материальная импликация. Двусторонняя условная операция, р - q, эквивалентна приведенному ниже выражению и является истинной только тогда, когда р и q имеют одинаковые истинностные значения. (р q) Л(др) Таким образом, выражение р q является истинным, только если р и q одновременно имеют истинное значение или ложное значение. Двусторонняя условная операция имеет такие толкования р если и только если q q если и только если р если р то q, и если д тор Как уже было сказано выше, тавтология — это составное высказывание, которое всегда является истинным, независимо оттого, истинны или ложны отдельные высказывания, входящие в его состав. С другой стороны, противоречиеэто составное высказывание, которое всегда является ложным. А контингентными называются высказывания, которые не представляют собой ни тавтологию, ни противоречие. Тавтологии и противоречия называются соответственно аналитически истинными и аналитически ложными высказываниями, поскольку их истинностное значение может быть определено исключительно на основании анализа формы. Например, истинностная таблица для выражения р V р показывает, что это — тавтология, а для выражения р Л р, что это — противоречие. Если условная операция одновременно представляет собой тавтологию, то эта операция именуется импликацией и содержит символ вместо символа -. 2.12. Пропозициональная логика 179 РЧ в котором р и q представляют собой любые высказывания, то данное выражение может быть переведено на естественный язык таким образом р влечет за собой q если р то q q только если р р является достаточным для q q если р q является необходимым для р Например, допустим, что через р обозначено высказывание "гражданин в возрасте 18 лет или старше, а q обозначает высказывание "имеет право голосовать. Условное выражение р - q может обозначать любое из следующих предложений гражданин находится в возрасте 18 лет или старше, и это влечет за собой, что данный гражданин имеет право голосовать если гражданин находится в возрасте 18 лет или старше, то данный гражданин имеет право голосовать гражданин имеет право голосовать, только если этот гражданин находится в возрасте 18 лет или старше гражданин находится в возрасте 18 лет или старше, и этого достаточно, чтобы данный гражданин имел право голосовать Двусторонняя условная операция, которая одновременно представляет собой тавтологию, называется логической эквивалентностью, или материальной эквивалентностью, и символически обозначается с помощью символа =» или =. Два логически эквивалентных высказывания всегда имеют одно и тоже истинностное значения. Например, р = р. К сожалению, не существует единственного возможного определения для импликации, поскольку количество истинностных таблиц для двух переменных, которые могут принимать истинные и ложные значения, равно 16. Поэтому в ранних экспертных системах, которые разрабатывались в х годах, применялись одиннадцать разных определений для операции импликации. Условная операция не имеет точно такой же смысл, как и выражение IF — THEN в процедурном языке или в экспертной системе, основанной на правилах. В процедурных языках ив экспертных системах конструкция IF — THEN указывает, что если истинны условия в определении IF, то должны быть выполнены действия, описания которых следует за ключевым словом THEN. А в логике значение условной операции определяется по ее истинностной таблице. Смысл такой операции может быть переведен на естественный язык многими способами. Например, если дано следующее выражение Глава 2. Представление знаний гражданин имеет право голосовать, если этот гражданин находится в возрасте 18 лет или старше гражданин должен иметь возраст 18 лет или старше, и это условие является необходимым для того, чтобы он имел право голосовать Таблица 2.4. Истинностная таблица для бинарных логических связок рлд рч РЧ Таблица Истинностная таблица для связки отрицания Множество логических связок называется адекватным, если с помощью связок, взятых только из этого множества, можно представить любую истинностную функцию. К примерам адекватных множеств относятся (, Л, V) (, Ли. Множество, содержащее единственный элемент, называется одноэлементным множеством. Одноэлементными являются два из адекватных множеств. Эти множества включают связки NOT- OR (NOR) и NOT-AND (NAND). Множество со связкой обозначается как Щ, а множество со связкой NAND — как (Знак операции () называется штрихом, или дизьюнкцией отрицаний. Этот знак используется для отрицания того, что р и q одновременно являются истинными. В некоторых случаях потребовалось изменить формулировки, чтобы полученные предложения стали грамматически правильными предложениями естественного языка. В последнем предложении говорится о том, что если не выполняется требование, обозначенное как q, тоне выполняется и р. Это предложение можно представить на правильном естественном языке так "Чтобы получить возможность голосовать, необходимо иметь возраст 18 лет или старше. Значения бинарных логических связок показаны в табл. 2.4. Эти связки называются бинарными, так как требуют двух операндов. Связка отрицания ( ) представляет собой знак унарной операции, применяемой к одному операнду, который следует за этим знаком (табл. 2.5). 2.13. Логика предикатов первого порядка 181 Таким образом, в выражении р q утверждается, что по меньшей мере одно из высказываний р или q является истинным. А в операции конъюнкции отрицаний) отрицается то, что является истинным либо р, либо о. Это означает, что в выражении р l q утверждается, что р и о одновременно являются ложными. Логика предикатов первого порядка Безусловно, пропозициональная логика является очень полезной, но имеет целый ряд ограничений. Основная проблема состоит в том, что пропозициональная логика может применяться только с полным высказыванием. Это означает, что с ее помощью нельзя исследовать внутреннюю структуру высказывания. Пропозициональная логика не позволяет даже доказать обоснованность примерно такого силлогизма Все люди смертны Все женщины — люди Следовательно, все женщины смертны В целях обеспечения возможности анализировать более общие случаи была разработана логика предикатов. В своей простейшей форме она принимает вид логики предикатов первого порядка и является основой таких языков логического программирования, как PROLOG. В настоящем разделе для обозначения логики предикатов первого порядка будет применяться просто термин логика предикатов. Пропозициональная логика — это подмножество логики предикатов. Логика предикатов позволяет рассматривать внутреннюю структуру предложений. В частности, в ней допускается использование таких специальных слов, как "все", "некоторые" и "ни один, называемых кванторами. Эти слова очень важны, поскольку позволяют присваивать явные количественные оценки другим словами более точно формулировать предложения. Все кванторы отвечают на вопрос "сколько" и поэтому позволяют применять более широкий круг выражений по сравнению с пропозициональной логикой. Квантор всеобщности Предложение с квантором всеобщности, или универсально квантифицированное предложение, принимает одно и тоже истинностное значение при подстановке всех объектов из одной и той же области определения. Квантор всеобщности представляется с помощью символа Ч, за которым следует один или несколько параметров, соответствующих переменным области определения. Символ Ч интерпретируется как "для каждого" или "для всех. Например, в области определения чисел следующее выражение гласит о том, что для каждого х (где х— Глава 2. Представление знаний 182 число) выражение х + х = х является истинным (Vx) (х + х = х) А если указанное выражение будет обозначено символом р, то приведенное выше утверждение может быть представлено еще более кратко следующим образом (Чх) (р) В качестве еще одного примера предположим, что р обозначает предложение "все собаки животные, как показано ниже. (Vx)(p) = (Чх)(если х — собаках животное) (если х — собака + x — животное) Это высказывание можно также записать таким образом Каждая собака не является животныы Все собаки не являются животныыи В качестве еще одного примера укажем, что предложение "все треугольники являются многоугольниками" записывается следующим образом (Vx)(x является треугольником — + х является многоугольником) Это высказывание можно прочитать так "Для всех х, если х треугольник, то х — многоугольник. Более короткий способ записи логических высказываний, в которых участвуют предикаты, состоит в использовании предикативных функций для описания свойств рассматриваемого предмета. Поэтому приведенное выше логическое высказывание можно также записать следующим образом (Vx) (triangle(x) — + polygon(x) Предикативные функции обычно записываются с применением более краткой системы обозначений, в которой предикаты обозначаются прописными буквами. Например, предположим, что Т обозначает треугольника Р — многоугольник. В таком случае утверждение, касающееся треугольников, может быть записано более кратко, как показано ниже. (Vх)(Т(х) - Р(х)) или (Vy)(T(y) — P(y)) Следует отметить, что вместо фиктивных переменных хи у можно использовать любые другие переменные. В качестве еще одного примера предположим, |