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

66
Гл. 1. Методы представления знаний
ций языка L
2
(обозначатся L
1 6
L
2
). Если L
1 6
L
2
и L
2 6
L
1
, тогда
L
1
≡ L
2
Важно заметить, что на основании представленной семантики кон- структов дескриптивных логик можно сделать вывод о том, что одни конструкты можно выразить через другие. Например, для того чтобы использовать отрицание, можно ограничиться только отрицанием кон- цепта (⌉A). Конструкт C может быть выражен в языке ALEU. Так же и ALC выражает конструкты E и U. Таким образом, ALEU есть тот же язык по свойствам выразительности и вычислимости, что и ALC (как и ALCEU).
Заметим здесь, что классификация языков по выразительности не соответствует классификации языков по сложности вычислений. Языки дескриптивных логик, имеющие одинаковую вычислительную слож- ность обладают разной выразительностью:
• языки AL и ALN принадлежат классу сложности, полиномиаль- ному по времени. При этом AL < ALN;
• языки ALE, ALR, ALER ALN принадлежат классу NP, при этом
ALE
< ALR < ALER;
• сложность вычислений для ALU, ALUN соответствует coNP, но при этом ALU < ALUN;
• языки ALC, ALUR, ALNR, ALCN, ALCR, ALEN, ALENR, ALUNR,
ALCNR по сложности вычислений принадлежат классу PSPACE,
в то время, как ALCNR имеет наиболее высокую выразитель- ность.
Утверждение 1.6.5. Пусть L — язык дескриптивной логики, по-
лученный из языка AL добавлением непустого набора конструктов
дескриптивной логики
U , C, E, R, N . Тогда AL < L.
1.6.5. Отображение дескриптивной логики в логику первого
порядка. Практически все выражения классической DL, построенные в языке AL, отображаются в формулы логики предикатов первого порядка со свободными переменными. Рассмотрим следующее отобра- жение [18]:
если
(·)
τ
и
(·)
σ
отображения ролей и концептов, соответственно,
в язык логики первого порядка, то:
A
τ x
= Ax
P
σxy
= P xy
T
τ x
= (x = x)
⊥
τ x
= (x 6= x)
(C ⊓ D)
τ x
= C
τ x
∧ D
τ x
(C ⊔ D)
τ x
= C
τ x
∨ D
τ x
(⌉C)
τ x
=⌉C
τ x
(∀P. C)
τ x
= ∀y(P
σxy
→ C
τ y
)

1.6. Элементы дескриптивной логики
67
(∃P. C)
τ x
= ∃y(P
σxy
∧ C
τ y
)
(> nP )
τ x
= ∃y
1
...y n
( ∧
i6=j y
i
6= y j
∧ ∧
i
P
σxyi
)
(6 nP )
τ x
= ∃y
1
...y n+1
i6=j
(∧y i
6= y j
→ ∨⌉
i
P
σxyi
)
(P ⊓ Q)
σxy
= P
σxy
∧ Q
σxy
Таким образом, формулы языка исчисления предикатов первого порядка имеют значительно более громоздкий вид, нежели соответ- ствующие им формулы дескриптивой логики.
1.6.6. Дескриптивная логика с конкретным доменом. Во мно- гих приложениях возникает необходимость при определении концептов использовать конкретные домены и соответствующие предикаты.
Примером такого рода может служить множество неотрицательных целых чисел с предикатными символами > (больше или равно) или
< (меньше). Предположим, что надо дать адекватное определение концепту ЖЕНЩИНА. Первая идея такого определения следующая:
ЖЕНЩИНА≡ ЧЕЛОВЕК ⊓ ЖЕНСКИЙ ПОЛ. Однако новорожденно- го ребенка женского пола (как и, например, трехлетнего возраста) вряд ли уместно назвать так. Таким образом, требуется указать некоторые дополнительные свойства, в частности, достаточный для этого возраст,
(например, не менее 18 лет), т. е. требуется ввести новую функцио- нальную роль ИМЕТЬ ВОЗРАСТ и определить концепт ЖЕНЩИНА
следующим образом: ЧЕЛОВЕК ⊓ ЖЕНСКИЙ ПОЛ ⊓ ИМЕТЬ ВОЗ-
РАСТ. >
18
. Здесь >
18
обозначает одноместный предикатный символ,
который интерпретируется как множество {n|n > 18} неотрицательных целых б´ольших или равных восемнадцати. Такое представление делает возможным рассуждения в конкретных доменах. Например, мы можем ввести новый атомарный концепт ПО КРАЙНЕЙ МЕРЕ18 для выра- жения свойства «не менее 18 лет». Далее, если ввести концепт ПО
КРАЙНЕЙ МЕРЕ21, то можно ввести подходящее отношение погло- щения между ними. Но это ничего не даст для установления, напри- мер, невыполнимости выражения ПО КРАЙНЕЙ МЕРЕ18 ⊓ САМОЕ
БОЛЬШЕЕ16. Таким образом, следует ввести подходящую процедуру рассуждений об интервалах неотрицательных целых чисел.
Рассмотрим процедуру расширения языка дескриптивной логики,
следуя [24].
Определение 1.6.1. Конкретный домен D состоит из множества dom
D
домена D и множества pred
D
предикатных символов домена D.
D = dom
D
∪ pred
D
. Каждому предикатному символу P местности n соответствует отношение такой же местности P
D
⊆ (dom
D
)
n
Пример 1.6.1. Множество натуральных чисел NAT с предикатами
<, >, = есть конкретный домен.
3*

