Часть 4.

В качестве примера использования поиска для решения более сложной проблемы рассмотрим задачу диагностирования механических неполадок в автомобиле. Хотя эта проблема на первый взгляд и не кажется такой же легкой задачей поиска в пространстве состояний, как игра "крестики-нолики" или шахматы, на самом деле она очень хорошо подходит для этой стратегии. Вместо того, чтобы каждой вершине графа про­странства состояний ставить в соответствие "состояние игровой доски", будем припи­сывать вершинам графа состояния частичного знания о механических неполадках ав­томобиля. Процесс исследования признаков неполадок и устранения их причины мо­жет быть представлен как поиск по всем состояниям, расширяющий наши знания о них. Начальная вершина графа пуста, она указывает на то, что о причинах неполадок ничего не известно. Первый вопрос, который механик мог бы задать клиенту, сводится к следующему: какие основные части системы (двигатель, коробка передач, рулевое управление, тормоза и т.д.), возможно, неисправны. Этот фрагмент диалога представ­лен в виде совокупности дуг, ведущих от начального состояния к состояниям, соответ­ствующим отдельным подсистемам автомобиля (рис. II.6).

67

С каждым состоянием графа связаны дуги (соответствующие основным диагностическим проверкам), которые ведут к состояниям, представляющим уточненные знания в процессе диагностики. Например, узел неисправности двигателя связан с узлами "двигатель запускается" и "двигатель не запускается". От узла "двигатель не запускает­ся" можно перемещаться к узлам "заводится" и "не заводится". Узел "не заводится" свя­зан с узлами "аккумулятор не работает" и "аккумулятор в порядке" (рис. II.7).

Можно построить граф, включающий все возможные вопросы и вершины, представляющие заключительные диагностические выводы. Решающее устройство сможет диаг­ностировать автомобильные неполадки, находя путь в этом графе. Заметим, что

68

конкретные вопросы, задаваемые в данном примере, определяют путь на графе. При этом каждый следующий ответ удаляет из рассмотрения ненужные вопросы. Хотя эта задача очень отличается от алгоритма нахождения оптимального пути в игре "крестики-нолики", она тоже решается путем поиска в пространстве состояний.

Нейронные сети и другие адаптивные системы также выполняют поиск, особенно во время обучения и адаптации. Всевозможные обобщения данных, которые самообучающаяся программа может сформировать в процессе обучения, можно представить себе как эле­менты пространства. Задача алгоритма обучения состоит в использовании обучающих дан­ных для поиска в этом пространстве. В нейронной сети, например, пространством поиска является множество всех наборов возможных весов связей сети. В процессе поиска набора связей, которые максимально соответствуют обучающим данным, эти веса изменяются.

Несмотря на эту очевидную универсальность, поиска в пространстве состояний не достаточно для автоматизации интеллектуального поведения, обеспечивающего (автоматическое) решение проблем. Но это важный инструмент для проектирования интеллектуальных программ. Если бы поиска в пространстве состояний было достаточно, то было бы довольно просто написать программу, играющую в шахматы. Для определе­ния последовательности ходов, ведущих к победе, на каждом этапе игры нужно было бы осуществлять полный поиск по всему пространству состояний. Этот метод решения за­дач известен как исчерпывающий поиск (exhaustive search), или поиск методом полного перебора. Хотя полный перебор может применяться в любом пространстве состояний, огромный размер пространства для интересных задач делает этот подход практически неприемлемым. Игре в шахматы, например, соответствует приблизительно 10120 различ­ных состояний игровой доски. Это на порядок больше, чем число молекул во Вселенной или число наносекунд, которые минули с "большого взрыва" (момента создания Вселен­ной). Поиск в таком пространстве состояний выходит за рамки возможностей любого вычислительного устройства, размеры которого должны быть ограничены до известной области мироздания, а реализация должна быть закончена прежде, чем эта область под­вергнется разрушительному действию энтропии.

В этой книге будет показано, как поиск в пространстве состояний можно использовать для практического подхода к любой проблеме. Поиск обеспечивает структуру для автоматизации решения задач, но эта структура лишена интеллекта. Такой подход не да­ет возможности формально описать задачу. Кроме того, простой полный перебор боль­шого пространства вообще практически неосуществим и непригоден для описания сущ­ности разумной деятельности.

Однако в реальной жизни люди используют поиск: шахматист рассматривает ряд возможных ходов, доктор исследует несколько возможных диагнозов, ученый программист принимает во внимание различные варианты проекта перед тем, как при­ступить к написанию кода. Однако люди не используют полный перебор: шахматист ис­следует только те ходы, которые, как свидетельствует опыт, должны быть эффективны­ми, доктор не требует проведения всех возможных анализов, которые не связаны каким-либо образом с имеющимися симптомами болезни. Проектируя программные средства, математик руководствуется опытом и теоретическими знаниями. Итак, решение задачи человеком основано на субъективных правилах, направляющих поиск к тем частям про­странства состояний, которые по каким-то причинам кажутся "обещающими".

Эти правила известны под названием эвристик (heuristics). Они составляют одну из центральных тем исследований в области искусственного интеллекта. Эвристика (термин возник от греческого слова "находить") - это стратегия для выборочного поиска в

69

пространстве состояний. Она направляет поиск вдоль линий, имеющих высокую вероят­ность успеха, уводя при этом исследователя от потраченных впустую или очевидно глу­пых усилий. Люди используют большое количество эвристик в решении задач. Если спросить механика, почему автомобиль перегревается, он может сказать что-то типа: "Обычно это означает, что не работает термостат". Если спросить доктора, что могло вызвать тошноту и боль в животе, он скажет, что это "вероятно, кишечный грипп или пищевое отравление".

