Главная arrow Логика arrow Логика первого порядка
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Логика первого порядка Печать

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

Начнем с краткого описания интерфейса Tell/Ask для базы знаний в логике первого порядка. Затем рассмотрим проблемную область семейных отношений, чисел, множеств и списков, а также мира вампуса.

 

Утверждения и запросы в логике первого порядка

Высказывания вводятся в базу знаний с помощью операции Tell, точно так же, как и в пропозициональной логике. Такие высказывания называются утверждениями. Например, можно ввести утверждения, что Джон — король и что короли — люди:

Tell{KB, King(John))

Tell (KB, Vx King(x) => Person{x) )

Мы можем задавать вопросы о содержимом базы знаний с использованием операции Ask. Например, следующее выражение:

Ask(XB, King(John))

возвращает true. Вопросы, заданные с помощью операции Ask, называются запросами, или целями (которые не следует путать с целями, используемыми при описании желаемых состояний агента). Вообще говоря, на любой запрос, который логически следует из базы знаний, должен быть получен утвердительный ответ. Например, если в ней содержатся два утверждения, приведенные в предыдущем абзаце, то следующий запрос:

Ask{KB, Person{John))

должен также возвратить true. Кроме того, можно задавать запросы с кванторами, такие как следующий:

Ask (KB, Зх Person(x) )

На этот запрос должен быть получен ответ true, но этот ответ — ни полезный, ни забавный. (Его можно сравнить с получением ответа "Да" на вопрос: "Можете ли вы сказать мне, который час?") Запрос с переменными, на которые распространяется квантор существования, имеет смысл: "Существует ли такое значение х, что...", и мы решаем его, предоставляя соответствующее значение х. Стандартная форма для ответа такого рода представляет собой подстановку, или список связывания, который является множеством пар "переменная—терм". В данном конкретном случае, при наличии только двух утверждений, ответом должно быть {х/ John]. А если имеется больше одного возможного ответа, может быть возвращен список подстановок.

 

Проблемная область родства

В качестве первого примера рассмотрим проблемную область семейных отношений, или родства. Эта проблемная область включает такие факты, как "Элизабет — мать Чарльза" и "Чарльз— отец Уильяма", и правила наподобие того, что "Бабушка — это мать родителя".

Очевидно, что объектами в этой проблемной области являются люди. В ней будут применяться два унарных предиката, Male (Мужчина) и Female (Женщина). Отношения родства (связи между родителями и детьми, братьями и сестрами, мужем и женой и т.д.) будут представлены с помощью бинарных предикатов: Parent (Родитель), Sibling (Брат или сестра), Brother (Брат), Sister (Сестра), Child (Ребенок), Daughter (Дочь), Son (Сын), Spouse (Супруг или супруга), Wife (Жена), Husband (Муж), Grandparent (Дедушка или бабушка), Grandchild (Внук или внучка), Cousin (Двоюродный брат или двоюродная сестра), Aunt (Тетя) и Uncle (Дядя). В качестве предикатов Mother (Мать) и Father (Отец) мы будем использовать функции, поскольку каждый человек имеет по одному из этих объектов (по крайней мере, в соответствии с законами природы).

Рассмотрим каждую из функций и предикатов, записывая все, что мы знаем о них, в терминах других символов. Например, мать — это родитель женского рода:

\/т,с Mother {с) - т <=> Female {т) л Parent (т, с)

Муж — это супруг мужского пола:

\fw,h Husband{h,w) <=> Male{h) л Spouse{h,w)

Мужчины и женщины — непересекающиеся категории людей:

Vx Male(x) <=> -iFemale(x)

Отношения между родителями и детьми являются взаимно противоположными:

\/р,с Parent (р, с) <=$ Child(cp)

Дедушка или бабушка — это родитель родителя:

\/д,с Grandparent (д, с) <=> Vp Parent {д,р) л Parent (р, с)

Брат или сестра — это еще один ребенок тех же родителей:

Ух, у Sibling(х, у) <=> х Ф у л Vp Parent (р,х) л Parent (р, у)

Каждое из этих высказываний может рассматриваться как одна из аксиом в проблемной области родства. Аксиомы обычно принято связывать чисто с математическими проблемными областями (и мы вскоре рассмотрим некоторые аксиомы для чисел), но они нужны во всех проблемных областях.

Аксиомы предоставляют основную фактическую информацию, на основании которой могут быть получены логическим путем полезные заключения. Кроме того, приведенные выше аксиомы родства имеют определения; последние представлены в форме Vx,y Р(х,у) <=> ... .

Аксиомы определяют функцию Mother и предикаты Husband, Male, Parent, Grandparent и Sibling в терминах других предикатов. Но приведенные выше определения можно "свести" к базовому множеству предикатов (Child, Spouse и Female), в терминах которых в конечном итоге определяются все остальные предикаты. Это — очень естественный способ, с помощью которого создается представление некоторой проблемной области, и он аналогичен способу, применяемому при создании пакетов программного обеспечения путем последовательного определения процедур из примитивных библиотечных функций.