68
Гл. 1. Методы представления знаний
Вычисления с нормальными формами с отрицаниями в таком рас- ширенном языке требуют, чтобы множество предикатных символов конкретного домена было замкнуто относительно отрицания, т. е. ес- ли P — n-арный предикатный символ в pred
D
, то должен существовать предикатный символ Q, такой что Q
D
= (dom
D
)
n
\P
D
. В этом случае будем полагать, что Q = ¬P . В дополнение к этому нам потребуется унарный предикатный символ для обозначения (dom
D
)
n
. Понятно,
также, что ¬ <
n
=>
n
Выясним теперь, какого рода механизмы рассуждений требуются в конкретных доменах. Пусть P
1
, P
2
, ... , P
к
(не обязательно различ- ные) — предикатные символы в pred
D
с местностями n
1
, n
2
, ..., n к
соответственно.
Рассмотрим коньюнкцию
∧P
i
(x
(i)
)
(i = 1, 2, ..., n),
где каждое x
(i)
представляет некоторый кортеж переменных. Важно заметить, что все переменные как в одном кортеже, так и в различных,
различаются. Будем говорить, что такая конъюнкция выполняется, ес- ли и только если существуют такие значения элементов из D, что при их подстановках на места соответствующих переменных конъюнкция становится истинной.
Определение 1.6.2. Конкретный домен будем называть допусти- мым если и только если а) множество его предикатных символов замкнуто относительно отрицания и содержит предикатный символ ⊤
D
для (dom
D
)
n и б) задача выполнимости приведенной выше конъюнкции разрешима в D.
Рассмотрим пример. Пусть мы хотим описать множество всех тех женщин, чьи отцы и мужья имеют одинаковый возраст. Соответствую- щее выражение будет иметь следующий вид:
ЖЕНЩИНА ⊓ (ИМЕЕТ ОТЦА ◦ ИМЕЕТ ВОЗРАСТ = ИМЕЕТ
МУЖА ◦ ИМЕЕТ ВОЗРАСТ).
Однако, для выражения того, что муж старше отца, в языке без конкретного домена средства отсутствуют. Поэтому следует ввести конкретный домен N (с предикатным символом <) и записать:
ЖЕНЩИНА ⊓ (ИМЕЕТ ОТЦА ◦ ИМЕЕТ ВОЗРАСТ, ИМЕЕТ
МУЖА ◦ ИМЕЕТ ВОЗРАСТ). <.
Определение 1.6.3. Интерпретация I языка ALC с конкретным доменом (этот язык будем обозначать через ALC(D)) содержит мно- жество (dom
D
)
I
— интерпретацию абстрактного домена и функцию интерпретации. Абстрактный домен и заданный конкретный домен не должны пересекаться, т. е. (dom
D
)
I
∩ dom
D
= ∅. Как и ранее, функ-

1.6. Элементы дескриптивной логики
69
ция интерпретации каждому имени концепта ставит в соответствие некоторое подмножество (dom
D
)
I
и каждой обычной роли — бинарное отношение в (dom
D
)
I
. Новым является то обстоятельство, что функ- циональная роль интерпретируется теперь как частичная функция из
(dom
D
)
I
в (dom
D
) × dom
D
. В качестве примера приведем определения прямоугольника и квадрата:
ПРЯМОУГОЛЬНИК = ∃(x, y, b, h). УСЛОВИЯ ПРЯМОУГОЛЬ-
НИКА,
КВАДРАТ = ПРЯМОУГОЛЬНИК ⊓ ∃(b, h). ЭКВИВАЛЕНТНЫ.
Здесь конкретные предикатные символы УСЛОВИЯ ПРЯМО-
УГОЛЬНИКА
и
ЭКВИВАЛЕНТНЫ
определяются следующим образом: ЭКВИВАЛЕНТНЫ (x, y) ↔ x = y, а УСЛОВИЯ ПРЯМО-
УГОЛЬНИКА (x, y, b, h) ↔ b > 0 и h > 0.
В заключение главы приведем сводку правил вывода в дескриптив- ной логике с конкретным доменом.
1.6.7. Правила вывода. Правила вывода в дескриптивной логике с конкретным доменом применяются к парам F. G, где F — факты,
G — цели. Имеются два вида правил вывода:
F. G → {A} ∪ F. G if B is in F
F. G → F. G ∪ {A} if B is in G
В соответствии с первым правилом множество фактов F пополня- ется ограничением A в том случае, если при тестировании множества фактов F находятся примеры выражений, перечисленные после «if».
В соответствии со вторым правилом множество целей G пополня- ется ограничением A в том случае, если при тестировании множества целей G находятся примеры выражений, перечисленные после «if».
Символ «→» используется в качестве разделителя.
Система ограничений будет называться противоречивой, если со- держит выражение вида:
• {a : {b}}, где a 6= b,
• {sP a, sP b, s : A}, где A ⊑ (6 1P ) и a 6= b,
• {P
1
(k
(1)
), ..., P
n
(k
(n)
)}, где ∧
n i=1
P
i
(k
(i)
) ⊥,
• {s : ⊤, s : D}.
Выражение x : X обозначает, что переменная x присутствует в мно- жестве X.
В результате применения правил вывода к паре ограничений F. G
строится система ограничений F
′
. G
′
, которая исследуется на предмет наличия противоречий.