Эвристика не абсолютно надежна. Даже лучшая игровая стратегия может быть побеждена противником, диагностические средства, разработанные опытными врачами, ино­гда терпят неудачу, опытные математики порой не в состоянии доказать трудную теоре­му. Нет гарантий, что хороший эвристический подход может и должен приблизить нас к верному оптимальному решению проблемы. Наиболее важно то, что эвристика исполь­зует знание о природе задачи для эффективного поиска решения.

Поиск в пространстве состояний обеспечивает средства формализации процесса решения проблемы, а эвристики позволяют привносить интеллект в этот формализм. Эти методы подробно обсуждаются в начальных главах этой книги и по-прежнему лежат в основе самых по­следних разработок в области искусственного интеллекта. В заключение заметим, что поиск в пространстве состояний - это формализм, независимый от каких-либо особых стратегий по­иска, и используемый как отправная точка во многих подходах к решению задач.

В этой книге будут исследованы теоретические аспекты представления знаний и поиска, а также рассмотрены вопросы применения этой теории для создания эффективных программ. Описание способов представления знаний начинается с исчисления предика­тов (глава 2). Хотя исчисление предикатов - только одна из схем, используемых в пред­ставлении знаний, оно обладает преимуществом четкой семантики и доказуемости пра­вильности высказываний, полученных с помощью правил вывода (inference rule). На примере логики предикатов читатель познакомится с проблемами представления знаний и их отношением к поиску. Затем будут продемонстрированы ограничения исчисления предикатов и введены альтернативные схемы представления (главы 6-8).

Глава 3 знакомит с поиском в контексте простых игр. На примере игр можно изучать вопросы, относящиеся к поиску в пространстве состояний, при этом не рассматривать пока проблемы, связанные с представлением знаний в более сложных системах. Эта методика затем применяется к пространствам состояний, определенным логическими решающими устройствами и экспертными системами (главы 4, 5, 7 и 12).

В главе 4 обсуждаются вопросы применения алгоритмов поиска. При этом мы обратим особое внимание на использование эвристик для управления поиском. В главе 5 рассматриваются продукционные системы (основанные на представлении знаний в виде продукцион­ных правил), представляющие собой обобщенную и мощную модель решения задач на ос­нове поиска. Глава 5 представляет другие способы решения задач, включая описание мето­дологии "классной доски" (стратегия решения сложных системных задач с привлечением разнородных источников знаний, взаимодействующих через общее информационное поле).

Альтернативные схемы представления

Мы сознательно составили введение в искусственный интеллект так, чтобы показать историческую перспективу. На начальных стадиях работа в области искусственного ин­теллекта была, главным образом, мотивирована и обоснована философской перспективой

70

вой гипотезы о физической символьной системе Ньюэлла и Саймона [Newell и Simon, 1976]. В свете этой теории при разработке интеллектуальных искусственных объектов преимущественное значение имели формальная логика и поиск. На протяжении всей книги, главным образом во второй ее части, будет представлено немало успешных результатов применения этих методик и инструментальных средств, основанных на сим­вольном представлении.

Однако существует много других подходов к представлению. В части 3 (глава 6) рассказывается о том, как первые простые системы усложнялись по мере решения более трудных задач. Появились нейросетевой, эволюционный, агентно-ориентированный и другие подходы к задаче представления.

Обучающиеся машины отражают требования, выдвигаемые к более сложным представлениям. В главе 9 будут рассмотрены традиционные подходы к обучению, основанные на символьном представлении информации. Глава 10 посвящена нейросетевому обучению, иногда называемому коннекционистскгш (connectionist). Глава 11 знакомит читателя с со­циальными и эмерджентными моделями обучения, которые нашли свое отражение в гене­тических алгоритмах, генетическом программировании и искусственной жизни.

Наконец, в настоящее время активно развивается стохастическое направление исследований. Эти методы, основанные на теории Байеса, часто используются в таких об­ластях, как абдуктивные суждения (abductive inference), обучение с подкреплением (reinforcement learning) и понимание естественного языка. Абдуктивные суждения важны в "обосновании наилучшей трактовки". В областях неточных знаний стохастические модели и связанные с ними алгоритмы вывода обеспечивают механизм логических рассуж­дений и механизм, учитывающий новую информацию для достижения максимально ве­роятного заключения. Например, в главе 8 представлены сети доверия (belief networks) Байеса, используемые для диагностики.

Понимание естественного языка - это еще один пример задачи, решаемой на основе шаблонов. Они могут быть представлены в виде множества фонем, последовательностей слов или образцов рассуждений. Таким образом, вероятностный анализ шаблонов важен как для понимания, так и для порождения естественного языка. В последнее время исследователи привнесли стохастические методы и в эту научную область. Задача понима­ния естественного языка рассматривается в главе 13.

В части II начинается рассмотрение схем представления.

71

Исчисление предикатов

Наконец мы в полной мере освоили возможности графического

изображения логического вывода - последней из наших способностей.

Это не столько естественный дар, сколько долгий и напряженный труд.

- Пирс (Pierce)

Существенное качество доказательства состоит в том,

чтобы заставить поверить.

- Ферма (Fermat)

2.0. Введение

