КулЛиб - Классная библиотека! Скачать книги бесплатно
Всего книг - 706317 томов
Объем библиотеки - 1349 Гб.
Всего авторов - 272772
Пользователей - 124662

Последние комментарии

Новое на форуме

Новое в блогах

Впечатления

DXBCKT про Калюжный: Страна Тюрягия (Публицистика)

Лет 10 назад, случайно увидев у кого-то на полке данную книгу — прочел не отрываясь... Сейчас же (по дикому стечению обстоятельств) эта книга вновь очутилась у меня в руках... С одной стороны — я не особо много помню, из прошлого прочтения (кроме единственного ощущения что «там» оказывается еще хреновей, чем я предполагал в своих худших размышлениях), с другой — книга порой так сильно перегружена цифрами (статистикой, нормативами,

  подробнее ...

Рейтинг: +1 ( 1 за, 0 против).
DXBCKT про Миронов: Много шума из никогда (Альтернативная история)

Имел тут глупость (впрочем как и прежде) купить том — не уточнив сперва его хронологию... В итоге же (кто бы сомневался) это оказалась естественно ВТОРАЯ часть данного цикла (а первой «в наличии нет и даже не планировалось»). Первую часть я честно пытался купить, но после долгих и безуспешных поисков недостающего - все же «плюнул» и решил прочесть ее «не на бумаге». В конце концов, так ли уж важен носитель, ведь главное - что бы «содержание

  подробнее ...

Рейтинг: 0 ( 0 за, 0 против).
DXBCKT про Москаленко: Малой. Книга 2 (Космическая фантастика)

Часть вторая (как и первая) так же была прослушана в формате аудио-версии буквально «влет»... Продолжение сюжета на сей раз открывает нам новую «локацию» (поселок). Здесь наш ГГ после «недолгих раздумий» и останется «куковать» в качестве младшего помошника подносчика запчастей))

