Лекции - Системы искусственного интеллекта
Подождите немного. Документ загружается.
величины И или Л. Такие таблицы в логике высказываний
называют таблицами истинности (таблица ).
Таблица
x y
x
yx
yx
yx
yx
Л Л И Л Л И И
Л И И Л И И Л
И Л Л Л И Л Л
И И Л И И И И
Таблицы истинности можно построить для любой формулы,
поскольку любая формула является композицией формул для
связок. Если формула интерпретирована, то её таблица
истинности определяет семантику интерпретированной формулы,
поскольку по ней всегда можно определить, какие же
отношения между свойствами объектов, обозначаемых
переменными, имеют место (формула истинна) и не имеют места
(формула ложна).
Общезначимые формулы и их роль. Формулы, истинные на
всех наборах значений своих аргументов, называют
общезначимыми формулами. Если какая-либо формула
является общезначимой, то этот факт обычно записывается с
использованием знака общезначимости
,
который ставится
перед формулой:
.
Проверку формулы на общезначимость
можно осуществить с помощью таблицы истинности: если
формула истинна во всех строках таблицы истинности, которая
содержит все возможные наборы аргументов формулы, то эта
формула общезначима. Рассмотрим, например, формулу
.)( xyyx
Таблицей истинности для неё является таблица
.
Таблица
x y x (yy) x(yy) x(yy)x
Л Л И И И И
Л И И И И И
И Л Л Л Л И
И И Л Л Л И
Из этой таблицы ясно, что формула x(yy)x
является общезначимой (во всех строках последнего столбца
стоит значение И). Ранее было заявлено, что истинность
высказывания
21
всегда означает, что истинность
1
влечет истинность
2
(здесь
1
и
2
являются формулами
логики высказываний). Потому, установив факт общезначимости
формулы
21
и истинность
,
1
всегда можно сделать
21
заключение об истинности
2
. Так, например, предположим,
что истинное значение логической переменной x в формуле
x(yy)x соответствует местонахождению кота слева
(Слева), а ложное значение логической переменной x
соответствует местонахождению кота справа (Справа),
истинное значение переменной y соответствует наличию сыра
около левой комнаты (Да), а ложное его отсутствию там
(Нет). В этом случае при истинности формулы x(yy)x
можно сделать заключение об истинности формулы x, что
соответствует нахождению кота у правой комнаты (Справа).
Таким образом, общезначимость формул вида
21
,
называемых импликативными формулами, является важным
свойством для получения заключения об истинности
2
,
называемого заключением, при истинности
,
1
называемого
посылкой. Для простоты импликативные формулы
21
будем
называть так же, как и связку
,
импликацией. В логике
высказываний известно много общезначимых формул, называемых
обычно законами логики высказываний.
Наиболее известными являются следующие законы:
коммутативные
,
1221
;
1221
дистрибутивные
),()()(
3121321
);()()(
3121321
ассоциативные
,)()(
321321
;)()(
321321
законы Де Моргана
),()()(
2121
);()()(
2121
закон двойного отрицания
.)(
11
В этих законах
обозначает любую правильно
построенную формулу логики высказываний.
Кроме общезначимых, существуют формулы выполнимые и не
выполнимые. Формула называется выполнимой, если существуют
наборы значений её аргументов, на которых она принимает
истинное значение, и наборы значений, на которых она
22
принимает ложное значение. Если на всех наборах значений её
аргументов принимает ложное значение, то она называется
невыполнимой.
Установление истинности следствия по общезначимой
импликативной формуле достаточно универсальный способ для
вывода заключений, но требует проверки общезначимости
последней.
Если формула
21
не является общезначимой, то
подобного заключения делать нельзя. Проверку общезначимости
можно осуществлять с помощью таблицы истинности. Однако
построение таблиц истинности слишком трудоемко для того,
чтобы можно было решать реальные задачи. Вместо этого
используют специальные правила вывода, применение которых
базируется не на понятии общезначимости формулы, в
частности общезначимости импликативной формулы, а на
понятии модели формулы.
Модель формулы. Любую среду, конкретизация в которой
при соответствующей интерпретации делает формулу истинной,
называют моделью этой формулы. Так, например, среда кота
является моделью формулы
плкплк
xxxzxxx
2
при
конкретизации переменных
кплк
xzxxx
2
,,,
соответственно как
высказываний "кот находится у левой комнаты", "у левой
комнаты лежит кусочек сыра", "у правой комнаты лежит
кусочек сыра", " кот переходит к правой комнате","кот
находится у правой комнаты" поскольку высказывание "если
кот находится у левой комнаты" и "у левой комнаты лежит
кусочек сыра" и "у правой комнаты лежит кусочек сыра" и
"кот переходит к правой комнате", то после этого "кот
находится у правой комнаты" и "у левой комнаты лежит
кусочек сыра", являющиеся конкретизацией формулы
плкплк
xxxzxxx
2
, истинно.
Понятие модели является важным в логике высказываний и
других логиках, поскольку позволяет удачно ввести понятие
выводимости одних, истинных при соответствующей
интерпретации формул, из других истинных. Считают, что
формула
выводима из формул
,,,,
21 m
если любая (но
одна и та же) модель всех этих формул
m
,,,
21
является
также моделью формулы
. Иными словами, если формулы
m
,,,
21
истинны на некотором множестве конкретизаций в
данной среде, то формула
выводима из них, если она также
истинна на всех конкретизациях этого множества. Факт
выводимости записывают с помощью символа выводимости
:
.,,
1
k
23
6.ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
Логическим исчислением, или просто исчислением,
называют совокупность, которая включает в себя: алфавит
(совокупность используемых символов); синтаксические
правила построения формул в алфавите; аксиомы (общезначимые
формулы); правила вывода по аксиомам производных формул или
теорем.
Правила вывода
имеют дело непосредственно с
формулами, а не с таблицами истинности, позволяя по
истинности одних формул делать заключения об истинности
других. Символы
и
в правиле вывода обозначают одну
или несколько формул;
называется условием, а
-
следствием. Если в условии или следствии формул несколько,
то они записываются через запятую. Нас прежде всего будут
интересовать только такие правила вывода, можно при любой
интерпретации сделать заключение об истинности всех формул,
входящих в следствие правила вывода. Обычно такие правила
называют состоятельными. Доказательство состоятельности
правила вывода можно осуществить с помощью таблицы
истинности, каждая строка которой соответствует одной из
моделей условия, а общее число строк совпадает с числом
всех моделей условия. Если всем этим условиям соответствуют
истинные следствия, то правило является состоятельным.
Классическое исчисление высказываний. Ранее мы
рассматривали язык логики высказываний. Если в качестве
алфавита логического исчисления взять алфавит логики
высказываний, в качестве синтаксических правил -
синтаксические правила логики высказываний, в качестве
аксиом - некоторое множество общезначимых формул, например
законов; в качестве правил всего два правила: модус поненс
и подстановки, указанные ниже, то в результате получим
исчисление, называемое обычно исчислением высказываний.
Классическим исчислением высказываний обычно называют
исчисление, аксиомами которого являются следующие
общезначимые формулы
),(
)),())((()(
,)(
,)(
),(
),(
)),((
)),)(()(()(
),)(()(
.
Обратим внимание, что все аксиомы логики высказываний
включают в себя только логические переменные и истинны при
любой интерпретации. Поэтому, если нам удастся достаточно
адекватно интерпретировать эти законы в какой-либо среде,
то исчисление высказываний может служить основой для
рассуждений об этой среде.
Классическое исчисление высказываний использует два
правила вывода.
Модус поненс. Из истинности условия импликации и
истинности самой импликации следует истинность следствия
импликации
.,
Правило подстановки. Из формулы
)( p
выводима формула
),(P
которая получается подстановкой в формулу
)( p
вместо
каждого вхождения переменной
p
формулы
P
).()( Pp
Другие исчисления высказываний. Существуют и другие
исчисления высказываний. Так, например, при решении
практических задач удобнее использовать не законы логики
высказываний, а правила, которые их заменяют. В этом случае
логическое исчисление называют натуральным исчислением
высказываний. В натуральном исчислении высказываний обычно,
помимо правил модус поненс и подстановки используют
следующие правила.
Исключение конъюнкта. Из истинности конъюнкции следует
истинность любого её конъюнкта
.
21 in
Введение конъюнкции. Из списка истинных формул следует
истинность их конъюнкции
.,,,
2121 nn
Введение дизъюнкции. Из истинности формулы следует
истинность её дизъюнкции с любыми другими формулами
.
211 ni
Исключение двойного отрицания. Из истинности двойного
отрицания формулы следует истинность её самой
.
25
Простая резолюция (удаление дизъюнкта). Из истинности
дизъюнкции и отрицания одного из её дизъюнктов следует
истинность формулы, которая получается из дизъюнкции
удалением этого дизъюнкта
.,
Резолюция. Из истинности двух дизъюнкций, одна из
которых содержит дизъюнкт, а другая - его отрицание,
следует формула, которая является дизъюнкций исходных
формул без упомянутого дизъюнкта и его отрицания
,
или эквивалентно
, .
Формализация вывода средствами логики высказываний.
Вернемся к нашему примеру - среде кота. Введем три
логические переменные
,,,
пл
xxx
k
истинное значение первой из
которых означает, что кот находится у левой комнаты, а
ложное, что он находится у правой комнаты; истинное
значение переменной
л
x
означает, что кусочек сыра лежит
около левой комнаты, а ложное, что его там нет; истинное
значение
п
x
означает, что кусочек сыра лежит около правой
комнаты, а ложное, что его там нет. В результате таких
обозначений табл. 1 можно заменить на табл. 4.Каждое
состояние среды можно рассматривать как комбинацию
(отношение) простейших свойств объектов, задаваемых
значениями отдельных логических переменных. Так, состояние
1
b
соответствует комбинации свойств кота и кусочков сыра,
состоящей в том, что кот находится у левой комнаты, и в то
же самое время около левой и правой комнат находится по
кусочку сыра. На русском языке эту комбинацию можно
выразить предложением "Кот находится около левой комнаты,
кусочек сыра лежит около левой комнаты и кусочек сыра лежит
у правой комнаты". В соответствии с уже приведенной выше
интерпретацией логических переменных
пл
xxx
k
,,
это
предложение можно представить формулой
,
пл
xxx
k
которая
истинна в единственном случае - все логические переменные,
входящие в нее, истинны, т.е. среда находится в состоянии
1
b
. Формулы такого типа, которые являются конъюнкцией
переменных с отрицанием или без него, называют
элементарными конъюнкциями. Если среда находится в
состоянии
2
b
, то истинна формула
пл
xxx
k
и т.д.
Таблица 4
Переменные
26
Состоян
ие
Формула,
описывающая
состояние
x
к
x
л
x
п
b
1
И И И
x
к
x
л
x
п
b
2
Л И И
x
к
x
л
x
п
b
3
И И Л
x
к
x
л
x
п
b
4
Л И Л
x
к
x
л
x
п
b
5
И Л И
x
к
x
л
x
п
b
6
Л Л И
x
к
x
л
x
п
b
7
И Л Л
x
к
x
л
x
п
b
8
Л Л Л
x
к
x
л
x
п
Элементарную конъюнкцию, в которую входит по одному
разу каждая переменная, которая определяет состояние среды,
с отрицанием или без отрицания, называют полной
конъюнкцией, или конституентой. Аналогично тому, как были
введены логические переменные
,,,
пл
xxx
k
введем логические
переменные
321
,, zzz
действий кота Идти налево, Идти направо,
Съесть. Соответственно Переменная принимает истинное
значение, если выполняется соответствующее ей действие. В
противном случае она принимает ложное значение. Для
простоты будем полагать, что кот не может одновременно
выполнять сразу более одного действия.
Рассмотрим теперь, как могут быть выражены в виде
формул переходы среды из одного состояния в другое при
совершении котом того или иного действия. Так если кот
находился в состоянии
1
b
и выполнил действие Идти направо,
то среда перейдет в состояние
.
2
b
Факт нахождения кота в
состоянии
1
b
и выполнение им в это время действия Идти
направо означает истинность
,
2 плкплк
xxxzxxx
а факт
перехода состояния
1
b
при выполнении действия Идти направо
в состояние
2
b
будем интерпретировать как истинность
формулы
,
2 плкплк
xxxzxxx
что позволяет при истинности
2
zxxx
плк
сделать заключение
об истинности
.
плк
xxx
Точно так же можно выразить в виде
аналогичных формул все остальные переходы, показанные на
рис. Представим их виде таблицы 5. В первых трех столбцах
этой таблицы указаны переходы, которые имеются на рис....,
а в последнем - формулы, соответствующие переходам.
Таблица 5
Переход
27
Импликация,
соответствующая переходу
Исходн
ое
состоя
ние
Действи
е
Результир
ующее
состояние
1
b
11
zc
1
b
плкплк
xxxzxxx
1
1
b
22
zc
2
b
плкплк
xxxzxxx
2
1
b
33
zc
5
b
плкплк
xxxzxxx
3
2
b
11
zc
1
b
плкплк
xxxzxxx
1
2
b
22
zc
2
b
плкплк
xxxzxxx
2
2
b
33
zc
4
b
плкплк
xxxzxxx
3
4
b
11
zc
3
b
плкплк
xxxzxxx
1
4
b
22
zc
4
b
плкплк
xxxzxxx
2
4
b
33
zc
4
b
плкплк
xxxzxxx
3
3
b
11
zc
3
b
плкплк
xxxzxxx
1
3
b
22
zc
4
b
плкплк
xxxzxxx
2
3
b
33
zc
7
b
плкплк
xxxzxxx
3
5
b
11
zc
5
b
плкплк
xxxzxxx
1
5
b
22
zc
6
b
плкплк
xxxzxxx
2
5
b
33
zc
5
b
плкплк
xxxzxxx
3
6
b
11
zc
5
b
плк1плк
xxxzxxx
6
b
22
zc
6
b
плкплк
xxxzxxx
2
6
b
33
zc
8
b
плкплк
xxxzxxx
3
Нахождение целевого состояния. Имея формулы для
состояний и переходов, введенные раньше, покажем теперь,
как их можно использовать для нахождения одного из целевых
состояний. Целевыми состояниями являются
7
b
и
8
b
. Если
среда находится в состоянии
7
b
, то это означает истинность
формулы
плк
xxx
, а если в состоянии
8
b
, то истинность
формулы
плк
xxx
.
Имеем таким образом постановку задачи:
* начальное состояние среды представлено истинной
формулой
;
плк
xxx
* множество формул представляют все состояния среды в
последнем столбце таблицы 4;
* множество допустимых переходов представлено
импликациями в последнем столбце таблицы 5;
28
* множество допустимых действий описывается формулами
,
321
zzz
,
321
zzz
;
321
zzz
* множество целевых состояний представлено формулами
плк
xxx
и
плк
xxx
.
Решение задачи состоит в нахождении последовательности
переходов, которые ведут из начального состояния в одно из
целевых, и может быть следующим.
1. Выбираем начальное состояние
.
1
bb
i
Это означает
истинность соответствующей ему формулы, которую будем
обозначать
.
i
В нашем случае
.
1 плк
xxx
2. Выбираем одно из действий
,
j
с
допустимых в состоянии
,
i
b
и соответствующую ему логическую переменную
,
j
z
например,
1
c
и
.
1
z
3. Полагаем, что формула
ji
z
истинна (среда находится
в состоянии
i
и совершает действие
j
c
).
4. Находим по таблице любую импликацию
,
kji
z
левой
частью которой является формула
ji
z
. (При
,
1
i
1
zz
j
и
111
zxxxz
плк
такой импликацией может быть например,
плкплк
xxxzxxx
1
).
5. Применяем правило модус поненс
kkjiji
zz
,
к
истинным формулам
,,
kjiji
zz
заключая согласно этому
правилу, что формула
k
истинна. (При
1
i
и
1
zz
j
,
плк1
xxx
k
т. е. в этом случае среда переходит из
состояния
1
b
снова в состояние
1
b
в результате действия
1
c
).
6. Проверяем, не является ли состояние
k
b
,
соответствующее формуле
k
, целевым. Если оно целевое и
последнее из всех, которые надо найти, то на этом поиск
завершается. В противном случае, поиск следует продолжить,
возвращаясь к п. 2 и начиная с состояния
k
b
(в п. 2
состояние
i
b
принимается равным
k
b
) или возвращаясь к
какому-либо состоянию, которое было достигнуто, но переходы
из которых еще не были рассмотрены.
Рассмотрим процедуру поиска решения для среды кота, в
результате которой будет найдена последовательность
действий, ведущая в целевое состояние
,
8
b
которое
представляется формулой
плк
xxx
. Эту процедуру
представим в виде таблицы 6, в первом столбце которой
запишем название и само правило вывода в общем виде из
числа описанных ранее, а во втором - результат его
применения.
Таблица 6
Исключение конъюнкта
in
21
3321
zzzz
Введение конъюнкта
33
, zxxxzxxx
плкплк
29
nn
2121
,,,
Модус поненс
,
плкплк
плкплк
,
xxxxxx
zxxxzxxx
33
Исключение конъюнкта
in
21
2321
zzzz
Введение конъюнкта
nn
2121
,,,
22
, zxxxzxxx
плкплк
Модус поненс
,
плкплк
плкплк
,
xxxxxx
zxxxzxxx
22
Модус поненс
,
плкплк
плкплк
,
xxxxxx
zxxxzxxx
33
Таким образом, для примера со средой кота был
осуществлен вывод формулы
плк
xxx
из исходных истинных
формул
плк
xxx
,
321
zzz
,
,
321
zzz
3
zxxx
плк
плк
xxx
,
2
zxxx
плк
плк
xxx
,
3
zxxx
плк
плк
xxx
,
что можно записать в виде выражения
плк
xxx
,
321
zzz
,
,
321
zzz
3
zxxx
плк
плк
xxx
,
2
zxxx
плк
плк
xxx
,
3
zxxx
плк
плк
xxx
плк
xxx
.
Приведенная задача со средой кота очень проста. В
реальных задачах число переменных, которые представляют
состояния среды, может быть гораздо большим, что сделает
практически нереальным представления состояний
конституентами. Выходом из этого положения может быть
интервальное представление состояний среды.
30