В этой главе мы рассматриваем исчисление предикатов как язык представления искусственного интеллекта. Достоинства исчисления предикатов описывались во введении в часть П. Их преимущества заключаются в четко сформулированной формальной семантике, обоснованности и полноте правил вывода. Эта глава начинается с краткого обзора исчисления высказываний (раздел 2.1). В разделе 2.2 определяется синтаксис и семантика исчисления предикатов. В разделе 2.3 мы обсуждаем правила вывода исчисления предикатов и их применение в решении задач. В заключении этой главы демонстрируется использование исчисления предикатов для реализации базы знаний финансового инвестиционного совета.

2.1. Исчисление высказываний

2.1.1. Символы и предложения

Исчисление высказываний и исчисление предикатов, рассматриваемое в следующем подразделе, являются, прежде всего, языками. Используя их слова, фразы и предложения, мы можем представлять свойства и отношения в окружающем мире и рассуждать о них. Первый шаг в описании языка - это знакомство с его составляющими, т.е. набором символов языка.

73

ОПРЕДЕЛЕНИЕ

СИМВОЛЫ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

Символы исчисления высказываний - это символы высказываний

Р, О, R, S, ..., значения истинности

true (истина), false (ложь) и логические связки

?, v, ¬, ®, =

Символы высказываний (пропозициональные символы) составляют высказывания (proposition) или утверждения относительно некоторого мира. Они могут быть как истинны, так и ложны, например, "автомобиль красный" или "вода мокрая". Высказывания обозначаются прописными буквами и начинаются буквой, расположенной в конце английского алфавита. В исчислении высказываний предложения формируются из элементарных символов согласно следующим правилам.

ОПРЕДЕЛЕНИЕ

ПРЕДЛОЖЕНИЯ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

Каждый логический символ и символ истинности являются предложением. Например: true, Р, Q и Я - предложения. Отрицание предложения есть предложение. Например: -.Ри-, false есть предложения.

Конъюнкция (логическое умножение), или операция И, двух предложений есть предложение.

Например: Рл-iP является предложением.

Дизъюнкция (логическое сложение), или операция ИЛИ, двух предложений есть предложение.

Например: Pv-iP является предложением.

Импликация (включение) одного предложения в другое есть предложение. Например: P®Q является предложением. Эквивалентность двух предложений есть предложение. Например: PvQ =R является предложением.

Легитимные предложения также называются правильно построенными формулами (well-formed formulas - WFF), или ППФ.

В выражениях вида P^Q элементы Р и О называются конъюнктами (членами конъюнктивных выражений). В выражениях вида P v Q элементы Р и О называются дизъюнктами. В импликации P®Q, P- предпосылка (premise), или антецедент (antecedent), a О - заключение, или логическое следствие.

В предложениях исчисления высказываний знаки () и [ ] используются для группировки символов в подвыражения и, таким образом, дают возможность управлять порядком их оценки и присваивания значений. Например, (P vQ)=R весьма отличается от

74

Pv(O=R), что можно продемонстрировать с помощью таблиц истинности (см. подраздел 2.1.2).

Выражение является предложением или правильно построенной формулой (ППФ) исчисления высказываний тогда и только тогда, когда оно может быть сформулировано в виде некоторой последовательности допустимых символов согласно установленным правилам. Например,

((PaQ)->R)=-Pv-QvP, является правильно построенным предложением в исчислении высказываний, поскольку:

Р, О, и Я - высказывания и поэтому предложения; PaQ - конъюнкция двух предложений, поэтому является предложением; (РлО)->R - импликация одного предложения в другое, т.е. предложение; -P и -Q - отрицания предложений, являющиеся предложениями; -Pv-Q - дизъюнкция двух предложений, поэтому является предложением; -Pv-OvR - дизъюнкция двух предложений, т.е. предложение;

((PaQ)->W)=-Pv-QvH- эквивалентность двух предложений, являющаяся предложением.

Мы получили первоначальное предложение, которое было создано путем применения ряда законных правил и поэтому является "правильно построенной формулой".

2.1.2. Семантика исчисления высказываний

В подразделе 2.1.1 мы познакомились с синтаксисом исчисления высказываний и определили набор правил для создания допустимых предложений. В этом разделе мы формально определим семантику ("значение") этих предложений. Поскольку программы искусственного интеллекта должны быть согласованы с представляющими их структурами, весьма важно продемонстрировать, что правдивость их заключений зависит только от правдивости начального знания, т.е. что процедуры вывода не содержат логических ошибок. Для этого весьма необходима точная интерпретация семантики.

Символ предложения соответствует утверждению относительно мироздания. Например, Р может обозначать высказывание "идет дождь", а О - высказывание "Я живу в коричневом доме". Предложение, давая некоторое описание мира, может быть как истинным, так и ложным. Присвоение значения истинности логическим предложениям называется интерпретацией. Следовательно, интерпретация (interpretation) - это утверждение относительно правдивости предложения в некотором возможном мире.

Формально интерпретация- это отображение логических символов на множество {T, F} (true - истина, false - ложь). Как упомянуто в предыдущем разделе, символы true и false являются также частями ряда ППФ исчисления высказываний; т.е. значения ППФ отличны от значения истинности, присвоенного предложению. Чтобы подчеркнуть это различие, для присвоения значения истинности используются символы Т и F.

Каждое возможное отображение значения истинности высказывания соответствует возможной интерпретации мира. Например, если Р обозначает высказывание "идет дождь", а Q- "я на работе", то набор высказываний {Р,О} имеет четыре различных функциональных отображения в таблице истинности {T,F}. Эти отображения соответствуют четырем различным интерпретациям. Семантика исчисления высказываний, подобно его синтаксису, определена индуктивно.

75

ОПРЕДЕЛЕНИЕ