70
Гл. 1. Методы представления знаний
Противоречивая система ограничений свидетельствует о том, что рассматриваемая формула не является логическим следствием базы знаний.
Правила организованы в 5 групп в зависимости от структуры фор- мулы.
Теорема 1.6.1 [23]. Сложность вычислений в дескриптивной ло-
гике с конкретным доменом равна coNP.
В заключение приведем список правил вывода дескриптивных логик с конкретным доменом (таблицы 1.4–1.8).
Т а б л и ц а 1.4. Доменные правила
DO1: F. G → {s : ⊤} ∪ F. G if s: C is in F
DO2: F. G → {s : ⊤} ∪ F. G if sRt is in F
DO3: F. G → {k : D} ∪ F. G if sP
D
k is in F
DO4: F. G → {k
1
: D, ..., k n
: D} ∪ F. G if P (k
1
, ..., k n
) is in F
DO5: F. G → F. G ∪ {s : ⊤} if s: C is in G
DO6: F. G → F. G ∪ {s : ⊤} if sRt is in G
DO7: F. G → F. G ∪ {k : D} if sP
D
k is in G
DO8: F. G → F. G ∪ {k
1
: D, ..., k n
: D} if P (k
1
, ..., k n
) is in G
Т а б л и ц а 1.5. Правила декомпозиции
D1: F. G → {s : C; s : D} ∪ F. G if s : C ⊓ D is in F
D2: F. G → {sQt} ∪ F. G if tQ
−
s is in F
D3: F. G → (F. G)[y/a] if y : {a} is in F
D4: F. G → {spy} ∪ F. G if s : ∃p is in F
and there is not with spt in F and y is a fresh variable
D5 : F. G → {spy} ∪ F. G if s: ∃pε is in F
D6: F. G → {sQy; y : C; ypt} ∪ F. G if s(Q : C)pt is in F ,
and there is no t
′
such that sQt
′
, t
′
: C, t
′
pt are all in F ,
and p 6= ε, and y is a fresh variable
D7: F. G → {sQt; t : C} ∪ F. G if s(Q : C)t is in F
D8: F. G → (F : G)[k/P
I
D
(s)]
if sP
D
k is in F and k is a variable
D9: F. G → {sp
1
k
1
, ..., sp n
k n
, P (k
1
, ..., k n
)} ∪ F. G
if s : P (p
1
, ...p n
) is in F
and there are no k
′
i such that sp i
k
′
i and P (k
′
1
, ..., k
′
n
) are in F .
The k i
are fresh variables for concrete objects