Нет конечно, и здесь есть место «поиску хабара» на свалке и заумным диалогам (ворчливых стариков), и битвой с «контролерской мышью» (и всей крысиной шоблой

  подробнее ...

Рейтинг: +1 ( 1 за, 0 против).
iv4f3dorov про Соловьёв: Барин 2 (Альтернативная история)

Какая то бредятина. Писал "искусственный интеллект" - жертва перестройки, болонского процесса, ЕГЭ.

Рейтинг: 0 ( 0 за, 0 против).
iv4f3dorov про Соловьёв: Барин (Попаданцы)

Какая то бредятина. Писал "искусственный интеллект" - жертва перестройки, болонского процесса, ЕГЭ.

Рейтинг: +1 ( 1 за, 0 против).

Методики Искусственного Интеллекта [Автор неизвестен] (doc) читать онлайн

Книга в формате doc! Изображения и текст могут не отображаться!


 [Настройки текста]  [Cбросить фильтры]

Методики ИИ
Введение
Многие виды умственной деятельности человека, такие, как написание программ для вычислительной машины, занятие математикой, ведение рассуждений на уровне здравого смысла и даже вождение автомобиля – требуют "интеллекта". На протяжении последних десятилетий было построено несколько компьютерных систем, способных выполнять подобные задачи.
Имеются системы, способные диагностировать заболевания, планировать синтез сложных синтетических соединений, решать дифференциальные уравнения в символьном виде, анализировать электронные схемы, понимать ограниченный объем человеческой речи и естественного языкового текста. Можно сказать, что такие систем обладают в некоторой степени искусственным интеллектом.
Работа по построению таких систем проводится в области, получившей название искусственный интеллект (ИИ).
При реализации интеллектуальных функций непременно присутствует информация, называемая знаниями. Другими словами, интеллектуальные системы являются в то же время системами обработки знаний.
В настоящее время в исследованиях по искусственному интеллекту выделились шесть основных направлений.
1. Представление знаний. В рамках этого направления решаются задачи, связанные с формализацией и представлением знаний в памяти системы ИИ. Для этого разрабатываются специальные модели представления знаний и языки описания знаний, внедряются различные типы знаний. Проблема представления знаний является одной из основных проблем для системы ИИ, так как функционирование такой системы опирается на знания о проблемной области, которые хранятся в ее памяти.
2. Манипулирование знаниями. Чтобы знаниями можно было пользоваться при решении задачи, следует научить систему ИИ оперировать ими. В рамках данного направления разрабатываются способы пополнения знаний на основе их неполных описаний, создаются методы достоверного и правдоподобного вывода на основе имеющихся знаний, предлагаются модели рассуждений, опирающихся на знания и имитирующих особенности человеческих рассуждений. Манипулирование знаниями очень тесно связано с представлением знаний, и разделить эти два направления можно лишь условно.
3. Общение. В круг задач этого направления входят: проблема понимания и синтеза связных текстов на естественном языке, понимание и синтез речи, теория моделей коммуникаций между человеком и системой ИИ. На основе исследований в этом направлении формируются методы построения лингвистических процессов, вопросно – ответных систем, диалоговых систем и других систем ИИ, целью которых является обеспечение комфортных условий для общения человека с системой ИИ.
4. Восприятие. Это направление включает разработку методов представления информации о зрительных образах в базе знаний, создание методов перехода от зрительных сцен к их текстовому описанию и методов обратного перехода, создание средств для порождения зрительных сцен на основе внутренних представлений в системах ИС.
5. Обучение. Для развития способности систем ИИ к обучения, т.е. к решению задач, с которыми они раньше не встречались, разрабатываются методы формирования условий задач по описанию проблемной ситуации или по наблюдению за ней, методы перехода от известного решения частных задач (примеров) к решению общей задачи, создание приемов декомпозиции исходной задачи на более мелкие и уже известные для систем ИИ. В этом направлении ИИ сделано еще весьма мало.
6. Поведение. Поскольку системы ИИ должны действовать в некоторой окружающей среде, то необходимо разрабатывать некоторые поведенческие процедуры, которые позволили бы им адекватно взаимодействовать с окружающей средой, другими системами ИИ и людьми. Это направление в ИИ разработано очень слабо.
В настоящем пособии рассматриваются только основы первых двух направлений – представление знаний и методы вывода.
Знания и их представление
Системы, основанные на знаниях – это системы программного обеспечения, основными структурными элементами которых являются база знаний и механизм логических выводов. В первую очередь к ним относятся экспертные системы, способные диагностировать заболевания, оценивать потенциальные месторождения полезных ископаемых, осуществлять обработку естественного языка, распознавание речи и изображений и т.д. Экспертные системы являются первым шагом в практической реализации исследований в области ИИ. В настоящее время они уже используются в промышленности.
Экспертная система – это вычислительная система, в которую включены знания специалистов о некоторой конкретной проблемной области и которая в пределах этой области способна принимать экспертные решения.
Базовая структура экспертной системы приведена на рис. 1.1.
Структурные элементы, составляющие систему, выполняют следующие функции.
База знаний – реализует функции представления знаний в конкретной предметной области и управление ими.
Механизм логических выводов – выполняет логические выводы на основании знаний, имеющихся в базе знаний.
Пользовательский интерфейс – необходим для правильной передачи ответов пользователю, иначе пользоваться системой крайне неудобно.
Модуль приобретения знаний – необходим для получения знаний от эксперта, поддержки базы знаний и дополнения ее при необходимости.
Модуль ответов и объяснений – формирует заключение экспертной системы и представляет различные комментарии, прилагаемые к заключению, а также объясняет мотивы заключения.
Перечисленные структурные элементы являются наиболее характерными, хотя в реальных экспертных системах их функции могут быть соответствующим образом усилены или расширены.
Знания в базе знаний представлены в конкретной форме и организация базы знаний позволяет их легко определять, модифицировать и пополнять. Решение задач с помощью логического вывода на основе знаний хранящихся в базе знаний, реализуется автономным механизмом логического вывода. Хотя оба эти компонента системы с точки зрения ее структуры являются независимыми, они находятся в тесной связи между собой и определение модели представления знаний накладывает ограничения на выбор соответствующего механизма логических выводов. Таким образом, при проектировании экспертных систем необходимо анализировать оба указанных компонента.
Чтобы манипулировать знаниями из реального мира с помощью компьютера, необходимо осуществлять их моделирование. К основным моделям представления знаний относятся:
- логические модели;
- продукционные модели;
- сетевые модели;
- фреймовые модели.
Прежде чем перейти к более детальному рассмотрению типичных моделей представления знаний в системах ИИ, ознакомимся с каждой из них.
Логические модели
В основе моделей такого типа лежит понятие формальной системы.
Постановка и решение любой задачи связаны с определенной предметной областью. Так, решая задачу составления расписания обработки деталей на металлорежущих станках, мы вовлекаем в предметную область такие объекты, как конкретные станки, детали, интервалы времени и общие понятия "станок", "деталь", "тип станка" и т.д.
Все предметы и события, которые составляют основу общего понимания необходимой для решения задачи информации, называются предметной областью. Мысленно предметная область представляется состоящей из реальных объектов, называемых сущностями.
Сущности предметной области находятся в определенных отношениях друг к другу. Отношения между сущностями выражаются с помощью суждений. В языке (формальном или естественном) суждениям отвечают предложения.
Языки предназначенные для описания предметных областей называются языками представления знаний. Универсальным языком представления знаний является естественный язык. Однако использование естественного языка в системах машинного представления знаний наталкивается на ряд препятствий, главным из которых является отсутствие формальной семантики естественного языка.
(Семантика – значение единиц языка).
Для представления математического знания в математической логике пользуются логическими формализмами – исчислением высказываний и исчислением предикатов. Эти формализмы имеют ясную формальную семантику и для них разработаны механизмы вывода. Поэтому исчисление предикатов было первым логическим языком, который применяли для формального описания предметных областей, связанных с решением прикладных задач.
Описания предметных областей, выполненные в логических языках, называются логическими моделями. Логические модели, построенные с применением языков логического программирования, широко применяются в базах знаний и экспертных системах.
Продукционные модели
Продукции (наряду с сетевыми моделями) являются наиболее популярными средствами представления знаний в системах ИИ. В общем виде под продукцией понимают выражение вида A  B. Обычное прочтение продукции выглядит так: ЕСЛИ А, ТО B. Импликация может истолковываться в обычном логическом смысле как знак логического следования B из истинного А. Возможны и другие интерпретации продукции, например А описывает некоторое условие, необходимое, чтобы можно было совершить действие B.
Если в памяти системы хранится некоторый набор продукций, то они образуют систему продукций. В системе продукций должны быть заданы специальные процедуры управления продукциями, с помощью которых происходит актуализация продукций и выполнение той или иной продукции из числа актуализированных.
В состав системы продукций входит база правил (продукций), глобальная база данных и система управления. База правил – это область памяти, которая содержит совокупность знаний в форме правил вида ЕСЛИ – ТО. Глобальная база данных – область памяти, содержащая фактические данные (факты). Система управления формирует заключения, используя базу правил и базу данных. Существуют два способа формирования заключений – прямые выводы и обратные выводы.
В прямых выводах выбирается один из элементов данных, содержащихся в базе данных, и если при сопоставлении этот элемент согласуется с левой частью правила (посылкой), то из правила выводится соответствующее заключение и помещается в базу данных или исполняется действие, определяемое правилом, и соответствующим образом изменяется содержимое базы данных.
В обратных выводах процесс начинается от поставленной цели. Если эта цель согласуется с правой частью правила (заключением), то посылка правила принимается за подцель или гипотезу. Этот процесс повторяется до тех пор, пока не будет получено совпадение подцели с данными.
При большом числе продукций в продукционной модели усложняется проверка непротиворечивости системы продукций, т.е. множества правил. Поэтому число продукций, с которыми работают современные системы ИИ, как правило, не превышают тысячи.
Сетевые модели
В основе моделей этого типа лежит конструкция, названная раньше семантической сетью. Семантический подход к построению систем ИИ находит применение в системах понимания естественного языка, в вопросно-ответных системах, в различных предметно – ориентированных системах.
В самом общем случае семантическая сеть представляет собой информационную модель предметной области и имеет вид графа, вершины которого соответствуют объектам предметной области, а дуги – отношениям между ними. Дуги могут быть определены разными методами, зависящими от вида представляемых знаний. Обычно дуги, используемые для представления иерархии, включают дуги типа "множество", "подмножество", "элемент". Семантические сети, используемые для описания естественных языков, используют дуги типа "агент", "объект", "реципиент".
В качестве простого примера рассмотрим предложения "Куин Мэри является океанским лайнером" и "Каждый океанский лайнер является кораблем". Они могут быть представлены через семантическую сеть (рис 1.2). В этом примере используется важный тип дуг "является".
В семантических сетях существует возможность представлять знания более естественным и структурированным образом, чем в других формализмах.
Фреймовые модели
В отличие от моделей других типов во фреймовых моделях фиксируется жесткая структура информационных единиц, называемых фреймами. Фрейм является формой представления некоторой ситуации, которую можно (или целесообразно) описывать некоторой совокупностью понятий и сущностей.
В качестве идентификатора фрейму присваивается имя фрейма. Это имя должно быть единственным во всей фреймовой системе.
Фрейм имеет определенную внутреннюю структуру, состоящую из множества элементов, называемых слотами, которым также присваиваются имена. Каждый слот в свою очередь представляется определенной структурой данных. В значение слота подставляется конкретная информация, относящаяся к объекту, описываемому этим фреймом. На рис 1.3 в качестве простого примера показан фрейм, описывающий человека.

Фрейм:
Имя
Имя слота:
Значение слота
Класс:
Животное
Структурный элемент:
Голова, шея, руки, …
Рост:
30 220 см
Масса:
1  200 кг
Хвост:
Нет
Язык:
Русский, английский, китайский …
Фрейм аналогии:
Обезьяна
Значением слота может быть практически что угодно: числа, формулы, тексты на естественном языке или программы, правила вывода или ссылки на другие слоты данного фрейма или других фреймов. В качестве значения слота может выступать набор слотов более низкого уровня, что позволяет реализовывать во фреймовых представлениях "принцип матрешки".
Связи между фреймами задаются значениями специального слота с именем "Связь". Часть специалистов по системам ИИ считают, что нет необходимости выделять фреймовые модели представления знаний, так как в них объединены все основные особенности моделей остальных типов.
Представление знаний и процедуры выводов с помощью логики предикатов
Понятие формальной системы
Появление формальных систем было обусловлено осознанием того факта, что совершенно различные системы, будь то технические, социальные, экономические или биологические, обладают глубоким сходством.
В формальной системе (ФС), оперирующей теми или иными символами, эти символы воспринимаются просто как элементы, с которыми обращаются согласно определенным правилам, зависящим только от формы выражений, образованных из символов. Понятие истинности появляется только в связи с возможными приложениями (интерпретациями) этой системы.
Формальные системы – это аксиоматические системы, т.е. системы с наличием определенного числа исходных заранее выбранных и фиксированных высказываний, называемых аксиомами.
Формальная система считается заданной, если выполнены следующие условия.
1. Задано некоторое множество, состоящее из конечного или бесконечного числа элементов, которые носят название термов. Имеется другое конечное множество, элементы которого есть связки или операции.
2. Любую линейную упорядоченную совокупность термов и операций называют формулой. Из множества формул выделяют подмножеств правильно построенных формул (ППФ). Для ППФ задают правила их конструирования, т.е. определяется эффективная процедура, позволяющая по данному выражению выяснять, является ли оно ППФ в данной ФС.
3. Выделено некоторое множество ППФ, называемых аксиомами ФС. При этом должна иметься эффективная процедура, позволяющая для произвольной ППФ, решить, является ли она аксиомой.
4. Имеется конечное множество R1, R2, …, Rk отношений между ППФ называемых правилами вывода. Понятие "вывода" также должно быть эффективным, т.е. должна существовать эффективная процедура, позволяющая для произвольной конечной последовательности ППФ решать, можно ли каждый член этой последовательности вывести из одной или нескольких предшествующих ППФ посредством некоторых фиксированных правил вывода. Выводом ФС называется любая последовательность ППФ A1, A2, …, An такая, что для любого i (i = ) ППФ Ai есть либо аксиома ФС, либо непосредственное следствие каких-либо предыдущих ППФ по одному из правил вывода.
ППФ В называется теоремой ФС, если существует вывод ФС, в котором последней ППФ является В.
Любая ФС задается четверкой где T – множество термов и операций; H – множество правил конструирования ППФ; A – система аксиом; R – множество правил вывода.
Можно расширить формальную систему введением дополнительных правил на множества H, A и R. Если на множество H действуют правила h, изменяющие синтаксис ФС, на множество A – правила , изменяющие систему аксиом, и если в ФС разрешается изменять набор правил вывода с помощью некоторых правил , то такое расширение ФС называется семиотической системой.
Для функционирования семиотической системы необходимо задать проблемно ориентированную формальную систему и правила ее изменения. Сама формальная система не является ни языком, ни системой знания, она не содержит никаких утверждений об объектах, а является просто исчислением – некоторого рода действиями по определенным правилам над последовательностями термов.
Два класса формальных систем являются математической базой для построения систем ИИ: исчисление высказываний и исчисление предикатов первого порядка.
Исчисление высказываний как формальная система
Сложное высказывание имеет истинностное значение, которое однозначно определяется истинностными значениями простых высказываний, из которых оно составлено.
Например: "Если студент ложится поздно спать и пьет кофе, то утром он встанет в плохом настроении или с головной болью". Это сложное высказывание состоит из следующих простых высказываний:
"Студент ложиться поздно спать"
"Студент пьет на ночь кофе"
"Утром студент встанет в плохом настроении"
" Утром студент встанет с головной болью"
Обозначив сложное высказывание через X, а простые соответственно через Y, Z, U, V, можно записать
X = если Y и Z, то U или V
Или X = (YZ)  (UV)
Каждую логическую связку можно рассматривать как операцию, которая образует новое высказывание – сложное из более простых.
Таким образом, всякое сложное высказывание можно записать в виде некоторой формулы, содержащей логические связки и символы, которые обозначают простые высказывания, называемые атомами. Чтобы узнать, истинно или ложно сложное высказывание, достаточно узнать истинные значение всех атомов, из которых оно составлено.
Пусть дана формула B и X1, X2, …, Xn – атомы, в ней встречающиеся. Тогда под интерпретацией формулы B будем понимать приписывание истинных значений атомам X1, X2, …, Xn. Формула B истинна в данной интерпретации тогда и только тогда, когда B принимает значение "истина", иначе B ложна в этой интерпретации.
Для формулы состоящей из n атомов существует 2n интерпретаций.
Формула исчисления высказываний, которая истинна во всех интерпретациях, называется тавтологией или общезначимой формулой. Примерами тавтологий являются XX, X(YX).
Формула исчисления высказываний называется противоречием, если она ложна во всех интерпретациях. Например, XX.
Рассмотрим без доказательства несколько правил образования тавтологий из тавтологий (очевидно, что для получения противоречий нужно применить к тавтологии операцию отрицания).
1. Пусть B есть некоторая формула, а B* - формула, полученная из B подстановкой формулы C вместо атома X везде, где он встречается в B. Тогда, если B – тавтология, то и B* также тавтология.
Это правило называется в ФС правилом подстановки.
2. Если B и B  C – тавтологии, то C – также тавтология.
Этот результат известен как правило дедуктивного вывода – modus ponens.
Теория дедуктивного вывода (раздел математической логики) занимается выводом утверждений из начального списка рассуждений, фактов, посылок, аксиом. Задавая интерпретации, в которых посылки истинны, получают и истинное заключение.
Исчисление предикатов первого порядка
Исчисление высказываний оказывается недостаточным для обоснования, например, таких рассуждений:
"Всякое положительное целое число есть натуральное число. Число 5 есть положительное целое число. Следовательно 5 есть натуральное число".
Это объясняется тем, что исчисление высказываний ограничивается структурой предложений в терминах простых высказываний, а приведенные рассуждения требуют анализа структуры предложения в смысле связи субъекта и предиката, как это делается в грамматике.
Слово "предикат" имеет два значения. В грамматике – сказуемое, в логике – логическое сказуемое, то, что в суждении высказывается о предмете суждения.
Пусть задано некоторое множество V = {v1, v2, …, vk}, в котором v1, v2, …, vk – какие – то определенные предметы из этого множества. Обозначим любой предмет из этого множества через x и назовем x предметной переменной. Тогда высказывания об этих предметах будем обозначать в виде P(v1), Q(v1, v2) и т.д., причем такие высказывания могут быть истинными и ложными. Например, если V = {1, 2, 3, …}, то высказывание "4 есть четное число" является истинным, а "7 есть четное число" – ложным. Если вместо конкретных чисел 4 и 7 поставим предметную переменную x, то получим предикат "x есть четное число", обозначенный P(x).
Таким образом, предикат на множестве V есть логическая функция, определенная на V. При фиксировании аргументов предиката функция превращается в высказывание.
В общем случае через P(x1, x2, …, xn) обозначим n – местный предикат, который превращается в высказывание при присвоении x1, x2, …, xn значений из соответствующих областей определения и имеет значение истина или ложь.
Таким образом, предикат, который не содержит переменных, совпадает с высказыванием.
Исчисление предикатов первого порядка представляет собой формальную систему, с помощью которой можно выразить большое разнообразие утверждений.
Неотъемлемой функцией языка предикатов является задание слов, которые описывают сущности изучаемого мира, и слов, которые описывают атрибуты, т.е. свойства этих сущностей, их поведение и отношения.
Первый тип слов является термами, второй – предикатами.
Элементарными компонентами языка предикатов являются предикатные символы и символы констант, переменных и функций. (Значение функции является сущностью описываемого мира, поэтому функция – тоже терм).
Атомарными предикатом называется последовательность из n (n  1 и конечно) термов, заключенная в круглые скобки, которые следуют за предикатным символом. Имя предикатного символа выражено некоторой последовательностью букв.
Например: отец(x, y) – атомарный предикат, описывающий отношение x к y.
В логике предикатов атомарные предикаты задают формулы для описания отношений между сущностями, определяемыми аргументами предикатов.
Если конструктор намеревается описать некоторую предметную область, используя для этого логику предикатов, он может определять предикаты по своему усмотрению в соответствии с конкретной ситуацией. Определение соответствия между элементами языка и отношениями, элементами и функциями в указанной области рассуждения и составляет семантику языка исчисления предикатов.
Очевидно, что определение предиката должно быть однозначным.
Предложения в логике предикатов называются предикатной формулой. Отношения в предикатной формуле задаются символами двух классов.
К символам первого класса относятся логические связки ,,,,, которые интерпретируются как отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность.
Импликация A  B полностью эквивалентна выражению AB и поэтому не является основным символом. Но включение символа  в число основных оправдывается тем, что выражение A  B аналогично выражению "если A то B" в естественном языке.
Символ  также может быть выражен через первые три символа, но используется из тех же соображений.
В качестве символов второго класса используются две связки  и . Связка  называется квантором общности, а  - квантором существования.
Пусть P(x) обозначает, что x обладает свойством P. Тогда выражение (x)P(x) означает утверждение: "Все x области V обладают свойством P" или "Для всякого предмета x области V выражение P(x) истинно".
Запись (x)P(x) означает, что существует предмет x из области V, обладающий свойством P, или существует предмет x области V, для которого P(x) истинно. Пусть A – формула исчисления предикатов. В выражении (x)A (или (x)A) формула A называется областью действия квантора (x) (соответственно (x)).
Вхождение переменной x в данную формулу называется связанным, если x является переменной входящего в эту формулу квантора x (или x) или находится в области действия входящего в эту формулу квантора. В противном случае вхождение переменной x в данную формулу называется свободным. Отсюда и переменная называется свободной (связанной) переменной в данной формуле если существуют свободные (связанные) ее вхождения в эту формулу.
Сказанное справедливо и для многоместных предикатов, т.е. для любого числа переменных в предикатной формуле. При этом возможна ситуация, когда часть переменных связана квантором общности, а другая часть – квантором существования.
В этом случае, во избежание неоднозначной интерпретации предикатов следует упорядочить переменные.
Пример. Предикат "любит(x, y)" описывает отношение x к y. Проквантифицируем переменную x квантором общности, а y – квантором существования (x)(y) любит(x, y) – "для всех x существует y, которого любит x".
Если поменять порядок записи кванторов, интерпретация изменится:
(y)(x) любит(x, y) – "существует y, которого любят все x".
Если все переменные предиката являются связанными, то такой предикат называют замкнутой формулой, т.е. формулой без свободных переменных.
Таким образом, исчисление предикатов первого порядка представляет собой расширение исчисления высказываний. Опускаемые далее слова "первого порядка" говорят о том, что применение кванторов допускается только к предметным переменным. (формула вида (P)P(A) не является ППФ в исчислении предикатов первого порядка)
Правила вывода логики предикатов
Рассмотрим формальную систему для исчисления предикатов.
1. Правила образования ППФ (В исчислении предикатов ППФ описывает обычное предложение общего вида – если говорить применительно к естественному языку).
а) Атомарный предикат есть ППФ.
б) Если A и B – ППФ и x – предметная переменная, то каждое из выражений А, AB, AB, AB, (x)A и (x)A есть ППФ.
в) Все результаты получаемые повторением а) и б) конечное число раз есть ППФ.
Воспользовавшись этими определениями можно записать предложение "все люди смертны": (x)[человек(x)  смертен(x)].
2. Правила вывода.
а) все аксиомы выводимы.
б) правило подстановки или специализации, аналогичное правилу подстановки для исчисления высказываний.
Если (x)P(x) есть ППФ, то и P(c) – тоже ППФ, где с – любой символ константы.
в) Правило дедуктивного вывода – modus ponens.
Если P(x) – ППФ и P(x)  Q(x), то Q(x) есть также ППФ.
Используя вместе правила модус поненс и специализацию можно доказать приведенное в начале раздела 2.3 утверждение.
Пусть P(x) и N(x) обозначают соответственно "x есть положительное число" и "x есть натуральное число".
Тогда утверждение "Всякое положительное целое число есть натуральное. Число 5 есть положительное целое число. Следовательно, 5 есть натуральное число" может быть доказано на языке исчисления предикатов следующим образом.
(x)(P(x)  N(x))
P(5)
N(5) вывод
Таким образом, правила вывода создают ППФ, выведенные из данных ППФ. В исчислении предикатов каждая выведенная формула называется теоремой, а используемая последовательность применений правил вывода составляет доказательство теоремы. В некоторых случаях решение проблемы может быть рассмотрено как задача поиска доказательства теоремы.
Семантика логики предикатов
Определение логической формулы в логике предикатов – это правила построения сложных предложений из простых предложений и синтаксических единиц, включающих описание отношений между основными понятиями атомарных предикатов. Эти правила соответствуют синтаксическим правилам естественного языка.
Таким образом, формулы логики предикатов строятся как символьные системы совершенно безотносительно к понятиям описываемого мира.
Очевидно, что между понятиями описываемого мира и предикатными формулами должно быть установлено соответствие. Такое определение соответствия предполагает следующие действия.
1. Установление соответствий между константами логики предикатов и сущностями описываемого мира (константы принимаются за имена объектов).
2. Установление соответствия между формулами логики предикатов и функциональными отношениями описываемого мира.
3. Установление соответствия между атомарными и концептуальными отношениями этого мира.
При выполнении действий, предусмотренных в пунктах (2) и (3) должно быть установлено число и назначение всех причастных к логическим формулам сущностей с их числом и назначением в описываемом мире.
Кроме того, требуется задать значение "истина" и "ложь" в зависимости от выполнения или невыполнения концептуальных отношений, описанных логическими формулами. Таким образом, в язык вносится конкретное смысловое содержание.
В формулы логики предикатов входят переменные семантически ограниченные кванторами  и  и не ограниченные ими переменные.
Логическая формула, в которой все переменные являются связанными (замкнутая формула), называется предложением. Предложениям можно однозначно поставить в соответствие какое – либо определенное значение - "истина" или "ложь". Ложность или истинность предикатной формулы, содержащей свободные переменные, можно оценить только тогда, когда в эти переменные будут подставлены некоторые сущности (формула обратится в высказывание). Значение предикатной формулы со связанными переменными можно определить, не производя такой подстановки. Например, (y)(x)отец(x, y) – "у каждого человека (у) имеется отец(x)" является истинной, а (x)(y)отец(x, y) – "все люди (x) имеют детей (y)" является ложью. Таким образом, предложение имеет такие же свойства, что и высказывание, не содержащее переменных.
Поставив в соответствие словам языка те понятия, которые познаются в реальной действительности, можно средствами этого языка передавать познанные понятия.
Рассмотрим пример представления в исчислении предикатов следующего высказывания.
Для каждого множества x существует множество y такое, что мощность y больше чем мощность x:
(x){множество(x)(y)(u)(v)[множество(y)мощн(x,u)мощн(y,v)G u,v)]} (предикат G(,) означает >)
Кроме того, возможно получать значения неизвестных логических формул, используя для этого уже оцененные формулы.
Например, если заданна группа логических формул:
(x)[человек(x)смертен(x)] – все люди смертны,
человек(Сократ) – Сократ – человек,
то используя правила вывода можно получить заключение (неизвестную логическую формулу):
смертен(Сократ).
(Вместо переменной x была вставлена константа "Сократ").
Доказательство методом резолюции
Рассмотренный выше метод вывода в логике предикатов легко воспринимается человеком, но для машинной реализации необходима более фундаментальная формализация метода. В качестве такого полноценного метода доказательства теорем используется метод резолюции. Для применения этого метода исходную группу заданных логических формул требуется преобразовать в некоторую нормальную форму. Это преобразование производится обычно в несколько стадий.
Префиксная формальная форма
Форма представления предметной формулы, в которой все кванторы выводятся за скобки и следуют непосредственно перед ППФ, носит название префиксной нормальной формы.
Для приведения к префиксной нормальной форме произвольной ППФ необходимо рассмотреть некоторые равносильные формулы в исчислении предикатов (без доказательств).
Имеем следующие пары равносильных формул:
(x)F(x)P = (x)(F(x)P);
(x)F(x)P = (x)(F(x)P);
(x)F(x)P = (x)(F(x)P);
(x)F(x)P = (x)(F(x)P).
При условии, что формула P не содержит свободно x и поэтому не входит в область действия кванторов.
Далее:
(x)F(x)(x)P(x) = (x)(F(x)P(x)),
(x)F(x)(x)P(x) = (x)(F(x)P(x)).
Но
(x)F(x)(x)P(x) (x)(F(x)P(x)),
(x)F(x)(x)P(x)  (x)(F(x)P(x)).
В последних двух случаях необходимо произвести переименование связанных переменных, т.е:
(x)F(x)(x)P(x) = (x)F(x)(y)P(y) = (x)(y)(F(x)P(y)),
(x)F(x)(x)P(x) = (x)F(x)(y)P(y) = (x)(y)(F(x)P(y))
при условии, что переменная y не появляется в F(x).
В двух последних отношениях связанная переменная в квантифицированном выражении является "немой" переменной и ее можно произвольно заменять на любой другой символ переменной, который еще не встречался в выражении.
С учетом приведенных формул алгоритм, преобразующий произвольную заданную формулу в равносильную в префиксной форме состоит из следующих шагов.
Шаг 1. Исключение логических связок  и  с помощью известных правил.
Шаг 2. Продвижение связки  до атома с использованием законов де Моргана. В результате выполнения этого шага получается формула, у которой знаки  могут стоять только перед атомами.
Шаг 3. Переименование связных переменных.
Шаг 4. Вынесение кванторов с помощью формул (*).
После четвертого шага формула приобретает префиксный вид.
Сколемовская нормальная формула
После того как кванторы вынесены в префиксную часть формулы, необходимо полностью исключить из предикатных формул кванторы, чтобы обеспечить возможность применения машинных процедур обработки предикатных формул. Но при исключении кванторов необходимо полностью сохранить семантику языка предикатов. Это можно сделать путем введения сколемовских функций.
Рассмотрим ППФ (y)(x)P(x,y) которую можно прочесть так: "Для всех y существует некоторый x (возможно зависящий от y), такой, что P(x,y)". Поскольку квантор существования находится в области действия некоторого квантора общности, то допускаем возможность, что тот x, который существует, может зависеть от y. Пусть эта зависимость будет явно определена с помощью некоторой функции f(y), отображающей каждое значение y в тот x, который "существует". Если x, который существует, заменить на такую сколемовскую функцию, то квантор существования можно исключить и записать (y)P(f(y),y). Тот факт, что переменная x проквантифицирована квантором  будет отражен при подстановке функции f(y) на место x.
Общее правило исключения квантора существования из ППФ состоит в замене каждого вхождения переменной, относящейся к квантору существования, на сколемовскую функцию, аргументы которой являются переменными, связанными кванторами общности, и область действия этих кванторов общности включает область действия исключаемого квантора существования. Приоритетность действия кванторов, имеющихся в префиксной форме представления, определяется слева направо. Например, формулу (x)(y)(z)F(x, y, z) можно переписать в следующем виде (x)(z)F(x, f(x), z), так как переменной, влияющей на связанную квантором  переменную y, является только x.
Если же исходная логическая формула имеет вид (x)(z)(y)F(x, y, z), то переменными, влияющими на переменную с квантором существования, являются x и z и тогда получаем (x)(z)F(x, f(x, z),z).
Если исключаемый квантор существования не входит в область действия никакого из кванторов общности, то применяется сколемовская функция без аргументов, т.е. просто константа. Так (x)P(x) становится P(A), где символ константы A используется для ссылки на элемент, который, как известно, существует. Важно, чтобы A был новым символом константы и не совпадал с другими символами для других ППФ.
Если исключить подобным образом связанные квантором существования переменные, то любые другие переменные, которые встречаются в формуле будут связаны только квантором . Порядок кванторов общности роли не играет, поэтому можно не указывать явно вхождения кванторов, а предположить по соглашению, что все переменные относятся к кванторам общности.
Клаузальная форма (форма предположений)
После проведения сколемовских преобразований результирующая ППФ представляет собой несколько предикатов, содержащих переменные и соединенных различными связками. Такая безкванторная форма называется матрицей. Любую матрицу можно привести к конъюнктивной нормальной форме (КНФ) многократным применением дистрибутивных правил. Чтобы привести матрицу к клаузальной форме или форме предложений, исключают символы , заменяя выражения вида (x1x2) на множество ППФ {x1,x2}. Результатом многократного использования таких замен будет некоторое конечное множество ППФ, каждая из которых является дизъюнкцией литералов. Любая ППФ, состоящая только из дизъюнкций литералов, называется предложением. Множество предложений, полученных в результате исключения символа  называется клаузальным множеством.
После исключения символов  необходимо осуществить переименование переменных. Символы переменных должны быть изменены так, чтобы каждый появлялся не более чем в одном предложении.
Следует отметить, что литералы в предложениях могут содержать переменные, но всегда подразумевается, что они относятся к кванторам общности. Если вместо переменных некоторого выражения подставляются термы, не содержащие переменных, то получаем так называемый основной частный случай литерала. Так Q(A, f(g(B))) является основным частным случаем Q(x, y)/
Когда резолюция используется в качестве правила вывода в системе доказательства теорем, то множество ППФ, исходя из которого мы хотим доказать теорему, сначала преобразовывается в совокупность предложений. Можно доказать, что если ППФ X логически следует из некоторого множества S правильно построенных формул, то она также логически следует из множества предложений, получаемых в результате преобразования ППФ из S в форму предложений.
Следовательно, для наших целей предложения являются вполне общей формой, в которой выражаются ППФ.
Пример преобразования исходной ППФ в клаузальную форму приведен в приложении 1.
Резолюция для основных предложений
Общее представление о правиле вывода с использованием резолюции лучшего всего рассмотреть на примере того, как она применяется в случае основных предложений.
Пусть имеются два основных предложения (т.е. предложения не содержащие переменных): P1P2…PN и P1Q2…QM. Считаем, что все Pi и Qj различны. Отметим, что эти предложения содержат дополнительные литералы (литералы, которые взаимно отличаются только символом отрицания).
Из этих двух родительских предложений можно вывести новое предложение, называемое их резольвентой. Резольвента вычисляется взятием дизъюнкции этих предложений с последующим исключением дополнительной (контрарной) пары: P1, P1.
Некоторые основные частные случаи резолюции приведены в таблице 2.1. Из этой таблицы видно, что резолюция позволяет объединить несколько операций в одно простое правило вывода.
Таблица 2.1
Предложения и резольвенты
Родительские предложения
Резольвенты
Комментарии
P и PQ(т.е. PQ)
Q
Модус поненс
PQ и PQ
Q
Предложение QQ "сворачивается" в Q. Эта резольвента называется слиянием.
PQ и PQ
QQ
PP
Здесь две возможные резольвенты; в данном случае обе являются тавтологиями.
P и P
NIL
Пустое предложение, является признаком противоречия
PQ и QR
(т.е. P  Q и Q  R)
PR
(т.е. PR)
Цепочка.
Унификация и подстановка
Чтобы применить резолюцию к предложениям, содержащим переменные, необходимо предварительно провести некоторую подстановку в переменные и ввести понятие унификации с помощью этой подстановки.
Пусть имеются два предиката L(x) и L(A), где x – переменная, а A – константа. Хотя предикатные символы и одинаковые, о самих предикатах этого сказать нельзя. Тем не менее, подстановкой A в x можно эти предикаты сделать одинаковыми. Однако операцию подстановки нельзя проводить при отсутствии каких-либо ограничительных условий. Подстановку t в x принято записывать как {t/x}. Поскольку в одну ППФ может входить более одной переменной и, следовательно, можно провести более одной подстановки, то обычно эти подстановки записываются в виде множества упорядоченных пар: {t1/x1; t2/x2; …, tn/xn}. Условия, допускающие подстановку, состоят в следующем:
1). xi является переменной, а ti – термом (константа, переменная, функция), отличным от xi.
2) для любой пары элементов из группы подстановок в правых частях символов "/" не содержатся одинаковые переменные.
Обозначим группу подстановок {t1/x1; t2/x2; …, tn/xn} через S. Если для некоторого представления L применяется подстановка содержащихся в ней переменных {x1; x2; …, xn}, то результат подстановки, при которой переменные заменяются соответствующими им термами t1; t2; …, tn, принято обозначать как LS.
Если имеется группа различных выражений предиката L, т.е. {L1, L2, …, Lm}, то подстановка S (положим, что она существует) такая, что в результате все эти выражения становятся одинаковыми, т.е. L1S = L2S =… LmS называется унификатором для {L1, L2, …, Lm}. Если такая подстановка S существует, то множество выражений {L1, L2, …, Lm} является унифицируемым.
Множество {L(x), L(A)} – унифицируемо, при этом унификатором является подстановка {A/x}.
Для одной группы выражений унификатор не обязательно единственный. Для группы выражений {L(x, y)}, L{z, f(x)} подстановка S = {x/z, f(x)/y} является унификатором, но унификатором является и подстановка S' = {A/x; A/z; f(A)/y}, где A – константа, а x – переменная.
В таких случаях возникает проблема: какую подстановку лучше всего выбрать в качестве унификатора.
Если существует несколько унификаторов, то среди них непременно найдется такая подстановка , что все другие унификаторы являются подстановками, выражаемыми в виде S, как сложная форма, включающая эту подстановку. В результате подстановки переменные будут замещены константами и описательная мощность ППФ будет ограничена.
Чтобы унифицировать два различных выражения предиката, необходима такая подстановка, при которой выражение с большой описательной мощностью согласуется с выражением, имеющим малую описательную мощность. Подстановка, которая является унификатором с минимальным ограничениями называется "наиболее общим унификатором" (НОУ). В рассмотренном выше примере из подстановок S и S' НОУ является подстановка S.
Метод отыскания НОУ из заданной группы предикатных выражений называется алгоритмом унификации. В таблице 2.2 приведены наиболее общие подстановочные частные случаи для нескольких множеств литералов.
Таблица 2.2
Унифицируемые множества.
Множество литералов
Наиболее общие подстановочные частные случаи
{P(x), P(A)}
P(A)
{P(f(x), y, g(y)), P(f((x), z, g(x)}
P(f(x), x, g(x))
{P(f(x, g(A, y)),g(A, y)), P(f(x, z), z)}
P(f(x, g(A, y)), g(A, y))
Резолюция в общем случае
Чтобы применить резолюцию к предложениям, содержащим переменные, необходимо найти такую подстановку, которая, будучи примененной к родительским предложениям, позволит получитьдополнительные литералы.
Пусть предполагаемые родительские предложения даются в виде множества литералов {Li} и {Mi} (дизъюнкция между литералами в множестве подразумевается) и пусть переменные в этих двух родительских предложениях разделены. Предположим, что {li} является подмножеством {Li}, а {mi} – подмножеством {Mi} – таким, что для объединения множеств {li} и {mi} существует НОУ S. Тогда говорят, что два предложения {Li} и {Mi} разрешаются, и что новое предложение является их резольвентой.
Если два предложения разрешаются, то они могут иметь более одной резольвенты, т.к. может иметься более чем один способ выбора {li} и {mi}.
Рассмотрим два предложения:
P(x, f(A))  P(x, f(y))  Q(y)
P(z, f(A))  Q(z)
Если {li} = {P(x, f(A))} и {mi} = {P(z,f(A))}, получаем резольвенту
P(z, f(y))  Q(z)  Q(y), S = {z/x}.
При {li} = {P(x, f(A)), P(x, f(y)) и {mi} = P(z, f(A))} получаем резольвенту
Q(A)  Q(z), S = {z/x, A/y}.
Заметим, что в последнем случае два литерала в первом предложении слились при выбранной подстановке в один, дополнительный к некоторому частному случаю из литералов второго предложения.
Всего имеется три различные резольвенты для этих предложений. Две из них получаются резолюцией на P, а одна – резолюцией на Q.
Можно доказать, что резолюция является логичным правилом вывода, т.е. что резольвента пары предложений также логически следует из этой пары предложений.
Резолюция используется в системе доказательств теорем специального вида и называется системой опровержения. При этом она является полной, т.е. любая ППФ, логически следующая из некоторого множества ППФ, может быть выведена из этого множества с использованием опровержения, основанного на резолюции.
Система опровержения на основе резолюции
В типичной задаче на доказательство теорем имеется множество S правильного построенных формул, исходя из которого нам нужно доказать некоторую целевую ППФ W. Системы, основанные на резолюции, предназначены для создания доказательства путем построения противоречия или опровержения. При таком опровержении сначала берется отрицание целевой ППФ и добавляется к множеству S. Это расширенное множество преобразуется в множество предложений (клаузальная форма), после чего резолюция используется при попытке вывести противоречие, представляемое пустым предложением NIL.
Пусть имеется множество S, состоящее из n ППФ A1, A2, …, An и пусть ППФ, для которой требуется выяснить, является ли она теоремой, есть W. Следовательно, можно сказать, что доказательство показывает справедливость (истинность) ППФ вида
(A1  A2  …  An  W)
при любой интерпретации.
Или, что эквивалентно, отрицание формулы (2.1) при любой интерпретации является ложью:
(A1  A2 … An  W)
Поскольку (2.2) является ППФ, ее можно преобразовать к форме клаузального множества, которое назовем Q.
Основная идея метода резолюции состоит
1) в проверке того, что содержит ли Q пустое предложение.
2) в проверке того, выводится ли пустое предложение из Q, если оно в Q отсутствует.
Любое предложение Ci из которых образуется Q является совокупностью атомарных предикатов или их отрицаний, соединенных символом дизъюнкции:
Ci = Pi1  Pi2  …  Pim
Само же множество Q является конъюнктивной формой:
Q = C1  C2  …  Ck.
Следовательно, условием истинности всех Ci в совокупности является условие истинности всех Ci в совокупности, и, наоборот, условием ложности Q является ложность по крайней мере одного Ci. Поскольку Ci имеет вид (2.3), условием, что Ci в какой – либо интерпретации будет ложным, является то, что множество {Pi1, Pi2, …, Pim} будет пустым.
Следовательно, если Q содержит пустое предложение, то формула (2.2) является ложью, поэтому формула (2.1) является истинной. Это означает что W логически следует из группы предикатов A1, A2, …,An, т.е. из S.
Рассмотрим простой пример такого процесса. Предположим, высказаны следующие утверждения:
1. Кто умеет читать, тот грамотный (x)(Ч(x)  Г(x))
2. Дельфины не грамотны (x)(Д(x)   Г(x))
3. Некоторые дельфины обладают интеллектом (x)(Д(x)  И(x))
Из этих посылок мы хотим доказать следующее утверждение:
4. Некоторые из тех, кто обладает интеллектом не умеет читать
(x)(И(x)   Ч(x))
Множество предложений, соответствующих утверждениям 13 таково:
1. Ч(x)  Г(x)
2. Д(y)  Г(y)
3а. Д(А)
3б. И(А)
Переменные в выражения разделены и А – сколемовская константа.
Отрицание теоремы, которую требуется доказать, преобразованное к форме предложения имеет вид:
4.  И(z)Ч(z)
Чтобы доказать теорему опровержением на основе резолюции, необходимо построить резольвенты для предложений (14), добавить эти резольвенты к базовому (первоначальному) множеству и продолжать таким же образом, пока не будет получено пустое предложение. Одно из возможных доказательств (их имеется более одного) создает следующую последовательность резольвент:
5. Ч(A) резольвента 3а и 4
6. Г(А) резольвента 5 и 1
7. Д(А) резольвента 6 и 2
8 NIL резольвента 7 и 3а
Стратегии управления для методов резолюции
Решения о том, какие два предложения в множестве предложений выбрать и какую резолюцию для этих предложений выполнять, принимаются с помощью стратегии безвозвратного управления.
Для выбора предложений в методах резолюции было предложено несколько стратегий.
Чтобы следить за тем, какие резолюции были выбраны, и чтобы избежать дублирования работы, удобно в стратегии управления использовать структуру, называемую граф вывода. Вершины этого графа помечены предложениями; изначально для каждого предложения из базового множества имеется вершина. Когда два предложения Ci и Cj создают резольвенту rij, то образуется новая вершина rij, причем ребра связывают ее с вершинами Ci и Cj. Говорят, что вершины Ci и Cj являются родителями rij и что rij является потомком Ci и Cj.
Опровержение на основе резолюции может быть представлено некоторым деревом опровержения, корневая вершина которого помечена предложением NIL. На рис 2.1 показан граф опровержения для примера, рассмотренного в разделе 2.7.
Стратегия управления направляет поиск опровержения, наращивая граф вывода до тех пор, пока не будет создано дерево, корневая вершина которого помечена пустым предложением NIL1. Стратегия управления для некоторой системы опровержения является полной, если ее использование приводит к процедуре, которая найдет опровержение, если только оно существует.
В приложении к ИИ полнота стратегии не столь важна как эффективность поиска опровержения.
Стратегия полного перебора (поиск в ширину)
В стратегии полного перебора сначала вычисляются все резольвенты первого уровня, затем все резольвенты второго уровня и т.д. Резольвентой первого уровня является резольвента для предложений из базового множества; резольвентой i-го уровня является такая, чей самый глубокий родитель является резольвентой (i-1)-го уровня. Стратегия полного перебора является полной, но весьма неэффективной, поскольку число предложений с ростом числа уровней увеличивается экспоненциально.
На рис 2.2 изображен граф опровержения, порожденный стратегией полного перебора для рассмотренной в 2.7 задачи. Пустое предложение в этом опровержении появляется уже на 3-ем уровне.
Стратегия опорного множества
Опровержение с использованием опорного множества состоит в том, что по крайней мере один из родителей в каждой резольвенте выбирается из предложений, возникающих из отрицания целевой ППФ или их потомков (опорное множество).
При опровержении с использованием опорного множества каждая резолюция несет в себе черты обратного рассуждения, поскольку в ней используется предложение, принадлежащие к отрицаниям целевой ППФ или являющееся их следствием. Обычно стратегии, основанные на опорном множестве оказываются более эффективными по сравнению с ничем не ограниченным поиском в ширину.
На рис 2.3 приведен граф опровержения, порожденный стратегией опорного множества для уже рассмотренной задачи. Эта стратегия не приводит к появлению пустого предложения уже на третьем уровне, но на каждом уровне создает меньше предложений по сравнению со стратегией полного перебора. Как правило, стратегия опорного множества приводит к более медленному росту множества предложений и тем самым позволяет ослабить комбинаторный взрыв.
Стратегия предпочтения одночленам
Стратегия предпочтения одночленам является такой модификацией стратегии опорного множества, в которой вместо заполнения каждого уровня, как и при поиске в ширину, пытаются выбрать однолитеральное предложение (одночлен) в качестве родительской вершины для резолюции. Этот процесс позволяет сконцентрировать поиск в направлении создания пустого предложения и поэтому, как правило, повышает эффективность. Дерево опровержения на рис 2.1 могло быть порождено и стратегией предпочтения одночленам.
Линейная по входу стратегия
Линейное по входу опровержение – это опровержение, в котором по крайней мере одно родительское предложение в каждой резольвенте принадлежит базовому множеству. На рис 2.4 показано, какой граф опровержения могла бы породить данная стратегия в нашем примере. И в этом случае использование такой стратегии не позволяет создать пустое предложение в 3-ем уровне. Можно заметить, что дерево опровержения на рис 2.1 проходит в качестве линейного по входу опровержения.
Имеются случаи, в которых опровержение существует, но не существует опровержения с линейной по входу стратегией. Следовательно, линейные по входу стратегии не являются полными. Несмотря на отсутствие свойства полноты, линейные по входу стратегии применяются довольно часто из-за их простоты и эффективности.
Комбинирование стратегий
Стратегии управления можно объединять. Комбинация стратегий опорного множества со стратегией, линейной по входу является широко распространенной. Иногда, такая комбинированная стратегия ведет к более медленному росту множества предложений, чем это происходит при использовании каждой стратегии в отдельности.
Что касается тех резолюций, которые допускаются рассмотренными стратегиями (опорного множества, линейная по входу), то в них ничего не говорится о порядке выполнения этих резолюций. Неподходящий порядок не препятствует нахождению опровержения, но сказывается на эффективности процесса опровержения. Упорядочивание выполнения резолюций может воспрепятствовать порождению большого числа ненужных предложений. Одним из примеров стратегий упорядочивания является стратегия предпочтения одночленам. Разработаны и другие стратегии упорядочивания, основанные на числе литералов в предложении и сложности термов предложения.
Кроме того, существуют стратегии упрощения, основанные на том, что множество предложений может быть упрощено исключением некоторых предложений или некоторых литералов из предложений. Применение стратегий упрощения также позволяет снизить скорость роста множества новых предложений.
Извлечение ответа из опровержения на основе резолюции
Многие применения систем доказательств теорем в исчислении предикатов основаны на доказательстве с помощью формул, содержащих переменные, относящиеся к квантору существования, и связаны с поиском значений или частных случаев для этих переменных. Другими словами; мы хотели бы узнать следует ли ППФ (x)W(x) логически из S, и если да, то каков тот частный случай для x, "который существует". Это обычная задача на доказательство теорем в исчислении предикатов, но создание удовлетворяющего теореме x требует, чтобы метод был "конструктивным".
Рассмотрим некоторый процесс, с помощью которого удовлетворяющий частный случай для некоторой переменной, относящейся к квантору существования, в ППФ может быть извлечен из опровержения на основе резолюции для этой ППФ.
Решим задачу следующего содержания: "Если Джим ходит туда же, "куда ходит Джон и если Джон в школе, то где Джим?" Очевидно, что в задаче определяются два факта, а затем задается вопрос, ответ на который предположительно может быть выведен из этих фактов.
Факты могут быть преобразованы в множество ППФ S:
(x)(B(Джон, x)  (Джим, x))
B(Джон, школа).
На вопрос: "Где Джим?" можно ответить, если доказать, что ППФ (x)B(Джим,x) логически следует из S, а затем найти тот частный случай x, "который существует". Основная идея состоит в преобразовании вопроса в целевую ППФ, содержащую квантор существования, такую, чтобы переменная, относящаяся к этому квантору, представляла ответ на вопрос. Если на вопрос можно дать ответ исходя из заданных фактов, то построенная таким образом ППФ будет логически следовать из S.
Опровержение на основе резолюции для рассматриваемого примера получается опытным путем. Преобразуем множество S и отрицание целевой ППФ в форму предложений и построим дерево опровержения. (рис 2.5)
B(Джон, y)  B(Джим,y) – аксиома 1
B(Джон, школа) – аксиома 2
B(Джим, x) – отрицание цели.
Извлечение ответа состоит в преобразовании дерева опровержения (с NIL в корневой вершине) в дерево доказательства с некоторым утверждением в корневой вершине, которое может быть использовано в качестве ответа.
В данном случае это происходит в результате следующего процесса.
1. Необходимо добавить к каждому предложению, следующему из отрицания целевой ППФ его собственное отрицание.
2. Следуя структуре дерева опровержения выполнить те же самые резолюции, что и раньше, пока в корневой вершине не будет построено некоторое предложение, которое и следует использовать в качестве ответного утверждения.
Дерево доказательства для нашего примера приведено на рис 2.6.
Расположенное в корневой вершине предложение представляет ответное утверждение, извлеченное при таком процессе.
Очевидно, что ответное предложение зависит от опровержения, из которого оно извлекается. Для одной и той же задачи могло бы существовать несколько различных опровержений. Из каждого опровержения можно было бы извлечь ответ, и, возможно, некоторые ответные утверждения будут носить более общий характер по сравнению с другими. Обычно нет способа узнать, является ли ответное утверждение, извлеченное из данного доказательства, наиболее общим, т.к. ввиду неразрешимости исчисления предикатов мы не всегда будем в состоянии узнать, нашли ли мы все возможные доказательства для некоторой ППФ W исходя из некоторого множества S.
Представление знаний правилами и логический вывод
Системы продукций
Разнообразные обобщения вычислительного формализма, известного под названием системы продукций, содержат четкое разделение между стандартными вычислительными компонентами: данными, операциями и управлением. Основными элементами системы продукций искусственного интеллекта являются глобальная база данных, множество правил продукций и система управления.
Глобальная база данных – центральная структура данных, используемая системой продукций ИИ. В зависимости от конкретной задачи эта база данных может быть простой, как обычная матрица чисел или сложной, как большая реляционная индексированная файловая структура.
Правила продукций применяются к глобальной базе данных. Для каждого правила имеется предварительное условие, которому эта база данных либо удовлетворяет, либо нет. Если предварительное условие выполняется, то правило может быть применено. Применение этого правила изменяет базу данных. Система управления выбирает, какое именно применимое правило следует использовать, и прекращает вычисления, когда глобальная база данных удовлетворяет терминальному условию (или условию остановки).
Структура такой системы продукций существенно отличается от структуры традиционной вычислительной системы с иерархически организованными программами. Глобальная база данных доступна для всех правил продукций; ни одна ее часть не ориентирована преимущественно на какое-либо из них. Одни правила не "вызывают" другие, связь между правилами осуществляется только через глобальную базу данных. Конструкция системы продукций является гораздо более модульной (по сравнению с традиционной вычислительной системой), и изменения в базе данных, системе управления или правилах могут производиться относительно независимо.
Будем различать несколько видов систем продукций. Они отличаются типами используемых ими систем управления, свойствами правил и баз данных, а так же способами их применения к конкретным задачам.
Задачи представления
Для решения задачи с помощью системы продукций необходимо определить глобальную базу данных, набор правил и задать стратегию управления. В области ИИ преобразование исходной формулировки задачи в такие три компоненты некоторой системы продукций называют проблемой представления. Обычно существует несколько способов такого представления. Искусство выбора хорошего представления очень существенно для применения методов ИИ к практическим задачам.
Рассмотрим решение задачи, представления на примере головоломки, известной как игра в 8. Эту игру иллюстрирует рис 3.1, где приводятся две конфигурации фишек. Рассмотрим задачу преобразования начальной конфигурации в указанную целевую. Решением служит правильная последовательность ходов, например, передвинуть фишку 6 вниз, передвинуть фишку 8 вниз и т.д.

