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

28
Гл. 1. Методы представления знаний
в этом случае называется выводимой формулой (или теоремой) фор- мальной системы F .
1.1.4. Алгебраические системы. Введем теперь некоторые алгеб- раические понятия, которые окажутся полезными в дальнейшем.
Определение 1.1.4. n-арным отношением R на M называется подмножество M
n
; записывается так: R ⊆ M
n
Пусть задано непустое множество — универсум M .
Упорядоченную тройку S = hM , G, Ri, где универсум M называется основным множеством, G — множество n-местных функций из M
n в M , а R — семейство n-арных отношений на M , будем называть алгебраической системой [7].
Если в определении алгебраической системы S положить R = ∅, то такая алгебраическая система называется алгеброй, а если G = ∅, то тогда алгебраическая система называется моделью.
Иногда удобнее использовать понятие многосортной или много-
основной алгебраической системы, полагая существование нескольких основных множеств M
1
, M
2
,..., M
n вместо одного множества M .
Тогда функции из G и отношения из R становятся многосортными,
т. е. с каждым местом в списке аргументов функции или отношения связывается некоторый сорт i, задаваемый, например, индексом одного из множеств из M
i
(i = 1, 2, ..., n), а сами функции и отношения опре- деляются на декартовых произведениях множеств из числа основных множеств.
1.1.5. Интерпретация.
Пусть заданы формальная система F
с языком L и универсум M . Зададим отображение I, которое всякому константному символу a языка L системы F ставит в соответствие некоторый элемент m ∈ M , всякому n-местному предикатному символу
P — n-местное отношение R ⊆ M
n
, а всякому m-местному функци- ональному символу f — m-местную функцию G: M
n
→ M . Тогда I
называется интерпретирующим отображением, а алгебраическая си- стема S = hM , G, Ri — моделью или интерпретацией формальной
системы
F . Элементы множества M , функции и отношения, соот- ветствующие константным, функциональным и предикатным символам языка L в смысле отображения I, называют иногда интерпретациями
константных, функциональных и предикатных символов языка L соот- ветственно.
При определенных обстоятельствах можно говорить и о моделях языка. Моделью языка L называется пара hM , Ii, где M и I — уже использовавшиеся только что универсум и интерпретирующее отобра- жение.
Заметим, что при данном универсуме M для символов языка L
существует много различных интерпретаций.

1.1. Формальные языки и формальные системы
29
1.1.6. Выполнимость и истинность. Рассмотрим теперь вопрос об истинности или ложности формул языка L в некотором возможном мире, в качестве которого будет выступать модель S.
В полной мере этот вопрос оказывается не таким уж простым.
Например, не существует регулярного метода, позволяющего по произвольной формуле языка L решать, истинна она или ложна в ал- гебраической системе hN, +, ∗, σ, 0i, где N — множество целых чисел,
+, ∗ и σ — операции сложения, умножения чисел и получения сле- дующего числа, соответственно; 0 — константа нуль (которую можно рассматривать как нульместную функцию). Заметим попутно, что эта алгебраическая система называется стандартной моделью арифметики.
Чтобы определить понятие «Предложение (формула) A истинно в модели S», мы должны вначале разбить S на меньшие части и решить этот вопрос для каждой из полученных частей. Если A имеет вид ¬B или B ∧ C, то ясно, что вначале надо решить вопрос об истиности B и C. С другой стороны, если A имеет вид ∀xB, то такое рассуждение не проходит, так как B может и не быть предложением,
поэтому бессмысленно спрашивать, истинно B в S или ложно. На самом деле, предполагается, что значения всякой свободной в фор- муле B переменной пробегают множество M . Поэтому имеет смысл вопрос: является ли формула B истинной в модели S, если значением свободной переменной является m? Если для каждого m из M ответ на этот вопрос окажется утвердительным, то можно говорить, что A
истинно в S. Если же в M найдется элемент m, для которого ответ будет отрицательным, то будем говорить, что A ложно в S. Однако если B имеет вид ∀yC, придется вновь преодолевать те же трудности.
Поэтому определение истинности формул в модели является индук- тивной процедурой, основанной на индуктивном определении формулы языка L из п. 1.1.1.
Напомним, что интерпретирующее отображение I всякому кон- стантному символу a языка L ставит в соответствие некоторый элемент m ∈ M , всякому n-местному предикатному символу P — n-местное отношение R ⊆ M
n
, а всякому n-местному функциональному символу f — n-местную функцию G: M
n
→ M ; иначе говоря,
I(a) = m,
I(P ) = R
и I(f) = G,
соответственно.
Итак, пусть P — n-местный предикатный символ, x
1
, x
2
, ..., x n
—
свободные переменные. Будем говорить, что:
(i) атомарная формула P (x
1
, x
2
, ..., x n
) выполняется в модели Ω,
если найдется подстановка a
1
/x
1
, a
2
/x
2
,..., a n
/x n
, где a
1
, a
2
,..., a n
—
константы, такая что (I(a
1
), I(a
2
), ..., I(a n
)) ∈ I(P );
(ii) формула ∀x
1
∀x
2
... ∀x n
P (x
1
, x
2
, ..., x n
) истинна в модели Ω если формула P (x
1
, x
2
, ..., x n
) выполняется на любой n-ке a
1
, a
2
, ..., a n
;