1.6. Элементы дескриптивной логики
71
Т а б л и ц а 1.6. Правила схемы
S1: F. G → {s : A
2
} ∪ F. G if s : A
1
is in F and A
1
⊑ A
2
is in Σ
S2: F. G → {t : A
2
} ∪ F. G if s : A
1
and sP t are in F , and A
1
⊑ ∀P. A
2
is in Σ
S3: F. G → {s : A
1
, t : A
2
} ∪ F. G if sP t is in F , and P ⊑ A
1
× A
2
is in Σ
S4: F. G → (F : G)[y/t] if s : A, sP y, sP t are in F , and A ⊑ (6 1P ) is in Σ
S5: F. G → {sP y} ∪ F. G if s : ∃(P : C)p is in G or s : ∃(P : C)p = ε is in G,
or else s : P (p
1
, ..., p n
) is in G with p i
= (P : C)q,
and there is no t with sP t in F ,
and there is an A with s: A in F and A ⊑ ∃P in Σ,
and y is a fresh variable
S6: F. G → {sP
D
k} ∪ F. G if s : ∃P
D
is in G or s : P (..., P
D
, ...) is in G,
and there is no k with sP
D
k in F ,
and there is an A with s : A in F and A ⊑ ∃P
D
in Σ,
and k is a fresh variable
Т а б л и ц а 1.7. Целевые правила
G1: F. G → F. G ∪ {s : C; s : D} if s : C ⊓ D is in G
G2: F. G → F. G ∪ {t : C} if s : ∃(Q : C) is in G or s : ∃(Q : C) = ε is in G,
and sQt is in F
G3: F. G → F. G ∪ {t : C, t : ∃p} if s : ∃(Q : C)p is in G
or s : ∃(Q : C)p = ε is in G
or s : P (p
1
, ..., p n
) is in G with p i
= (Q : C)q and sQt is in F
Т а б л и ц а 1.8. Правила композиции
C1: F. G → {s : C ⊓ D} ∪ F. G if s : C, s : D is in G
C2: F. G → {s : ⊤} ∪ F. G if s : C is in G
C3: F. G → {s : ∃p} ∪ F. G if p = ε or there exist t with spt in F
and s : ∃p is in G
C4: F. G → {s : ∃p = ε} ∪ F. G if p = ε or sps is in F , and s : ∃p = ε is in G
C5: F. G → {s(Q : C)pt} ∪ F. G
there is a t
′
such that sQt
′
, t
′
: C, t
′
pt is in F , such that s : ∃(Q : C)p or s : ∃(Q : C)p = ε or s : P (..., (Q : C)p, ...) is in G
C6: F. G → {s(Q : C)t} ∪ F. G if sQt, t : C are in F , and s : ∃(Q : C) or s : ∃(Q : C) = ε is in G
D7: F. G → {s : P (p
1
, ..., p n
) s : P (p
1
, ..., p n
)} ∪ F. G
if there exist k i
i = 1...n (n > 1) with sp i
k i
in F
and s : P (p
1
, ..., p n
) is in G

Г л а в а 2
МЕТОДЫ АВТОМАТИЗАЦИИ РАССУЖДЕНИЙ
Введение
Во введении мы приведем краткую характеристику основных про- цедур рассуждений, таких как дедукция, индукция, аналогия, рассуж- дения на основе прецедентов, абдукция и аргументация. Затем более детально рассмотрим методы автоматизации некоторых из названных типов рассуждений в вычислительных системах.
Начнем с дедуктивных рассуждений.
Дедуктивное рассуждение — это последовательность дедуктив- ных умозаключений. Дедуктивным называют такое умозаключение,
в котором из знания большей степени общности выводится знание меньшей степени общности. Первые точные схемы дедуктивных умо- заключений принадлежат Аристотелю (384–322 гг. до нашей эры). Эти схемы носят название силлогизмов. К числу основных силлогизмов
Аристотеля относятся категорический силлогизм, условный силло-
гизм, разделительный силлогизм, условно-разделительный силло-
гизм; сокращенные, сложные и сложносокращенные силлогизмы или
энтимемы.
Каждый из силлогизмов имеет несколько разновидностей, отличаю- щихся друг от друга количеством и качеством посылок и называемых
модусами. Связано такое разделение с тем, что все суждения по своему качеству делятся на четыре вида: общеутвердительные, общео- трицательные, частноутвердительные и частноотрицательные.
Так, простой категорический силлогизм состоит из трех сужде- ний, два из которых выступают в качестве посылок, а одно — заклю- чение. Первая из посылок носит общеутвердительный характер, вторая посылка и заключение могут носить частноутвердительный характер.
Например, «Каждый студент должен владеть дедуктивным методом»,
«Сидоров — студент»; «Сидоров должен владеть дедуктивным мето- дом». Здесь до точки с запятой приведены посылки, а после точки с запятой — заключение силлогизма.

Введение
73
Существует определенный набор правил работы с силлогизмами,
определяющих корректность их применения. Можно считать, что имен- но с этими событиями связано возникновение науки под названием
логика.
С середины XIX в. (Дж. Буль, 1847, О. де Морган, 1858) появились первые работы по формализации аристотелевой логики. Г. Фреге (1848)
и Ч. Пирс (1885) ввели в логику предикатные переменные, предмет- ные переменные и кванторы. В ходе последовавших затем работ по применению логического подхода к изучению оснований математики был создан богатый логический аппарат и оформилась математическая научная дисциплина под названием математическая логика.
В классической математической логике основными правилами де- дуктивных рассуждений являются аксиомы и правила вывода.
Например, правило модус поненс (правило отделения):
если
A, B и C — формулы, то из выводимости A и B → C следует
выводимость
C;
или аксиомы:
(A → B) → (¬B → ¬A).
Дедуктивные рассуждения относят к числу достоверных рассужде-
ний.