2
8
3

1
2
3
1
6
4

8

4
7

5

7
6
5
Определим элементы задачи, соответствующие трем компонентам – состояния, ходы и цель задачи.
В игре в 8 каждая конфигурация фишек является состоянием задачи. Множество всех возможных конфигураций образует пространство состояний задачи. Многие задачи имеют пространство очень большого размера. У игры в 8 оно относительно невелико – 9! различных конфигураций (362880).
Очевидно, что при решении задачи представления, предпочтительны представления с малыми пространствами состояний. Иногда имеющееся пространство состояний можно сократить, отбросив ряд правил и объединив некоторые из них, образовав более мощные. Возможно прийти к меньшему пространству и в результате переформулировки задачи, например, изменения самого понятия о том, что такое состояние.
Определив на смысловом уровне состояния задачи, необходимо сконструировать машинное представление, или описание, которое затем используется как глобальная база данных системы продукций. Для игры в 8 простым описанием является сам массив или матрица чисел размером 3x3. Исходная глобальная база данных будет описанием начального состояния задачи. В принципе для описания состояния можно использовать любую структуру данных. Сюда относятся строки символов, векторы, множества, деревья и списки.
Каждый ход преобразует одно состояние задачи в другое. Удобно интерпретировать игру в 8 как игру, в которой имеется 4 хода: передвижение пробела (пустой клетки) налево, вверх, направо и вниз. Эти ходы моделируются правилами продукции, которые соответствующим образом применяются к описаниям состояний. У каждого правила есть предварительные условия, которым должно удовлетворять описание состояния, чтобы правила были применимы к этому описанию состояния. Так, предварительное условие для правила, соответствующего передвижению пробела вверх, вытекает из требования, чтобы пустая клетка уже не находилась в верхнем ряду. (Первоначальное представление игры в 8 может определить 32 правила: передвижение фишки 1 влево, вправо, вверх, вниз, передвижение фишки 2 влево и т.д. Очевидно, что эти правила можно заменить лучшим представлением, использующим перемещение пробела).
В игре 8 необходимо достичь особого состояния задачи, а именно целевого (рис. 3.1). Можно также рассматривать задачи, для которых целью является достижение любого из явно указанных состояний задачи. На языке состояний, ходов и целей решением задачи является последовательность ходов, которая переводит исходное состояние в целевое.
Целевое условие задачи служит основой для терминального условия системы продукций. В соответствии со стратегией управления правила последовательно применяются к описаниям состояний до тех пор, пока не будет получено описание целевого состояния. При этом сохраняется информация о сделанных ходах с тем, чтобы иметь возможность объединить их в последовательность, представляющую решение задачи.
В некоторых задачах на решение накладываются некоторые дополнительные ограничения. Например, можно потребовать, чтобы решение задачи об игре 8 достигалось за минимальное число ходов. В общем случае каждому ходу приписывается цена, а затем ищется решение, имеющее минимальную цену.
Стратегии поиска для систем продукций
Правила вывода и запоминание уже опробованных последовательностей правил и баз данных, порожденных их применением, образуют стратегию управления для систем продукций.
В большинстве приложений ИИ информация, доступная стратегии управления, недостаточна для того, чтобы выбрать наиболее подходящее правило при каждом обращении к множеству правил. Поэтому работу систем продукций можно представить как процесс поиска, в котором правила подвергаются испытанию до тех пор, пока не обнаружится, что некоторая их последовательность порождает базу данных, удовлетворяющую терминальному условию. Эффективные стратегии управления предполагают наличие достаточной информации о решаемой задаче, чтобы то правило, которое будет выбрано из множества правил, с большой вероятностью было наиболее подходящим.
Различают два основных типа стратегий управления, безвозвратный и пробный.
В безвозвратном режиме управления выбирается применимое правило и используется необратимо, без возможности пересмотра в дальнейшем.
В пробном режиме управления выбирается применимое правило (либо произвольно, либо на каком-то разумном основании); это правило используется, но резервируется возможность впоследствии заново вернуться к этой ситуации, чтобы применить другое правило.
Далее, различают два типа пробных режимов управления: с возвращением и с поиском на графе.
В режиме с возвращением, при выборе правила определяется некоторая точка возврата. Если последующие вычисления приведут к трудностям в построении решения, то процесс вычисления переходит к предыдущей точке возврата, где применяется другое правило, и процесс продолжается.
Во втором типе пробного режима, который называют управление с поиском на графе, предусмотрено запоминание результатов применения одновременно нескольких последовательностей правил. Здесь используются различные виды графовых структур и процедур поиска на графе.
Рассмотрим различные режимы управления на примере игры в 8.
Безвозвратный режим.
На первый взгляд может показаться, что безвозвратный режим управления не подходит к системам продукций для решения задач, где требуется процесс поиска. Однако, когда имеется достоверная локальная информация, безвозвратная система продукций может использовать ее для построения явной глобальной информации о решении (не имея исходно явной глобальной информации).
Одним из известных примеров применения локальной информации для построения глобального решения, является алгоритм "подъема на гору", применяемы и при поиске максимума функции. В любой точке необходимо двигаться в направлении наибольшей крутизны (локальная информация), чтобы, в конечном счете, найти максимум функции (глобальная информация). Для определенного класса функций знание направления наиболее крутого подъема достаточно, чтобы найти решение.
Можно применить алгоритм "подъема на гору" в возвратной системе продукций. Для этого необходима некоторая действительная функция, определенная на глобальной базе данных. Стратегия управления использует эту функцию для выбора правила. Она выбирает (безвозвратно) применимое правило, которое порождает базу данных, дающую наибольшее увеличение значения этой функции. Максимальное значение этой функции должно соответствовать той базе данных, которая удовлетворяет терминальному условию.
Применяя алгоритм "подъема на гору" к игре 8, можно использовать в качестве функций от описания состояния число фишек (взятое с отрицательным знаком), находящихся "не на том месте", по сравнению с расположением фишек в описании целевого состояния. Например, значение этой функции для исходного состояния (рис 3.1) равно –4, значение для целевого состояния равно 0.
На рис 3.2 показана последовательность состояний, через которые проходит система продукций, при решении этой задачи. Значение функции "подъема на гору" для описания каждого состояния заключено в кружок.