Обратите внимание на то, что множество примитивных базовых предикатов не обязательно должно быть уникальным; с таким же успехом можно использовать множество Parent, Spouse и Male. Как будет показано ниже, в некоторых проблемных областях нельзя найти четко определимое базовое множество.

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

Vx,y Sibling{x,y) <=> Sibling(y, х)

Это — аксиома или теорема? В действительности это — теорема, которая логически следует из аксиомы, определяющей понятие родственных отношений между братьями и сестрами. Если в базу знаний с помощью операции Ask будет введен запрос в виде этого высказывания, то должно быть получено значение true.

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

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

Ух Person(х) <=> ...

К счастью, логика первого порядка позволяет использовать предикат Person, не определяя его полностью. Вместо этого можно записывать частичные спецификации свойств, которыми обладает каждый человек, и свойств, которые идентифицируют некоторый объект как человека:

Vx Person(х) => ...

Vx ... => Person(х)

Аксиомы могут также представлять собой просто "голые факты", такие как Male (Jim) и Spouse (Jim, Laura). Такие факты формируют описания конкретных экземпляров задачи, что дает возможность находить ответы на конкретные вопросы. Ответы на эти вопросы представляют собой теоремы, которые следуют из аксиом. Но часто приходится убеждаться в том, что ожидаемые ответы получить не удается, например, можно было бы ожидать, что удастся вывести логическим путем факт Female(Laura) из аксиом Male(George) и Spouse (George, Laura), но данный факт не следует как теорема из этих аксиом. Такая ситуация свидетельствует о том, что в базе знаний не хватает какой-то аксиомы.

Числа, множества и списки

По-видимому, числа представляют собой наиболее яркий пример того, как может быть построена крупная теория из крошечного ядра аксиом. В этом разделе будет описана теория натуральных чисел, или неотрицательных целых чисел. Для этого потребуется предикат NatNum, который будет принимать истинное значение при использовании параметра, представляющего собой натуральное число; кроме того, требуется один константный символ, 0, и один функциональный символ, S (successor — преемник). Аксиомы Пеано определяют натуральные числа и операцию сложения. Натуральные числа определяются рекурсивно:

NatNum{0)

Vn NatNum{n) => NatNum{S{n))

Это означает, что 0 — натуральное число и для каждого объекта л, если n — натуральное число, S(n) — натуральное число. Необходимы также аксиомы для ограничения действия функции определения преемника:

Vn О Ф S(n)

\/т,п т Ф п => S{m) Ф S{n)

Теперь мы можем определить операцию сложения в терминах функции определения преемника:

\/т NatNum(m) => +@,т) - т

\/т,п NatNum(m) л NatNum(n) => +(S(m),n) = S(+(m,n))

В первой из этих аксиом утверждается, что сложение числа 0 с любым натуральным числом т приводит к получению самого числа т. Обратите внимание на использование бинарного функционального символа "+" в терме + @, т); в обычной математике такой терм принято записывать в виде 0+т с использованием инфиксной системы обозначений. (Система обозначений, которая используется в этом разделе для логики первого порядка, называется префиксной.) Чтобы было удобнее читать высказывания, касающиеся чисел, здесь будет также разрешено использовать инфиксные обозначения. Кроме того, мы можем записывать как s(n) как л+1, поэтому вторая аксиома принимает следующий вид:

\/т,п NatNum(m) л NatNum{n) => (тп+1) +п - {т+п)+1

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

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

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

В качестве синтаксического упрощения в данном разделе будет использоваться обычный словарь теории множеств. Пустое множество представляет собой константу, которая записывается как {}. Применяется также один унарный предикат, Set, который принимает истинное значение, если его фактическим параметром является множество. Бинарными предикатами являются х е s (х — элемент множества s) и Si с 32C! — подмножество, не обязательно строгое, множества s2). В качестве бинарных функций применяются s± n s2 (пересечение двух множеств), s± u s2 (объединение двух множеств) и {х| s} (множество, полученное в результате присоединения элемента х к множеству s). Один из возможных наборов аксиом приведен ниже.

Списки подобны множествам. Различия между ними состоят в том, что списки упорядочены, а один и тот же элемент может появляться в списке несколько раз. Для списков может использоваться словарь ключевых слов Lisp: Nil — это списокконстанта без элементов; Cons, Append, First и Rest — функции; Find— предикат, который выполняет для списков такие же функции, какие Member выполняет для множеств. List? — предикат, принимающий истинное значение только при получении параметра, представляющего собой список. Как и в случае множеств, обычно принято использовать синтаксические упрощения в логических высказываниях, в которых применяются списки. Пустой список обозначается как [ ]. Терм Cons (х, у), где у— непустой список, записывается как [х\у]. Терм Cons(х,Nil) (т.е. список, содержащий только элемент х) записывается как [х]. Список из нескольких элементов, такой как [А, в, С], соответствует вложенному терму Cons (A, Cons(B, Cons (С, Nil))).