СЕМАНТИКА ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

Интерпретация набора высказываний - это присвоение значения истинности, Г или F, каждому пропозициональному символу.

Символу true (истина) всегда присваивается Г, а символу false (ложь) - значение F. Интерпретации, или значения истинности, предложений (ППФ) определены следующим образом.

Определение истинности отрицания -,Р, где Р- это любой препозиционный символ, осуществляется так. Высказывание ®Р есть F, если Р имеет значение Г; и высказывание -,Р есть Т, если Р имеет значение F.

Определение истинности конъюнкции л осуществляется так: высказывание имеет значение Т, только если оба конъюнкта имеют значение Г; иначе выражение имеет значение F.

Определение истинности дизъюнкции v осуществляется так: высказывание имеет значение F, только если оба дизъюнкта имеют значение F; иначе выражение имеет значение Г.

Определение истинности импликации -» осуществляется так: высказывание имеет значение F только тогда, когда предпосылка (символ перед импликацией) есть Г, и значение истинности следствия (символа после импликации) есть F; иначе выражение имеет значение Т.

Истинность эквивалентности = определяется так: высказывание эквивалентности имеет значение Т только тогда, когда оба выражения имеют одинаковое значение истинности для всех возможных интерпретаций; иначе выражение эквивалентности имеет значение F.

Значения истинности сложных выражений часто описываются таблицами истинности. Таблица истинности содержит все возможные варианты значения истинности для элементарных суждений (атомарных формул), составляющих большие выражения, и задает значение истинности выражениям для каждой возможной интерпретации. Таким образом, в таблице истинности перечисляются все возможные варианты интерпретации данного выражения. Например, таблица истинности для РлО (рис. 2.1) дает значения истинности выражения для каждого возможного значения операнда. Выражение РлО истинно только тогда, когда и Р, и О имеют значение Т. Операции "или" (v), "не" (-.), "импликация" (->) и "эквивалентность" (=) определены аналогичным образом. Построение их таблиц истинности предлагается выполнить в качестве упражнений.

Два выражения в исчислении высказываний эквивалентны, если они имеют одни и те же значения при всех возможных значениях элементов, составляющих выражение. Эта эквивалентность может быть продемонстрирована с помощью таблиц истинности. Например, доказательство эквивалентности P->Q и -PvQ определяется таблицей истинности, показанной на рис. 2.2.

Демонстрируя идентичность таблиц истинности для двух различных предложений в исчислении высказываний, мы можем доказывать эквивалентность следующих выражений. Для логических выражений Р, О и R

76

