Лекции - Системы искусственного интеллекта
Подождите немного. Документ загружается.
Далее на основании следующего варианта правила (7.9),
т.е.
o
n
zjixjix
jixjixjixjix
)1,()1,(
)),1()1,(),(),(
яч
ччн
(
имеем
o
n
zxx
xxxx
),(),(
)),(),(),(),(
11 11
31 22( 2121
яч
ччн
агент приходит к выводу, что у него есть единственная
возможность повернуться в ячейке (1,2), что он и делает на
основании следующего варианта правила , т.е.
).,(),()1,()1,(
)),1()1,(),(),(
jixjixzjixjix
jixjixjixjix
so
n
няч
ччн
(
Тем самым
).2,1()2,1()1,1()1,1(
))3,1()2,2()2,1()2,1(
so
n
xxzxx
xxxx
няч
ччн
(
Затем агент устанавливает возможность выполнения
действия перехода и возвращается в ячейку (1,1) на
основании правил типа
,)1,1()1,1()2,1()2,1(
ms
zxxxx
ячн
).1,1()1,1()1,1()1,1()2,1()2,1(
0 ss
xxzxxxx
нячн
Оказавшись вновь в ячейке (1,1), агент последовательно
устанавливает возможность поворота к ячейке (2,1),
совершает этот поворот, устанавливает возможность перехода
в эту ячейку и совершает его. Все это он делает на
основании следующих правил, аналогичных по типу уже
рассмотренным
,)1,2()1,2()1,1()1,1(
0
zxxxx
s
ячн
),1,1()1,1()1,2()1,2()1,1()1,1(
0 es
xxzxxxx
нячн
,)1,2()1,2()1,1()1,1(
me
zxxxx
ячн
).1,2()1,2()1,2()1,2()1,1()1,1(
eme
xxzxxxx
нячн
Очутившись в ячейке (2,1), агент ощущает сквозняк и
отсутствие зловония на основании правил типа
),1,2()1,2(
с
xx
н
).1,2()1,2(
зн
xx
Так как зловония в ячейке (2.1) нет (
)1,2(
з
x
истинна),
агент, используя формулу типа
)3,1()2,2()1,1()1,2(
чччз
xxxx
и правила модус поненс и исключение конъюнкта, заключает,
что чудовища нет в ячейке (2,2) (
)2,2(
ч
x
истинна). Агент
41
ощущает сквозняк в ячейке (2,1) (
)1,2(
с
x
истинна), поэтому,
используя формулу типа
),1,3()2,2()1,1()1,2(
яяяс
xxxx
правило модус поненс и простую резолюцию, заключает, что в
ячейке (3,1), к которой он стоит лицом, имеется яма (
)1,3(
я
x
истинна). Отсюда на основании правил типа
,)2,2()2,2()1,3()1,2()1,2(
0
zxxxxx
e
ячян
),1,2()1,2(
)2,2()2,2()1,3()1,2()1,2(
0
n
e
xx
zxxxxx
н
ячян
а затем правил (7.6), (7.7)
,)2,2()2,2()1,2()1,2(
mn
zxxxx
ячн
),2,2()2,2()2,2()2,2()1,2()1,2(
nmn
xxzxxxx
нячн
агент сначала совершает поворот в сторону ячейки (2,2), а
затем переходит в неё. В ячейке (2,2) на основании формул
),2,2()2,2(
сн
xx
)2,2()2,2(
зн
xx
он обнаруживает, что в ней нет ни зловония, ни сквозняка
(истинны формулы
),2,2(
з
x
)2,2(
с
x
).
Далее по формулам (7.4), правил модус поненс и
исключением конъюнкта он устанавливает, что чудовища и ямы
в ячейке (2,3) также нет (истинны формулы
),3,2(
ч
x
)3,2(
я
x
)
),1,2()2,3()3,2()2,1()2,2(
)1,2()2,3()3,2()2,1()2,2()2,2(),2,2(
ччччч
чччччзз
xxxxx
xxxxxxx
).1,2()2,3()3,2()2,1()2,2(
)1,2()2,3()3,2()2,1()2,2()2,2(),2,2(
яяяяя
яяяяяcc
xxxxx
xxxxxxx
После этого агент может воспользоваться одной из формул
типа (7.6), одной из формул типа (7.7) и правилом модус
поненс для перехода в ячейку (2,3)
,)3,2()3,2()2,2()2,2(
),3,2()3,2()2,2()2,2(
mmn
n
zzxxxx
xxxx
ячн
ячн
.)3,2()3,2()3,2()3,2(
)3,2()3,2()2,2()2,2(
nn
mn
xxxx
zxxxx
нн
ячн
В результате агент оказывается в ячейке (2,3) (истинна
)3,2(
н
x
) и видит блеск золота (истинна
)3,2(
б
x
на основании
правила
)3,2()3,2(
бн
xx
). Используя формулу и правило модус
42
поненс, агент может сделать заключение о возможности
совершения действия
3
z
по изъятию золота из ячейки (2,3)
.)3,2()3,2(),3,2()3,2(
33
zzxxxx
бнбн
Число формул в логике высказываний, требуемых для
представления знаний. Нетрудно заметить, что число формул,
которые требуются для постановки задачи, растет довольно
быстро, хотя среда чудовища имеет всего 16 ячеек и все её
объекты, кроме агента, не изменяют своего местоположения.
Так, число формул типа (7.4) равно 32, (7.5) - 16, (7.6) -
64, (7.7) - 16, (7.8) - 16, (7.9) - 128, (7.10) - 16,
(7.11) - 128, (7.12) - 16, (7.13) - 32, (7.14) - 32, что в
сумме составляет 496.
В случае более сложной среды необходимо представить все
возможные изменения местоположения других объектов,
например, чудовища, в ответ на действия агента и для
действия каждого такого объекта предусмотреть свои формулы.
Занижая оценку, будем полагать, что число формул в среде с
l
ячейками равно
.
5
l
Тогда при
,7,6,5l
это будут числа
3125, 7776, 16807,... соответственно. Могут потребоваться
также правила, которые учитывают предысторию действий
агента. Все это может привести к огромному числу формул,
для хранения которых потребуется такой большой объем
памяти, которой может не хватить даже на современных
компьютерах. Кроме того, сама постановка задачи, требующая
записи такого огромного числа формул, может стать
практически невыполнимой задачей. В то же время многие
реальные задачи часто, несмотря на большое число
переменных, могут иметь сравнительно небольшое количество
формул в постановке задачи и достаточно успешно решаться с
использованием логики высказываний. К числу таких задач,
например, относятся задачи анализа логических схем.
43
9.ЛОГИКА ПРЕДИКАТОВ
Ранее было показано, каким образом логику высказываний,
можно использовать для представления знаний и логических
рассуждений. Однако выразительные возможности логики
высказываний невысоки. Требуется слишком много формул
логики высказываний для описания даже простых сред.
Например, в случае простой среды чудовища для того, чтобы
указать факт наличия или отсутствия любого объекта
(чудовища, агента, ям, золота) в какой-либо ячейке среды,
пришлось ввести для каждого объекта множество логических
переменных, число которых совпадает с числом ячеек среды, и
сопоставить каждое местонахождение объекта в какой-либо
ячейке с координатами
),( ji
истинному значению переменной,
соответствующей объекту и этой ячейке. Понятно, что число
таких переменных равно числу ячеек среды, умноженному на
число объектов.
Здесь мы изучим логику предикатов первого порядка,
называя её в дальнейшем просто логикой предикатов, которая
существенно более выразительна, чем логика высказываний, и
позволяет представлять знаний о среде гораздо более
компактно. Выразительность логики предикатов является
следствием её основополагающей идеи, которая заключается во
взаимно-однозначном сопоставлении каждого уникального (не
совпадающего ни с каким другим) объектом среды с
индивидуальной объектной константой, которая обозначается
именем (названием) объекта, а класс однотипных по каким-
либо свойствам объектов - с объектной переменной, значением
которой являются объектные константы. Объектные константы и
переменные в литературе часто называют индивидными, или
предметными.
Предикатом называют высказывательную функцию,
определенную на множестве наборов значений объектных
переменных. Эта функция может принимать только два
значения: Истина (И) и Ложь (Л), называемые истинностными
значениями. Отношения объектов среды представляются на
языке логики предикатов, как и на языке логики
высказываний, в виде определенных предложений
(высказываний, формул логики предикатов), которые
используют объектные переменные и объектные константы, а
также ряд других конструкций, включая уже известные связи и
скобки.
Рассмотрим подробнее язык логики предикатов.
Синтаксис и семантика. Синтаксис логики предикатов с
использованием метаязыка Бэкуса-Наура приведен ниже.
Рассмотрим семантику всех синтаксических конструкций,
приведенных здесь.
Формула
Атом
Предложение
Предложение Связка Предложение
Квантор (Переменная,...,Переменная) Предложение
Предложение
(Предложение),
Атом
Предикатный символ (Терм,...,Терм)
Терм=Терм,
Терм
Функциональный символ (Терм,...,Терм)
Константа
Переменная
Связка
,
Квантор ,
Константа Строка символов, начинающаяся с прописной
буквы,
Переменная Строка символов, со строчной буквы,
Предикатный символ Строка символов, со строчной
буквы,
Функциональный символ Строка символов, со строчной
буквы.
Рис. 8.1.
Объектные переменные. Объектные переменные или просто
переменные обозначаются строкой символов, которая
начинается со строчной буквы и записывается курсивом.
Областью значений каждой переменной является множество
констант, в общем случае даже бесконечное. Как это область
значений очерчивается, будет ясно из дальнейшего.
Функции. Для того чтобы задать такие отношения между
объектами, когда в точности один объект соответствует
множеству других объектов используют функции. Например,
если объектами являются двоичные цифры 0 и 1 и десятичные
цифры 0,1,...,9, то любому набору из трех двоичных цифр,
который представляет двоичное число, можно однозначно
сопоставить десятичную цифру. Если двоичные цифры
сопоставить с переменными
,,, zyx
а десятичные с переменной
,q
то рассмотренное отношение между двоичными и
десятичными цифрами можно представить в виде функции
преобразование_2_в_10
).,,( zyx
45
Выражение преобразование_2_в_10 называют функциональным
символом. Так при
1,0,1 zyx
с помощью функции
преобразование_2_в_10
),,( zyx
получим значение функции,
равное
.5q
Отметим, что функция в логике предикатов не
предполагает обязательного наличия какого-либо алгоритма
вычисления значения функции по её аргументам. Она лишь
задает с помощью констант и переменных определенное
отношение между объектами, соответствующими её аргументами,
и каким-то одним объектом.
Объектные константы. Каждая объектная константа,
называемая в дальнейшем, если это не вызывает путаницы,
просто константой, взаимно однозначно сопоставляется в
процессе интерпретации с каким-либо одним объектом среды.
Константа обозначается строкой символов, которая начинается
с прописной буквы, и, чаще всего, эта строка символов
совпадает с именем или наименованием объекта и записывается
курсивом, например, Владимир, Чудовище, Кот и т. д.
Термы. Константы, переменные и функции являются
термами. Выбор констант, переменных и функций для данной
среды полностью является прерогативой того, кто использует
логику предикатов. Предположим, например, что наша среда
имеет такие объекты, как крылья и птицы, и нам известно,
что "птицы имеют крылья". Спрашивается, как выразить это
знание? Введем константы, которые обозначают конкретный вид
птиц, например, Воробей, Синица, Соловей и константу
Крылья, которая обозначает объект крылья. Введем также
переменную
,x
которая обозначает все объекты, которые
являются птицами: функциональный символ имеет крылья ставит
во взаимно-однозначное соответствие любой птице объект
крылья. Тогда функция имеет_крылья
)(x
задает отношение
между объектом крылья и птицей
.x
Если, например,
x
Воробей, то имеет_крылья
(Воробей)=Крылья. Но это не единственная возможность
выразить отношения между птицами и крыльями. Функция может
не содержать аргументов, т.е. иметь только функциональный
символ. Термы, которые не содержат аргументов, т.е.
константы, переменные и функции без аргументов, называют
элементарными термами.
Предикатный символ. С помощью предикатов задаются
отношения между объектами. Такие отношения задаются
выражением, которое начинается как и в случае с функцией,
строкой символов, записанных курсивом, первая буква которой
строчная. Эта строка символов называется предикатным
символом. За ним в скобках следует упорядоченный набор
переменных или констант, соответствующих объектам, которые
46
находятся в поименованном отношении. Так, например, если
два человека Владимир и Марина являются братом и сестрой,
то это отношение родства может быть выражено с помощью
конструкции брат_и_сестра(Владимир, Марина), где
брат_и_сестра является предикатным символом, а (Владимир,
Марина) - упорядоченным набором объектных констант.
Конструкция брат_и_сестра(Владимир, Марина) является
предикатом, способным принимать одно из двух значений
Истина или Ложь. В случае истинного значения предиката
будем говорить также, что отношение, задаваемое предикатом,
имеет место, а в случае ложного - не имеет места.
Отношение между птицами и крыльями выраженное выше с
помощью функции, может быть выражено и с помощью предиката
крылья
),(x
который истинен, если это отношение выполняется.
Это может быть, например, когда
x
Воробей, т.е. когда
истинен предикат крылья(Воробей).
Атомы. Выражение предикатный символ (терм, терм,...,
терм) называют атомом. Атом представляет предикат. Особо
выделяется атом, предикатным символом которого является
знак равенства, а аргументом два терма. Этот атом можно
было бы представить, как равны(терм, терм) или =(терм,
терм), но, как правило, его записывают в обычной инфиксной
форме терм=терм. Этот атом истинен, когда значение обоих
термов совпадают. Атомы без знака отрицания или со знаком
отрицания называют литералами.
Кванторы. Когда мы имеем дело с объектами, то возникает
естественная потребность выразить какие-либо общие свойства
целого множества объектов. Кванторы как раз служат этим
целям. Таких кванторов в логике предикатов всего два.
Квантор общности . Вспомним, что при решении задачи
поиска золота в среде чудовища для того, чтобы выразить
правило "В какой бы ячейке агент не находился, если он
видит блеск золота, то он должен его взять", было
использовано 16 однотипных формул, число которых совпадает
с числом ячеек. Эти формулы имели вид
4444
(8.1)
1111
збн
збн
збн
.),(),(
,
,),(),(
,
,),(),(
zxx
zjixjix
zxx
Здесь
),(),,( jixjix
бн
отдельные переменные. Каждая из них
принимает истинное значение, если соответствующий ей объект
(в данном случае агент и золото, точнее блеск золота)
находится в ячейке
).,( ji
Обратим ещё раз внимание на то,
что
),( jix
н
и
),( jix
б
это индексированные логические
47
переменные с индексами
,, jiб,н,
каждая из которых считается
единым неделимым символом. Большое количество формул
пришлось вводить из-за того, что в логике высказываний нет
возможности представить указанное выше правило в виде одной
формулы. В логике предикатов такая возможность имеется и,
вместо 16 формул в логике высказываний, в логике предикатов
можно написать одну
,),(),(),().(
збн
28 zjixjixji
где знак называется квантором общности. Но в этой
формуле
),( jix
н
,
),( jix
б
и
з
z
уже не являются логическими
переменными. Здесь
збн
zxx ,,
предикатные символы, вид которых
для удобства сохранен тем же, что и в логических
переменных, а
ji,
числовые объектные переменные,
соответствующие координатам ячеек. На естественном языке
это правило формулируется следующим образом.
"Для всех ячеек с координатами
ji,
и видит в ней блеск
золота, то он должен его взять".
Смысл квантора общности совпадает с выражение
естественного языка: "Для всех...". Множество формул (8.1)
логики высказываний эквивалентно одной формуле (8.2) логики
предикатов, т.е. имеет место
).)4,4()4,4(())2,1()2,1((
))1,1()1,1(()),(),(),((
збнзбн
збнзбн
zxxzxx
zxxzjixjixji
Квантор существования . Квантор общности позволяет
формулировать высказывания о свойствах целого множества
объектов. В то же время часто возникает необходимость
высказываться о свойствах отдельных объектов из какой-либо
совокупности. Для этого используют квантор существования
. Вернемся к примеру со средой чудовища. Ранее, для того,
чтобы выразить знания о наличии чудовища в ячейках,
соседних ячейке с координатами
),( ji
, если в ней ощущается
зловоние, было введено 16 формул, в которых индексы
ji,
пробегают множество значений от 1 до 4. Вместо этих 16
формул с помощью квантора общности можно записать одну
формулу, помня, что теперь вместо логических переменных
используются предикаты, а индексы стали числовыми
объектными переменными
).,(),(),(),(),(),(),().( 1111 38
чччччз
jixjixjixjixjixjixji
На естественном языке высказывание, которое
соответствует этой формуле, звучит так: "Для всех ячеек с
координатами
),( ji
справедливо: если ощущается зловоние в
ячейке с координатами
),,( ji
то существует ячейка, соседняя
ячейке с координатами
),,( ji
в которой находится чудовище".
Для того чтобы выразить часть этого высказывания "...
48
существует ячейке, соседняя ячейке с координатами
),,( ji
в
которой находится чудовище" в логике высказываний были
использованы формулы, в которых справа от знака импликации
стоит дизъюнкция пяти логических переменных. В логике
предикатов имеется возможность более короткой записи этой
части высказывания с использованием квантора существования
)).11((
)11(((),()(
igigjh
jhjhighgxhg
,
ч
Используя эту запись вместо 16 формул логики
высказываний, в логике предикатов можно ограничиться одной
формулой
)).((
)(((),()(),(),).(
11
11 , ( 48
чз
igigjh
jhjhighgxhgjixji
Квантор существования произносится на естественном
языке как "Существует...".
Взаимосвязь между кванторами. Считают, что квантор
связывает переменные, которые записываются за значком
квантора в скобках. Поэтому их называют связанными.
Переменные же, которые ни один квантора не связывает,
называют свободными. Взаимосвязь между кванторами
существования и общности можно легко выразить с помощью
связки
и она основана на следующем соображении: если
какая-либо совокупность переменных связана квантором
общности таким образом, что все объекты, которым
соответствуют эти переменные, не обладают каким-то общим
свойством, то не существует объекта (а следовательно, и
соответствующей ему переменной), который обладал бы этим
свойством. Например, в случае с чудовищем, если во всех
ячейках нет чудовища, то это означает, что не существует ни
одной ячейки, в которой бы находилось чудовище и наоборот.
Эту взаимосвязь можно описать следующей формулой
).,(),(),(),( jixjijixji
чч
Если же ямы находятся во всех ячейках, то это означает,
что не существует ячейки, в которой не было бы ямы. Эту
взаимосвязь можно выразить формулой
).,(),(),(),( jixjijixji
яя
Продолжая аналогичные рассуждения и обозначая
)(xP
любую формулу, переменная
x
которой связана кванторами,
получаем следующие законы, которые характеризуют
взаимосвязь между кванторами
),()()()( xPxxPx
),()()()( xPxxPx
49
),()()()( xPxxPx
),()()()( xPxxPx
Равенство. Ранее рассматривался атом особого типа терм
терм, называемый равенством, в котором используется знак
равенства в инфиксной форме. Этот знак, который является
предикатным символом, свидетельствует о том, что формула
терм терм истинна только в том случае, если оба терма
соответствуют одному и тому же объекту. Обозначая константы
символами
YX ,
, переменные символами
yx,
, функциональный
символ
F
, это можно пояснить с помощью таблицы
Таблица
YX
Формула истинна, если константы
X
и
Y
именуют
один и тот же объект
Yx
Формула истинна, если переменная
x
принимает
значение, равное константе
Y
yx
Формула истинна, если значение переменной
x
совпадает со значением переменной
y
)(YFX
Формула истинна, если значение функции
)(YF
совпадает с константой
X
)(YFx
Формула истинна, если значение функции
)(YF
совпадает со значением переменной
x
)(yFX
Формула истинна, если значение функции
)(yF
совпадает со значением константы
X
Использование равенства можно пояснить двумя примерами
из мира чудовища. Имеем формулу
),,(),(),().( jxixji 33 58
яя
которая на естественном языке читается следующим образом:
"Существуют
ji,
такие, что в ячейках с координатами
),,3( i
),3( j
находится яма". Для нашего примера действительно
существуют ячейки с координатами
),3,3(
)3,3(
, в которых
находится яма. Это означает, что формула (8.5) истинная при
значениях координат
),3,3(
)3,3(
. Значения переменных
ji,
могут быть как различными, так и одинаковыми. Если же
используется формула (8.5) с равенством, то она будет
истинна только при равных значениях
i
и
j
).(),(),(),().( jijxixji 33 68
яя
Следующая формула с отрицанием равенства, наоборот,
будет истинная при различных координат
).(),(),(),().( jijxixji 33 78
яя
50