Лекции - Системы искусственного интеллекта
Подождите немного. Документ загружается.
Аксиомы, теоремы, факты и цели. Определение таких
понятий, как интерпретация, общезначимость, модель,
выводимость формул, введенных выше для логики высказываний,
остаются справедливыми и для логики предикатов. В
математической литературе, посвященной логике первого
порядка, аксиомами обычно называют формулы, истинные при
всех интерпретациях в некоторой среде. Как и в случае
логики высказываний, это можно выразить и другими словами:
аксиомами называют такие формулы логики предикатов, для
которых среда является моделью при всех их интерпретациях.
Как уже отмечалось, атомы с отрицаниями или без них
называют литералами. Аксиомы, которые являются литералами,
все аргументы которых константы, часто называют фактами.
Аксиомы, не являющиеся фактами, часто называют правилами.
Факты и правила представляют собой формулы логики
предикатов. Основная задача агента - вывод на основании
фактов и правил истинных формул, называемых обычно
теоремами, целями или целевыми формулами.
При описании аксиом и целей конкретной среды возникает
много вопросов. Приведем некоторые из них.
Как определить, что сформулировано достаточно аксиом,
которые относятся к данной среде, для того, чтобы можно
было вывести все интересующие нас цели?
Как избежать избыточного числа аксиом?
В каком виде аксиомы лучше всего сформулировать?
Переход от естественного языка к языку логики
предикатов. Переход от высказываний на естественном языке к
высказываниям на языке логики предикатов достаточно прост,
хотя и требует определенной аккуратности. Рассмотрим пример
перевода на язык логики предикатов первого порядка
предложений естественного языка. Если мы хотим выразить на
естественном языке знания о том, что некоторое существо
(объект), которое имеет крылья, является птицей, или что
существо, которое летает и несет яйца, также является
птицей, то мы можем записать это в виде двух следующих
предложений русского языка.
Если существо имеет крылья, то это существо - птица.
Если существо летает и несёт яйца, то это существо -
птица.
Те же знания можно выразить на языке логики предикатов
в виде таких правил или формул
).( 18
имеет_крылья (существо) птица (существо),
имеет_крылья (существо) несет_яйца (существо) птица
(существо)
51
Для того чтобы перейти к этой форме представления
знаний в языке логики предикатов сначала, глядя на
предложения русского языка, определяем, что же является
объектом, который необходимо сопоставить с константой или
переменной. В данном случае речь шла о классе некоторых
существ, обладающих определенными свойствами. Поскольку
речь идет не о конкретном существе, а о классе существ, то
вводим переменную существо для обозначения всех
представителей этого класса. Свойства существ задаются
фразами русского языка "имеет крылья", "летает", "несет
яйца", "птица". Из этих фраз, обозначающих свойства,
построим соответствующие предикатные символы,
имеет_крылья, летает, несет_яйца, птица. С использованием
этих обозначений фразы "существо имеет крылья", "существо
летает", "несет яйца", "это существо - птица" заменяются
соответственно на предикаты имеет_крылья (существо),
летает (существо), несет_яйца (существо), птица
(существо). Из этих предикатов образуются формулы или
правила (9.1), в которых слову "и" соответствует связка ,
а словам "Если..., то" - связка .
Вид существа определяет наличие или отсутствие у него
перечисленных свойств. Если это существо синица, то она
имеет крылья, а если этим существом является кролик, то,
естественно, у него нет крыльев. Иначе говоря, фраза
"синица имеет крылья", справедлива или истинна в русском
языке, а фраза "кролик имеет крылья" ошибочна или ложна. В
соответствии с этим предикат имеет_крылья(Синица)
принимает истинное значение И, а предикат
имеет_крылья(Кролик) - ложное Л. Слова Синица и Кролик в
данном случае являются объектными константами. Подставляя
значений объектных констант, имеем теперь возможность
вычислять истинность или ложность формул (9.1).
В данном примере использованы так называемые
одноместные предикаты, которые имеют по одному аргументу.
Предикаты могут быть также многоместные (имеют более одного
аргумента). В случае одноместного предиката предикатный
символ соответствует какому-либо свойству объекта. В случае
многоместных предикатов предикатный символ рассматривается
либо как некоторое общее свойство объектов, соответствующих
аргументам, либо чаще всего, как отношение, в котором эти
объекты находятся, что, впрочем, также является их
свойством. Формулы задают отношения между такого типа
свойствами, но только с использованием связок.
Логика предикатов, как и логика высказываний,
необходима для решения задач. Постановка задачи на языке
52
логики предикатов, даже если есть соответствующее описание
на естественном языке, далеко не простое дело. Для
облегчения этого процесса на основе логики предикатов
разрабатываются более удобные языки, которые учитывают
особенности конкретных сред. Этим языкам будет уделено
внимание в дальнейшем. Сейчас же вернемся к среде чудовища
и рассмотрим, как можно осуществить постановку задачи для
среды чудовища в логике предикатов.
53
9.ПОСТАНОВКА ЗАДАЧИ ДЛЯ СРЕДЫ ЧУДОВИЩА
В ЛОГИКЕ ПРЕДИКАТОВ.
Осуществим последовательно введение термов, атомов,
фактов, правил и формул цели.
Термы:
константы Агент, Чудовище, Яма, Золото, Зловоние,
Сквозняк, Блеск, 1,2,3,4;
переменные
,,,, hgji
областью значения которых являются
константы 1,2,3,4;
переменная
,x
областью значений которой является
множество констант Агент, Чудовище, Яма, Золото.
Атомы:
находится
),,( jix
, истинность которого свидетельствует,
что объект
x
находится в ячейке с координатами
,, ji
а
ложность - он там не находится;
пахнет
),,( ji
истинность которого свидетельствует, что в
ячейке с координатами
ji,
агент ощущает зловоние, а
ложность - не ощущает;
сквозит
),,( ji
истинность которого свидетельствует, что
в ячейке с координатами
ji,
агент ощущает сквозняк, а
ложность - не ощущает;
блестит
),,( ji
истинность которого свидетельствует, что
в ячейке с координатами
),( ji
агент видит блеск золота, а
ложность - блеск ему не видим;
ориентация
),,( ji
истинность которого свидетельствует,
что агент стоит лицом к ячейке с координатами
),,( ji
, а
ложность - он не стоит лицом к ячейке с этими координатами;
перейти
),,( ji
истинность которого свидетельствует, что
агент переходит в ячейку с координатами
),,( ji
к которой он
стоит лицом, а ложность, - что он никуда не переходит;
повернуться
),,( ji
истинность которого свидетельствует,
что агент поворачивается направо на 90 оставаясь в ячейке
с координатами
),,( ji
а ложность - не поворачивается;
взять
),,( ji
истинность которого свидетельствует, что
агент берет золото в ячейке с координатами
),,( ji
а ложность
- что он ничего не берет.
Постановка задачи в терминах логики предикатов теперь
будет выглядеть следующим образом.
Факты, которые определяют начальное местоположение
объектов. Начальная ситуация показана на рис. , который мы
повторяем.
4 З С Я
3 Ч,З З,С,Б Я С
2 З С
1 Н С Я С
1 2 3 4
С учетом введенных термов и атомов её (начальную)
ситуацию можно представить формулой
находится (Агент, 1,1) ориентация (1,2) пахнет
(1,1) сквозит (1,1)
Правила, определяющие условия местонахождения объектов
среды. Как и прежде, если в какой-либо ячейке не ощущается
зловония, то в соседних ей ячейках чудовища нет. Точно так
же, если в какой-либо ячейке нет сквозняка, то в соседних
ячейках нет ям. Импликации, с помощью которых можно
выразить эти знания, теперь приобретают следующий вид
),( ji
пахнет
),( ji
находится (Чудовище,
hg,
)
ig((
)),11(()11( igigjhjhjh
),( ji
сквозит
),( ji
находится (Яма,
hg,
)
ig((
)).11(()11( igigjhjhjh
Знания о наличии чудовища или ямы в ячейках, соседних
данной ячейке, если в ней соответственно ощущается зловоние
или сквозняк, можно представить в виде
),( ji
пахнет
),(),( hgji
находится (Чудовище,
hg,
)
ig((
)),11(()11( igigjhjhjh
),( ji
сквозит
),(),( hgji
находится (Яма,
hg,
)
ig((
)).11(()11( igigjhjhjh
Правила, определяющие условия выполнения агентом
действий и допустимых переходов. Агент может перейти в
соседнюю ячейку, если там его не подстерегает опасность в
виде чудовища или ямы. Поэтому формулами, определяющими
действия по переходу в соседнюю ячейку, являются следующие:
),( ji
находится (Агент,
),( ji
ориентация
),( hg
ig((
))11(()11( igigjhjhjh
находится
(Чудовище,
hg,
)
находится (Яма,
hg,
)
перейти,
hg,
)
находится (Агент,
))1(((),( jhighg
ориентация
higji (())2,(
)1j
ориентация
)(1())2,( jhigji
ориентация
)),2( ji
))(1( jhig
ориентация
)).,2( ji
Формула, которая определяет условия выполнения
действий по изъятию золота, имеет вид
),( ji
находится (Агент,
),( ji
блестит
),( ji
взять
).,( ji
Формулы, которые определяют условия выполнения действий
поворота агента направо, имеют вид
55
),( ji
находится (Агент,
),( ji
ориентация
),( hg
hig (((
)11 jhj
))11((( igigjh
(находится
(Чудовище,
),hg
находится (Яма,
)), hg
повернуться
higji )((),(
)1j
ориентация
)1()(),1( jhigji
ориентация
)()1(),1( jhigji
ориентация
)()1()1,( jhigji
ориентация
)).1,( ji
Формулы цели. Цель агента - нахождение и изъятие
золота, а решение задачи - последовательность действий,
которая приводит его в ячейку, где находится золото.
Поэтому формулой цели будет просто взять
).,( ji
56
10.ИСЧИСЛЕНИЕ ПРЕДИКАТОВ
Ранее было определено понятие логического исчисления.
Одним из таких исчислений является классическое исчисление
предикатов. Как и любое другое исчисление оно построено на
использовании:
алфавита (совокупности используемых символов);
синтаксических правил построения формул в алфавите;
аксиом (общезначимых исходных формул);
правил вывода по аксиомам производных формул или
теорем.
Алфавит и синтаксические правила построения формул в
исчислении предикатов определены выше. Множество аксиом
классического исчисления предикатов определяется следующим
образом: каждая аксиома классического исчисления
высказываний трансформируется в аксиому классического
исчисления предикатов. Эта трансформация выражается только
в том, что все её логические переменные рассматриваются как
предикаты, а формулы как формулы логики предикатов первого
порядка.
К этому множеству аксиом, которые являются аналогом
аксиом классического исчисления высказываний, добавляются
две следующие аксиомы:
)()()( yaxx
,
)()()( xxy
.
Общезначимость этих аксиом можно проверить с помощью
таблиц истинности.
Множеством правил классического исчисления предикатов
является модус поненс
- ,
, в котором
и
являются
формулами логики предикатов первого порядка, и два правила
введения кванторов:
)()( xx
,
)()( xx
.
Классическое исчисление предикатов первого порядка не
единственно. Существует множество других исчислений,
построенных на основе классического, но использующих,
помимо правил классического исчисления предикатов, и другие
правила. В частности, выше были введены такие правила
вывода в логике высказываний, как исключение конъюнкта,
введение конъюнкции, исключение двойного отрицания, простая
резолюция, резолюция. Эти правила справедливы и для логики
предикатов, с тем только отличием, что в них используются
формулы логики предикатов, а не логики высказываний.
Как и в случае классического исчисления высказываний,
все аксиомы классического исчисления предикатов не содержат
констант. Кроме того, все предикатные символы в
классическом исчислении высказываний являются абстрактными
в том смысле, что любой предикатный символ в аксиомах
логического исчисления может быть переименован и от этого
ничего не изменится. Иными словами, аксиомы классического
исчисления предикатов, как и аксиомы классического
исчисления высказываний, остаются аксиомами при любой
интерпретации.
При использовании классического исчисления предикатов
для описания свойств какоё-либо конкретной среды
абстрактные предикатные символы заменяют конкретными,
называемыми также индивидуальными предикатными символами.
Кроме того, вводят факты, аксиомы и правила, не являющиеся
аксиомами классического исчисления предикатов и зависящие
от той среды, для которой осуществляется формализация
постановки задачи. В результате получается некоторое новое
логическое исчисление. Формулы этого исчисления по-прежнему
строят по тем же правилам, показанным на рис. 8.1. С его
помощью можно выводить формулы, которые нельзя получить в
классическом исчислении высказываний. С практической точки
зрения нас интересуют именно такие исчисления, учитывающие
особенности конкретных сред. В дальнейшем ряд таких
исчислений и будет рассмотрен. Чтобы отличать такие
исчисления от классического исчисления логики предикатов
первого порядка, назовём их неклассическими исчислениями.
их числу относятся также исчисления, которые строятся не на
основе логики предикатов первого порядка. Здесь же
продолжим изучение неклассических исчислений, построенных
на основе логики первого порядка.
Пусть, например, среди множества аксиом в
неклассическом исчислении для какой-либо среды имеется две
аксиомы
)()( xx
и
)()( BA
, где
x
переменная;
BA,
константы;
,
предикатные символы. Спрашивается, можно ли
на основании этих аксиом, используя правило модус поненс
,
, заключить, что формула
)(B
истинна. Если
принять
)(A
,
)(B
, то такое заключение можно было бы
сделать, если бы среди исходных аксиом имелась аксиома
)(A
. Её у нас нет. Имеется только аксиома
)()( xx
. Эта
аксиома гласит: "Для всех
x
имеет место истинность формулы
)(x
". Когда речь идёт о всех
x
формулы
)(x
, то имеются в
виду, естественно, только те
x
, областью значений которых
58
являются заранее оговоренные константы, среди которых есть
константа
A
хотя бы потому, что она встречается в
предикате
)(A
формулы
)()( BA
, т.е. в предикате,
предикатный символ
которого совпадает с предикатным
символом предиката в аксиоме
)()( xx
. Это означает, что
предикат
)(A
истинен. Следовательно, можно
воспользоваться правилом модус поненс и заключить, что
формула
)(B
истинна. Таким образом, чтобы воспользоваться
правилом модус поненс
)()()(),( BBAA
,
пришлось по аксиоме
)()( xx
получить аксиому
)(A
. Это
равносильно использованию правила вывода, означающего, что
при наличии аксиомы
)()( xx
вместо переменной
x
в
предикат
)(x
можно подставить константу
A
(эта
подстановка обозначается
Ax
) и в результате получить
аксиому
)(A
. Это правило называют правилом исключения
квантора общности. Кроме этого правила могут потребоваться
также правила исключения квантора существования, которые
записывают в общем виде следующим образом:
исключения квантора общности
)()()( Axxx
;
исключения квантора существования
)()()( Axxx
;
введение квантора существования
)()()( AxxA
.
Здесь
)(x
произвольная формула логики предикатов, имеющая
связанную квантором общности или существования переменную
x
;
)( Ax
формула
)(x
, в которой все вхождения
переменной
x
заменены на константу
A
.
Снова пример со средой чудовища. Вернемся к решению
задачи нахождения агентом золота в среде чудовища. Выше
были сформулированы необходимые для решения задачи аксиомы.
Перечислим их в несколько виде и перенумеруем, вводя
дополнительно два атома: находится (Препятствие,
i
, 0),
находится (Препятствие, 0
j
,). Здесь используется
дополнительная константа Препятствие, соответствующая
некоторому вымышленному объекту, который ограничивает
передвижение объекта в ячейки, хотя бы одна координата
которых равна нулю.
Предварительно напомним, что восприятие агента
позволяет ему определять наличие зловония, сквозняка или
блеска только в той ячейке, где он находится. Поэтому
59
полное начальное состояние среды чудовища агенту
неизвестно. Находясь в ячейке (1,1), он может
воспользоваться только восприятиями в этой ячейке.
Формулы, определяющие начальные знания агента:
).( 110
находится (Агент, 1,1)
).( 210
ориентация (1,2)
).( 310
находится (Зловоние, 1,1)
).( 410
находится (Сквозняк, 1,1)
).( 510
находится (Яма, 1,1)
).( 610
)(i
находится (Препятствие,
i
, 0)
).( 710
)( j
находится (Препятствие, 0,
j
)
Для того чтобы выразить возможность восприятия агентом
зловония, сквозняка или блеска в ячейках (1,2), (2,1),
(3,1), соответственно введём следующие формулы:
).( 810
находится (Агент, 1,2) находится (Зловоние, 1, 2),
).( 910
находится (Агент, 2,1) находится (Сквозняк, 2, 1)
находится (Зловоние, 1, 2),
).( 1010
находится (Агент, 2,3) находится (Блеск, 2, 3),
).( 1110
находится (Агент,1,2) находится (Сквозняк, 1,2),
).( 1210
находится (Агент,2,2) находится (Зловоние 2,3),
).( 1310
находится (Агент,2,2) находится (Сквозняк, 2,2).
Формулы, определяющие условия местонахождения объектов
в зависимости от восприятия:
).( 1410
),( ji
находится (Зловоние,
ji,
находится
(Чудовище,
ji,
) находится (Чудовище,
1ji,
)
находится (Чудовище,
1ji,
)
находится (Чудовище,
ji ,1
)
находится(Чудовище,
ji ,1
),
).( 1510
),( ji
находится (Сквозняк,
ji,
находится
60