30
Гл. 1. Методы представления знаний
(iii) формула ¬A истинна в модели Ω, если A — ложна;
(iv) формула A → B истинна в модели Ω, если A — истинна и B —
истинна, либо A — ложна и B — ложна, либо A — ложна, а B —
истинна (в модели Ω);
(v) формула может быть истинной только в силу пп. (i)–(iv).
В случае, когда A не истинна в Ω, мы говорим, что A ложна в Ω или что Ω — модель предложения ¬A. Если дано множество предложений
Σ такое, что Ω является моделью каждого из предложений σ ∈ Σ, то
Ω — модель этого множества.
Предложение, истинное в каждой модели языка L, называется ис- тинным.
Рассмотрим простой пример. Пусть в языке L определен трехмест- ный предикатный символ «СЕМЬЯ». Интерпретирующее отображе- ние I таково, что ставит в соответствие этому предикатному символу трехместное отношение «СЕМЬЯ», т. е. I(«СЕМЬЯ») = «СЕМЬЯ». По- скольку это отношение конечно, то можно задать его в виде таблицы,
каждая строка которой содержит имена членов одной семьи.
Т а б л и ц а 1.1
Мать
Отец
Ребенок
Аня
Петя
Вася
Галя
Женя
Коля
Тогда модель включает универсум M , состоящий из имен членов всех семей и трехместное отношение «СЕМЬЯ». Если мы желаем узнать что-либо о выполнимости формулы «СЕМЬЯ»(x, y, z) в по- строенной таким образом модели, то, рассматривая различные наборы значений (из универсума M ) переменных x, y, z, увидим, что в таблице имеется, например, строка (Аня, Петя, Вася) и отсутствует строка
(Аня, Петя, Коля). Это означает, что формула «СЕМЬЯ»(x, y, z) выпол- нима в построенной модели, а именно, выполняется на тройках (Аня,
Петя, Вася) и (Галя, Женя, Коля) и не выполняется, например, на тройке (Аня, Петя, Коля).
Отсюда следует, в частности, что предложение
∀x ∀y ∀z«СЕМЬЯ»(x, y, z)
ложно, а, к примеру, предложение
∃x∃y∃z«СЕМЬЯ»(x, y, z)
истинно в построенной модели,
Завершая этот раздел, вспомним о том, что язык L — язык исчис- ления предикатов первого порядка и на нем записаны аксиомы этого

1.2. Системы, основанные на правилах, или продукционные системы
31
исчисления (п. 1.1.2), а для формул этого языка определены правила вывода и на них распространяется понятие выводимости из п. 1.1.3.
Одно из основных утверждений, устанавливающих тесную связь между понятиями выводимости в исчислении предикатов первого порядка и истинности, приведено ниже.

32
Гл. 1. Методы представления знаний
систем, основанных на правилах, хорошо согласуются с эволюционным характером разработки больших программных систем, предполагаю- щих использование значительных объемов знаний.
Перейдем теперь к более детальному изложению основных идей систем, основанных на правилах, следуя, главным образом, рабо- там [8, 9].
1.2.1. Правила для представления знаний.
Определение 1.2.1. Правилом называется упорядоченная тройка множеств П = hC, A, Di, где C — условие правила; A — множество добавляемых правилом фактов; D — множество удаляемых правилом фактов.
Как и было обещано в начале главы, для записи элементов ос- новных конструкций языка представления знаний (в данном случае,
языка правил), т. е. условия C правила П, множеств A и D будем (хотя это не обязательно) использовать язык исчисления предикатов первого порядка. А именно, будем полагать, что множества C, A и D суть множества атомарных формул языка исчисления предикатов первого порядка.
Напомним здесь, что в п. 1.1.1 фактами были названы атомарные формулы исчисления предикатов первого порядка без свободных пере- менных.
Что касается правил, то в них атомарные формулы со свободными переменными из множеств C, A и D превращаются в факты в про- цессе применения правил, т. е. в результате выполнения соответству- ющих подстановок (m
1
, m
2
, ..., m n
) на места свободных переменных
(x
1
, x
2
, ..., x n
) и проверки для каждой формулы P (x
1
, x
2
, ..., x n
) из C
выполнения условия (m
1
, m
2
, ..., m n
) ∈ I(P ), т. е. выполнимости в те- кущем состоянии рабочей памяти.
Определение 1.2.2. Будем говорить, что условие правила выпол-
нено, если в текущем состоянии рабочей памяти выполняется каждая из атомарных формул условия.
Определение 1.2.3. Правило применимо к состоянию рабочей па- мяти, если его условие выполнено в этом состоянии.
1.2.2. Рабочая память. Рабочая память должна быть согласо-
вана с множеством правил. Согласование выполняется следующим образом: пусть П — некоторое множество правил; C, A и D —
объединения условий, множеств добавляемых фактов и множеств уда- ляемых фактов по всему множеству П. M — множество индивидов предметной области. Тогда для каждой n-местной атомарной формулы
P (x, y, ..., z) ∈ C ∪ A ∪ D рабочая память должна содержать n-местное