Закон контрапозиции импликации: P-*Q s (-iQ-»-iP). Закон Моргана: -.(PvQ)s(-1pA-1O) u-,(PaQ)&(-

Эти тождества могут быть использованы для приведения выражения исчисления высказываний к синтаксически различным, но логически эквивалентным формам. Используя эти тождества вместо таблиц истинности данных выражений, докажите эквивалентность выражений, преобразуя одно выражение в другое через последовательность эквивалентных выражений. Первая программа искусственного интеллекта Logic Theorist (Логический теоретик) [Newell и Simon, 1956], разработанная Ньюэллом, Саймоном и Шоу, использовала преобразования эквивалентных форм выражений для доказательства многих теорем из [Whitehead и Russell, 1950]. Правила вывода дают возможность заменять логическое выражение другими формами с эквивалентными значениями истинности, что очень важно. Для использования правил modus ponens (раздел 2.3) и резолюции (resolution) (глава 12) необходимо, чтобы выражения были заданы в определенной форме.

Рис. 2.1. Таблица истинности для оператора л

Рис. 2.2. Таблица истинности, демонстрирующая тождественность выражений P->Q и -PvQ

2.2. Основы исчисления предикатов

В исчислении высказываний каждый атомарный (элементарный) символ (Р, О и т.д.) обозначает высказывание некоторой сложности. При этом не существует способа получить доступ к компонентам отдельного суждения. Исчисление предикатов предоставляет эту возможность. Например, вместо того, чтобы разрешить единственный символ высказывания Р, обозначив все предложение "во вторник шел дождь", мы можем создать предикат погода или weather, который описывает отношения между датой и погодой: погода(вторник, дождь) или weather(tuesday, rain). Посредством правил вывода можно изменять выражения исчислений предикатов, непосредственно обращаясь к их компонентам и выводя новые предложения.

Кроме того, исчисление предикатов позволяет включать в выражения переменные. Переменные помогают создавать обобщенные утверждения относительно классов логических объектов. Например, можно заявить, что для всех значений X, где X - день недели, утверждение погода{Х, дождь) или weather(X, rain) есть истина; т.е. каждый день идет дождь. Как и при исчислении высказываний, сначала определим синтаксис языка предикатов, а затем обсудим его семантику.

77

2.2.1. Синтаксис предикатов и предложений

Перед тем как определить синтаксис правильных выражений в исчислении предикатов, определим алфавит и грамматику для создания символов языка. Это соответствует лексическому аспекту определения языка программирования. Символы исчисления предикатов, подобно лексемам в языке программирования, являются неприводимыми (минимальными) синтаксическими элементами: они не могут быть разбиты операциями языка на составляющие.

В этой книге мы представляем символы исчисления предикатов как строки букв и цифр, начинающиеся с буквы. Пробелы и неалфавитно-цифровые символы использовать нельзя, хотя символ подчеркивания (_) может использоваться для удобства чтения.

ОПРЕДЕЛЕНИЕ

СИМВОЛЫ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ

Алфавит исчисления предикатов состоит из следующих элементов.

Набор букв английского алфавита как верхнего, так и нижнего регистра.

Набор цифр - 0, 1,..., 9.

Символ подчеркивания _.

Символы в исчислении предикатов начинаются с буквы, за которой следует последовательность перечисленных выше знаков.

Приведем пример допустимых знаков в алфавите исчисления предикатов.

a R 69 р _z Вот пример недопустимых знаков в алфавите исчисления предикатов.

# % @ / & " " К допустимым символам исчисления предикатов относятся следующие.

George fire3 torn _andJerry bill XXXX friendsof Приведем примеры строк, содержащих неразрешенные знаки.

3jack "no blanks allowed" ab%cd ***71 duck\\\

Символы (или идентификаторы), как будет показано в подразделе 2.2.2, используются для обозначения объектов, свойств или отношений в области рассуждения. Как и в большинстве языков программирования, использование "слов", которые имеют зарезервированное значение, помогает понимать программный код. Например, выражения л{д,к) и любит(Джордж,Кейт) формально эквивалентны (т.е. имеют одинаковую структуру). Однако второй вариант может быть удобнее для понимания (людьми-читателями) смысла отношений, описанных этим выражением. Следует подчеркнуть, что такие подробные имена предназначены исключительно для улучшения удобочитаемости выражений. Единственное значение, которое может иметь выражение исчисления предикатов, - это значение, определяемое их формальной семантикой.

Круглые скобки, запятые (,) и точки (.) используются исключительно для правильного построения выражений и не обозначают объекты или отношения из области рассуждения. Они называются несобственными символами (improper symbol).

78

Символы исчисления предикатов могут представлять переменные, константы, функции или предикаты. Константами называют определенные объекты или свойства из области рассуждения. Символьные константы должны начинаться со строчной буквы (буквы нижнего регистра). Таким образом, george, tree, tall и blue - примеры правильных символьных констант. Константы true (истина) и false (ложь) зарезервированы как символы истинности.

Идентификаторы переменных используются для обозначения общих классов объектов или свойств из области рассуждения. Переменные представляются идентификаторами, начинающимися с прописной буквы. Так, George, BILL и Kate - допустимые переменные, в то время как geORGE и bill - нет.

Исчисление предикатов также допускает существование функций для объектов из некоторой области рассмотрения. Идентификаторы функций (подобно константам) начинаются с символа нижнего регистра (строчной буквы). Функции обозначают отображение одного или нескольких элементов множества (называемого областью определения функции) в однозначно определяемый элемент другого множества (множества значений функции). Элементы определения и множества значений - это объекты из области рассмотрения. Помимо обычных арифметических функций, таких как сложение и умножение, функции могут определять отображения между нечисловыми областями.

Заметим, что наше определение символов исчисления предикатов не содержит чисел или арифметических операторов. Система счисления не включена в примитивы исчисления предикатов. Мы лишь аксиоматически определили "базовое" исчисление предикатов [Manna и Waldinger, 1985]. Его производные представляют теоретический интерес, но они менее важны в применении исчисления предикатов в качестве модели представления искусственного интеллекта. Для удобства включим арифметику в язык описания.

Каждый функциональный символ связан с арностью (arity), указывающей на количество параметров этой функциональной зависимости. Так, например, символ father мог бы обозначать функцию арности 1, которая позволяет определить отца, a plus мог бы быть функцией арности 2, которая отображает два числа в их арифметическую сумму.

Функциональное выражение - это идентификатор функции, за которым следуют его аргументы (или параметры). Аргументы - это элементы области определения функции. Число аргументов равно арности функции. Аргументы заключаются в круглые скобки и разделяются запятыми. Например,

f(X,Y)

father(david) price(bananas)

Все эти выражения являются правильно определенными функциональными выражениями.

Каждое функциональное выражение обозначает отображение аргументов в единственный объект множества значений, называемый значением функции. Например, если father- это унарная функция, то father(david) является функциональным выражением, значением которого (по желанию автора) есть george. Если plus - это функция арности 2, определенная на множестве целых чисел, то plus{2,3) является функциональным выражением, значением которого является целое число 5. Замена функции ее значением называется ее оцениванием (evaluation).

Понятие символа исчисления предикатов, или терма, формализовано следующим определением.

79

ОПРЕДЕЛЕНИЕ СИМВОЛЫ И ТЕРМЫ К символам исчисления предикатов относятся следующие.

Символы истинности true и false. Это зарезервированные символы.

Символы констант - это символьные выражения, начинающиеся с символа

нижнего регистра (строчный символ).

Символы переменных- это символьные выражения, начинающиеся с символа

верхнего регистра (прописной символ).

Функциональные символы - это символьные выражения, начинающиеся с сим

вола нижнего регистра (строчный символ). С функциями связывается арность,

указывающая на число их аргументов.

Функциональное выражение (function expression) состоит из функциональной константы арности л, за которой следуют л термов f,, f2, ..., tn, заключенных в круглые скобки и отделенных друг от друга запятыми.

Терм исчисления предикатов может быть константой, переменной или функциональным выражением.

Таким образом, термом исчисления предикатов обозначают объекты и свойства из области определения данной задачи. Примеры термов:

cat

times(2,3)

X

blue

mother(jane)

kate

Символы в исчислении предикатов могут также представлять предикаты. Предикатные символы, подобно константам и именам функций, начинаются с буквы нижнего регистра. Предикат указывает на отношения между несколькими объектами (в том числе нулевым числом объектов) в мире. Количество объектов, связанных таким образом, определяет арность предиката. Примеры предикатов:

like equals on near part_of

Атомарное высказывание (атомарная формула) (atomic sentence), самая примитивная единица языка исчислений предикатов, является предикатом арности л, за которым следует л термов, заключенных в круглые скобки и разделенных запятыми. Вот примеры атомарных высказываний.

likes(george,kate) likes(X,george)

llkes{george,susie) likes(X,X)

likes(george,sarah,tuesday) frlends(bill,rlchard)

friends{bill,george) friends(father_of(davld), father_of{andrew))

helps(bill,george) helps(rlchard~bill)

Символами предикатов в этих выражениях являются likes, friends и helps. Символ предиката может быть использован с различным числом аргументов. В этот пример включены два различных предиката likes, один из которых зависит от двух, а другой -

80

от трех аргументов. Если символ предиката используется в предложениях с различной арностью, то считается, что он представляет два различных отношения. Таким образом, отношение предиката определяется его именем и арностью. Два отличных предиката likes могли бы составлять часть одного и того же описания мира; однако этого избегают, так как могут возникнуть недоразумения.

В приведенных выше примерах предикатов bill, george и kate являются постоянными символами и представляют объекты из области определения задачи. Аргументы предиката являются термами и могут также содержать переменные или функциональные выражения. Например,

friends(father_of(david),father of(andrew))

является предикатом, описывающим отношения между двумя объектами из области рассуждения. Аргументы здесь представлены как функциональные выражения, значения которых (будем считать, что father_of(david) есть george и father_of(andrew) есть alien) являются параметрами предиката. После оценки функциональных выражений представленное выше выражение примет вид.

friends(george, alien)

Эти идеи формализованы в следующем определении. ОПРЕДЕЛЕНИЕ

ПРЕДИКАТЫ И АТОМАРНЫЕ ПРЕДЛОЖЕНИЯ

Символы предиката - это символы, начинающиеся с символа нижнего регистра. Предикаты связаны с положительным целым числом, определяющим арность, или "число аргументов", предиката. Предикаты с одинаковым именем, но различной арностью считаются различными.

Атомарное предложение - это предикатная константа арности п, за которой следуют п термов t1 t2,..., tn ,заключенных в круглые скобки и отделенных запятыми. Значения истинности true и false тоже являются атомарными предложениями.

Атомарные предложения также называются атомарными выражениями, атомами или предложениями.

Мы можем комбинировать атомарные предложения и формировать предложения в исчислении предикатов, используя логические операторы. Это те же самые логические связки, которые используются в исчислении высказываний

^, v, -, -> И =.

Переменная, встречающаяся в предложении в качестве параметра (аргумента), относится к неопределенным объектам в области определения. Исчисление предикатов первого порядка (подраздел 2.2.2) включает два символа: кванторы переменных (variable quantifier) V и 3. Они ограничивают значение предложения, содержащего переменную. За квантором следует переменная и предложение, как показано ниже.

3Yfriends(Y,peter) VX likes(X,ice_cream)

Квантор всеобщности V означает, что предложение истинно для всех значений переменной. В примере VX likes(X,ice_cream) выражение истинно для всех значений X в области определения X. Квантор существования 3 указывает, что предложение истинно

81

по крайней мере для одного значения в области определения. Выражение ЗУ friends(Y.peter) истинно, если имеется по крайней мере один объект У, который является другом Питера. Более подробно кванторы рассматриваются в подразделе 2.2.2. Предложения в исчислении предикатов определены индуктивно.

ОПРЕДЕЛЕНИЕ

ПРЕДЛОЖЕНИЯ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ Каждое атомарное предложение есть предложение.

Если s - предложение, то его отрицание s тоже является предложением.

Если S1 и S2 - предложения, то их конъюнкция а^Ягтоже является предложением.

Если S1 и S2 - предложения, то их дизъюнкция э^гтоже является предложением.

Если S1 и S2 - предложения, то их импликация st-«гтоже является предложением.

Если S1 и S2 - предложения, то их эквивалентность Si=s2 тоже является предло

жением.

Если X - переменная и s предложение, то VX s есть предложение.

Если X - переменная и s предложение, то ЭХ s есть предложение.

Далее следуют примеры правильно построенных предложений.

Пусть times (умножить) и plus (сложить) - символы функций арности 2 и пусть equal (равно) и foo являются предикатными символами арности 2 и 3 соответственно.

plus(two, three) (сложить два и три) - это функция, т.е. не атомарное предложение.

equal (plus{two,three), five) - это атомарное предложение.

equal(plus(2,3), seven) - это атомарное предложение. Заметим, что это предложение при стандартной интерпретации операций сложения и уравнивания является ложным. Формальная правильность и истинность значения - независимые понятия.

ЭХ foo(X,two,plus{two,three))Aequal{plus(two,three),five) - предложение, потому что оба конъюнкта являются предложениями.

{foo(two,two,plus{two,three)))->equal(plus(two,three),five)=true) - это предложение, потому что все его компоненты - предложения, связанные логическими операторами.

