Лекции - Системы искусственного интеллекта
Подождите немного. Документ загружается.
Ш а г 3 9 . В соответствии с формулами (10.85), (10.86) и
правилом модус поненс получаем
).( 8710
находится (Яма, 2,2) находится (Яма, 1,1)
находится (Яма, 3,1).
Ш а г 4 0 . В соответствии с формулой (10.15) и правилом
исключения квантора общности получаем
).( 8810
находится (Сквозняк 1,2)
находится (Яма, 1,1)
находится (Яма, 2,2)
находится (Яма, 1,3).
Ш а г 4 1 . В соответствии с формулами (10.58), (10.11),
(10.88) и правилами модус поненс и исключения конъюнкта
получаем
).( 8910
находится (Яма, 1,1),
).( 9010
находится (Яма, 2,2),
).( 9110
находится (Яма, 1,3).
Ш а г 4 2 . В соответствии с формулами (10.87), (10.5),
(10.90) и правилом резолюции получаем
).( 9210
находится (Яма, 3,1).
Ш а г 4 3 . В соответствии с формулой (10.30) и правилом
исключения квантора общности получаем
).( 9310
находится ( Агент, 2,1) ориентация (3,1)
находится (Яма, 3,1) повернуться_налево (2,2)
находится ( Агент, 2,1) ориентация (2,2).
Ш а г 4 4 . В соответствии с формулами (10.92), (10.83),
(10.84) и правилом введения конъюнкции общности получаем
).( 9410
находится ( Яма, 3,1)
находится ( Агент, 2,1) ориентация (3,1).
Ш а г 4 5 . В соответствии с формулами (10.94), (10,93) и
правилом модус поненс общности получаем
).( 9510
повернуться_налево (2,2)
находится ( Агент, 2,1) ориентация (2,2).
71
Ш а г 4 6 . В соответствии с формулой (10.95) и правилом
исключения конъюнкта получаем
).( 9610
повернуться_налево (2,2),
).( 9710
находится ( Агент, 2,1),
).( 9810
ориентация (2,2).
Ш а г 4 7 . В соответствии с формулой (10.21) и правилом
исключения квантора общности получаем
).( 9910
находится ( Агент, 2,1) ориентация (2,2)
находится (Чудовище, 2,2)
находится (Яма, 2,2) перейти (2,2)
находится ( Агент, 2,2) ориентация (2,3).
Ш а г 4 8 . В соответствии с формулами (10.9), (10.14),
(10.97), (10.98), (10.90) и правилами исключения квантора
общности, модус поненс и введения конъюнкции получаем
).( 10010
находится ( Агент, 2,1) ориентация (2,2)
находится (Чудовище, 2,2)
находится (Яма, 2,2).
Заметим, что шаг 48 не является таким простым, как все
остальныею Его детализацию предлагается выполнить
самостоятельно.
Ш а г 4 9 . В соответствии с формулами (10.100), (10.99)
правилом модус поненс получаем
).( 10110
перейти (2,2) находится ( Агент, 2,2)
ориентация (2,3).
Ш а г 5 0 . В соответствии с формулой (10.101) и правилом
исключения конъюнкта получаем
).( 10210
перейти (2,2),
).( 10310
находится ( Агент, 2,2),
).( 10410
ориентация (2,3).
Ш а г 5 1 . В соответствии с формулами (10.103), (10.12) и
правилом модус поненс получаем
).( 10510
находится ( Зловоние, 2,2).
72
Ш а г 5 2 . В соответствии с формулами (10.103), (10.13) и
правилом модус поненс получаем
).( 10610
находится ( Сквозняк, 2,2).
Ш а г 5 3 . В соответствии с формулой (10.14) и правилом
исключения квантора общности получаем
).( 10710
находится ( Зловоние, 2,2)
находится ( Чудовище, 2,2)
находится ( Чудовище, 2,1)
находится ( Чудовище, 2,3)
находится ( Чудовище, 1,2)
находится ( Чудовище, 3,2).
Ш а г 5 4 . В соответствии с формулами (10.105), (10.107)
и правилом модус поненс получаем
).( 10810
находится ( Чудовище, 2,2)
находится ( Чудовище, 2,1)
находится ( Чудовище, 2,3)
находится ( Чудовище, 1,2)
находится ( Чудовище, 3,2).
Ш а г 5 5 . В соответствии с формулой (10.108) и правилом
исключения конъюнкта получаем
).( 10910
находится ( Чудовище, 2,2),
).( 11010
находится ( Чудовище, 2,1),
).( 11110
находится ( Чудовище, 2,3),
).( 11210
находится ( Чудовище, 1,2),
).( 11310
находится ( Чудовище, 3,2).
Ш а г 5 6 . В соответствии с формулой (10.15) и правилом
исключения квантора общности получаем
).( 11410
находится ( Сквозняк, 2,2)
находится ( Яма, 2,2)
находится ( Яма, 2,1)
73
находится ( Яма, 2,3)
находится ( Яма, 1,2)
находится ( Яма, 3,2).
Ш а г 5 7 . В соответствии с формулой (10.114) и правилом
исключения конъюнкта получаем
).( 11510
находится ( Яма, 2,1),
).( 11610
находится ( Яма, 2,3),
).( 11710
находится ( Яма, 1,2),
).( 11810
находится ( Яма, 3,2).
Ш а г 5 8 . В соответствии с формулой (10.21) и правилом
исключения квантора общности получаем
).( 11910
находится ( Агент, 2,2) ориентация (2,3)
находится ( Чудовище, 2,3)
находится ( Яма, 2,3)
перейти (2,3) находится ( Агент, 2,3)
ориентация (2,4).
Ш а г 5 9 . В соответствии с формулами (10.103), (10.104),
(10.11), (10.116) и правилом введения конъюнкции получаем
).( 12010
находится ( Агент, 2,2) ориентация (2,3)
находится ( Чудовище, 2,3)
находится ( Яма, 2,3).
Ш а г 6 0 . В соответствии с формулами (10.120), (10.119)
и правилом модус поненс получаем
).( 12110
перейти (2,3) находится ( Агент, 2,3)
ориентация (2,4).
Ш а г 6 1 . В соответствии с формулой (10.121) и правилом
исключения конъюнкта получаем
).( 12210
перейти (2,3),
).( 12310
находится ( Агент, 2,3),
).( 12410
ориентация (2,4).
74
Ш а г 6 2 . В соответствии с формулами (10.123), (10.10) и
правилом модус поненс получаем
).( 12510
находится (Блеск, 2,3).
Ш а г 6 3 . В соответствии с формулой (10.24) и правилом
исключения квантора общности получаем
).( 12610
находится ( Агент, 2,3)
находится (Блеск, 2,3) взять (2,3).
Ш а г 6 4 . В соответствии с формулами (10.123), (10.125)
и правилом введения конъюнкции получаем
).( 12710
находится ( Агент, 2,3) находится (Блеск, 2,3).
Ш а г 6 5 . В соответствии с формулами (10.127), (10.126)
и правилом модус поненс получаем
).( 12810
взять (2,3).
Ш а г 6 5 . В соответствии с формулами (10.127), (10.126)
и правилом модус поненс получаем
).( 12910
взять (2,3)
),( ji
взять
),( ji
.
Таким образом, была достигнута (выведена) цель (10.33).
Трудности процедуры поиска решения в среде чудовища.
Процедура поиска решения сравнительно простой задачи в
среде чудовища потребовала 66 шагов. На каждом шаге
применялось какое-либо одно правило вывода. (Некоторые
шаги, например, шаг 48 вывода формулы (10.100), были
несколько укрупнены). Что можно заметить, анализируя эту
процедуру?
Несмотря на простоту задачи, число шагов кажется
несоразмерно большим (66 шагов).
Также кажется слишком большим количество новых истинных
литералов, которые были выведены в процессе поиска решения
(130 литералов).
Выбор очередного шага неоднозначен. Количество новых
истинных литералов, которые можно вывести из уже известных,
назовём степенью ветвления.
На степень ветвления сильно влияют правила исключения
квантора общности, поскольку при его использовании
осуществляется замена переменных константами, а число таких
замен в принципе может быть даже бесконечным.
Приходится очень часто применять правила введения
конъюнкции, комбинируя литералы в целях получения формул,
которые являются комбинацией литералов, для использования
их в правилах модус поненс. Также часто приходится
75
применять правило исключения конъюнктов в целях получения
литералов для использования их в правилах ведения
конъюнкции.
Итак, в выводе, который только что был
продемонстрирован, всё время приходилось выводить
истинность отдельных литералов, а затем, комбинируя их в
истинную конъюнкцию
и используя какую-либо истинную
импликацию
, применять правило модус поненс
,
для получения новой истинной формулы
, по которой затем
снова приходилось выводить истинные литералы, и так до тех
пор, пока не получится требуемая нам истинная формула.
Поскольку в этом процессе всё время приходилось спускаться
на уровень отдельных литералов, то естественным образом
напрашивается идея ввести ограничения на вид используемых в
исчислении и правиле модус поненс формул так, чтобы не
приходилось постоянно и раздельно применять правила
исключения квантора общности, исключения конъюнкта и
введения конъюнкции.
Для этого предлагается ввести обобщенное правило модус
поненс
,
, в котором
и
не являются
произвольными формулами логики предикатов первого порядка.
Отметим, что обобщенным его называют в связи с тем, что оно
позволяет избавится от раздельного использования правил
исключения квантора общности, исключения конъюнкта и
введения конъюнкции, хотя с общей точки зрения это правило
является частным случаем правила модус поненс.
Обобщенное правило модус поненс. Обозначим
)(
некоторый атом, имеющий предикатный символ
и множество
вхождений переменных и констант
. Тогда обобщенное
правило модус поненс принимает вид
),(,),(),(
)()(
)(),()(
),(
)(
),(
,
)(
)(
)(
.
Смысл этого правила состоит в следующем. Формулы
)(,),(),(
являются атомами и каждый из них имеет
множество вхождений констант и переменных
. В формуле
)()()()(
,
представленной импликацией,
)(),(,),(),(
76
являются атомами, каждый из которых имеет множество
вхождений константа и переменных
. Если существуют
подстановки
такие, что
)(
),(
)(
),(
. . . . . . . . . . .
)(
),(
то будет истинным атом
)(
. Напомним, что
)(
означает, что вместо аргументов
атома
подставляются
аргументы
. При этом необходимо соблюдать следующие
требования:
Вместо переменной в
можно подставлять переменную из
. Такую подстановку называют переименованием переменной.
Вместо переменной в
можно подставлять константу из
. Такую подстановку называют конкретизацией переменной.
Вместо переменной в
можно подставлять функцию из
.
Такую подстановку называют заменой переменной.
Вместо одной и той же переменной везде следует одну и
ту же константу или функцию. Переименовываются одновременно
все вхождения одной и то же переменной.
Процесс поиска нужной подстановки
называют
унификацией, а формулу, в атомы которой осуществлена
подстановка, называют унифицированной. В некоторых
исчислениях для подстановки, конкретизации и замены
переменной вводят отдельные правила. Подстановка называется
наиболее общей, если благодаря ей наименьшее число
переменных замещается константами. В обобщенном правиле
модус поненс вместо
)()( xx
записывают
)(x
, т.е. кванторы
общности подразумеваются, но не употребляются. Кванторы
существования в обобщенном правиле модус поненс вообще не
используются. Поскольку обобщенное правило модус поненс
является единственным, которое мы собираемся использовать в
процессе вывода, то, следовательно, постановка задачи
изначально должна удовлетворять следующим условиям.
Формулы в постановке задачи не должны содержать
кванторов существования.
Если они все же есть, то, прежде чем решать задачу, от
кванторов существования следует избавиться с помощью,
например, правила исключения квантора существования или
каким-либо другими способами, речь о которых пойдёт дальше.
Все формулы в постановке задачи должны быть атомами или
импликациями, левая часть (посылка) которых является
77
конъюнкцией атомов, а правая (заключение) - либо атомом,
либо пустым символом.
Такие формулы называют хорновскими формулами.
Преобразование произвольных формул логики предикатов в
хорновские формулы непростая задача, причём не любую
формулу можно преобразовать к такому виду. В нашем примере
со средой чудовища кванторов существования, не считая
формулы цели, вообще нет, тем не менее, подобное
преобразование всех формул невозможно. Например, это нельзя
сделать для формул (10.18), (10.19). Рассмотрим, как
выполняется указанное преобразование для формул (10.1)-
(10.32). Для того чтобы можно было легко сопоставить эти
формулы с их преобразованиями, будем последние нумеровать
теми же числами, но со звездочкой, комментируя производимые
преобразования (если в преобразованиях нет необходимости,
то соответствующая формула переписывается без комментариев.
*
).( 110
находится (Агент, 1,1)
*
).( 210
ориентация (1,2).
Выполняя преобразования на основе закона
Ложь
Ложь ,
получаем
*
).( 310
находится (Зловоние, 1,1) Ложь,
*
).( 410
находится (Сквозняк, 1,1) Ложь,
*
).( 510
находится (Яма, 1,1) Ложь.
Простым удалением квантора общности (если он есть) или
на основе закона
)()()()(
получаем следующие формулы:
*
).( 610
)(i
находится (Препятствие,
i
, 0)
*
).( 710
)( j
находится (Препятствие, 0,
j
),
*
).( 810
находится (Агент, 1,2) находится (Зловоние, 1,
2),
находится (Агент, 2,1) находится (Сквозняк, 2, 1)
*
).( 910
находится (Агент, 2,1)
находится (Зловоние, 2,1),
*
).( 1010
находится (Агент, 2,3) находится (Блеск, 2, 3).
78
Выполняя преобразования на основе закона
)(
Ложь =
Ложь,
получаем следующие формулы:
*
).( 1110
находится (Агент,1,2) находится (Сквозняк, 1,2)
Ложь,
*
).( 1210
находится (Агент,2,2) находится (Зловоние 2,3)
Ложь,
*
).( 1310
находится (Агент,2,2) находится (Сквозняк, 2,2)
Ложь.
Вторая формула в (10.9)
*
может быть преобразована
аналогично.
С помощью преобразования
)()()(
)(()(
)
,
удаления квантора существования и правила исключения
конъюнкта, получаем следующие формулы:
*
).( 1410
находится (Чудовище,
ji,
)
находится (Зловоние,
ji,
),
находится (Чудовище,
1ji,
)
находится (Зловоние,
ji,
),
находится (Чудовище,
1ji,
)
находится (Зловоние,
ji,
),
находится (Чудовище,
ji ,1
)
находится (Зловоние,
ji,
),
находится (Чудовище,
ji ,1
)
находится (Зловоние,
ji,
);
*
).( 1510
находится (Яма,
ji,
)
79
находится (Сквозняк,
ji,
),
находится (Яма,
1ji,
)
находится (Сквозняк,
ji,
),
находится (Яма,
1ji,
)
находится (Сквозняк,
ji,
),
находится (Яма,
ji ,1
)
находится (Сквозняк,
ji,
),
находится (Яма,
ji ,1
)
находится (Сквозняк,
ji,
);
*
).( 1610
находится (Зловоние,
ji,
)
находится (Чудовище,
ji,
),
находится (Зловоние,
1ji,
)
находится (Чудовище,
ji,
),
находится (Зловоние,
1ji,
)
находится (Чудовище,
ji,
),
находится (Зловоние,
ji ,1
)
находится (Чудовище,
ji,
),
находится (Зловоние,
ji ,1
)
находится (Чудовище,
ji,
).
Следующие формулы преобразовать к требуемому виду
невозможно. Оставим их в прежнем виде, исключив квантор
существования:
*
).( 1710
находится (Чудовище,
ji,
)
находится (Зловоние,
ji,
)
находится (Зловоние,
1ji,
)
находится (Зловоние,
1ji,
)
находится (Зловоние,
ji ,1
)
80