Файл: Методыискусственногоинтеллекта.pdf

82
Гл. 2. Методы автоматизации рассуждений
2.1.3. Метод резолюций для исчисления предикатов первого
порядка. Как мы видели, наиболее существенным моментом в исполь- зовании метода резолюций является нахождение в дизъюнкте литеры,
контрарной литере в некотором другом дизъюнкте. Если в исчислении высказываний это достаточно просто, то в исчислении предикатов,
когда мы имеем дело с формулами, содержащими индивидные пере- менные, ситуация усложняется. Рассмотрим, например, дизъюнкты:
C
1
: P (x) ∨ Q(x),
C
2
: ¬P (f (x)) ∨ R(x).
В C
1
не существует литеры, контрарной какой-либо литере из C
2
Однако вспоминая, что все переменные в формулах P (x) и Q(x) имеют универсальную квантификацию, и подставляя f(x) в C
1
вместо x,
получим
C
1
: P (f (x)) ∨ Q(f (x)),
C
2
: ¬P (f (x)) ∨ R(x).
Эти два дизъюнкта уже легко резольвировать; получим
Q(f (x)) ∨ R(x).
Если в C
1
и C
2
подставлять на места переменных другие подходящие термы, можно получать новые резольвенты C. Например, подставив a вместо x в C
2
и f(a) вместо x в C
1
, получим резольвенту
Q(f (a)) ∨ R(a).
Таким образом, резольвента
Q(f (x)) ∨ R(x)
является, в некотором смысле, наиболее общей по отношению ко всем другим, так как все иные резольвенты (в частности, предыдущая)
являются ее примерами.
Из сказанного видно, что получение резольвент из дизъюнктов часто требует подстановок.
Определение 2.1.5. Подстановка — это конечное множество вида
{t
1
/v
1
, ..., t n
/v n
}, где каждая v i
— переменная, а каждый t i
— терм,
отличный от v i
, и все v i
различны. Подстановка, которая не содержит элементов, называется пустой и обозначается ε.
Определение 2.1.6. Пусть θ = {t
1
/v
1
, ..., t n
/v n
} — подстановка и E — выражение. Тогда Eθ — выражение, полученное из E одновре- менной заменой всех вхождений переменной v i
на терм t i
Eθ называют примером E.

