ФОРМИРОВАНИЕ РАССУЖДЕНИЙ С ИСПОЛЬЗОВАНИЕМ ИНФОРМАЦИИ, ЗАДАННОЙ ПО УМОЛЧАНИЮ

например, такой, что Длинный Джон Сильвер имеет одну ногу. Кроме того, было показано, что механизм наследования в семантических сетях предоставляет простой и естественный способ переопределения значений, заданных по умолчанию. В этом разделе проводится более общее исследование заданной по умолчанию информации, с тем чтобы можно было понять семантику умолчаний, а не просто создать какой-то процедурный механизм.
Открытые и закрытые миры
Предположим, что вы просматриваете доску объявлений университетской кафедры компьютерных наук и видите сообщение со словами: "Студентам будут предложены следующие курсы лекций: CS 101, CS 102, CS 106, ЕЕ 101". Итак, сколько курсов здесь предлагается? Если вы ответите "четыре", то поступите в соответствии с принципами работы типичной системы баз данных. После ввода информации в реляционную базу данных с помощью оператора, эквивалентного следующим четырем утверждениям:
Course {CS, 101), Course(CS, 102), Course(CS, 106),
Course(EE, 101) (10.2)
запрос на языке SQL select count (*) from Course возвратит 4. С другой стороны, логическая система первого порядка, скорее всего, ответит примерно в том смысле, что количество предлагаемых курсов должно находиться в пределах от одного до бесконечности, но только не быть равно "четырем". Причина этого состоит в том, что эти утверждения Course не отрицают возможности, что могут также предлагаться другие не упомянутые здесь курсы, а также не позволяют сделать вывод, что все указанные курсы отличаются друг от друга.
Этот пример показывает, что системы баз данных и соглашения, неявно применяемые людьми при общении, отличаются от логики первого порядка по меньшей мере в двух аспектах. Во-первых, в языках баз данных (и в языках общения людей) предполагается, что предоставленная информация является полной, поэтому предполагается, что базовые атомарные высказывания, не обозначенные как истинные, являются ложными. Такое предположение называется предположением о замкнутом мире, или CWA (Closed-World Assumption). Во-вторых, обычно предполагается, что разные имена относятся к различным объектам. В этом состоит предположение об уникальности имен, или UNA (Unique Names Assumption), которое было впервые описано в контексте имен действий в разделе 10.3.
В логике первого порядка такие соглашения не приняты, и поэтому необходимо их определять явно. Чтобы сформулировать высказывание, что предлагаются четыре и только четыре разных курса, необходимо записать следующее:
Course(d, п) [d,n] = [OS,101] v [d,n] = [CS,102]
v [d,n] = [CS,106] v [d,n] = [EE,101] (10.3)
Уравнение 10.3 называется дополнением10 уравнения 10.2. Вообще говоря, такое дополнение должно содержать определение для каждого предиката (высказывание в форме "тогда и только тогда"), а каждое определение должно содержать по одному дизъюнкту для каждого определенного выражения, головой которого является этот предикат11. Как правило, такое дополнение создается, как описано ниже.
1. Собрать все выражения с одним и тем же названием предиката (Р) и с одной и той же арностью (л).
2. Преобразовать каждое выражение в нормальную форму Кларка, например, заменить выражение
P(ti,..., fcn) где ti — термины, выражением
P{vlt vn) где vL — вновь введенные переменные, a Wi — переменные, которые присутствуют в первоначальном выражении. При этом следует использовать одно и то же множество vL для каждого выражения. Это приводит к получению такого множества выражений:
P(vlf j , Vn) 3. Скомбинировать их вместе в одно большое дизъюнктивное выражение:
P(vlt .... vn) f- Bi v ... v Bk
4. Сформировать завершение, заменяя оператор <— оператором эквивалентности:
P(vlt vn) « Bi v ... v Bk
Пример дополнения Кларка для базы знаний, включающей и базовые факты, и правила, приведен в табл. 10.2. Чтобы ввести в действие предположение об уникальности имен, достаточно сформировать дополнение Кларка для отношения равенства, где единственными известными фактами являются CS=CS, 101 = 101 и т.д. Оставляем эту задачу читателю в качестве упражнения.

Предположение о замкнутом мире позволяет найти минимальную модель отношения. Это означает, что в данном примере можно найти модель отношения Course с наименьшим количеством элементов. Минимальная модель отношения Course, соответствующая уравнению 10.2, имеет четыре элемента; при меньшем количестве элементов возникало бы противоречие. Для хорновских баз знаний всегда имеется уникальная минимальная модель. Следует отметить, что с учетом предположения об уникальности имен это утверждение распространяется также и на отношение равенства, поскольку каждый терм равен только самому себе. Как ни парадоксально, это означает также, что минимальные модели являются одновременно и максимальными, в том смысле, что включают максимально возможное количество объектов.
Было бы допустимо взять любую хорновскую программу, сформировать дополнение Кларка и передать полученный результат в программу автоматического доказательства теорем для выполнения логического вывода. Но обычно является более эффективным использование механизма логического вывода специального назначения, такого как Prolog, поскольку в этом механизме логического вывода уже учитываются предположения о замкнутом мире и уникальности имен.
Те, кому приходится использовать предположение о замкнутом мире, должны соблюдать осторожность при выборе способа формируемых рассуждений. Например, при использовании базы данных с результатами переписи населения было бы резонно принимать предположение о замкнутом мире при формировании рассуждений о текущем населении городов, но было бы неправильно делать вывод, что в будущем не родится ни один ребенок, лишь на основании того, что база данных не содержит записей, касающихся будущих дней рождения. Благодаря CWA база данных становится полной в том смысле, что позволяет дать либо положительный, либо отрицательный ответ на каждый атомарный запрос; если же какие-то факты не заданы в этой базе данных изначально (например, о будущих рождениях), то CWA не может применяться. Более сложная система представления знаний может дать пользователю возможность указывать правила, по которым следует применять предположение о замкнутом мире.







Материалы

Яндекс.Метрика