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

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

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

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

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

И если Джордж действительно друг Сьюзи и Кейт, то каждое из этих выражений бу­дет иметь значение истинности Т. Если же Джордж — друг Сьюзи, но не Кейт, то первое выражение будет иметь значение истинности Г, а второе — значение истинности F[А.Д.7] Чтобы использовать исчисление предикатов для решения задач, объекты и отношения в интерпретируемой области определения описываются с помощью набора корректных выражений. Термы и предикаты этих выражений обозначают объекты и отношения в об­ласти определения. Так формируется база данных выражений исчисления предикатов, каждое из которых, имея значение истинности 7", описывает "состояние мира". Описание Джорджа и его друзей — это простой пример такой базы данных. Другой пример — мир блоков, описанный во введении в часть П.

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

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

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

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

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

3. Каждая функция f арности (числа операндов) т определяется для т параметров из D и задает отображение из D^m в D.

4. Каждый предикат р арности п определяется для п параметров из D и задает ото­бражение из D" в {7", F}.

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

ОПРЕДЕЛЕНИЕ

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

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

1. Значение константы— это элемент из D, которому соответствует данная кон­станта в интерпретации /.

2. Значение переменной — это множество элементов из D, которые соответствуют данной переменной в интерпретации /.

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

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

5. Значение атомарного предложения равно либо Т, либо F, и определяется интер­претацией /.

6. Значение отрицания предложения равно Г, если значение предложения равно F; и значение отрицания предложения равно F, если значение предложения равно Т[А.Д.8] 7. Значение конъюнкции двух предложений равно Г, если оба предложения прини­мают значение Т, иначе оно равно F.

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

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

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

12. Значение 3XS равно Г, если в интерпретации существует значение X, для которо­го S равно Г; иначе оно равно F.

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

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

VX(p(X)vq(y)->r(X))

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

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

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

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

Переменные также могут быть связаны квантором существования. В этом случае выражение с переменной считается истинным, если оно истинно по крайней мере для[А.Д.9] одного значения из области определения переменной. Квантор существования обозна­чается 3. Область действия квантора существования также задается круглыми скобками, в которых все вхождения переменной считаются связанными этим квантором.

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

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

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

-,VXp(X)s3X-,p(X)

3Xp(X)=3Vp(V)

VXg(X)=VVg(y)

VX(p(X)Aq(X))^Xp(X)A\fYq(Y)

3X(p(X)vq(X))=BXp(X)v3Yq(Y)

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

ОПРЕДЕЛЕНИЕ

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

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

V{Likes)Likes(george,kate)

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

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

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{basketball_player(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)

2.2.3. Значение семантики на примере "мира блоков"

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

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

Исчисление предикатов декларативно, т.е. не существует никакой принятой синхро­низации или порядка рассмотрения каждого выражения. Тем не менее в разделе 7.4 мы дополнительно рассмотрим процедурную семантику (procedural semantics) или ясно оп­ределенную методологию для оценки этих выражений во времени. Конкретный пример процедурной семантики для выражений исчисления предикатов — это язык PROLOG (глава 14). Создаваемое нами ситуационное исчисление связано с рядом вопросов, вклю­чающих проблему фреймов и немонотонности логических интерпретаций. Эти вопросы будут представлены на рассмотрение позже. Для этого примера достаточно сказать, что выражения исчисления предикатов будут оцениваться слева направо[А.Д.11]

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