2
8
3

2
8
3

2

3


2
3

1
2
3

1
2
3
1
6
4

1

4

1
8
4

1
8
4


8
4

8

4
7

5

7
6
5

7
6
5

7
6
5

7
6
5

7
6
5














Из рис 3.2 видно, что одно из применений правил не привело к увеличению значения функции. Если ни одно из применимых правил не обеспечивает увеличение значения функции, то выбирается (произвольно) то правило которое, не уменьшает ее значение. Если таких правил нет, процесс прекращается.
Для конкретного примера игры в 8 стратегия "подъема на гору" позволила найти путь к целевому состоянию. В общем случае подобные функции могут иметь много локальных максимумов, что делает этот метод несостоятельным.
Бывают и другие несостоятельности метода "подъема на гору", например, процесс может попасть на "плато" или "хребет". Этих трудностей можно было бы избежать, если бы удалось построить более удачную функцию "подъема на гору", что не всегда возможно. Таким образом, использование методов "подъема на гору" для управления выбором правила в безвозвратных системах продукций ограничено.
Режим с возвращением
Процесс возвращения является одним из способов построения пробной стратегии. Выбирается некоторое правило и, если оно не ведет к решению, то последующие шаги "забываются", а вместо него выбирается другое правило. С формальной точки зрения стратегию возвращения можно использовать независимо от того, насколько полной информацией для правильного выбора правила мы располагаем. Правила можно выбирать даже произвольно, т.к. в конечном счете, в управлении предусмотрено возвращение, позволяющее выбрать подходящее правило. Очевидно, что наличие достоверной информации о выборе правил сделает процесс решения более эффективным, а возвращения более редкими.
Применим стратегию возвращения к примеру игры в 8. Правила будем выбирать в соответствии с произвольным порядком: передвигать пробел сначала влево, потом вверх, затем направо и вниз. Возвращение будет происходить каждый раз, когда: а) порождается описание состояния, которое уже встречалось на пути к описанию исходного состояния; б) было применено некоторое произвольно выбранное число правил, но описание целевого состояния не было построено или в) более не существует применимых правил.
В случае б) выбранное число представляет собой границу глубины данного процесса с возвращением.
Последовательность подобных применений правил и возвращений к игре в 8 приведена на рис 3.3. Хотя на рисунке не приведен полностью весь процесс поиска решения (граница глубины поиска выбрана 6), решающая последовательность ходов в конце концов будет обнаружена, т.к. будут исследованы все возможные пути. Следует отметить, что если граница глубины установлена слишком малой, то процесс решения может не достичь цели.
Процесс с возвращением будет более эффективным, если выбор правила осуществляется не произвольно, а направляется с помощью информации о том, каким мог бы быть наилучший ход. Например, можно было бы воспользоваться "алгоритмом подъема на гору" для выбора правила. При безвозвратном режиме управления применение этого метода может оказаться несостоятельным, механизм возвращения оставляет возможность для исследования альтернативных путей.























Поиск на графе
Графы (или, более точно, деревья) являются весьма полезными структурами для сохранения информации о результатах применения нескольких последовательностей правил.
Рассмотрим режим управления с поиском на графе при решении игры в 8. Можно запомнить различные примененные правила и соответственно порожденные базы данных с помощью структуры, называемой деревом поиска. Пример такого дерева приведен на рис. 3.4.
Наверху, или в корне дерева находится описание исходной конфигурации. Различные правила, которые здесь можно применить, соответствуют связям или направленным дугам, идущим к вершинам – преемникам, представляющим те состояния, которые можно достичь из исходного состояния за один ход. Стратегия управления с поиском на графе наращивает такое дерево до тех пор, пока не будет порождена база данных, удовлетворяющая терминальному условию.
На рис 3.4 показаны все возможные здесь правила, примененные к каждому описанию состояния. Это обуславливает чрезвычайную неэффективность системы управления, поскольку результирующее дерево растет слишком быстро. Можно было бы построить гораздо более узкое дерево, если использовать некоторые специфические для задачи знания, чтобы сфокусировать его рост в направлении, более близком к цели.
Если при построении дерева поиска не используется никакая эвристическая информация об области задачи, то процедура поиска называется неинформированной.
Методы без информации дают решение задачи, но в процессе поиска создается слишком много вершин. Поскольку на практике всегда существуют ограничения на время и память для реализации процесса поиска, эти методы являются весьма неэффективными.
Информацию о задаче, которая позволяет сократить поиск решения, называют эвристической, а процедуры поиска использующие ее – методами эвристического поиска. Эвристическая информация используется таким образом, чтобы процесс поиска распространялся только по наиболее перспективным направлениям. Для вычисления "перспективности" вершин можно применить, например, метод использования оценочной функции.
Обозначим оценочную функцию символом f. Тогда f(n) дает значение этой функции в вершине дерева поиска n. В качестве примера рассмотрим использование оценочной функции для упорядочивания вершин при построении дерева поиска для игры в 8. Будем считать, что вершина с меньшей оценкой с большей вероятностью окажется на оптимальном пути. В качестве такой оценочной функции возьмем выражение
f(n) = d(n) + W(n)
где d(n) –глубина вершины n на дереве поиска и W(n) – число находящихся на нужном месте клеток в базе данных, связанной с вершиной n (рис 3.5). Таким образом конфигурация исходной вершины дает значение f = 0 + 4 = 4.