2.1. Автоматизация дедуктивных рассуждений
83
Определение 2.1.7. Подстановка θ называется унификатором для множества {e
1
, e
2
, ..., e k
} тогда и только тогда, кода e
1
θ = e
2
θ = ... =
= e k
θ. Если для множества E существует унификатор, то оно называ- ется унифицируемым.
Определение 2.1.8. Унификатор σ для множества {e
1
, e
2
, ..., e k
}
будет наиболее общим унификатором тогда и только тогда, когда для каждого унификатора θ этого множества найдется такая подстановка λ,
что θ = σλ.
Пример 2.1.3. Множество {P (a, y), P (x, f(b))} унифицируемо, так как подстановка θ = {a/x, f(b)/y} является его унификатором.
Таким образом, ключевой задачей метода резолюций для исчисле- ния предикатов первого порядка является нахождение наиболее общего унификатора. Прежде чем переходить к изложению общего алгоритма ее решения, дадим определение множества рассогласований.
Определение 2.1.9. Множество рассогласований непустого мно- жества выражений W есть такое множество подвыражений, которые начинаются с различающихся символов, находящихся в одних и тех же позициях в выражениях из W .
Пример 2.1.4. Если W = {P (x, f(y, z)), P (x, a), P (x, g(h(k(x))))},
то первой позицией, в которой появляются различные символы, явля- ется пятая (символы «P », «(», «x», «,» первых четырех позиций во всех выражениях из W совпадают); таким образом, множеством рассогла- сований будет являться множество W = {f(y, z), a, g(h(k(x)))}.
Перейдем теперь к алгоритму унификации.
Алгоритм унификации:
Шаг 1. Положим k = 0, W
k
= W и σ
k
= ε.
Шаг 2. Если W
k
— единичный дизъюнкт, то σ
k
— наиболее общий унификатор для W . В противном случае — поиск множества D
k рассогласований для W
k
Шаг 3. Если существуют такие элементы v k
и t k
в D
k
, что v k
—
переменная, не входящая в t k
, то перейти к п. 4. Иначе W не унифицируемо.
Шаг 4. Пусть σ
k+1
= σ
k
{t k
/v k
}, тогда W
k+1
= W
k
{t k
/v k
}.
Шаг 5. k := k + 1; перейти к п. 2.
Приведем некоторые примеры применения унификации.
Пример 2.1.5. Пусть W = {Q(f(a), g(x)), Q(y, y)}.
1. Положим σ
0
= ε и W
0
= W ;
2. Множеством рассогласований для W
0
является D
0
= {f (a), y},
т. е. v
0
= y и t
0
= f (a);

84
Гл. 2. Методы автоматизации рассуждений
3. Тогда σ
1
= σ
0
{t
0
/v
0
} = ε{f (a)/y} = {f (a)/y};
4. W
1
= W
0
{t
0
/v
0
} = {Q(f (a), g(x), Q(y, y)}{f (a)/y} =
= {Q(f (a), g(x), Q(f (a), f (a))};
5. Множеством рассогласований для W
1
является D
1
= {g(x), f (a)};
6. Так как подстановки, исключающей последнее рассогласование,
не существует, то множество W не унифицируемо.
Пример 2.1.6. Пусть W = {P (x, f(y)), P (a, u)}. На первом про- ходе алгоритма будет найдена подстановка σ
1
= a/x, так как мно- жество рассогласований D
0
= {x, a}. Множество W
1
будет равно
{P (a, f (y)), P (a, u)}. На втором проходе алгоритма подстановка будет расширена до σ
2
= {a/x, f (y)/u)} и W
2
= {P (a, f (y))}. Так как W
2
состоит из одного литерала, то алгоритм закончит работу и выдаст s
2
Пример 2.1.7. Пусть W = {P (x, f(y)), P (a, b)}. На первом проходе алгоритма будет найдена подстановка σ
1
= a/x и W
1
= {P (a, f (y)),
P (a, b)}. На третьем шаге второго прохода будет выдано сообщение о том, что множество W неунифицируемо, так как множество рассо- гласования D
1
= {f (y), b} не содержит переменной.
Отметим, что при выполнении шага 4 из множества W
k удаляется одна из переменных (переменная v k
), а никакой новой переменной не возникает. Это означает, что алгоритм унификации всегда заканчивает работу. Ясно также, что если алгоритм заканчивает работу на шаге 3,
то множество M неунифицируемое. Также понятно, что если алгоритм заканчивает работу на шаге 2, то σ
k
— унификатор множества W .
Таким образом, возвращаясь, собственно, к методу резолюций,
получаем следующую схему применения метода в случае исчисления предикатов первого порядка:
1. Взятие отрицания целевой формулы.
2. Приведение множества формул к сколемовской нормальной фор- ме.
3. Нахождение унифицирующих подстановок и унификация множе- ства дизъюнктов.
4. Резольвирование множества дизъюнктов и нахождение пустого дизъюнкта (если таковой существует).
Примеры
В заключение параграфа рассмотрим несколько примеров приме- нения метода резолюций в исчислении высказываний и в исчислении предикатов.

2.1. Примеры
85
Пример 2.1.8. Даны 4 утверждения:
P → S,
S → U ,
P ,
U.
Преобразуем все утверждения в стандартную форму:
(1) ¬P ∨ S,
(2) ¬S ∨ U ,
(3) P ,
(4) U.
Докажем путем опровержения, что U — логическое следствие из
(1), (2) и (3). Отрицаем (4) и получаем
(1) ¬P ∨ S,
(2) ¬S ∨ U ,
(3) P ,
(4) ¬ U
отрицание заключения,
(5) S
резольвента (3) и (1),
(6) U
резольвента (5) и (2),
(7)
резольвента (6) и (4).
Пример 2.1.9. Дано множество формул:
F
1
: (∀x) C(x) → (W (x) ∧ R(x))

,
F
2
: (∃x)(C(x) ∧ O(x)),
G : (∃x)(O(x) ∧ R(x)).
Доказать, что G является логическим следствием F
1
и F
2
. Преобра- зуем F
1
, F
2
и ∼ G в стандартную форму и получим следующие пять дизьюнктов:
(1) C(x) ∨ W (x),
(2) C(x) ∨ R(x) из F
1
,
(3) C(a),
(4) O(a) из F
2
,
(5) ¬O(x) ∨ ¬R(x) из ¬G.

86
Гл. 2. Методы автоматизации рассуждений
Это множество дизьюнктов невыполнимо. Докажем при помощи метода резолюций:
(6) R(a)
резольвента (3) и (2),
(7) ¬R(a) резольвента (5) и (4),
(8)
резольвента (7) и (6).
Таким образом, G — логическое следствие F
1
и F
2
Пример 2.1.10.
Дано множество формул:
F
1
: (∃x) P (x) ∧ (∀y)(D(y) → L(x, y))

,
F
2
: (∀x) P (x) → (∀y)(Q(y) → ¬L(x, y))

,
G : (∀x) D(x) → ¬Q(x))

Преобразуем F
1
, F
2
и ∼ G в следующие дизъюнкты:
(1) P (a),
(2) ¬D(y) ∨ L(a, y) из F
1
,
(3) ¬P (x) ∨ ¬Q(y) ∨ ¬L(x, y) из F
2
,
(4) D(b)
(5) Q(b) из ¬G.
Используя метод резолюций, получим
(6) L(a, b)
резольвента (4) и (2),
(7) ¬Q(y) ∨ ¬L(a, y)
резольвента (3) и (1),
(8) ¬L(a, b)
резольвента (5) и (7),
(8)
резольвента (6) и (8).
2.2. Индуктивные рассуждения
2.2.1. Понятие квазиаксиоматической теории.
Прежде чем рассматривать собственно индуктивные рассуждения, охарактеризуем в целом тот класс рассуждений, к которому можно отнести индуктив- ные рассуждения.
Прежде всего, заметим, что хотя индуктивные рассуждения явля- ются правдоподобными, т. е. не являются достоверными, они не долж- ны быть тривиально недостоверными, например, не должны использо- вать некорректные правила вывода типа
A, A → B ⇒ B → A.

2.2. Индуктивные рассуждения
87
Далее, для них характерна контекстная зависимость от условий при- менения посылок; следующей их характеристикой является неполнота информации, часто приводящая к использованию посылок с неопреде- ленным истинностным значением. Это последнее обстоятельство озна- чает, в частности, многозначность используемой для формализации подобных рассуждений логики.
Неполнота информации связана с открытостью предметной области или, как принято иногда говорить, с открытостью мира. Это озна- чает, что в этом случае мы имеем дело с открытостью множества утверждений, представляющих систему знаний о предметной области и используемых в качестве посылок в выводах.
Логическим уточнением понятия открытого мира является понятие квазиаксиоматической теории, введенное В. К. Финном [28].
Квазиаксиматическая теория K = hΣ, Σ
′
, Ri, где Σ — некоторое множество аксиом предметной области, не полностью ее харатеризую- щее; Σ
′
— множество фактов предметной области или гипотез; R —
множество правил вывода (как достоверного, так и правдоподобного).
Пусть K
n
— состояние квазиаксиоматической теории, полученное в результате n последовательных применений правил правдоподобного вывода из R, K
n
= hΣ
n
, Σ
′
n
, Ri, а K
0
— начальное состояние, тогда пара hΣ, Σ
′
i , где Σ =
n
S
0
Σ
n и Σ
′
=
n
S
0
Σ
′
n
, соответствует n-му состоянию базы знаний.
Последовательность состояний K
0
, K
1
, ..., K
n квазиаксиоматиче- ской теории K, где K
0
— начальное состояние, K
n
— заключи- тельное состояние, такое, что применение правил правдоподобно- го вывода к K
n порождает K
n+1
, причем K
n+1
= K
n
, называется p-рассуждением. Применение правил достоверного вывода из R к ре- зультатам p-рассуждения называется pr-рассуждением.
Если из того, что Ф выводима из Г, где Г — некоторое множество формул, следует, что Ф выводима из Г и Ψ, где Ψ — формула, то вывод называется монотонным. В противном случае, вывод называется немонотонным.
Рассмотрим правило индуктивного вывода A(a
1
), ..., A(a n
) ⇒
⇒ ∀xA(x), введенное в 2.1.2. Если элементы a
1
, ..., a n
не исчерпыва- ют U, то новый индивид a n+1
∈ U может не обладать свойством A и заключение ∀xA(x) оказывается несправедливым. Это означает, что
∀xA(x) не выводится из A(a
1
), ..., A(a n
) и B(a n+1
) (где B — какое либо свойство a n+1
), т. е. индуктивный вывод не является монотонным.
2.2.2. Немонотонные рассуждения. Формализацией немонотон- ных рассуждений являются немонотонные логики. Здесь мы кратко рассмотрим, следуя [29], одну из них — немонотонную модальную логику, предложенную Мак-Дермоттом.

88
Гл. 2. Методы автоматизации рассуждений
В логике Мак-Дермотта рассматриваются формулы вида p, ¬p и
M p (p доказуема, p опровержима и p возможна соответственно).
Опишем язык немонотонной модальной логики первого порядка.
Введем вначале алфавит языка Λ. Алфавит включает:
1. Счетное множество букв: z, y, x, ..., которое будем называть мно- жеством символов для обозначения переменных языка;
2. Счетное множество букв a, b, c, ..., которое будем называть мно- жеством символов для обозначения констант языка;
3. Счетное множество прописных букв P , Q, ... для обозначения предикатных символов языка;
4. Счетное множество строчных букв f, g, ... для обозначения функ- циональных символов;
5. Символы для логических связок → (влечет), ¬(не);
6. Символ для квантора ∀ (для любого);
7. Символ модального оператора L (необходимо);
8. ( , ) — скобки.
Предикатные буквы P , Q, ... и функциональные буквы f, g, ... могут быть n-местными или, как еще говорят, n-арными. Иначе говоря,
с каждым предикатным или функциональным символом будем связы- вать некоторое натуральное число, равное числу его аргументов.
Здесь следует заметить, что присутствующие в языке модальные операторы необходимости (L) и возможности (M ) являются аналогами соответстствующих операторов в модальных системах и, следователь- но, допускают аналогичную интерпретацию, например, в множествах возможных миров.
Определим теперь понятие формулы или правильно построенного выражения языка Λ.
Формулы языка
Λ определяются индуктивным образом. Начнем с определения терма языка:
1. Переменная есть терм.
2. Константа есть терм.
3. Если t
1
, t
2
, ..., t m
, ..., t n
— термы, а f и g — функциональные символы арности m и n, соответственно, то f(t
1
, t
2
, ..., t m
) и g(t
1
, t
2
, ... , t n
) также термы.
4. Если t
1
, t
2
, ..., t m
, ..., t n
— термы, а P и Q — предикатные символы арности m и n, соответственно, то P (t
1
, t
2
, ..., t m
) и
Q(t
1
, t
2
, ... , t n
) — атомарные формулы.
5. Атомарная формула есть формула.
6. Если p, q — формулы, то p → q, ¬p, ¬q — формулы.
7. Если p — формула, то ∀xp — формула.
8. Если p — формула, Lp — формула.

2.2. Индуктивные рассуждения
89 9. Всякое слово в алфавите языка является формулой тогда и только тогда, когда это можно показать с помощью конечного числа применений пп. 1–8.
Определим, кроме того, модальность возможности, введя модаль- ный оператор M : M p = ¬L¬p.
Схемы аксиом включают:
1. Схемы классических аксиом:
А) p → (q → p).
Б) (p → (q → r)) → ((p → q) → (p → r)).
В) (¬q → ¬p) → ((¬q → p) → q).
Г) ∀x p(x) → p(t/x), где t — терм без связанных переменных.
Д) ∀x(p → q) → (p → ∀xq), где x не входит в p.
2. Схемы модальных аксиом:
а) Lp → p.
б) L(p → q) → (Lp → Lq).
в) ∀x Lp → L∀xp.
г) Lp → LLp.
д) ¬Lp → L¬Lp.
3. Правила вывода:
а) p, p → q), +q.
б) p ⊢ ∀xp.
в) p ⊢ Lp.
г) ⊣ (¬p) ⊢ M p (где знак ⊣ читается «невыводимо»).
Последнее правило и есть основное правило немонтонного вывода,
так как позволяет присваивать статус возможности формуле, отрица- ние которой не является выводимым. С точки зрения классической математической логики статус возможности соответствует понятию выполнимости.
С другой стороны, если по этому правилу выведено M p или фор- мула q выводима из M p и если в системе появился новый факт, поз- воляющий вывести ¬p, формулу q следует отвергнуть. Таким образом,
именно это правило придает рассматриваемой системе немонотонный характер. Как уже было замечено выше и как следует из приведенных соображений, к немонотонным относятся и индуктивные рассуждения,
один из видов которых рассматривается ниже.
2.2.3. ДСМ — метод индуктивного вывода. Индуктивные рас- суждения, или рассуждения на основе индукции, оказываются по- лезными при решении ряда задач, среди которых — обнаружение