Определение предложений исчисления предикатов и приведенные примеры приводят к мысли о необходимости проверки: является ли выражение предложением. Метод такой проверки можно записать в виде рекурсивной функции verify_sentence, которая получает в качестве параметра рассматриваемое выражение и возвращает значение success (успех), если выражение является предложением.

function verify_sentence(expression); begin case

выражение является атомарным предложением: return SUCCESS; выражение имеет вид Q X s, где Q - либо V либо 3,а X - переменная, если verify_sentence(s) возвращает SUCCESS then return SUCCESS else return FAI1; выражение имеет вид -is:

if verify_sentence(s) возвращает SUCCESS

82

then return SUCCESS else return FA11;

выражение имеет вид Si op s2, где op - бинарный логический оператор:

if verify_sentence(Si) возвращает SUCCESS и

verify_sentence (s2) возвращает SUCCESS then return SUCCESS else return FAIL; в остальных случаях: return FAIL end end.

В заключение этого раздела приведем пример использования исчисления предикатов. Рассмотрим модель простого мира. Рассматриваемая область определения - набор семейных отношений в библейской генеалогии.

mother(eve.abel)

mother{eve,cain)

father(adam,abel)

father(adam,cain)

VXVY father(X, Y)vmother(X, Y)->parent(X, Y)