1.2. Системы, основанные на правилах, или продукционные системы
33
конечное отношение I(P ) ⊆ M
n
, где I — интерпретирующее отобра- жение (рис. 1.1.)
Рис. 1.1. Стрелками показано отображение I; R
1
, R
2
, R
3
— отношения
Таким образом, рабочая память должна содержать множество ко- нечных отношений или таблиц, каждая из которых является интерпре- тацией одного из предикатных символов, входящего в объединенное множество условий, списка добавляемых или удаляемых фактов.
Заметим здесь, что правило можно рассматривать как действие или команду исполнительному органу, которая может разворачиваться в последовательность действий. Добавляемые и удаляемые правилом факты называются эффектом действия и выполняют модификацию
модели мира, т. е. формируют в рабочей памяти системы отражение тех изменений в мире, которые произошли после выполнения действий,
предписанных правилом.
Правила могут также рассматриваться как средство пополнения знаний о мире, например, в результате обучения.
1.2.3. Стратегии управления. Стратегия управления предназна- чена для организации процесса вычислений.
В самом общем виде ее можно описать следующим образом.
Шаг 1. Выбрать очередное правило из множества правил.
Шаг 2. Проверить выполнимость условия правила в текущем состоя- нии рабочей памяти.
Шаг 3. Если условие правила выполнено, поместить правило в кон- фликтное множество.
Шаг 4. Если множество применимых правил исчерпано, выбрать ка- кое-либо правило из конфликтного множества правил и приме- нить его.
Шаг 5. Перейти к шагу 1.
Условиями остановки являются пустое конфликтное множество,
либо достижение целевого состояния.
Приведенная стратегия порождает недетерминированный процесс,
поскольку она не устанавливает, каким образом следует выбирать правило из множества применимых правил.
2 Г. С. Осипов

34
Гл. 1. Методы представления знаний
В большинстве случаев информации, доступной стратегии управле- ния, недостаточно для точного решения задачи выбора. Поэтому работу систем, основанных на правилах, можно охарактеризовать как процесс
поиска, при котором правила подвергаются испытанию до тех пор,
пока не обнаружится, что некоторая их последовательность порож- дает состояние рабочей памяти, удовлетворяющее целевому условию.
При этом часто используются различные эвристики, сокращающие перебор. (Эвристикой будем называть правило выбора без достаточных теоретических оснований.) Вид эвристики обычно диктуется условия- ми задачи. Позже мы обсудим различные эвристики, а пока уточним,
что стоит за словами «Проверить выполнимость условия правила»
и «Применить правило».
В п. 1.2.2 было установлено соответствие между множеством ато- марных формул условий, множеством добавляемых и удаляемых фак- тов из правил и множеством отношений рабочей памяти.
Проверка выполнимости условия выбранного правила состоит в том,
что в каждую атомарную формулу P (x, y, ..., z) условия подставля- ются значения из текущего состояния рабочей памяти, а именно, из таблицы, соответствующей P (x, y, ..., z) в смысле отображения I. При этом обычно известно и соответствие столбцов таблицы I(P ) сортам аргументов формулы P (x, y, ..., z) (в многосортном языке).
Если существует подстановка σ = (m
1
, m
2
, ..., m n
), такая что σ ∈
∈I(P ), то формула условия P (x, y, ..., z) выполняется на этой подста- новке.
Если существуют подстановки σ
1
, σ
2
, ..., σ
k
, такие что на местах од- ноименных свободных переменных всех формул условия оказываются одинаковые значения и при этом все формулы условия оказываются выполнены, то условие правила выполнено в текущем состоянии рабо- чей памяти.
Что касается применения правила, оно состоит в том, что в текущее состояние рабочей памяти добавляются факты из множества добав- ляемых фактов правила и удаляются факты из множества удаляемых фактов.
Происходит это следующим образом. Если установлена выполни- мость условия некоторого правила, свободные переменные в формулах условия, как было сказано выше, приобретают значения из записей текущего состояния рабочей памяти. При этом происходят и замены свободных переменных в формулах из множеств A и D теми значе- ниями, которые были подставлены на места одноименных свободных переменных в формулы условия. Для тех формул из множества A,
которые в результате этого процесса превратились в факты, значе- ния, находящиеся на местах свободных переменных, дописываются в таблицы, соответствующие этим формулам в смысле отображения I,