- •Куцый н. Н. Системы искусственного интеллекта
- •1.Искусственный интеллект
- •2.Агенты – носители искусственного интеллекта
- •3. Среды и агенты
- •4.Логические рассуждения
- •5.Логика высказываний
- •6.Исчисление высказываний
- •7.Рассуждения в терминах интервалов
- •9.Логика предикатов
- •9.Постановка задачи для среды чудовища в логике предикатов.
- •10.Исчисление предикатов
- •11.Прямой и обратный вывод
- •12.Полнота и непротиворечивость исчисления
- •13.Вывод на основе правила резолюции
- •14.Автомат и среда
- •15.Язык и автомат
- •Вопросы и упражнения
10.Исчисление предикатов
Ранее было определено понятие логического исчисления. Одним из таких исчислений является классическое исчисление предикатов. Как и любое другое исчисление оно построено на использовании:
алфавита (совокупности используемых символов);
синтаксических правил построения формул в алфавите;
аксиом (общезначимых исходных формул);
правил вывода по аксиомам производных формул или теорем.
Алфавит и синтаксические правила построения формул в исчислении предикатов определены выше. Множество аксиом классического исчисления предикатов определяется следующим образом: каждая аксиома классического исчисления высказываний трансформируется в аксиому классического исчисления предикатов. Эта трансформация выражается только в том, что все её логические переменные рассматриваются как предикаты, а формулы как формулы логики предикатов первого порядка.
К этому множеству аксиом, которые являются аналогом аксиом классического исчисления высказываний, добавляются две следующие аксиомы:
,
.
Общезначимость этих аксиом можно проверить с помощью таблиц истинности.
Множеством
правил классического исчисления
предикатов является модус поненс
,
в котором
и
являются формулами логики предикатов
первого порядка, и два правила
введения кванторов:
,
.
Классическое исчисление предикатов первого порядка не единственно. Существует множество других исчислений, построенных на основе классического, но использующих, помимо правил классического исчисления предикатов, и другие правила. В частности, выше были введены такие правила вывода в логике высказываний, как исключение конъюнкта, введение конъюнкции, исключение двойного отрицания, простая резолюция, резолюция. Эти правила справедливы и для логики предикатов, с тем только отличием, что в них используются формулы логики предикатов, а не логики высказываний.
Как и в случае классического исчисления высказываний, все аксиомы классического исчисления предикатов не содержат констант. Кроме того, все предикатные символы в классическом исчислении высказываний являются абстрактными в том смысле, что любой предикатный символ в аксиомах логического исчисления может быть переименован и от этого ничего не изменится. Иными словами, аксиомы классического исчисления предикатов, как и аксиомы классического исчисления высказываний, остаются аксиомами при любой интерпретации.
При использовании классического исчисления предикатов для описания свойств какоё-либо конкретной среды абстрактные предикатные символы заменяют конкретными, называемыми также индивидуальными предикатными символами. Кроме того, вводят факты, аксиомы и правила, не являющиеся аксиомами классического исчисления предикатов и зависящие от той среды, для которой осуществляется формализация постановки задачи. В результате получается некоторое новое логическое исчисление. Формулы этого исчисления по-прежнему строят по тем же правилам, показанным на рис. 8.1. С его помощью можно выводить формулы, которые нельзя получить в классическом исчислении высказываний. С практической точки зрения нас интересуют именно такие исчисления, учитывающие особенности конкретных сред. В дальнейшем ряд таких исчислений и будет рассмотрен. Чтобы отличать такие исчисления от классического исчисления логики предикатов первого порядка, назовём их неклассическими исчислениями. их числу относятся также исчисления, которые строятся не на основе логики предикатов первого порядка. Здесь же продолжим изучение неклассических исчислений, построенных на основе логики первого порядка.
Пусть,
например, среди множества аксиом в
неклассическом исчислении для какой-либо
среды имеется две аксиомы
и
,
где
переменная;
константы;
предикатные
символы. Спрашивается, можно ли на
основании этих аксиом, используя правило
модус поненс
,
заключить, что формула
истинна. Если принять
,
,
то такое заключение можно было бы
сделать, если бы среди исходных аксиом
имелась аксиома
.
Её у нас нет. Имеется только аксиома
.
Эта аксиома гласит: "Для всех
имеет место истинность формулы
".
Когда речь идёт о всех
формулы
,
то имеются в виду, естественно, только
те
,
областью значений которых являются
заранее оговоренные константы, среди
которых есть константа
хотя бы потому, что она встречается в
предикате
формулы
,
т.е. в предикате, предикатный символ
которого совпадает с предикатным
символом предиката в аксиоме
.
Это означает, что предикат
истинен. Следовательно, можно
воспользоваться правилом модус поненс
и заключить, что формула
истинна. Таким образом, чтобы воспользоваться
правилом модус поненс
,
пришлось
по аксиоме
получить аксиому
.
Это равносильно использованию правила
вывода, означающего, что при наличии
аксиомы
вместо переменной
в предикат
можно подставить константу
(эта подстановка обозначается
)
и в результате получить аксиому
.
Это правило называют правилом исключения
квантора общности.
Кроме этого правила могут потребоваться
также правила исключения
квантора существования,
которые записывают в общем виде следующим
образом:
исключения квантора общности
;
исключения квантора существования
;
введение квантора существования
.
Здесь
произвольная
формула логики предикатов, имеющая
связанную квантором общности или
существования переменную
;
формула
,
в которой все вхождения переменной
заменены на константу
.
Снова пример со средой чудовища. Вернемся к решению задачи нахождения агентом золота в среде чудовища. Выше были сформулированы необходимые для решения задачи аксиомы. Перечислим их в несколько виде и перенумеруем, вводя дополнительно два атома: находится (Препятствие, , 0), находится (Препятствие, 0 ,). Здесь используется дополнительная константа Препятствие, соответствующая некоторому вымышленному объекту, который ограничивает передвижение объекта в ячейки, хотя бы одна координата которых равна нулю.
Предварительно напомним, что восприятие агента позволяет ему определять наличие зловония, сквозняка или блеска только в той ячейке, где он находится. Поэтому полное начальное состояние среды чудовища агенту неизвестно. Находясь в ячейке (1,1), он может воспользоваться только восприятиями в этой ячейке.
Формулы, определяющие начальные знания агента:
находится
(Агент,
1,1)
ориентация
(1,2)
находится
(Зловоние,
1,1)
находится
(Сквозняк,
1,1)
находится
(Яма,
1,1)
находится
(Препятствие,
,
0)
находится
(Препятствие,
0,
)
Для того чтобы выразить возможность восприятия агентом зловония, сквозняка или блеска в ячейках (1,2), (2,1), (3,1), соответственно введём следующие формулы:
находится
(Агент,
1,2)
находится
(Зловоние,
1, 2),
находится
(Агент,
2,1)
находится
(Сквозняк,
2, 1)
находится (Зловоние, 1, 2),
находится
(Агент,
2,3)
находится
(Блеск,
2, 3),
находится
(Агент,1,2)
находится
(Сквозняк,
1,2),
находится
(Агент,2,2)
находится
(Зловоние
2,3),
находится
(Агент,2,2)
находится
(Сквозняк,
2,2).
Формулы, определяющие условия местонахождения объектов в зависимости от восприятия:
находится
(Зловоние,
находится
(Чудовище,
)
находится
(Чудовище,
)
находится
(Чудовище,
)
находится
(Чудовище,
)
находится(Чудовище,
),
находится
(Сквозняк,
находится
(Яма, ) находится (Яма, )
находится (Яма, )
находится (Яма, )
находится(Яма, ),
находится
(Чудовище,
находится
(Зловоние, ) находится (Зловоние, )
находится (Зловоние, )
находится (Зловоние, )
находится(Зловоние, ),
находится
(Чудовище,
)
находится
(Зловоние, ) находится (Зловоние, )
находится (Зловоние, )
находится (Зловоние, )
находится(Зловоние, ),
находится
(Зловоние,
находится
(Чудовище, ) находится (Чудовище, )
находится (Чудовище, )
находится (Чудовище, )
находится(Чудовище, ),
находится
(Сквозняк,
находится
(Яма, ) находится (Яма, )
находится (Яма, )
находится (Яма, )
находится(Яма, ).
Формулы, определяющие условия выполнения агентом действий:
находится
(Агент,
)
ориентация
находится (Чудовище, )
находится (Яма, )
перейти находится (Агент, )
ориентация
,
находится
(Агент,
)
ориентация
находится (Чудовище, )
находится (Яма, )
перейти находится (Агент, )
ориентация
,
находится
(Агент,
)
ориентация
находится (Чудовище, )
находится (Яма, )
перейти
находится
(Агент,
)
ориентация
,
находится
(Агент,
)
ориентация
находится (Чудовище, )
находится (Яма, )
перейти
находится
(Агент,
)
ориентация
,
находится
(Агент,
)
находится (Блеск, ) взять ,
находится
(Агент,
)
ориентация
(находится (Чудовище, )
находится (Яма, )
находится (Препятствие, ))
повернуться_направо ориентация
находится (Агент, ) ориентация ,
находится
(Агент,
)
ориентация
(находится (Чудовище, )
находится (Яма, )
находится (Препятствие, ))
повернуться_направо ориентация
находится (Агент, ) ориентация ,
находится
(Агент,
)
ориентация
(находится (Чудовище, )
находится (Яма, )
находится (Препятствие, ))
повернуться_направо
находится (Агент, ) ориентация ,
находится
(Агент,
)
ориентация
(находится (Чудовище, )
находится (Яма, )
находится (Препятствие, ))
повернуться_направо
находится (Агент, ) ориентация ,
находится
(Агент,
)
ориентация
(находится (Чудовище, )
находится (Яма, )
находится (Препятствие, ))
повернуться_налево
находится (Агент, ) ориентация ,
находится
(Агент,
)
ориентация
(находится (Чудовище, )
находится (Яма, )
находится (Препятствие, ))
повернуться_налево
находится (Агент, ) ориентация ,
находится
(Агент,
)
ориентация
(находится (Чудовище, )
находится (Яма, )
находится (Препятствие, ))
повернуться_налево
находится (Агент, ) ориентация ,
находится
(Агент,
)
ориентация
(находится (Чудовище, )
находится (Яма, )
находится (Препятствие, ))
повернуться_налево
находится (Агент, ) ориентация .
Формула цели:
взять
.
Вывод. Рассмотрим подробно вывод с использованием правил исключения квантора общности, конъюнкта и введения конъюнкции. Вывод разобьём на шаги, на каждом из которых будем применять только одно из перечисленных правил, а в результате получать новую формулу.
Шаг 1.В соответствии с правилом исключения квантора общности и формулой (10.14) получаем
находится
(Зловоние,
1,1)
находится
(Чудовище,1,1) находится (Чудовище, 1,2)
находится (Чудовище, 2,1).
Шаг 2.В соответствии с формулами (10.3), (10.34) и правилом модус поненс получаем
находится
(Чудовище,
1,1)
находится (Чудовище,1,2)
находится (Чудовище, 2,1).
Шаг 3.В соответствии с формулой (10.35) и правилом исключения конъюнкта получаем
находится
(Чудовище,
1,1),
находится
(Чудовище,1,2),
находится
(Чудовище,
2,1).
Шаг 4.В соответствии с правилом исключения квантора общности и формулой (10.15) получаем
находится
(Сквозняк,
1,1)
находится (Яма,1,2)
находится (Яма, 2,1).
Шаг 5.В соответствии с формулами (10.4), (10.39) и правилом модус поненс получаем
находится
(Яма, 1,2)
находится
(Яма,
2,1).
Шаг 6.По (10.40) и правилу исключения конъюнкта получаем
находится
(Яма, 1,2),
находится
(Яма,
2,1).
Заметим, что так как ячеек хотя бы с одной нулевой координатой не существует, то соответствующие им предикаты не включены в формулы (10.39) и (10.40).
Шаг 7.В соответствии с формулами (10.1), (10.2), (10.37), (10.41) и правилом введения конъюнкции
находится
(Агент, 1,1)
ориентация
(1,2)
находится (Чудовище, 1,2)
находится (Яма, 1,2).
Шаг 8.В соответствии с формулой (10.21) и правилом исключения квантора общности получаем
находится
(Агент, 1,1)
ориентация
(1,2)
находится (Чудовище, 1,2)
находится (Яма, 1,2) перейти (1,2)
находится (Агент, 1,2) ориентация (1,3).
Шаг 9.В соответствии с формулами (10.43), (10.44) и правилом модус поненс получаем
перейти
(1,2)
находится
(Агент, 1,2)
ориентация (1,3).
Шаг 10.В соответствии с формулой (10.45) и правилом исключения конъюнкта получаем
перейти
(1,2)
находится
(Агент, 1,2)
ориентация
(1,3).
Шаг 11.В соответствии с формулами (10.47), (10.8) и правилом модус поненс получаем
находится
(Зловоние,
1,2).
Шаг 12.В соответствии с формулами (10.47), (10.11) и правилом модус поненс получаем
находится
(Сквозняк,
1,2).
Шаг 13.В соответствии с формулой (10.48) и правилом исключения квантора общности получаем
находится
(Зловоние,
1,2)
находится (Чудовище, 1,1)
находится (Чудовище, 1,2)
находится (Чудовище, 1,3)
находится (Чудовище, 2,2).
Шаг 14.В соответствии с формулами (10.49), (10,51) и правилом модус поненс получаем
находится
(Чудовище,
1,1)
находится (Чудовище, 1,2)
находится (Чудовище, 1,3)
находится (Чудовище, 2,2).
Шаг 15.В соответствии с формулой (10.52) и правилом резолюции (согласно (10.36) истинен предикат находится (Чудовище, 1,1), а по (10.37) - истинен предикат находится (Чудовище, 1,2); следовательно, находится (Чудовище, 1,1) и находится (Чудовище, 1,2)ложны) получаем
находится
(Чудовище,
1,3)
находится (Чудовище, 2,2).
Чудовище только одно и поэтому только один из предикатов в формуле (4.53) должен быть истинным. Определить, однако, какой из них истинен, агент не может. Поэтому попытаемся сформулировать действия, которые, находясь в ячейке (1,2), агент может совершать в предположении, что чудовище может быть в любой из двух ячеек (1,3) или (2,2).
Шаг 16.В соответствии с формулой (10.27) и правилом исключения квантора общности получаем
находится
(Агент,
1,2)
ориентация
(1,3)
находится (Чудовище, 1,3)
повернуться_направо (1,2)
находится (Агент, 1,2) ориентация (2,2).
Шаг 17.В соответствии с формулами (10.47), (10.48), (10.53) правилом введения конъюнкции получаем
находится
(Агент,
1,2)
ориентация
(1,3)
находится (Чудовище, 1,3).
Шаг 18.В соответствии с формулами (10.54), (10.55), (10.53) и правилом модус поненс получаем
повернуться
(1,2)
находится
(Агент,
1,2)
ориентация (2,2).
Шаг 19.В соответствии с формулой (10.56), (10.55), (10.53) и правилом исключения конъюнкции получаем
повернуться
(1,2),
находится
(Агент,
1,2),
ориентация
(2,2).
Шаг 20.В соответствии с формулой (10.28) и правилом исключения квантора общности получаем
находится
(Агент,
1,2)
ориентация (2,2)
(находится (Чудовище, 2,2)
находится (Яма, 2,2)) повернуться (1,2)
находится (Агент, 1,2) ориентация (1,1).
Шаг 21.В соответствии с формулой (10.53), (10.58), (10.59) и правилом введения конъюнкции получаем
находится
(Агент,
1,2)
ориентация (2,2)
(находится (Чудовище, 2,2).
Шаг 22.В соответствии с формулами (10.60), (10.61) и правилом модус поненс получаем
повернуться
(1,2)
находится
(Агент,
1,2)
ориентация (1,1).
Шаг 23.В соответствии с формулой (10.62) и правилом исключения конъюнкта получаем
повернуться
(1,2),
находится
(Агент,
1,2),
ориентация
(1,1).
Шаг 24.В соответствии с формулой (10.20) и правилом исключения квантора общности получаем
находится
(Агент,
1,2)
ориентация
(1,1)
находится (Чудовище, 1,1)
находится (Яма, 1,1)
перейти (1,1) находится (Агент, 1,1)
ориентация (1,0).
Шаг 25.В соответствии с формулами (10.5), (10.36), (10.64), (10.65) и правилом введения конъюнкции получаем
находится
(Агент,
1,2)
ориентация
(1,1)
находится (Чудовище, 1,1)
находится (Яма, 1,1).
Шаг 26.В соответствии с формулами (10.67), (10.66) и правилом модус поненс получаем
перейти
(1,1)
находится
(Агент,
1,1)
ориентация (1,0).
Шаг 27.В соответствии с формулой (10.68) и правилом исключения конъюнкта получаем
перейти
(1,1),
находится
(Агент,
1,1),
ориентация
(1,0).
Таким образом, агент вернулся в ячейку (1,1), но ориентация его изменилась. Теперь он стоит лицом к несуществующей ячейке (1,0).
Шаг 28.В соответствии с формулой (10.6) и правилом исключения квантора общности получаем
находится
(Препятствие,
1,0).
Шаг 29.В соответствии с формулой (10.29) и правилом исключения квантора общности получаем
находится
(Агент,
1,0)
ориентация
(1,0)
(находится (Препятствие, 1,0)
находится (Чудовище, 1,0)
находится (Яма, 1,0))
повернуться_налево (1,1) .
находится (Агент, 1,1) ориентация (2,1).
Шаг 30.В соответствии с формулами (10.70), (10.71), (10.72) и правилом введения конъюнкции получаем
находится
(Агент,
1,1)
ориентация
(1,0)
(находится (Препятствие, 1,0).
Шаг 31.В соответствии с формулами (10.73), (10.74) и правилом модус поненс получаем
повернуться_налево
(1,1)
находится (Агент, 1,1) ориентация (2,1).
Шаг 32.В соответствии с формулой (10.75) и правилом исключения конъюнкта получаем
повернуться_налево
(1,1),
находится
(Агент,
1,1)
ориентация
(2,1).
Шаг 33.В соответствии с формулой (10.23) и правилом исключения квантора общности получаем
находится
(Агент,
1,1)
ориентация
(2,1)
находится (Чудовище, 2,1)
находится (Яма, 2,1) перейти (2,1)
находится (Агент, 2,1) ориентация (3,1).
Шаг 34.В соответствии с формулами (10.77), (10.78), (10.38), (10.42) и правилом введения конъюнкции
находится
(Агент,
1,1)
ориентация
(2,1)
находится (Чудовище, 2,1)
находится (Яма, 2,1).
Шаг 35.В соответствии с формулами (10.80), (10.79) и правилом модус поненс
перейти
(2,1)
находится
(Агент,
2,1)
ориентация (3,1).
Шаг 36.В соответствии с формулой (10.81) и правилом исключения конъюнкта получаем
перейти
(2,1),
находится
(Агент,
2,1),
ориентация
(3,1).
Шаг 37.В соответствии с формулами (10.83), (10.9) и правилом модус поненс получаем
находится
(Сквозняк
2,1).
Шаг 38.В соответствии с формулой (10.19) и правилом исключения квантора общности получаем
находится
(Сквозняк
2,1)
находится
(Яма,
2,2)
находится (Яма, 1,1) находится (Яма, 3,1).
Шаг 39.В соответствии с формулами (10.85), (10.86) и правилом модус поненс получаем
находится
(Яма,
2,2)
находится
(Яма,
1,1)
находится (Яма, 3,1).
Шаг 40.В соответствии с формулой (10.15) и правилом исключения квантора общности получаем
находится
(Сквозняк
1,2)
находится (Яма, 1,1)
находится (Яма, 2,2)
находится (Яма, 1,3).
Шаг 41.В соответствии с формулами (10.58), (10.11), (10.88) и правилами модус поненс и исключения конъюнкта получаем
находится
(Яма,
1,1),
находится
(Яма,
2,2),
находится
(Яма,
1,3).
Шаг 42.В соответствии с формулами (10.87), (10.5), (10.90) и правилом резолюции получаем
находится
(Яма,
3,1).
Шаг 43.В соответствии с формулой (10.30) и правилом исключения квантора общности получаем
находится
(Агент,
2,1)
ориентация
(3,1)
находится (Яма, 3,1) повернуться_налево (2,2)
находится (Агент, 2,1) ориентация (2,2).
Шаг 44.В соответствии с формулами (10.92), (10.83), (10.84) и правилом введения конъюнкции общности получаем
находится
(Яма,
3,1)
находится (Агент, 2,1) ориентация (3,1).
Шаг 45.В соответствии с формулами (10.94), (10,93) и правилом модус поненс общности получаем
повернуться_налево
(2,2)
находится (Агент, 2,1) ориентация (2,2).
Шаг 46.В соответствии с формулой (10.95) и правилом исключения конъюнкта получаем
повернуться_налево
(2,2),
находится
(Агент,
2,1),
ориентация
(2,2).
Шаг 47.В соответствии с формулой (10.21) и правилом исключения квантора общности получаем
находится
(Агент,
2,1)
ориентация
(2,2)
находится (Чудовище, 2,2)
находится (Яма, 2,2) перейти (2,2)
находится (Агент, 2,2) ориентация (2,3).
Шаг 48. В соответствии с формулами (10.9), (10.14), (10.97), (10.98), (10.90) и правилами исключения квантора общности, модус поненс и введения конъюнкции получаем
находится
(Агент,
2,1)
ориентация
(2,2)
находится (Чудовище, 2,2)
находится (Яма, 2,2).
Заметим, что шаг 48 не является таким простым, как все остальныею Его детализацию предлагается выполнить самостоятельно.
Шаг 49. В соответствии с формулами (10.100), (10.99) правилом модус поненс получаем
перейти
(2,2)
находится
(Агент,
2,2)
ориентация (2,3).
Шаг 50.В соответствии с формулой (10.101) и правилом исключения конъюнкта получаем
перейти
(2,2),
находится
(Агент,
2,2),
ориентация
(2,3).
Шаг 51.В соответствии с формулами (10.103), (10.12) и правилом модус поненс получаем
находится
(Зловоние,
2,2).
Шаг 52.В соответствии с формулами (10.103), (10.13) и правилом модус поненс получаем
находится
(Сквозняк,
2,2).
Шаг 53.В соответствии с формулой (10.14) и правилом исключения квантора общности получаем
находится
(Зловоние,
2,2)
находится (Чудовище, 2,2)
находится (Чудовище, 2,1)
находится (Чудовище, 2,3)
находится (Чудовище, 1,2)
находится (Чудовище, 3,2).
Шаг 54.В соответствии с формулами (10.105), (10.107) и правилом модус поненс получаем
находится
(Чудовище,
2,2)
находится (Чудовище, 2,1)
находится (Чудовище, 2,3)
находится (Чудовище, 1,2)
находится (Чудовище, 3,2).
Шаг 55.В соответствии с формулой (10.108) и правилом исключения конъюнкта получаем
находится
(Чудовище,
2,2),
находится
(Чудовище,
2,1),
находится
(Чудовище,
2,3),
находится
(Чудовище,
1,2),
находится
(Чудовище,
3,2).
Шаг 56.В соответствии с формулой (10.15) и правилом исключения квантора общности получаем
находится
(Сквозняк,
2,2)
находится (Яма, 2,2)
находится (Яма, 2,1)
находится (Яма, 2,3)
находится (Яма, 1,2)
находится (Яма, 3,2).
Шаг 57.В соответствии с формулой (10.114) и правилом исключения конъюнкта получаем
находится
(Яма,
2,1),
находится
(Яма,
2,3),
находится
(Яма,
1,2),
находится
(Яма,
3,2).
Шаг 58.В соответствии с формулой (10.21) и правилом исключения квантора общности получаем
находится
(Агент,
2,2)
ориентация
(2,3)
находится (Чудовище, 2,3)
находится (Яма, 2,3)
перейти (2,3) находится (Агент, 2,3)
ориентация (2,4).
Шаг 59.В соответствии с формулами (10.103), (10.104), (10.11), (10.116) и правилом введения конъюнкции получаем
находится
(Агент,
2,2)
ориентация
(2,3)
находится (Чудовище, 2,3)
находится (Яма, 2,3).
Шаг 60.В соответствии с формулами (10.120), (10.119) и правилом модус поненс получаем
перейти
(2,3)
находится
(Агент,
2,3)
ориентация (2,4).
Шаг 61.В соответствии с формулой (10.121) и правилом исключения конъюнкта получаем
перейти
(2,3),
находится
(Агент,
2,3),
ориентация
(2,4).
Шаг 62.В соответствии с формулами (10.123), (10.10) и правилом модус поненс получаем
находится
(Блеск,
2,3).
Шаг 63.В соответствии с формулой (10.24) и правилом исключения квантора общности получаем
находится
(Агент,
2,3)
находится (Блеск, 2,3) взять (2,3).
Шаг 64.В соответствии с формулами (10.123), (10.125) и правилом введения конъюнкции получаем
находится
(Агент,
2,3)
находится
(Блеск,
2,3).
Шаг 65.В соответствии с формулами (10.127), (10.126) и правилом модус поненс получаем
взять
(2,3).
Шаг 65.В соответствии с формулами (10.127), (10.126) и правилом модус поненс получаем
взять
(2,3)
взять
.
Таким образом, была достигнута (выведена) цель (10.33).
Трудности процедуры поиска решения в среде чудовища. Процедура поиска решения сравнительно простой задачи в среде чудовища потребовала 66 шагов. На каждом шаге применялось какое-либо одно правило вывода. (Некоторые шаги, например, шаг 48 вывода формулы (10.100), были несколько укрупнены). Что можно заметить, анализируя эту процедуру?
Несмотря на простоту задачи, число шагов кажется несоразмерно большим (66 шагов).
Также кажется слишком большим количество новых истинных литералов, которые были выведены в процессе поиска решения (130 литералов).
Выбор очередного шага неоднозначен. Количество новых истинных литералов, которые можно вывести из уже известных, назовём степенью ветвления.
На степень ветвления сильно влияют правила исключения квантора общности, поскольку при его использовании осуществляется замена переменных константами, а число таких замен в принципе может быть даже бесконечным.
Приходится очень часто применять правила введения конъюнкции, комбинируя литералы в целях получения формул, которые являются комбинацией литералов, для использования их в правилах модус поненс. Также часто приходится применять правило исключения конъюнктов в целях получения литералов для использования их в правилах ведения конъюнкции.
Итак,
в выводе, который только что был
продемонстрирован, всё время приходилось
выводить истинность отдельных литералов,
а затем, комбинируя их в истинную
конъюнкцию
и используя какую-либо истинную импликацию
,
применять правило модус поненс
для получения новой истинной формулы
,
по которой затем снова приходилось
выводить истинные литералы, и так до
тех пор, пока не получится требуемая
нам истинная формула. Поскольку в этом
процессе всё время приходилось спускаться
на уровень отдельных литералов, то
естественным образом напрашивается
идея ввести ограничения на вид используемых
в исчислении и правиле модус поненс
формул так, чтобы не приходилось постоянно
и раздельно применять правила исключения
квантора общности, исключения конъюнкта
и введения конъюнкции.
Для этого предлагается ввести обобщенное правило модус поненс , в котором и не являются произвольными формулами логики предикатов первого порядка. Отметим, что обобщенным его называют в связи с тем, что оно позволяет избавится от раздельного использования правил исключения квантора общности, исключения конъюнкта и введения конъюнкции, хотя с общей точки зрения это правило является частным случаем правила модус поненс.
Обобщенное
правило модус поненс. Обозначим
некоторый атом, имеющий предикатный
символ
и множество вхождений переменных и
констант
.
Тогда обобщенное правило модус поненс
принимает вид
.
Смысл
этого правила состоит в следующем.
Формулы
являются атомами и каждый из них имеет
множество вхождений констант и переменных
.
В формуле
,
представленной импликацией,
являются
атомами, каждый из которых имеет множество
вхождений константа и переменных
.
Если существуют подстановки
такие, что
. . . . . . . . . . .
то
будет истинным атом
.
Напомним, что
означает, что вместо аргументов
атома
подставляются аргументы
.
При этом необходимо соблюдать следующие
требования:
Вместо переменной в можно подставлять переменную из . Такую подстановку называют переименованием переменной.
Вместо переменной в можно подставлять константу из . Такую подстановку называют конкретизацией переменной.
Вместо переменной в можно подставлять функцию из . Такую подстановку называют заменой переменной.
Вместо одной и той же переменной везде следует одну и ту же константу или функцию. Переименовываются одновременно все вхождения одной и то же переменной.
Процесс поиска нужной подстановки называют унификацией, а формулу, в атомы которой осуществлена подстановка, называют унифицированной. В некоторых исчислениях для подстановки, конкретизации и замены переменной вводят отдельные правила. Подстановка называется наиболее общей, если благодаря ей наименьшее число переменных замещается константами. В обобщенном правиле модус поненс вместо записывают , т.е. кванторы общности подразумеваются, но не употребляются. Кванторы существования в обобщенном правиле модус поненс вообще не используются. Поскольку обобщенное правило модус поненс является единственным, которое мы собираемся использовать в процессе вывода, то, следовательно, постановка задачи изначально должна удовлетворять следующим условиям.
Формулы в постановке задачи не должны содержать кванторов существования.
Если они все же есть, то, прежде чем решать задачу, от кванторов существования следует избавиться с помощью, например, правила исключения квантора существования или каким-либо другими способами, речь о которых пойдёт дальше.
Все формулы в постановке задачи должны быть атомами или импликациями, левая часть (посылка) которых является конъюнкцией атомов, а правая (заключение) - либо атомом, либо пустым символом.
Такие формулы называют хорновскими формулами.
Преобразование произвольных формул логики предикатов в хорновские формулы непростая задача, причём не любую формулу можно преобразовать к такому виду. В нашем примере со средой чудовища кванторов существования, не считая формулы цели, вообще нет, тем не менее, подобное преобразование всех формул невозможно. Например, это нельзя сделать для формул (10.18), (10.19). Рассмотрим, как выполняется указанное преобразование для формул (10.1)-(10.32). Для того чтобы можно было легко сопоставить эти формулы с их преобразованиями, будем последние нумеровать теми же числами, но со звездочкой, комментируя производимые преобразования (если в преобразованиях нет необходимости, то соответствующая формула переписывается без комментариев.
находится
(Агент,
1,1)
ориентация
(1,2).
Выполняя преобразования на основе закона
Ложь Ложь ,
получаем
находится
(Зловоние,
1,1)
Ложь,
находится
(Сквозняк,
1,1)
Ложь,
находится
(Яма,
1,1)
Ложь.
Простым удалением квантора общности (если он есть) или на основе закона
получаем следующие формулы:
находится
(Препятствие,
,
0)
находится
(Препятствие,
0,
),
находится
(Агент,
1,2)
находится
(Зловоние,
1, 2),
находится (Агент, 2,1) находится (Сквозняк, 2, 1)
находится (Агент, 2,1)
находится (Зловоние, 2,1),
находится
(Агент,
2,3)
находится
(Блеск,
2, 3).
Выполняя преобразования на основе закона
Ложь
=
Ложь,
получаем следующие формулы:
находится
(Агент,1,2)
находится
(Сквозняк,
1,2)
Ложь,
находится
(Агент,2,2)
находится
(Зловоние
2,3)
Ложь,
находится
(Агент,2,2)
находится
(Сквозняк,
2,2)
Ложь.
Вторая формула в (10.9)* может быть преобразована аналогично.
С помощью преобразования
,
удаления квантора существования и правила исключения конъюнкта, получаем следующие формулы:
находится
(Чудовище,
)
находится (Зловоние, ),
находится (Чудовище, )
находится (Зловоние, ),
находится (Чудовище, )
находится (Зловоние, ),
находится (Чудовище, )
находится (Зловоние, ),
находится (Чудовище, )
находится (Зловоние, );
находится
(Яма,
)
находится (Сквозняк, ),
находится (Яма, )
находится (Сквозняк, ),
находится (Яма, )
находится (Сквозняк, ),
находится (Яма, )
находится (Сквозняк, ),
находится (Яма, )
находится (Сквозняк, );
находится
(Зловоние,
)
находится (Чудовище, ),
находится (Зловоние, )
находится (Чудовище, ),
находится (Зловоние, )
находится (Чудовище, ),
находится (Зловоние, )
находится (Чудовище, ),
находится (Зловоние, )
находится (Чудовище, ).
Следующие формулы преобразовать к требуемому виду невозможно. Оставим их в прежнем виде, исключив квантор существования:
находится
(Чудовище,
)
находится (Зловоние, )
находится (Зловоние, )
находится (Зловоние, )
находится (Зловоние, )
находится(Зловоние, );
находится
(Зловоние,
)
находится (Чудовище, )
находится (Чудовище, )
находится (Чудовище, )
находится (Чудовище, )
находится(Чудовище, );
находится
(Сквозняк,
)
находится (Яма, ) находится (Яма, )
находится (Яма, ) находится (Яма, )
находится(Яма, );
С помощью преобразования
,
удаления квантора существования и правила исключения конъюнкта получаем следующие формулы:
находится
(Агент,
)
ориентация
находится (Чудовище, )
находится (Яма, ) перейти ;
находится (Агент, ) ориентация
находится (Чудовище, )
находится (Яма, )
находится (Агент, );
находится (Агент, ) ориентация
находится (Чудовище, )
находится (Яма, )
ориентация
(
).
Число
подформул в системе формул
совпадает с числом литералов вследствие
импликативной формулы
и различаются они только последним
литералом. Поэтому для остальных формул
-
выпишем только первую подформулу
находится (Агент, ) ориентация
находится (Чудовище, )
находится (Яма, ) перейти ;
находится
(Агент,
)
ориентация
находится (Чудовище, )
находится (Яма, ) перейти ;
находится (Агент, ) ориентация
находится (Чудовище, )
находится (Яма, ) перейти ;
находится
(Агент,
)
находится (Блеск, )
взять .
Подформулы
системы формул
-
получаются аналогично, но их ещё больше.
Выпишем, как и в предыдущем случае,
только по одной (первой) подформуле:
находится (Агент, ) ориентация
находится (Чудовище, )
повернуться_направо ;
находится
(Агент,
)
ориентация
находится (Чудовище, )
повернуться_направо ;
находится
(Агент,
)
ориентация
находится (Чудовище, )
повернуться_направо ;
находится
(Агент,
)
ориентация
находится (Чудовище, )
повернуться_направо ;
находится
(Агент,
)
ориентация
находится (Чудовище, )
повернуться_налево ;
находится
(Агент,
)
ориентация
находится (Чудовище, )
повернуться_налево ;
находится
(Агент,
)
ориентация
находится (Чудовище, )
повернуться_налево ;
находится (Агент, ) ориентация
находится (Чудовище, )
повернуться_налево .
Применение обобщенного правила модус поненс вследствие того, что в нём используются не отдельные атомы, а их конъюнкции, делает вывод боле эффективным. Это объясняется тем, что подставнока одних и тех же констант осуществляется сразу для совокупности атомов, входящих в конъюнцию левой части импликации и, если необходимо, то правой.