VXVYVZ parenf(X, Y)^parent(X,Z)->sibling(Y,Z)

В этом примере для определения набора отношений родителей и детей использованы предикаты mother (мать) и father (отец). В терминах этих предикатов импликация дает общее определение других отношений, в том числе родительских и братских. Интуиция подсказывает, что импликацию можно использовать для описания братских отношений, например sibling(cain, abel). Для реализации этого процесса на компьютере необходимо его формализовать, т.е. определить алгоритмы вывода. При задании этих алгоритмов нужно соблюдать осторожность, поскольку они действительно должны выводить правильные заключения из данного набора утверждений исчисления предикатов. Для того чтобы это было именно так, вначале определим семантику исчисления предикатов (подраздел 2.2.2), а затем перейдем к правилам вывода (раздел 2.3).

2.2.2. Семантика исчисления предикатов

Определив правильно построенные выражения в исчислении предикатов, важно задать их значения в терминах объектов, свойств и отношений в некотором мире. Семантика исчисления предикатов обеспечивает формальную основу для определения значений истинности корректно построенных выражений.

Истинность выражений зависит от соответствия констант, переменных, предикатов и функций объектам и отношениям в области определения. Из истинности отношений в области определения следует истинность соответствующих выражений.

Например, информация относительно некоторого человека Джорджа и его друзей Кейт и Сьюзи может быть выражена так.

friends(george,susie) friends(george,kate)

И если Джордж действительно друг Сьюзи и Кейт, то каждое из этих выражений будет иметь значение истинности Т. Если же Джордж - друг Сьюзи, но не Кейт, то первое выражение будет иметь значение истинности Т, а второе - значение истинности F.

83

Чтобы использовать исчисление предикатов для решения задач, объекты и отношения в интерпретируемой области определения описываются с помощью набора корректных выражений. Термы и предикаты этих выражений обозначают объекты и отношения в области определения. Так формируется база данных выражений исчисления предикатов, каждое из которых, имея значение истинности Т, описывает "состояние мира". Описание Джорджа и его друзей - это простой пример такой базы данных. Другой пример - мир блоков, описанный во введении в часть И.

Основываясь на интуиции, определим семантику исчисления предикатов формально. Сначала определим интерпретацию в области определения D. Затем, используя эту интерпретацию, определим присвоение значений истинности предложениям языка.

ОПРЕДЕЛЕНИЕ ИНТЕРПРЕТАЦИЯ

Пусть область определения D - некоторое непустое множество. Интерпретация на D - это связывание логических объектов из D с каждой константой, переменной, предикатом и функциональным символом в выражении исчисления предикатов на основе следующих правил.

Каждой константе ставится в соответствие элемент из D.

Каждой переменной ставится в соответствие непустое подмножество из D; оно

является областью допустимых значений для этой переменной.

Каждая функция f арности (числа операндов) т определяется для т параметров

из D и задает отображение из Dm в D.

Каждый предикат р арности п определяется для п параметров из D и задает ото

бражение из D" в {Т, F).

При таком определении интерпретации, чтобы получить значение выражения, следует присвоить выражению значение истинности на этой интерпретации.

ОПРЕДЕЛЕНИЕ

ЗНАЧЕНИЯ ИСТИННОСТИ ВЫРАЖЕНИЙ ИСЧИСЛЕНИЯ ПРЕДИКАТОВ

Пусть существует выражение Е и интерпретация / для Е на непустой области определения D. Значение истинности для Е определяется так.

Значение константы- это элемент из D, которому соответствует данная кон

станта в интерпретации /.

Значение переменной - это множество элементов из D, которые соответствуют

данной переменной в интерпретации /.

Значение функционального выражения - это такой элемент из D, который полу

чается в результате оценивания функции для значений параметров, соответст

вующих интерпретации.

Значение символа истинности true - это Г, a false - F.

Значение атомарного предложения равно либо 7", либо F, и определяется интер

претацией /.

Значение отрицания предложения равно 7", если значение предложения равно F; и

значение отрицания предложения равно F, если значение предложения равно Т.

84

7. Значение конъюнкции двух предложений равно Г, если оба предложения принимают значение Г, иначе оно равно F.

8 -10. Значение истинности выражений, использующих операции v, -> и =, определяется значениями их операндов, как описано в подразделе 2.1.2.

Наконец, для переменной X и предложения S, содержащего X, выполняются следующие соотношения.

Значение выражения VXS равно Т, если S равно Г для всех значений X из /, иначе

оно равно F.

Значение EXS равно T, если в интерпретации существует значение X, для которо

го S равно Г; иначе оно равно F.