Результаты применения оценочной функции приведены на рис 3.5. Значение f для каждой вершины заключены в кружок. Видно, что найден тот же решающий путь, что и при полном поиске на графе (рис 3.4), но использование оценочной функции позволило раскрыть значительно меньше вершин.
Результаты поиска в значительной степени определяются выбором оценочной функции.
Таким образом, использование эвристической информации может существенно уменьшить объем поисковой работы, требуемой для обнаружения приемлемых путей.
Выбор стратегии управления
Важной характеристикой вычислительного процесса для выбора правил является объем имеющейся информации или "знаний" о задаче, который используется при вычислениях. В ситуации полной неинформированности выбор делается абсолютно произвольно, без учета какой-либо имеющейся о данной задаче информации. В ситуации полной информированности стратегия управления руководствуется достаточно полным знанием, чтобы каждый раз выбрать "верное" правило.
В целом вычислительная эффективность системы продукций зависит от того, в каком положении между этими двумя крайними случаями находится данная стратегия управления.
Можно разделить вычислительные затраты в системе продукций на две глобальные категории: а) затраты на применение правил (стоимость пути к цели) и б) затраты на управление (стоимость поиска правила необходимого для нахождения этого пути).
Полностью неинформированная система управления несет небольшие расходы по пункту б), но это приводит к существенному увеличению расходов по пункту а). Полная информация о решаемой задачи дает обратное распределение расходов. Эти тенденции отражены на рис 3.6. В большинстве практических задач стремятся к тому, чтобы минимизировать некоторую комбинацию стоимости пути к цели (применений правил) и стоимости поиска, необходимого для нахождения этого пути (управления), усредненную по всем ожидаемым задачам.
Обратные и двухсторонние системы продукций
Система продукций для решения игры в 8 при всех рассмотренных режимах управления работает непосредственно от исходного состояния к целевому, т.е. в прямом направлении и ее можно назвать прямой системой продукций.
Эта задача могла бы быть решена и в обратном направлении – продвижением от целевого состояния к исходному и с применением обратных ходов. Каждый ход породил бы подцелевое состояние, из которого непосредственно первоочередное целевое состояние можно достичь за один ход вперед. Система продукций для решения игры в 8 таким способом просто изменила бы назначения состояний и целей и использовала бы правила, соответствующие обратным ходам.
Хотя между системами продукций, работающими над решением задачи в прямом и обратном направлениях, нет формального различия, часто оказывается удобным ввести его в явном виде
Если в задаче можно выделить четкие на интуитивном уровне, состояния и цели и если принято решение пользоваться описаниями этих состояний как глобальной базой данных системы продукций, эту систему называют прямой системой продукций. Правила применяются к описаниям состояний для порождения новых состояний, и эти правила называются П - правилами. Наоборот, если используются описания целей задачи как глобальная база данных, система называется обратной системой продукций. Тогда правила применяются к описаниям целей для порождения описания подцелей, и эти правила называются О-правилами. Наиболее эффективное направление решения определяется структурой пространства состояний. (Для игры в 8 начальное и целевое состояния единственны и направление решения не имеет существенного значения)
Часто удачной является попытка решить задачу путем двустороннего поиска – одновременно в прямом и обратном направлении. Для этого в глобальную базу данных включают описания как состояний, так и целей. К части описания состояний применяются П – правила, а к части описания целей – О-правила. При поиске такого типа терминальное условие для управляющей системы, которое позволяет сделать вывод о том, что задача решена, должно быть определено как разновидность условия соответствия между частью описания состояний и частью описания цели в глобальной базе данных. Управляющая система должна также на каждой стадии принимать решения об использовании П- либо О-правила.
Специализированные системы продукций
Коммутативные системы продукций
При определенных условиях порядок, в котором множество применимых правил используется в базе данных, несущественен. Когда эти условия выполняются, эффективность работы системы продукций можно повысить, отказываясь от исследования излишних путей решения, эквивалентных во всем, кроме очередности правил.
Система продукций коммутативна, если она обладает следующими свойствами по отношению к любой базе данных D:
а) Каждое из множества правил, применимое к D, применимо к любой базе данных, полученной при использовании любого применимого правила к D.
б) Если целевое условие удовлетворяется базой D, то оно также удовлетворяется любой базой данных, полученной при использовании любого применимого правила к D.
в) База данных, полученная в результате применения к D любой последовательности применимых к D правил, инвариантна относительно перестановок к этой последовательности.
На рис 3.7 рассматриваются три правила – П1, П2 и П3, - которые применимы к базе данных SO. После использования правил каждое по-прежнему является применимым к результирующим базам данных; после использования двух правил подряд все три остаются применимыми. Одна и та же база SG формируется независимо от последовательности применения правил из множества {П1, П2, П3}.
Процесс применения правил, показанный на рис 3.7 коммутативен. При получении базы SG, очевидно, следует рассмотреть только один из многих приведенных путей. Методы исключения из рассмотрения избыточных путей являются важными для коммутативных систем.
Коммутативность системы не означает, что всю последовательность правил использованных для преобразования исходной базы данных в базу, удовлетворяющую определенному условию, можно переупорядочить. После того, как некоторое правило было применено к базе данных, применимыми могут стать дополнительные правила. Только те правила, которые изначально применимы к базе данных, можно объединить в произвольную последовательность и применить к этой базе, чтобы получить результат, не зависящий от порядка.
Коммутативные системы продукций являются важным подклассом, обладающим особыми свойствами. В них всегда можно использовать безвозвратный режим управления, поскольку применение правила никогда не приводит к необходимости его отмены. Любое правило, которое было применимо к возникавшей ранее базе данных, применимо и к имеющейся в настоящий момент. Нет необходимости вводить механизм применения различных последовательностей правил. Применение неудачного правила отодвигает, но не делает невозможным завершение процесса. После решения задачи можно удалить лишние правила из решающей последовательности.
Существует простой способ преобразования любой системы продукций в коммутативную. Использование этого преобразования приводит к более сложной глобальной базе данных и множеству правил, но допускает более простой режим управления (безвозвратный). Это изменение представления просто переводит систему на более низкий уровень. Например, существует представление задачи для решения с помощью системы продукций. Пусть в системе имеются глобальная база данных, правила и стратегия управления с поиском на графе, которая порождает дерево поиска глобальных баз данных. Рассмотрим другую систему продукций, глобальной базой данных которой является полное дерево поиска первой. Правила новой системы продукций представляют собой различные способы, позволяющие преобразовывать дерево поиска с помощью стратегии управления первой системы продукций. Очевидно, что любые правила второй системы, применимые на любом этапе, остаются применимы и в дальнейшем. Коммутативные свойства второй системы явным образом реализуют недетерминированную возможность проб в стратегии управления первой системы.
Разложимые системы продукций
Коммутативность – не единственное условие, выполнение которого дает определенную свободу выбора очередности применяемых правил.
Рассмотрим систему с исходной базой данных (C, B, Z), правила продукций которой основаны на следующих правилах переписывания.
П1: C  (D, L); П2: C  (B, M); П3: B  (M, M); П4: Z  (B, B, M),
а терминальное условие состоит в том, что эта база данных должна содержать только символ M.
В режиме управления с поиском на графе можно было бы исследовать много эквивалентных путей, получения базы данных, содержащей только M. Избежать рассмотрения лишних путей можно, если заметить, что исходная база данных может быть разбита на отдельные компоненты, которые можно обрабатывать независимо. Исходная база данных разлагается на составляющие C, B и Z. Правила продукций применимы независимо к каждой составляющей (возможно, параллельно). Результаты этих операций также подвергаются декомпозиции и так далее, пока каждая компонента базы данных не будет содержать только символы M.
В системах ИИ базы данных часто допускают подобное разбиение. Каждое применение правил воздействует только на ту компоненту глобальной базы данных, которая используется для проверки выполнения соответствующего предварительного условия этого правила. Поскольку некоторые из правил применяются, по существу, параллельно, их порядок не имеет значения.
Чтобы разложить базу данных, необходимо уметь разложить и соответствующее терминальное условие. Если каждая составляющая обрабатывается отдельно, то и глобальное терминальное условие должно быть выражено через терминальные условия каждой составляющей. Наиболее важным является случай, когда глобальное терминальное условие можно выразить как конъюнкцию того же терминального условия для каждой составляющей баз данных.
Системы продукций, глобальные базы данных и терминальные условия которых допускают декомпозицию, называются разложимыми.
Хотя возможна параллельная обработка составляющих баз данных, обычно ищется стратегия управления, которая обрабатывает их в некотором последовательном порядке. Существует два основных способа упорядочивания этих компонент: а) расположить их в каком-то жестком порядке в момент их порождения, или б) динамически переупорядочивать их в ходе обработки. В первом случае полностью обрабатывается каждая составляющая и только после этого обрабатывается следующая. При обработке составляющей может возникнуть база, которую также можно разложить. Компоненты этой базы данных также обрабатываются по очереди. Обычно для отбора правил используется стратегия с возвращением совместно со стратегией жесткого упорядочивания для обработки компонент.
Графы И/ИЛИ
Более гибкие стратегии управления для разложимых систем продукций допускают динамическое упорядочивание составляющих баз данных в ходе обработки. Для описания работы систем продукций в таком режиме удобно пользоваться структурами, которые называются графами И/ИЛИ. На рис 3.8 приведен пример дерева типа И/ИЛИ для задачи переписывания, описанной в разделе 3.4.2.
Как и в случае обычных графов, граф типа И/ИЛИ состоит из вершин, помеченных глобальными базами данных. Вершины, помеченные составными базами данных, имеют множество вершин преемников, каждая из которых помечена одной из составляющих. Эти вершины преемники называются вершинами типа И, так как для полной обработки составной базы данных должны быть обработаны полностью все ее составляющие. Множество вершин типа И на рис 3.8 обозначаются дугой, объединяющей входящие в них дуги графа, которая называется k-связкой (k – число вершин преемников).
К составляющим базам данных можно применять правила. Вершины, помеченные этими составляющими базами данных, имеют вершины преемники, которые помечены базами, полученными в результате применения правил. Эти вершины – преемники называют вершинами типа ИЛИ, поскольку для полной обработки составляющей базы данных полностьюдолжна быть обработана база данных, порожденная в результате применения лишь одного из правил.
На рис 3.8 все вершины, соответствующие какой – либо составляющей базе данных, которая удовлетворяет терминальному условию, заключены в двойную рамку. Такие вершины называются терминальными.
Системы дедукции на основе правил
Дедукция (от латинского deductio - выведение), вывод по правилам логики. Системы, которые рассматриваются в этой главе используют ППФ в форме, близкой к первоначальному виду. Правильно построенные формулы, представляющие знания в виде утверждений, относящихся к некоторой проблеме, разделяются на две категории: правила и факты. Правила состоят из утверждений в форме импликаций. Обычно они выражают общие знания о конкретной предметной области и используются в качестве порождающих правил. Факты – это утверждения, которые не выражаются в форме импликаций; они представляют специфические знания, относящиеся к конкретному случаю. Задачей систем продукций, обсуждаемых в данной главе, является доказательство целевой ППФ исходя из этих фактов и правил.
Этот тип систем доказательства теорем является примером непосредственного доказательства. Система непосредственного доказательства не обязательно является более эффективной по сравнению с системой опровержения, но ее действие легче воспринимается на интуитивном уровне. Системы такого типа называют системами дедукции, основанными на правилах.
Импликационные ППФ
Способ, которым эксперт выражает некоторую совокупность знаний о данной области, часто содержит важную информацию о том, как можно использовать эти знания.
Например известно, что "если x > 0 и y > 0, то x  y > 0". На языке предикатов это утверждение выглядит так:
(x) ( y) ((G(x, 0)  G(y, 0))  G(times(x, y), 0),
где G – предикат, означающий "больше", times – функция, означающая "произведение".
Но это утверждение может быть представлено и совершенно эквивалентной формулировкой
(x) (y) ((G(x, 0)  G(times(x, y), 0)  G(y, 0).
Логическое содержание математического выражения остается тем же, хотя его можно представить множеством эквивалентных предикатных формул. Но конкретная формулировка на естественном языке часто несет эвристическую управляющую информацию.
Большая часть знаний, используемых в системах ИИ, непосредственно представима импликационными выражениями.
Если преобразовывать подобные выражения в форму предложений (как при использовании резолюции), то можно потерять полезную управляющую информацию, содержащуюся в заданной импликационной форме.
Применение импликационных ППФ в качестве правил в системе продукций позволяет системе делать логический вывод, применяя порождающие правила к глобальной базе данных. Каждый вывод может опираться в данный момент на одну ППФ, являющуюся правилом. Это ограничение выгодным образом влияет на эффективность системы.
Прямая система дедукции
Форма И/ИЛИ для выражения фактов
Прямая система в качестве начальной глобальной базы данных содержит факты, представленные как ППФ исчисления предикатов и преобразованные в безимпликационную форму, называемой формой И/ИЛИ. При преобразовании ППФ в форму И/ИЛИ исключаются символы импликации, символы отрицания вносятся вглубь формулы так, чтобы область их действия была ограниченна одним предикатом. Результирующее выражение затем подвергается сколемовским преобразованиям и переводится в префиксную форму, переменные в пределах действия кванторов общности разделяются переименованием, переменные, относящиеся к кванторам существования, заменяются сколемовскими функциями и кванторы общности опускаются. Полученное в результате преобразований выражение в форме И/ИЛИ состоит из подвыражений литералов, соединенных символами  и . Выражение в форме И/ИЛИ не является предложением (в отличие от результатов преобразований, описанных в разделе 2.6) и его подвыражения не "размножаются".
Граф И/ИЛИ для представления выражений для фактов
Выражение для факта в форме И/ИЛИ может быть представлено с помощью графа типа И/ИЛИ. На рис. 4.1 приведено дерево типа И/ИЛИ для факта, преобразованного к форме И/ИЛИ. Каждое подвыражение выражения для факта представляется вершиной графа. Дизъюнктивно связанные подвыражения для факта представляются нисходящими вершинами, связанными с их родительской вершиной k-связкой. Каждое конъюнктивное подвыражение представляется одной нисходящей вершиной, связанной с родительской вершиной односвязкой (1 – связкой). (Объяснение той ситуации, что конъюнктивное понятие, т.е. k-связка, используется для разделения дизъюнкций в выражении для факта, будет приведено ниже.) Концевые вершины представления в виде графа И/ИЛИ для некоторого факта помечаются литералами, встречающимися в выражении для факта. Вершину, помеченную всем выражением для факта, называют корневой; в графе у нее нет предшествующих вершин.

















Интересно показать, что множество предложений, в которое можно преобразовать ППФ, находящуюся в корневой вершине, можно прочитать как множество графов решения, заканчивающихся в корневых вершинах.
Так предложения, соответствующие выражению Q(, A)  ((R()  P())  S(A, )), имеют вид:
Q(, A),
S(A, )  R(),
S(A, )  P().
Каждое предложение можно получить как дизъюнкцию литералов в концевых вершинах одного из графов решения на рис. 4.1.
Следует отметить, что в настоящей главе графы И/ИЛИ используются для других целей, чем в разделе 3.4.3. Там графы И/ИЛИ были представлениями для управляющей стратегии, направляющей работу систем продукций, допускающих декомпозицию. Здесь же они применяются в качестве форм представления для глобальной базы данных системы продукций.
Использование правил для преобразования графов типа И/ИЛИ
Порождающие правила, используемые прямой системой продукций применяются к графовым структурам типа И/ИЛИ, чтобы получить преобразованную графовую структуру. Эти правила основываются на импликационных ППФ, которые представляют общие знания или утверждения в предметной области. В качестве правил будем рассматривать только импликации вида L  W, где L (левая часть правила или антецедент) – одиночный литерал, а W (правая часть правила или консеквент) – произвольная ППФ. Все переменные в этой импликации считаются относящимися к квантору общности, который охватывает всю импликацию в целом.
Переменные в фактах и правилах разнесены так, чтобы одна переменная встречалась не более чем в одном правиле и чтобы переменные в правилах были отличны от переменных в фактах.
Ограничение однолитеральным антецедентом существенно упрощает процесс сопоставления при применении правил к графам И/ИЛИ, но не вызывает никаких практических ограничений в использовании правил. Импликации, содержащие дизъюнкции литералов в левой части, могут быть переписаны, как совокупность правил. Например, (L1  L2)  W эквивалентна паре правил L1  W и L2  W.
Любая импликация с однолитеральным антецедентом может быть приведена к форме, в которой область квантификации – вся импликация. Для этого необходимо совершить преобразования к форме И/ИЛИ, описанные в разделе 4.2.1 и затем восстановить импликацию.
Чтобы объяснить, как такие правила применяются к графам И/ИЛИ, рассмотрим вначале случай перепозиционального исчисления без переменных.
Правило вида L  W может быть применено к любому графу И/ИЛИ, имеющему концевую вершину n, помеченную литералом L. Результатом является новый граф И/ИЛИ, в котором вершина n теперь имеет отходящую односвязку, к некоторой дочерней вершине (также помеченной L), являющейся корневой вершиной графовой структуры И/ИЛИ, представляющей W.
Пусть имеется правило S  (X  Y)  Z и факт ((P  Q)  R)  (S  (T  U)). Построим граф И/ИЛИ для факта и применим к нему правило.
Правило можно применить к концевой вершине графа И/ИЛИ для факта, помеченной S. Результатом является графовая структура, приведенная на рис. 4.2. Две вершины, помеченные S (для факта и для правила) соединены дугой, которая называется дугой соответствия.


До применения правила граф И/ИЛИ представлял некоторое выражение для конкретного факта. Его множество графов решения, заканчивающихся в концевых вершинах, представляло собой выражение для факта в виде предложений.
Результирующий после применения правила граф (рис 4.2) представляет собой и первоначальный факт, и выражение для факта, выводимого из первоначального и рассматриваемого правила.
При использовании правила L  W для преобразования представления F(L) для факта в виде графа И/ИЛИ описанным способом создается новый граф, содержащий представление для F(W). Множество решающих графов, оканчивающихся в концевых вершинах этого графа, представляет множество предложений для F(W) в форме предложений. Это множество предложений включает все множество, которое было бы создано путем выполнения всех возможных резолюций на L между L  W в форме предложений и F(L) в форме предложений .
Для нашего примера форма предложений для правила: S  X  Z и S  Y  Z. Те предложения в выражении для факта, взятом в форме предложений, которые разрешились бы на S при любом из этих двух правил имеют вид P  Q  S и R  S. Полное множество резольвент, которое может быть получено из этих четырех предложений разрешением на S, таково:
X  Z  P  Q; Y  Z  P  Q; R  Y  Z; R  X  Z.
Все они включены в число предложений, представленных графами решения на рис. 4.2.
Таким образом, применение правила к графу И/ИЛИ реализует очень экономично тот вывод, который иначе потребовал бы нескольких резолюций.
После применения правила к некоторой вершине, она перестает быть концевой вершиной графа, но остается однолитеральной и к ней можно продолжать применять правила. Вершину графа, помеченную одиночным литералом, называют литеральной. Множество предложений, представляемых графом И/ИЛИ, соответствует множеству решающих графов, заканчивающихся в литеральных вершинах.
Использование целевой ППФ для остановки
Задачей прямой системы продукций является доказательство некоторой целевой ППФ на основе ППФ для факта и множества правил. В этой системе имеется ограничение на тип целевого выражения, которое она способна доказать, а именно она способна доказать только такие целевые ППФ, которые являются дизъюнкцией литералов.
Целевые литералы, также как и правила, могут быть использованы для наращивания графа И/ИЛИ. Когда один из целевых литералов соответствует литеральной пометке для некоторой литеральной вершины n графа, то с вершиной n связывают новую вершину, помеченную этим сопоставимым целевым литералом. Этот потомок называется целевой вершиной. Целевые вершины соединяются дугами соответствия со своими родительскими вершинами. Система продукций успешно заканчивает работу, если создает граф И/ИЛИ, содержащий граф решения, заканчивающийся в целевых вершинах.
На рис. 4.3. показан граф И/ИЛИ, который удовлетворяет условию остановки, основанному на целевой ППФ вида (C  G).
Потомки вершины (A  B) соединяются с ней двусвязкой. Таким образом, оба потомка должны встретится в окончательном графе решения, что и происходит. В этом и заложено основание для использования k-связок при разделении дизъюнктивно связанных подвыражений в фактах. Если некоторый граф решения для вершины n включает какого-либо потомка вершины n через некоторую k-связку, то он должен включать всех потомков, связанных этой k-связкой.
Описанная система продукций, основываясь на применении правил к графам И/ИЛИ коммутативна и, следовательно, позволяет использовать безвозвратный режим управления. Система продолжает применять применимые правила до тех пор, пока не будет получен граф И/ИЛИ, содержащий некоторый граф решения.
Выражения, содержащие переменные
Рассмотрим прямые системы продукций, работающие с выражениями, содержащими переменные.






















Пусть правило вида L  W применяется к графу И/ИЛИ, где L – некоторый литерал, а W – ППФ в виде И/ИЛИ, причем все выражения могут содержать переменные. Данное правило применимо, если граф И/ИЛИ содержит литеральную вершину L, унифицируемую с L. Предположим, что соответствующий НОУ есть U. Тогда применение правила приводит к наращиванию графа путем образования дуги соответствия, направленной от вершины L графа И/ИЛИ, представляющего WU. Дуга соответствия также помечается НОУ, т.е. U.
Рассмотрим применение правила P(A, B)  (S(A)  T(B)) к факту (P(x, y)  (Q(x, A)  R(B, y))). Представив этот факт графом И/ИЛИ и применив к этому графу правило, получим новый граф И/ИЛИ, изображенный на рис. 4.4. Этот граф имеет два графа решения, которые заканчиваются в концевых вершинах и включают вновь добавленную дугу соответствия. Предложения, соответствующие полученным графам решения, таковы: S(A)  T(B)  Q(A, A) и S(A)  T(B)  R(B, B).
При построении этих предложений был применен наш НОУ U к литералам, появляющемся в концевых вершинах графа решения. Эти предложения могли бы быть получены из факта и правила в форме предложений при выполнении резолюции на P.
После применения к графу И/ИЛИ нескольких правил он содержит более одной дуги соответствия. При выделении множества предложений в таком графе учитываются только те графы решения, которые заканчиваются в литеральных вершинах, имеющих согласованные подстановки на дугах соответствия. Предложение, представленное согласованным графом решения, получается специальной подстановкой, называемой унифицирующей композицией, к дизъюнкции литералов, помечающих терминальные вершины.

















Понятие унифицирующей композиции подстановок определяется следующим образом. Пусть имеется некоторое множество подстановок {u1, u2, … , un}, где каждое ui есть множество пар
ui = {ti1/i1, ti2/i2, … , tim(i)/ im(i)}, t – обозначает термы, а  - переменные. Определим исходя из {u1, u2, … , un} два выражения:
U1 = (11, … , 1m(1), … , n1, … , nm(n));
U2 = (t11, … , t1m(1), … , tn1, … , tnm(n)).
Подстановки {u1, u2, … , un} называются согласованными, когда U1 и U2 унифицируемы, а унифицирующей композицией U называется НОУ для U1 и U2.
Некоторые примеры унифицирующих композиций приведены в таблице 4.1.

Таблица 4.1

U1
U2
U
{A/x}
{B/x}
Не согласованны
{x/y}
{y/z}
{x/y, x/z}
{f(z)/x}
{f(A)/x}
{f(A)/x, A/z}
{x/y, x/z}
{A/z}
{A/x, A/y, A/z}
{g(y)/x}
{f(x)/y}
Не согласованны
{f(g(x1))/x3, f(x2)/x4}
{x4/x3, g(x1)/x2}
{f(g(x1))/x3, f(g(x1))/x4, g(x1)/x2}

Операция, соответствующая унифицирующей композиции, ассоциативна и коммутативна, поэтому унифицирующая композиция не зависит от порядка, в котором генерируются дуги соответствия.
Если одно и то же правило применяется более одного раза, то важно, чтобы при каждом случае использовались переименованные переменные. Иначе можно без необходимости наложить дополнительные ограничения на подстановки.
Процесс надстраивания графа И/ИЛИ с применением правил или целевых литералов заканчивается успешно, когда создается согласованный граф решения, имеющий целевые вершины в качестве всех своих терминальных вершин. В этом случае система продукций дает доказательство того, что целевая дизъюнкция получается применением унифицирующей композиции окончательного графа решения к дизъюнкции литералов в целевых вершинах этого графа.
Обратные системы продукций
Целевые выражения в форме И/ИЛИ
Обратная система продукций способна работать с целевыми выражениями произвольного вида. Целевая ППФ преобразуется в форму И/ИЛИ с помощью тех же процедур, которые применялись для факта в разделе 4.2.1.
После этого целевые ППФ в форме И/ИЛИ могут быть представлены графами И/ИЛИ. Но в случае целевых выражений k-связки в этих графах используются для разделения конъюнктивно связанных подвыражений.
Пусть имеется целевая ППФ в форме И/ИЛИ P(f(z))  (Q(f(y), y)  (R(f(y))  S(y))). Граф И/ИЛИ для этой целевой ППФ приведен на рис. 4.5.
















Концевые вершины этого графа помечены целевыми литералами. В целевых графах И/ИЛИ любая вершина, дочерняя по отношению к корневой, называется вершиной подцели, а выражения, помечающие такие дочерние вершины – подцелями.
Множество предложений для представления целевой ППФ в виде предложений может быть "считано" с множества графов решения, оканчивающихся в концевых вершинах (рис. 4.5):
P(f(z)),
Q(f(y), y)  R(f(y)),
Q(f(y),y)  S(y).
Целевые предложения являются конъюнкциями литералов, а диъюнкция этих предложений – формой предложений для целевой ППФ.
Применение правил в обратной системе
В обратной системе О-правила основываются на импликациях, содержащихся в утверждениях, также как и П-правила в прямой системе. Для О-правил вводится ограничение вида W  L, где W – любая ППФ (по предположению в форме И/ИЛИ), а L – литерал; областью квантификации для любой переменной является целиком вся импликация. Ограничение О-правилами такой формы упрощает поиск соответствий и не вызывает никаких важных практических трудностей. К тому же импликация вида W  (L1  L2) может быть преобразована в правила W  L1, W  L2.
Такое О-правило применимо к графу типа И/ИЛИ, представляющему некоторую целевую ППФ, если граф содержит литеральную вершину L, которая унифицируется с L. Результат применения правила состоит в том, что дуга соответствия из вершины L добавляется к новой дочерней вершине L. Эта новая вершина является корневой вершиной представления WU в виде графа И/ИЛИ, где U – НОУ для L и L, который помечает дугу соответствия.
Условие остановки
Выражения для фактов, используемых обратной системой, ограничены выражениями в форме конъюнкции литералов. Такие выражения могут быть представлены как некоторое множество литералов. Когда литерал, отвечающий факту, соответствует некоторой литеральной вершине графа, дочерняя вершина факта может быть добавлена к этому графу. Эта вершина факта связанна с соответствующей ей литеральной вершиной подцели с помощью дуги соответствия, помеченной НОУ. Один и тот же литерал факта может быть использован несколько раз, но с различными переменными при каждом использовании, что приведет к созданию кратных вершин факта.
Условие успешного завершения работы для обратной системы состоит в том, что граф типа И/ИЛИ должен содержать согласованный граф решения, заканчивающийся в вершинах фактов.
Рассмотрим пример работы обратной системы. Пусть имеются следующие факты:
собака (Джим),
лает (Джим),
виляет-хвостом (Джим),
мяукает (Мурка).
И пусть используются следующие правила:
П1: (виляет-хвостом(x1)  собака(x1))  ласкается(x1)
П2: (ласкается(x2)  лает(x2))  боится(y2, x2)
П3: собака(x3)  животное(x3)
П4: кошка(x4)  животное(x4)
П5: мяукает(x5)  кошка(x5)
Требуется ответить на вопрос: существуют ли кошка и собака такие, что кошка не боится собаки?
Целевое выражение имеет вид:
(x)(y)(кошка(x)  собака(y)  боится(x, y))
Согласованный граф решения для этой задачи показан на рис. 4.6.
Вершины фактов заключены в двойные рамки, а применение правил помечено их номерами. Для проверки согласованности графа решения нужно найти унифицирующую композицию для всех подстановок на дугах соответствия: {x/x5}; {Мурка/x}; {Джим/y}; {Джим/y}; {Джим/y}; {x/y2, y/x2}; {y/x1}. Результатом будет {Мурка/x5, Мурка/x, Джим/y, Мурка/y2, Джим/x2, Джим/x1}.
Применяя унифицирующую композицию к целевому выражению, получаем ответное утверждение: (кошка(Мурка)  собака(Джим)  боится(Мурка, Джим)).
Стратегии управления для систем дедукции
Для управления поиском согласованного графа решения можно использовать различные приемы. Рассмотрим два из них на примере обратной системы, но они могут быть приложимы и к прямой системе.
Стратегия управления для обратной системы дедукции может быть основана на попытке обнаружения согласованного графа путем поиска любого графа решения с последующей проверкой на согласованность.
При применении более тонкой стратегии проверка на согласованность ведется по частям, по мере построения графов-кандидатов до нахождения полного графа решения. Иногда несогласованность становится очевидной достаточно рано и несогласованные частичные графы решения могут быть сразу отброшены, что уменьшает объем перебора.
Пусть необходимо доказать цель P(x)  Q(x). Фактами являются R(A) и Q(A), а правила имеют вид П1: R(y)  P(y); П2: S(z)  P(B).
Граф И/ИЛИ для решения этой задачи приведен на рис. 4.7. Здесь видны два графа решения, являющиеся кандидатами. В одном имеется подстановка {x/y; A/x}, в другом – {B/x; A/x}. Последняя не является согласованной. И если Q(A) является единственной парой, соответствующей Q(x), то очевидно, что П2 не может быть частью какого-либо решения. Следовательно, обнаружение несогласованности на ранних этапах процесса поиска может позволить урезать ветвь графа И/ИЛИ. Так в графе на рис. 4.7 нет смысла генерировать подцели для S(z).
Другая стратегия управления для обратной системы дедукции связана с построением графа связи правил. При этом определяются все возможные соответствия между правилами и запоминаются результирующие подстановки. Такая оценка выполняется до решения какой-либо конкретной проблемы с помощью этих правил. Такой процесс полезен на практике, если множество правил не слишком велико.
На рис. 4.8 приведен пример графа связи правил для примера, приведенного на рис. 4.6. При построении графа каждое правило записывается в виде графа И/ИЛИ с последующим соединением дугами соответствия литералов в антецедентах правил со всеми консеквентами, соответствующими правилу. Дуги соответствия помечаются соответствующими НОУ.
Для решения конкретной задачи можно связать целевой граф И/ИЛИ и вершины фактов с графом связи правил (целевые вершины – с консеквентами

правил, вершины фактов – с антецедентами). Увеличенный граф связи правил просматривают, чтобы найти графы – кандидаты на решение. Если такой кандидат найден и существует унифицирующая композиция подстановок для этого графа, то задача является решенной. В противном случае в пределах графа связи правил следует взять другой граф – кандидат на решение.

"Резолюция" внутри графов И/ИЛИ
Обратная система не в состоянии доказывать тавтологические целевые выражения вида (P  P). Точно так же прямая система не способна распознавать противоречивые выражения для фактов, такие как (P  P).
Чтобы преодолеть эти недостатки, системы должны иметь возможность делать логические выводы "внутри" цели или факта.
Рассмотрим следующие выражения для обратной системы:
Цель: (P(x, y)  Q(x, y))  V(x, y)
Правила: П1(R()  S(u, B))  P(u, )
П2 (S(A, q)  W(r))  Q(r, q)
Факты: R(B)  W(B)  V(A, B)  V(B, B)
После применений правил П1 и П2 получаем граф И/ИЛИ. Этот граф имеет два дополнительных литерала, предикаты которых унифицируются с НОУ вида {A/x; B/y} – рис. 4.9. Это соответствие показано с помощью ребра, соединяющего вершины, представляющие дополнительные литералы, ребро помечено указанным НОУ.

Форма предложений для целевых выражений, представляемых графом И/ИЛИ включает предложения:
V(x, y)  R(y)  S(x, B); V(x, y)  W(x)  S(A, y)
Если бы мы выполнили целевую резолюцию на S между этими двумя предложениями, то после разделения переменных получили бы следующую целевую резольвенту:
V(A, y)  R(y)  V(t, B)  W(t).
Представление выражения графом И/ИЛИ является менее общим, чем представление в виде предложений, поскольку переменные в графе не могут быть полностью разделены. Это ограничение не позволяет в общем случае представить выражения, которые могут быть получены при применении резолюции в целевых подвыражениях.
Одним из способов представления операции резолюции, выполняемой между двумя целевыми предложениями, является соединение литерала в одном частичном графе решения с дополнительным литералом в другом (как на рис. 4.9). Принимается, что эта связанная структура представляет предложения, составленные из литеральных вершин в парах всех графов решения, заканчивающихся в литеральных вершинах и соединенных таким образом. С таким спаренным графом решения ассоциируется подстановка, являющаяся унифицирующей композицией подстановок в каждом члене пары плюс подстановка, связанная с сопоставлением дополнительных литералов.
Таким образом, структура на рис. 4.9 включает определенное представление для предложения R(B)  W(A)  V(A, B). Это предложение не является таким общим, как то, что было получено посредством целевой резолюции между предложениями цели (при полном разделении переменных). Такое ограничение общности может помешать найти некоторые доказательства. Так, например, выражение R(B)  W(A)  V(A, B) не может быть доказано исходя из заданных фактов, а выражение V(A, y)  R(y)  V(t, B)  W(t) – может быть доказано. Поэтому операцию сопоставления дополнительных пар литералов в графах И/ИЛИ называют ограниченной целевой резолюцией (ОЦР).
Чтобы использовать ОЦР в обратных системах, необходимо модифицировать условие остановки. Для этого делается предположение, что литералы соединенные ребром соответствия ОЦР, являются терминальными вершинами. Пара соединенных таким образом частичных графов решения составляет решение – кандидат, если все остальные вершины являются терминальными. Такой предполагаемый граф решения является окончательным, если связанная с ним подстановка является согласованной.
В примере на рис. 4.9 сопоставление остающихся нетерминальных вершин с фактами не дает согласованного графа решения. Очевидно, для этого требуется большая степень общности, чем та, что может быть получена применением ОЦР к целевому выражению в виде графа И/ИЛИ.
Требуемая общность может быть получена, если представить заданное целевое выражение в виде предложений с разделением переменных
(P(x1, y1)  V(x1, y1))  (Q(x2, y2)  V(x2, y2)).
Если представить это выражение графом И/ИЛИ и применить к нему правила и ОЦР, то можно получить согласованный граф решения.
Комбинация прямой и обратной системы
И прямая, и обратная системы дедукции, основанные на правилах, имеют ограничения. Обратная система способна обрабатывать целевые выражения произвольного вида, но выражения для фактов должны состоять из конъюнкций литералов. Прямая система способна обрабатывать выражения для фактов произвольного вида, но целевые выражения должны состоять из дизъюнкций литералов. Эти системы можно объединить в одну, обладающую достоинствами обеих, но не имеющую присущих им недостатков.
Глобальная база данных такой комбинированной системы состоит из двух структур графов И/ИЛИ, одна из которых представляет цели, а другая факты. Сначала эти структуры представляют заданные выражения для цели и факта, вид которых теперь ничем не ограничен. Структуры модифицируются О- и П- правилами. При этом вопрос о том, какие правила будут работать над графом фактов, а какие – над графом целей, решает конструктор системы.
Хотя правила и называются О- и П- правилами, новая система продукций работает в одном направлении, модифицируя состоящую из двух частей глобальную базу данных. При этом О-правило по-прежнему должно иметь однолитеральные консеквенты, а П-правило – антецеденты.
Остановка процедуры должна быть связана с согласованием этих двух графовых структур, которые могут быть объединены дугами соответствия между вершинами, помеченными унифицируемыми литералами. В начальных графах дуги соответствия между графами целей и фактов должны связывать соответствующие концевые вершины. После расширения графов применением правил такие сопоставления могут иметь место в любой литеральной вершине.
Процедура должна обрываться только тогда, когда будут доказаны выражения, стоящие в корневых вершинах графа факта и графа цели (или когда будет получено заключение, что такое доказательство не может быть найдено при заданных ограничениях на ресурсы). Одно из возможных простых условий остановки основывается на симметричном отношении гашение между вершиной факта и вершиной цели. Гашение определяется рекурсивно следующим образом.
Две вершины n и m находятся в отношении гашение друг с другом, если одна из них является вершиной для некоторого факта, а другая – целевой вершиной и если n и m помечены унифицируемыми литералами или же вершина n имеет k-связку, отходящую ко множеству дочерних вершин, такому, что отношение гашение справедливо для каждого члена этого множества.
Когда корневая вершина графа целей и корневая вершина графов фактов "гасят" друг друга, имеем предполагаемое решение. Графовая структура, которая показывает, что корневые вершины для цели и факта гасят друг друга, называется предполагаемым графом гашения. Это решение является действительным, если согласуются НОУ всех соответствий в предполагаемом графе гашение.
Пример соответствия между начальным графом факта и начальным графом цели приведен на рис. 4.10. Согласованный граф гашение показан более жирными дугами. Унифицирующая композиция для всех НОУ у дуг соответствия есть {f(a)/; A/y}. Проверка на окончание процесса не ведет к обнаружению доказательства того, что целевой граф следует из графа фактов. Для этой проблемы потребовалась бы операция резолюции факт-цель более общего вида, чем та, что реализована в простой проверке на окончание, основанной на свойстве гашение.


Сетевые модели представления знаний
Сетевые модели находят все большее применение в системах понимания естественного языка, в вопросно-ответных системах, а также в различных предметно ориентированных системах управления и принятия решения.
В самом общем случае сетевая модель представляет собой информационную модель предметной области и имеет вид графа, вершины которого соответствуют объектам предметной области, а дуги – отношениям между ними. В зависимости от типов отношений, используемых в модели, различают классифицирующие сети, функциональные сети и сценарии. В классифицирующих сетях используются отношения структуризации. Такие сети позволяют в базах знаний вводить разные иерархические отношения между информационными единицами. Функциональные сети характеризуются наличием функциональных отношений. Их часто называют вычислительными моделями, т.к. они позволяют описывать процедуры "вычислений" одних информационных единиц через другие. В сценариях используются причинно-следственные отношения, а также отношения типов "средство – результат", "орудие – действие" и т.п. Если в сетевой модели допускаются отношения различного типа, то ее обычно называют семантической сетью.
Важной чертой семантических сетей является возможность представлять знания более естественным и структурированным образом, чем это делается в других формализациях.
Модель семантической сети Куиллиана
Исследования по семантическим сетям начались с работ М.Р. Куиллиана, который в качестве структурной модели долговременной памяти предложил модель понимания смысла слов, получившую название TLC – модели (Teachable Language Comprehender: доступный механизм понимания языка). В этой модели для описания долговременной памяти была использована сетевая структура как способ представления семантических отношений между словами (концептами).
Основной идеей модели было описание значений класса, к которому принадлежит объект, его прототипа и установление связи со словами, отображающими свойства объекта. В качестве примера на рис. 5.1 показана очень простая семантическая сеть для представления концептуального объекта "чайник". В этой сети определенны операторы отношений, называемые классом, свойством и примером, для которых описаны значения.

Таким образом, в модели Куллиана концептуальные объекты представлены ассоциативными сетями, состоящими из вершин, представляющих концепты и дуг, показывающих отношения между концептами.
Подобная ассоциативная структура называется плоскостью, описываемые концепты объекта называются вершинами типа, а связанные с ними соответствующие отдельные слова (ассоциативные слова) – вершинами лексем. В любой плоскости существует одна вершина типа и необходимое для определения концептов число вершин лексем. Например, как показано на рис. 5.2 вершина типа "комбайн" имеет одну вершину лексемы "машина", которая с помощью указателя образует еще одну вершину типа. Последняя, в свою очередь, содержит еще несколько вершин лексем.
Вершины лексем определяют всевозможные сущности, имеющие место в реальном мире, например классы, свойства, примеры, время, место, средство, объекты и т.п. Преимущество лексем по сравнению с типами заключается в экономии машинной памяти и предотвращении дублирования определения концептов.

В TLC – модели используется представление данных в форме "элемент" и "свойство" и можно структурировать знания, заменив вершину типа на элемент, а вершину лексемы на свойство. Данные, основанные на фактах, в долговременной памяти можно представить с помощью структур трех типов: элементы, свойства, указатели.
За элемент обычно принимается отдельное слово, имя существительное, предложение (например, "собака", "Америка", "хороший человек"). Свойство – это структура, описывающая элемент, оно соответствует таким частям речи как имя прилагательное, наречие, глагол (например "твердый", "быстро", "любит птиц"). При этом описания свойств представляют собой пару "атрибут – значение атрибута". И наконец, указатели связывают элементы и свойства. На рис. 5.3 показаны эти отношения.
Дедуктивные возможности модели Куиллиана определялись отношением "подкласс" и отношением "модификация". Понятие может быть определено в терминах более общего понятия (т.е. первое есть подкласс второго) и с помощью модифицирующего свойства, которое является комбинацией "атрибут – значение атрибута". При этом свойство, истинное для элементов класса, также истинно и для элементов любого его подкласса. Таким образом, семантическая сеть Куиллиана представляла комбинацию двух механизмов: таксономической иерархии, основанной на отношении "класс – подкласс", и описания свойств элементов класса, как пар "атрибут – значение атрибута".
(Таксономия – теория классификации и систематизации сложноорганизованных областей действительности, имеющих обычно иерархическое строение).


Структурирование знаний
Хотя семантическая сеть Куиллиана сама по себе является моделью памяти, в ней не раскрывается, каким образом осуществляется представление знаний. В процессе решения проблемы представления было введено понятие разбиения на блоки, что позволило сгруппировать вершины и дуги семантической сети в отдельные структуры, названные блоками. Эти структуры отождествляются с важными объектами в предметной области системы. Если системе нужна информация об одном из этих объектов, то открывается доступ к соответствующему блоку и отыскиваются сразу все могущие оказаться полезными сведения об этом объекте. Для таких схем представления используется термин структурированные объекты, поскольку основной упор делается на структуру представления.
Наиболее важным в блочной организации семантических сетей является введение отношений "множество – подмножество" и "целое – часть". Рассмотрим эти отношения.
Важной техникой, используемой в семантических сетях, является иерархия или система классификации. В соответствии с этой техникой объекты, относящиеся к проблемной области, классифицируются на некоторое число категорий или классов на основании их общих свойств. Например, множество людей может быть классифицировано на мужчин, женщин, детей и т.д. Дети классифицируются на мальчиков и девочек и т.п. Такого вида классификации формализуются в семантических сетях с помощью отношения isa (от английского is a – есть некоторый). Одной из важных черт isa – иерархии является то, что свойства "высших" типов автоматически переносятся на "низшие", т.е. предшествующие по is a иерархии. Например, свойство иметь "вес" присуще физическим объектам, следовательно, оно присуще одушевленным объектам, человеку, мужчине, женщине и т.д.
Isa – иерархия позволяет избежать значительной части дублирования информации в сети. Так, если некоторый факт истинен для каждого подмножества некоторого множества, то его можно хранить только в структуре знаний для этого множества.
Не менее важным является также отношение "целое – часть". Оно носит название part of (часть чего-либо). Это отношение позволяет разбивать информацию по уровням детализации. Part of – структура может представлять собой дерево, в котором каждая родительская вершина является part of – структурой для ее потомков.
Рассмотрим предложение, представляющее факт "все собаки – животные". Это предложение можно представить в форме, показанной на рис. 5.4 (а), использовав для этого две вершины "собака" и "животное" и дугу, показывающую отношение между ними. Если присвоить собаке некоторое имя, то сеть можно расширить рис. 5.4 (б). В этом случае, кроме двух представленных в сети фактов "Шарик – собака", "собака – животное", из нее, используя отношение isa, можно вывести факт "Шарик – животное", т.е. получить вывод, благодаря иерархии наследования. В сети можно представить и знания, касающиеся атрибутов объекта. Например, факт "все собаки имеют хвост" показан в сети на рис 5.4 (в).
При расширении семантической сети в ней возникают и другие отношения. Например, если рассмотренную на рис. 5.4 (в) сеть дополнить фактом "Шарик имеет конуру", то сеть будет иметь вид, представленный на рис 5.4 (г), где конура – i – это конкретная конура, которой владеет Шарик, она является, экземпляром понятия "конура". Таким образом приведено представление с обобщенными отношениями совокупности предметов между ветвью отношения владения, конурой и конурой – i.
Кроме того, при желании можно дополнить сеть информацией "Шарик владеет конурой с весны по осень", тогда вершинами необходимо представить не только объекты, но и ситуации и действия. На рис. 5.5 показана полученная таким образом семантическая сеть. В этой сети для вершины ситуации "владеть – i", определено несколько связей. Такая вершина называется падежной рамкой (case frame), она определяет различные аргументы предиката ситуаций. Обозначаются семантические падежи метками agt и obj; agt – агент, т.е. лицо, вызывающее действие, а obj – объект, т.е. предмет, подвергающийся действию.
Большинство семантических сетей имеет унифицированную структуру применительно к "агентам" и "объектам" по отношению к некоторому концепту. Преимущества использования такой структуры в вершинах сети заключаются в возможности наследования ожидаемых значений и значений по умолчанию, которые являются значениями атрибута в вершине экземпляра типа "владеет – i" рис. 5.5.

























Таким образом, основными понятиями и принципами, лежащими в основе структурирования знаний, являются следующие:
принцип локальности представления информации: блоки, фреймы и т.п.;
специализация – обобщение понятий (семантика индивидуальных понятий проявляется в описаниях через общие понятия);
семантические падежи;
наследование свойств;
таксономия, т.е. иерархия понятий.
5.3 Разделение семантической сети
Рассмотрим структуру семантической сети, предложенную Г. Хендриксом, в которой можно записывать таксономическую информацию, общие утверждения, включая квантификацию, информацию о процессах и процедурах модальности (мнения, желания), информацию о границе локальных контекстов и т.п. Г. Хендрикс предложил метод, называемый разделением семантической сети, и вывел понятие иерархически упорядоченного множества пространств, определяющих границы действия вершин экземпляров (рассматриваемых в качестве переменных).
Пример сети Хендрикса приведен на рис. 5.6. В этой сети УНИВЕРСУМ обозначает универсальный класс, который объединяет различные объекты. Этот класс содержит три подкласса: ЮРИДИЧЕСКИЕ ЛИЦА, СИТУАЦИИ И ФИЗИЧЕСКИЕ ОБЪЕКТЫ. Метка S обозначает отношения включения, а метка ds кроме отношения включения подразумевает, что элементы одного класса отличны от элементов другого. Например элементы подкласса СИТУАЦИИ отличны от элементов ЮРИДИЧЕСКИЕ ЛИЦА и ФИЗИЧЕСКИЕ ОБЪЕКТЫ.
Метка e обозначает элемент класса. Соответственно, метка de обозначает, что данный элемент отличен от всех других элементов, обозначения которых указанны другими e (или de) – дугами для данного класса. Например, FORD и G.M. (General Motors) обозначают различные элементы класса КОМПАНИИ. Метки agt и obj используются для обозначения семантических падежей так же, как и в предыдущем разделе. Метки conse и ante обозначают соответственно консеквент (правую часть) и антецедент (левую часть) импликации.
Семантическая сеть построена по блочному принципу и каждый блок имеет вершину входа, например, вершины P, B и M для трех блоков соответственно. Блок – одна из основных структурных единиц сети наравне с вершинами и дугами. Каждая вершина и каждая дуга сети принадлежит одному или нескольким блокам. Например, вершина M принадлежит трем блокам.
Дуги, принадлежащие блоку, указываются тем, что их метки записаны внутри прямоугольника – так, дуга, связывающая M с МУСТАНГ, принадлежит блоку, ограниченному самым маленьким прямоугольником, но не принадлежит блоку, ограниченному большим прямоугольником. Таким образом, разбиение сети на блоки дает возможность для образования иерархии блоков.
Рассмотрев блоки с вершинами B и M и классы ИМПЛИКАЦИЯ и СТРОИТЬ, можно получить следующее утверждение: "Если М является элементом класса МУСТАНГ, то для некоторой ситуации B из класса СТРОИТЬ агентом B является FORD, а объектом B является M". На языке логики предикатов первого порядка это утверждение записывается следующим образом:
( M  МУСТАНГ)  (( B  СТРОИТЬ) agt(B) = FORD  obj(B) = M)
Таким образом, в сети имеется возможность представлять комбинацию кванторов общности и существования.
В рассматриваемой семантической сети могут присутствовать блоки логических операций: отрицания, дизъюнкции и импликации. Эти блоки особенно важны для построения процедур дедуктивного вывода. Что касается конъюнкции, то она реализуется в сети довольно просто с помощью механизма наследования или множественными вершинами и дугами e, de, s, ds.
Дизъюнкция, входящая в некоторый блок S, описывает альтернативные наборы понятий и отношений и утверждает, что понятия и отношения, удовлетворяющие по крайней мере одному из описаний, существуют в мире, представленном блоком S.
Пример сети, в которой закодирована дизъюнкция D= "или OLD.BLACK была построена компанией Форд или OLD.BLACK принадлежит Джону", представлена на рис. 5.7.
Компоненты дизъюнкции D представлены здесь блоками (супервершинами) S2 и S3, причем они являются различными элементами D. Структура дизъюнкции вложена в конъюнкцию блока S1. Блок S1 обеспечивает частичное описание некоторого мира (т.е. набора понятий и их отношений) и каждая структура в S1 представляет собой некоторое понятие или ситуацию, встречающуюся в этом мире. Такимобразом, при рассмотрении сети из S1 такие понятия как OLD.BLACK и D становятся "видимыми". Однако структуры в блоках S2 и S3 из S1 не "видны". Так как известно, что S1 включает ситуации, описанные по крайней мере, в одном из компонентов D, например в S2, то мир будет включать все ситуации, описанные структурами, которые "видимы" из S2. И в данном случае сюда будут включены структуры из S2 и S1, но исключены структуры из S3.


Отрицание в семантической сети включает в себя описание некоторого множества понятий и отношений, имеющих место в блоке S, и означает, что ни одно множество, удовлетворяющее описанию, не может существовать в мире, выраженом блоком S. На рис. 5.8 показана сеть, представляющая утверждение: "Компания G.M. не строила OLD.BLACK". Как и в примере с операцией дизъюнкции, структуры с отрицанием внутри S2 не "видимы" при рассмотрении из S1, хотя отрицание само по себе "видимо".
Импликация, входящая в блок S, описывает два набора понятий и отношений, и утверждает, что если понятия и отношения существуют в мире, представленном блоком S, который удовлетворяет первому из двух описаний (левая часть импликации ante), то понятия и отношения, удовлетворяющие второму описанию (правой части импликации conse), также существуют в этом мире. Импликация представляется вершиной с дугами, идущими к блокам, содержащим предшествующие (ante) и последующие (conse) описания. Пример сети с импликацией был представлен на рис. 5.6.


Одной из важных особенностей сети является ее способность представления произвольно сгруппированных кванторов общности и существования.
Квантор существования является "встроенным" понятием в том смысле, что если некоторый элемент (вершина или дуга) входит в данный блок, то соответствующее понятие существует в мире, который данный блок представляет.
Для представления квантора общности можно использовать квантор существования и отрицание:
(x  X) P(x) = ((x  X) P(x))
Эта формула представлена на рис. 5.9. Такое представление логически верно, но не наглядно.

Рассмотрим другое представления квантора общности:
(x  X) P(x) = x [(x  X)  P(x)]
Здесь переменная x встречается как в антецеденте, так и в консеквенте. Это свойство используется в системе для представления переменной с квантором общности. На рис. 5.10 (а, б) показано представление формул (x  X) P(x) и (x  X) P(x).




Представление семантической сети в виде совокупности фреймов
Понятие о фреймовых моделях
В отличие от моделей других типов во фреймовых моделях фиксируется жесткая структура информационных единиц, которая называется протофреймом. В структуре фреймов широко используются концепция слотов, т.е. незаполненных участков, которые заполняются в процессе активации, функционирования фрейма в соответствии с определенными условиями или предписаниями, которыми они сопровождаются. Каждый фрейм можно рассматривать как сеть, состоящую из нескольких вершин и отношений. На самом верхнем уровне фрейма представлена фиксированная информация: факт, касающийся состояния объекта, который обычно считается истинным. На последующих уровнях расположено множество слотов, которые обязательно должны быть конкретными значениями и данными. В общем виде структура фрейма выглядит следующим образом:
(Имя фрейма:
Имя слота1 (значения слота1)
Имя слота2 (значения слота 2)
…………………………………
Имя слота k (значения слота k))
Значением слота может быть практически что угодно (числа или математические соотношения, тексты на естественном языке или программы, правила вывода или ссылки на другие слоты данного фрейма или других фреймов). В качестве значения слота может выступать набор слотов более низкого уровня, что позволяет во фреймовых представлениях реализовывать "принцип матрешки".
При конкретизации фрейма ему и слотам присваиваются конкретные имена и происходит заполнение слотов. Таким образом, из протофреймов, получаются фреймы-экземпляры. Переход от исходного протофрейма к фрейму-экземпляру может быть многошаговым, за счет постепенного уточнения значений слота.
Например, структура таблицы 5.1, записанная в виде протофрейма, имеет следующий вид:
Таблица 5.1
Фамилии
Год рождения
Специальность
Стаж (годы)
Попов
1965
слесарь
5
Сидоров
1946
токарь
20
Иванов
1925
токарь
30
Петров
1937
сантехник
25

(Список работников:
Фамилии (значение слота 1);
Год рождения (значение слота 2);
Специальность (значения слота 3);
Стаж (значение слота 4)).
Если в качестве значений слотов использовать данные таблицы 5.1, то получится фрейм-экземпляр:
(Список работников:
Фамилия (Попов – Сидоров – Иванов – Петров);
Год рождения (1965 – 1946 – 1925 – 1937);
Специальность (Слесарь – Токарь – Токарь – Сантехник);
Стаж (5 – 20 – 30 – 25)).
Связи между фреймами задаются значениями специального слота с именем <<Связь>>. Часть специалистов по искусственному интеллекту полагают, что нет необходимости специально выделять фреймовые модели в представлении знаний, так как в них объединены все основные особенности моделей остальных типов. Поэтому фреймовые модели часто рассматриваются в общем контексте с сетевыми моделями.
5.4.2 Семантическая модель как совокупность фреймов
Будем рассматривать семантическую сеть как некоторый ориентированный граф с помеченными вершинами и дугами, в котором выделены также помеченные подграфы, называемые фреймами.
Исходными элементами семантических сетей будем считать типы, константы, предметные переменные и простые фреймы. Определим эти элементы.
Типы (сорта, семантические категории) представляют неформальные общие, родовые идеи физических или абстрактных объектов, которые выделяют в предметной области. Примеры типов: ЧИСЛО, ТОЧКА, ПОСТАВЩИК, ПРЕДПРИЯТИЕ, ЧЕЛОВЕК и т.п.
Имена типов присваиваются некоторым вершинам семантической сети. Типы делятся на две категории: простые типы и составные типы. Простые типы соответствуют начальным понятиям. Составные определяются с помощью фреймов из простых типов.
Константы представляют конкретные предметы типов. Константа всегда ассоциируется хотя бы с одним типом. Эта связь указывается дугой семантической сети, помеченной символом i (instance of – пример чего-либо). Пример константы: 7 имеет тип ЧИСЛО, 7 имеет тип ЦЕЛОЕ ЧИСЛО и т.п.
Переменные представляют собой свободные и связанные предметные переменные. Каждая переменная ассоциируется с одним типом. Эта связь указывается дугой семантической сети, помеченной символов t. Дуга ведет от вершины, помеченной именем переменной, к вершине, помеченной именем типа.
Фрейм в данном случае будем определять как некоторые помеченные подграфы семантической сети. Фреймы либо представляют некоторые "куски" знания, которыми можно манипулировать как целыми блоками, либо являются некоторыми структурами для определения составных типов. Соответственно этому, фреймы делятся на функциональные и структурные. Фрейм является простым, если он не содержит в себе других фреймов.
Простой функциональный фрейм содержит единственное понятие выражающее функцию или отношение ("центральная вершина"), а также содержит переменные или константы ("переферические вершины"). Из центральной вершины простого функционального фрейма к его переферическим вершинам ведут помеченные дуги. Одна дуга помечена буквой r (result - результат), остальные символами a1, a2, …, an. Центральная вершина помечена именем функции, а переферические – именами переменных и констант. Простой функциональный фрейм показан на рис. 5.11.
Семантические сети предназначены для представления знаний о проблемных областях (или "мирах"). Фактически в каждом конкретном случае мы имеем дело с одним "действительным" миром. Интерпретация понятий семантической сети, соответствующая этому действительному миру называется "стандартной". Однако ограничиться одной только стандартной интерпретацией нельзя. Нам необходимо выведение следствий из уже описанного знания, а логические следствия можно получить, предполагая альтернативные миры. Кроме того, действительный мир чаще всего не статичен. Следовательно, стандартная интерпретация изменчива. Поэтому вводится понятие класса альтернативных интерпретаций, включающих также стандартную интерпретацию. Класс не выбирается произвольно, но состоит из допустимых для данной семантической сети интерпретаций. Допустимые интерпретации должны быть согласованы.
Для согласования интерпретаций вводится понятие подстановка и специализация. Рассмотрим простой функциональный фрейм F. Пусть x1, x2, …, xn, y – все переменные, входящие в F, а A1, A2, …, An, С – типы этих переменных. Переменные xi соответствуют аргументам фрейма F, а y – переменная, соответствующая результату.
Элементарной подстановкой для фрейма F называется выражение вида
 = {i/xi; /y; Di/Ai} i = 1, n, где i,  - либо переменные, либо константы, а Di, Ai – типы.
Подстановка, не содержащая переменных, называется константной, фрейм, не содержащий переменных, также называется константным.
Результат применения подстановки  к фрейму F будет обозначаться через F. Таким образом, для любой константной элементарной подстановки  для произвольного фрейма F фрейм F является константным.
Пусть  - элементарная константная подстановка для простого функционального фрейма F. Истинный относительно некоторой интерпретации Y константный фрейм F будем называть константным элементарным примером. фрейма F. Подстановка , приводящая к истинному константному фрейму F называется специализацией.
Рассмотрим два фрейма F10 и F11 показанные на рис. 5.12. Обозначим через F10 вариант фрейма F10, полученный из последнего подстановкой
{x1/x; z1/z}.
Тогда подстановка вида
 = {F10/y1; F10/y2; ПОЛОЖИТЕЛЬНОЕ ЧИСЛО/ЧИСЛО}
из фрейма F11 образует фрейм F12, который показан на рис. 5.13. Функциональный фрейм F12 дает пример составного функционального фрейма. Фрейм F12 содержит в качестве подфреймов F10, F10 и F11.




















Таким образом, сеть фреймов можно рассматривать как семантическую сеть с блочной структурой, позволяющую реализовать альтернативные интерпретации предметных областей. Фрейм в такой сети содержит информационный и процедурный элементы, которые обеспечивают преобразование информации внутри фрейма и его связь с другими фреймами. Слоты фрейма заполняются конкретной информацией в процессе функционирования фрейма. В сети фреймов могут быть также реализованы и логические связки, и кванторы общности и существования.
Дедуктивный вывод на семантических сетях
Особенностью семантической сети (которая в то же время является ее недостатком) заключается в целостности системы, выполненной на ее основе. Именно эта целостность не позволяет разделить базу знаний и механизм вывода. Рассмотрим основные дедуктивные процедуры, ориентированные на представление знаний о предметной области в виде семантических сетей.
Метод наложений
В этом случае происходит сопоставление частей сетевой структуры. Метод основан на построении подсети, соответствующей вопросу, и сопоставлении ее с базой данных сети. При этом для исчерпывающего сопоставления с базой данных вершинам переменных подсети присваиваются гипотетические значения. Рассмотрим в качестве примера следующий процесс сопоставления с частью базы данных. Пусть имеется часть базы данных, приведенная на рис. 5.14 (а), в отношении которой возникает вопрос "Чем владеет Шарик". Этот вопрос представляется в виде подсети рис. 5.14 (б) и проводится сопоставление. При этом сначала отыскивается вершина "владеть", имеющая ветвь "владелец", направленную к вершине "Шарик", следует соединение с вершиной, которая показывает "собственность", и ответ на вопрос.
Вопрос вида "существует ли животное, которое владеет конурой" можно представить с помощью подсети, как показано на рис. 5.14. Однако эта подсеть не годится для непосредственного сопоставления с базой данных рис. 5.14 (а). Для этого из узла "Шарик" к узлу "животное" проводится дуга is a (означающая, что Шарик является животным). Теперь становится возможным соединение владеет - ? с владеет – i и проведение сопоставления. В результате ответ на вопрос звучит как "Да, - это Шарик".
Метод поиска пересечений
Этот метод широко используется в семантических сетях. Основная идея метода заключается в доказательстве истинности некоторого высказывания, заданного выражениями, представимыми вершинами сети, между которыми имеются явные связи. Поиск этого высказывания осуществляется одновременно от каждой из двух вершин сети, например А и В во всех направлениях (ограниченных дугами определенного вида) до тех пор, пока не произойдет пересечение в некоторой вершине путей, идущих из вершин А (длина пути lA) и (длина пути lB). Обычно выбирается тa вершина, для которой сумма lA + lB минимальна. В общем случае может быть найдено пересечение более, чем в одной вершине. Например, на вопрос "какие отношения между Мариной и Андреем" для подсети на рис. 5.15 можно получить ответ "Андрей отдал эту книгу (BK – i) Марине.












Очевидно, что в семантических отношениях узлов и дуг семантической сети не должно быть противоречий.
Специализированные выводы
В ряде систем для вывода определенных фактов используются специализированные правила или процедуры. Эти методы основаны на свойствах отношений. Например, если отношение R является транзитивным и надо доказать истинность факта a R b, то в сети надо найти путь от a до b по отношению R. Если такой путь существует, то отсюда вытекает истинность факта a R b. В общем случае определяют отношения как композицию других отношений R = R1  R2  …  Rn, и они используются как схема поиска при выводе новых утверждений.
(Транзитивностью называют одно из свойств логического отношения величин. Отношение R является транзитивным, если из a R b и b R c вытекает, что a R c. Например, a=b и b=c, следовательно a=c. Отношение "=" транзитивно. Но если ab и bc, то отсюда не следует, что ac, следовательно отношение "" не является транзитивным).
5.5.4 Дедуктивный вывод на "раскрашенных" семантических сетях
Основной недостаток рассмотренных выше методов вывода заключается в ограниченности дедуктивных возможностей и связан с комбинаторном ростом числа наложений или пересечений негибкостью этих методов при переходе с одной предметной области на другую. В последнее время разрабатываются дедуктивные алгоритмы, приспособленные для решения задач в широком спектре систем принятия решений и гибко реагирующие на любые изменения предметной области.
Рассмотрим особенности структуры семантических сетей, которые используются в таких алгоритмах.
В семантических сетях связями между понятиями являются структурные, логические и процедурные связи. Например, в предметной области, касающейся учета текущей успеваемости студентов на факультете, сведения о конкретном студенте могут включать его фамилию, специальность, группу, в которой он учится, курс, дисциплину и т.п.
Тогда между понятиями СТУДЕНТ и ДИСЦИПЛИНА имеется структурная связь. Между понятиями УСПЕВАЮЩИЙ и СТУДЕНТ – тривиальная логическая связь: всякий индивидуум, принадлежащий понятию УСПЕВАЮЩИЙ, принадлежит также понятию СТУДЕНТ. Более сложная логическая связь наблюдается между понятиями УСПЕВАЮЩИЙ, БАЛЛ и ДИСЦИПЛИНА: индивидуум является успевающим тогда и только тогда, когда его оценка по каждой дисциплине не менее трех баллов. Между понятиями средняя успеваемость, ГРУППА и ДИСЦИПЛИНА имеется процедурная связь, заключающаяся в том, что средняя успеваемость студентов по данной дисциплине в группе вычисляется как среднее арифметическое оценок всех студентов группы по данному предмету. В системах, основанных на семантических сетях, как правило, используются структурные связи, а логические и процедурные применяются реже.
Слабое использование логических связей сильно ограничивает дедуктивные возможности систем. Между тем, в семантической сети можно отобразить выражения разной сложности и это осуществляется за счет введения новых отношений типа "условие" и "заключение".
Вначале рассмотрим семантическую сеть, соответствующую простому высказыванию например, "книга 1 лежит на столе 1". В исчислении предикатов первого порядка высказывание имеет вид: лежит (книга 1, стол 1). В сети рис. 5.16 буквой P обозначена пропозициональная вершина, соответствующая данному высказыванию в целом. Из вершины P выходят дуги (case 1, case 2, pred), которые являются бинарными отношениями. Дуги с меткой prop указывают пропозициональную вершину и помогают в поиске таких вершин. (В дальнейшем для простоты дуги с меткой prop будем опускать).










Дизъюнкт вида B1  B2  …  Bm  A1  A2  …  An в дальнейшем будем представлять как B1  B2  …  Bm  A1  A2  …  An, где B1, B2, …, Bm – условия, а A1, A2, …, An – заключения (решения) дизъюнкта. Дизъюнкты без условия являются утверждениями.
Рассмотрим примеры выражений и соответствующие им дизъюнктные формы. Пусть дано следующее выражение: "Куб номер 2 находится всегда в том же месте, где куб номер 1". В форме дизъюнкта это выражение имеет следующий вид: B(куб1, x)  B(куб2, x). Здесь B – предикат "находится в месте", а x – представляет любой индивидуум, т.е. связан квантором общности. Утверждение "куб номер 1 находится в месте a" будет записано как И  B(куб1, a) или в дальнейшем будем употреблять сокращенную запись:  B(куб1, a).
Выражение "куб номер 1 не находится в месте a" будет иметь вид: B(куб1, a)  Л или B(куб1, a) , что позволяет выразить отрицание. Аналогично записываются выражения, содержащие конъюнкцию условий и/или дизъюнкцию заключений.
Если в выражениях имеются кванторы существования, то переменные, связанные этими кванторами, заменяются сколемовскими функциями, а оставшиеся кванторы общности опускаются.
Чтобы уменьшить перебор при поиске информации и при выводе новых утверждений, т.е. для повышения эффективности работы системы принятия решения, над семантическими сетями совершают операцию типа "раскраски" семантических сетей.
Правило раскраски состоит в следующем: если имеется дизъюнкт BA, то условие дизъюнкта B будет "раскрашено" на семантической сети цветом Ц1 (соответствующие дуги изображаются непрерывной линией), а заключение А – цветом Ц2 (на рисунках пунктирной линией).
Допустим, имеется следующий набор высказываний:
Если куб номер 1 находится в месте а, то куб номер 2 находится в том же месте.
Если куб 1 номер 1 находится в месте а, то куб номер 3 находится в месте b.
Куб номер 1 находится в месте а.
В дизъюнктивной форме эти высказывания имеют следующий вид:
В(куб1, а)  В(куб2, а)
В(куб1, а)  В(куб3, b)
В(куб1, а)
Соответствующая раскрашенная сеть имеет вид, приведенный на рис. 5.17. Допустим, мы хотим найти в сети утверждение  В(куб1, а).
Сначала находим все пропозициональные вершины, которые связаны с вершинами В, куб1 и а. Такими вершинами являются Р2, Р4, Р6. Затем последовательно проверяем эти вершины, обнаруживая, что Р2 и Р4 являются условиями дизъюнкта и поэтому они исключаются, а вершине Р6 соответствует третье утверждение. За счет локального возбуждения того или иного участка сети значительно уменьшается время поиска нужного утверждения.
Преимущество такого представления заключается в следующем:
а) дается эффективная индексация информации с помощью раскрашенных графов, что позволяет обрабатывать сети большой размерности;
б) эффективно удаляется из сети информация, не относящаяся к данному вопросу или к данной ситуации.
В дальнейшем для простоты будем изображать семантическую сеть, состоящую из дизъюнктивных вершин, т.е. вершин, которым соответствуют исходные дизъюнкты, предикатных вершин и дуг, помеченных двумя цветам. После таких упрощений сеть, представленная на рис. 5.17 будет иметь вид, показанный на рис. 5.18. Здесь g1, g2, g3 – исходные дизъюнкты, а В – предикат.












Такие упрощенные семантические сети будем называть L – сетями. Они вводятся только для удобства иллюстрации процедур дедуктивного вывода.
Математически задача дедуктивного вывода формулируется следующим образом. Задается логико-лингвистическая модель, которая на языке исчисления предикатов имеет вид:
B11  B12  …  B1m1  A11  A12  …  A1n1,
B21  B22  …  B2m2  A21  A22  …  A2n2,
…………………………………………………
Br1  Br2  …  Brmr  Ar1  Ar2  …  Arnr,
где Bji – условия вывода, Aji – заключения (решения) вывода, выраженные предикатами, и каждая формула этой модели представляет собой дизъюнкт. Дизъюнкты, имеющие как условия, так и заключения, представляют собой общие законы – аксиомы. Дизъюнкты без условий – факты. Дизъюнкты без заключений – это отрицания фактов или цели, которые нужно доказать. Каждой логико-лингвистической модели сопоставляется эквивалентная ей семантическая сеть. На вход сети подается ситуация, представленная совокупностью фактов A1, A2, …, Ae.
Эта ситуация, накладываемая на семантическую сеть, представляет собой текущее состояние системы, отражающее динамику ее изменения. Кроме того, на вход модели подается запрос следующего вида:
K1 x1 K2 x2 … Kn xn (M1  M2  …  Mk  N1  N2  …  Nh), где Ki  {, }, Mi и Ni – условия и заключения запроса.
Решением задачи дедукции является получение противоречий в семантической сети или пустой сети (по аналогии с пустым предложением в методе резолюции). С прикладной точки зрения решением задачи дедуктивного вывода будет являться получение управляющих воздействий для системы принятия решений, представляющих собой значения переменных при сопоставлении фрагментов семантической сети в процессе вывода пустой сети. Следовательно, при решении этой задачи необходимо использовать некоторый алгоритм семантической унификации, который позволит определить согласованные подстановки (также по аналогии с методом резолюции).
В качестве правил вывода в алгоритмах дедукции применяются два известных правила modus tollens и modus ponens:
B  A 2) B  A
A   B
 