90
Гл. 2. Методы автоматизации рассуждений
закономерностей в массивах данных, восстановление вида функции по ее примерам, восстановление грамматики неизвестного языка по множеству его текстов и другие.
Индуктивные рассуждения можно рассматривать как инструмент для порождения гипотез. При этом порождаемые гипотезы не обязаны быть достоверными и требуют дальнейшего анализа, результатом кото- рого должно явиться их обоснование (либо опровержение). Но это —
задача других методов, один из которых — рассуждения на основе аргументации — будет рассмотрен в следующем параграфе, а пока займемся изучением индуктивного метода порождения гипотез в том виде, в каком его предложил В. К. Финн [30].
Идея метода восходит к 1900 г. Она была предложена в начале
XX в. английским логиком и философом Джоном Стюартом Милем.
Эта идея такова: пусть задано множество структур типа объект–свой- ство. Пусть задача состоит в том, что для некоторого нового объекта требуется установить его неизвестное свойство. В основе подхода ле- жит предположение о том, что за каждое свойство объекта отвечает некоторая его составная часть или фрагмент. Поэтому на первом эта- пе для заданного свойства выполняется поиск фрагментов объектов,
«ответственных» за это свойство. Для этого анализируются структуры объектов и выполняется поиск объектов, имеющих совпадающие свой- ства и структурное сходство. Полагается, что именно общие фрагменты объектов, обладающих совпадающими свойствами, являются причи- ной этих свойств. Затем выполняется поиск такого рода фрагментов в новых объектах и, если такие фрагменты обнаружены, объектам приписываются свойства, причинами которых являются обнаруженные фрагменты. В простейшем случае полагается, что свойства, за которые ответственны те или иные фрагменты, порождаются только этими фрагментами и никак не зависят от окружения или контекста. Иначе говоря, предполагается, что свойства целого сводятся к сумме свойств его частей. Метод, основанный на указанных соображениях, был на- зван ДСМ-методом. Здесь мы изложим формализацию ДСМ-метода,
предложенную в [31]. Опишем вначале кратко его схему.
Итак, пусть O — множество объектов; P — множество свойств этих объектов; C — множество возможных причин свойств из P ; V —
множество оценок. Каждый из элементов множеств O, P , C также является множеством, а V = {+1, −1, 0, τ}.
Определим далее отображение F : P × O → V , так что f(p j
, o i
) =
= f ij
, где F
ij
∈ V .
Полагаем f(p, o) = +1, если достоверно известно, что объект o обладает свойством p; f(p, o) = −1 означает, что гипотеза «объект o обладает свойством p» опровергается (имеются только аргументы «про- тив» и ни одного аргумента «за»). Если f(p, o) = 0, то это означает