Квантификация переменных - это важная часть семантики исчисления предикатов. Если переменная используется в предложении, например, X в предложении likes(george,X), то она выполняет роль заполнителя и обозначает знакоместо. На это место в выражении может быть подставлена любая константа, допускаемая интерпретацией. Заменяя переменную X в предложении likes(george,X) значением kate или susie, получим утверждения likes{george,kate) и likes(george,susie). Переменная X может быть замещена любыми допустимыми константами. Данное имя переменной можно заменить любым другим именем переменной, например Y или PEOPLE, при этом значение выражения не изменится. Таким образом, переменная является шаблоном для подстановки. В исчислении предикатов переменные должны быть связаны одним из двух кванторов: универсальности или существования. Переменная считается свободной, если она не связана квантором универсальности или существования. Выражение считается замкнутым (closed), если все его переменные связаны кванторами. Основное выражение (ground expression) вообще не имеет никаких переменных. В исчислении предикатов все переменные должны быть связаны кванторами.

Для обозначения квантора всеобщности применяется символ V. Для указания области действия квантора, т.е. выделения имен переменных, на которые распространяется действие квантора, часто используются круглые скобки. Так, например,

VX(p(X)vq(V)-»r(X))

указывает, что переменная X связана квантором всеобщности в р(Х) и в г(Х).

Квантор всеобщности усложняет вычисление значения истинности предложения, потому что для определения истинности выражения необходимо проверить все возможные значения переменной. Например, чтобы определить значение истинности VX likes(george,X), где переменная X задана на множестве всех людей, необходимо проверить все возможные значения X.

Если область определения интерпретации бесконечна, исчерпывающая проверка всех подстановок переменной, связанной квантором всеобщности, в вычислительном отношении совершенно невозможна, так как алгоритм никогда не остановится. Из-за этой проблемы исчисление предикатов считают неразрешимым.

Поскольку исчисление высказываний не использует переменные, предложения имеют только конечное число возможных значений истинности, и их можно проверить полным перебором. Для этого используются таблицы истинности.

Переменные также могут быть связаны квантором существования. В этом случае выражение с переменной считается истинным, если оно истинно по крайней мере для

85

одного значения из области определения переменной. Квантор существования обозначается Э. Область действия квантора существования также задается круглыми скобками, в которых все вхождения переменной считаются связанными этим квантором.

Анализ истинности выражения, содержащего переменную, связанную квантором существования, может оказаться не проще, чем оценивание выражений, содержащих переменные под квантором всеобщности. Предположим, необходимо определить истинность выражения. Для этого можно подставлять в него различные значения каждой переменной, пока не будет найдено такое, которое делает выражение истинным. Если область определения переменной бесконечна, и выражение ложно при всех подстановках значений, алгоритм никогда не завершится.

Приведем несколько примеров взаимосвязи между операцией отрицания и кванторами всеобщности и существования. Эти соотношения используются в системах опровержения резолюций, описанных в главе 12. В приведенных соотношениях имя переменной используется в качестве формального символа, который заменяет набор констант. Для предикатов р и q и переменных X и У выполняются следующие соотношения.

-3Xp(X)=VX-p(X)

-VXp(X)s3X-p(X)

3Xp(X)^3Yp(Y)

VXq(X)=VYq(Y)

VX(p(X)Aq(X))=VXp{X)A\/Yq(Y)

3X(p(X)vq(X))=3Xp{X)v3Yq(Y)

На определенном нами языке переменные, связанные квантором всеобщности и квантором существования, могут ссылаться только на объекты (или константы) из рассматриваемой области определения. Имена предикатов и имена функций не могут быть заменены именами переменных, стоящих под знаком квантора. Этот язык называется исчислением предикатов первого порядка (first-order predicate calculus).

ОПРЕДЕЛЕНИЕ

ИСЧИСЛЕНИЕ ПРЕДИКАТОВ ПЕРВОГО ПОРЯДКА

Исчисление предикатов первого порядка позволяет связывать знаком квантора переменные, соответствующие объектам из предметной области, но не предикаты или функции. Например,

\/{Likes)Likes(george,kate)

не является правильно построенным выражением в исчислении предикатов первого порядка. Существуют исчисления предикатов высших порядков, в которых такие выражения поддаются интерпретации. Некоторые исследователи [McCarthy, 1968], [Appelt, 1985] использовали языки высших порядков, чтобы представить знания в программах понимания естественного языка.

Многие грамматически правильные английские предложения могут быть представлены в исчислении предикатов первого порядка с помощью символов, связок и символьных переменных, определенных в этом разделе. Важно заметить, что не существует уникального отображения предложений в выражения исчисления предикатов. Английское предложение может иметь любое число различных представлений в области исчисления предикатов. Основная трудность для программистов систем искусственного интеллекта заключается в том, чтобы найти схему использования предикатов, оптимальную с точки зрения выразительности и эффективности оконча-

86

тельного представления. Приведем примеры английских и русских предложений, представленных средствами исчисления предикатов.

If it doesn't rain on Monday, Tom will go to the mountains. (Если в понедельник не будет дождя, Том пойдет в горы.)

-weather(rain,monday)->go(tom, mountains)

Emma is a Doberman pinscher and a good dog. (Эмма - это доберман-пинчер и хорошая собака.)

gooddog(emma)Aisa(emma,doberman)

All basketball players are tall. (Все баскетболисты - высокие.)

VX(basketballjilayer(X)->tall(X))

Some people like anchovies. (Некоторые люди любят анчоусы.)

3X(person(X)Alikes(X,anchovies))

If wishes were horses, beggars would ride. (Если бы желания были лошадьми, то нищие бы ездили верхом.)

equal(wishes,horses)->ride(beggars) Nobody likes taxes. (Никто не любит налоги.) -3Xlikes(X,taxes)