B   A
С помощью первого правила получаем отрицания литер из исходных дизъюнктов, а с помощью второго правила – утверждения.
Рассмотрим выводы в семантической сети с применением 1-го и 2-го правил в упрощенном виде.
Применение первого правила.
Пусть имеется следующая логическая модель, представленная в форме дизъюнктов
 A
A  B
B  C
C  D
D  E
Необходимо доказать истинность утверждения  Е. Соответствующая L-сеть показана на рис 5.19. Здесь g1, g2, g3, g4 и g5 обозначают вершины, соответствующие дизъюнктам логической модели.










Для доказательства возьмем отрицание доказываемого и будем осуществлять выводы до тех пор, пока не получим противоречие.



Отрицанием доказываемого будет Е . После добавления этого дизъюнкта и после многократного применения первого правила семантическая сеть преобразуется так, как показано на рис. 5.20 (а, б, в, г, д). Непрерывными линиями обозначены дуги – условия дизъюнктов, а прерывистыми – заключения дизъюнктов. На последнем этапе получили противоречие, так как в семантической сети находится как факт  А, так и его отрицание А . Это означает, что факт  Е доказан в данной логической модели.
Применение второго правила.
Пусть имеется следующая логическая модель
A  B
B  C
C 
Допустим, надо доказать дизъюнкт A , отрицанием которого является A. L-сеть после добавления этого дизъюнкта примет вид, показанный на рис. 5.20 (а). После применения второго правила данная сеть преобразуется так, как показано на рис. 5.21 (б, в).
Получили противоречие, что означает, что А  доказано в данной логической модели. При доказательстве правила 1 и 2 можно комбинировать.



Очевидно, что в L-сетях более сложной структуры могут учитываться и другие логические связки.
Особенности различных способов представления знаний
Хотя все описанные в предыдущих разделах способы представления знаний и различны на первый взгляд, по существу они имеют много общего и их различие носит концептуальный характер. Оно отражает лишь тот факт, что все разработки велись по разным концепциям. Взаимное различие способов представления кроется скорее в их внешнем виде. На некотором глубоком уровне все типы представления знаний должны быть эквивалентны.
Так, предложения логики предикатов имеют много общего с продукционными правилами. Интерпретируя правила продукции как предложение логики предикатов, можно без каких-либо затруднений заменить его на предикаты. В общем случае каждую дугу семантической сети можно задать бинарным предикатом, как отношение между сущностями, описываемыми узлами. Но эта попарная равнозначность отношений не означает, что различные способы представления позволяют получать равнозначные системы представления.
Выбор той или иной системы представления является прерогативой конструктора экспертной системы и определяется простотой представления решаемой проблемы тем или иным формализмом. Кроме того, учитывается и сложность механизма вывода, который определяется выбранным формализмом.
Тем не менее, каждая из моделей представления знаний обладает своими достоинствами и недостатками.
Логике предикатов присущ высокий уровень модульности знаний. Описательная мощность логики предикатов первого порядка как единой системы представления знаний выше, чем у других систем. Используемый в логике предикатов вывод на основе резолюции является самым эффективным и формализованным и получил широкое распространение. Однако, достоинства логических моделей на основе исчисления предикатов первого порядка обуславливают и присущие этим системам представления недостатки.
Границы описательных возможностей предикатов определяются синтаксическими правилами. Эти правила чрезвычайно просты в отличие от синтаксических правил любого естественного языка. Одной из причин этой простоты является отсутствие исключений, что и приводит к снижению описательных возможностей языка предикатов, так как невозможно видоизменять принятые формализмы без создания соответствующих теоретических основ. Таким образом, чрезмерный уровень формализации представления и вывода оказываются недостатками логических моделей. К недостаткам этих моделей относятся и трудности прочтения логических описаний, и не слишком высокая производительность обработки знаний. Кроме того, в процессе вывода человек не пользуется системой, основанной на принципе резолюции. Поэтому при создании систем интерактивного взаимодействия человека и машины для решения сложных проблем метод резолюции может оказаться не совсем подходящим.
Популярность продукционных моделей определяется следующими достоинствами:
подавляющая часть человеческих знаний может быть записано в виде продукций;
системы продукций являются модульными и удаление или добавление продукций, как правило, не приводит к изменениям в остальных продукциях;
наличие в продукциях указателей на сферу применения продукций позволяет эффективно организовывать память, сократить время поиска необходимой информации;
при объединении систем продукций и сетевых представлений получаются средства большой описательной и вычислительной мощности.
При этом продукционные модели имеют по крайней мере два недостатка:
при большом числе продукций становится сложной проверка непротиворечивости системы продукций, что усложняет процедуру добавления новых продукций;
из-за недетерминированности системы, т.е. неоднозначного выбора выполняемой продукции, возникают трудности при проверке корректности работы системы.
Именно поэтому число продукций, с которыми работают, как правило, современные системы ИИ, не превышает тысячи.
Сетевые модели пока не имеют общей теории. В них много эвристик и вариантов решения. Одним из основных достоинств сетевых моделей является возможность представлять знания более естественным и структурированным образом, чем в других формализмах. Это весьма простой и понятный способ описания предметного мира на основании отношений между элементами сети – узлами и дугами. Некоторые операции на семантической сети, которые при других представлениях выполнялись бы с помощью явного применения правил и механизмов, могут быть выполнены с большой степенью автоматизма.
Однако, ввод семантического знания в структурное сужает общность декларативного представления, хотя и повышает его эффективность. Кроме того, следует учитывать, что расширение сети, дополнение ее новыми фактами вызывает проблему квантификации новых переменных, снижает однородность сети и приводит к необходимости увеличения арсенала методов вывода. С увеличением размеров сети существенно возрастает время поиска по сравнению со способами, не имеющими стратегии. И, наконец, результат вывода, получаемого с помощью семантической сети, особенно в иерархических системах, не гарантирует такую достоверность вывода, как логический формализм.
Учитывая достоинства и недостатки различных моделей представления, в современных исследованиях в области искусственного интеллекта предпочитают объединение преимуществ различных моделей в новом, смешанном представлении.
Приложения
Пример преобразования ППФ в форму предложений
Пусть имеется ППФ вида:
(x) {P(x)  {(y) [P(y)  P(f(x, y))]  (y) [Q(x, y)  P(y)]}}.
Исключим  (импликацию) подстановкой x1  x2 вместо x1  x2
(x) {P(x)  {(y) [P(y)  P(f(x, y))]  (y) [Q(x, y)  P(y)]}}.
Ограничим область действия символа отрицания (не более чем к одной отмеченной формуле). Используем законы Моргана и формулы эквивалентности:
(x) {P(x)  {(y) [P(y)  P(f(x, y))]  (y) [Q(x, y)  P(y)]}}.
Разделим переменные:
(x) {P(x)  {(y) [P(y)  P(f(x, y))]  () [Q(x, )  P()]}}.
Исключим кванторы существования (исключение состоит в замене каждого вхождения переменной, относящейся к квантору существования, на сколемовскую функцию, аргументы которой представляют собой те переменные, которые связаны кванторами общности, область действия которых включает и область действия исключаемого квантора существования). Для нашего примера получим:
(x) {P(x)  {(y) [P(y)  P(f(x, y))]  [Q(x, g(x))  P(g(x))]}}, где g(x) – сколемовская функция.
Преобразование в предваренную (префиксную) форму – отбрасывание кванторов общности, каждый из которых имеет свою переменную. Их можно переместить в начало формулы и отбросить. Такая формула называется матрицей. Для нашего примера
(x)(y) {P(x)  {[P(y)  P(f(x, y))]  [Q(x, g(x))  P(g(x))]}}
Преобразование в конъюнктивную нормальную форму (КНФ). Любая матрица может быть записана как конъюнкция конечного множества дизъюнкций литералов. Это можно сделать многократным применением дистрибутивных правил [x1  (x2  x3)] на [(x1  x2)  (x1  x3)].
Для нашего примера:
{[P(x)  P(y)  P(f(x, y))]  [P(x)  Q(x, g(x))]  [P(x)  P(g(x))]}.
Исключение символов конъюнкции. Результат – множество ППФ, состоящих из дизъюнкций литералов:
P(x)  P(y)  P(f(x, y));
P(x)  Q(x, g(x));
P(x)  P(g(x)).
Переименование переменных. Символы переменных должны быть изменены так, чтобы каждый появлялся не более, чем в одном предложении. Тогда:
P(x1)  P(y)  P(f(x1, y));
P(x2)  Q(x2, g(x2));
P(x3)  P(g(x3)).
Полученное множество предложений и есть каузальная форма.

Литература
1. Вагин В.М. Дедукция и обобщение в системах принятия решений. – М.: Наука, 1988. – 384с.
2. Нильсон Н. Принципы искусственного интеллекта. – М.: Радио и связь, 1985. – 376с.
3. Искусственный интеллект. – В 3-х кн. Кн.2. Модели и методы: Справочник / Под ред. Д.А. Посиелова – М.: Радио и связь, 1990. – 304с.
4. Представление и использование знаний: Пер. с япон. / Под ред. Х. Уэно, М. Исидзука. – М.: Мир, 1989. – 220с.
5. Осуга С. Обработка знаний: Пер. с япон. – М.: Мир, 1989. – 293с.