Управление стратегией вывода в продукционных системах

Вопрос№1

Определение. Формальная система представляет собой совокупность чисто абстрактных объектов, не связанных с внешним миром, в которой представлены правила оперирования множеством символов только в синтаксической трактовке без учета смыслового содержания.

Под теоремой в формальной системе понимают высказывание, истинное в данной системе, - это некоторое обоснованное и строгое утверждение, которое строится на основе определенных логических правил и доказательства. Доказательство – это способ получения одних выражений из других с помощью операций над символами и построение обоснованной аргументации, следствием которой и является теорема.

Неопределяемые термины – это те термины и понятия, смысл и содержание которых считается уже известным, и через них вводятся все новые понятия и термины. Совершенно аналогично вводится некоторая часть постулатов (формул), которые, как считается в данной теории, не требуют доказательства. Обычно это утверждения, правильность которых не вызывает сомнения, и они принимаются как очевидные истины. Такие выражения (формулы) называют аксиомами, а системы, в основе построения которых лежит использование аксиом, называются аксиоматическими системами.

Определение. Формальным доказательством, или просто доказательством называется последовательность формул  такая, что каждая формула  является либо аксиомой, либо выводима из предшествующих ей формул.

Определение.Формула t называется теоремой, если существует доказательство, в котором она является последней.

Задаваемые при описании формальной системы правила вывода называют также правилами вывода заключений, т.е. они позволяют определить является ли данная формула теоремой данной формальной системы, или нет.

Различают два типа правил вывода.

1. Правила, применяемые к формулам, рассматриваемым как единое целое, в этом случае их называют продукционными правилами.

Пример.x < y и y < z ® x < z - это продукция с двумя посылками.

2. Правила, которые могут применяться к любой отдельной части формулы, причем сами эти части являются формулами, входящими в состав формальной системы. В этом случае их называют правилами переписывания.

Пример. x - x = 0, это выражение имеет смысл при любом значении входящей в него в качестве подвыражения переменной x.

Определение. Правило подстановки заключается в замещении всех вхождений какой-либо переменной на формулу из формальной системы, которая не содержит этой переменной.

Определение. Интерпретация представляет собой распространение исходных положений какой-либо формальной системы на реальный мир. Интерпретация придает смысл каждому символу формальной системы и устанавливает взаимно однозначное соответствие между символами формальной системы и реальными объектами. Теоремы формальной системы, будучи интерпретированы, становятся после этого утверждениями в обычном смысле слова, и в этом случае уже можно делать выводы об их истинности или ложности.

Определение. Исчисление высказываний (логика высказываний) – это формальная система, интерпретацией которой является алгебра высказываний. Под высказыванием понимается повествовательное предложение, о котором можно сказать, что оно истинно или ложно.

1. Алфавит, который состоит из символов трех категорий:

а) бесконечное счетное множество высказываний (или переменных высказываний), которые обычно обозначаются буквами: A, B, C, x, y, z, a, b, c,  ,  и т.д.;

б) логические операторы (или логические связки), которые обозначают символы логических операций ( , &,  и т.д.);

в) открывающиеся и закрывающиеся скобки: ( , ) .

Других символов в ИВ нет.

2. Правила построения формул. Для обозначения формул обычно используют заглавные буквы латинского алфавита. Эти буквы не являются символами исчисления и служат для условного обозначения формул. Формулы в ИВ определяются следующим образом

Формулы в исчислении высказываний однозначно получаются с помощью правил, которые описываются базисом и индуктивным шагом:

базис: всякое высказывание есть формула;

индуктивный шаг: если X и Y - формулы, то , , ,  и т.д. - также формулы;

3. Аксиомы. Существует несколько вариантов подбора аксиом , как исходных тождественно истинных формул. Эти наборы эквивалентны в том смысле, что они определяют один и тот же класс выводимых формул.

4. Правила вывода. Правила вывода устанавливают отношения на множестве формул исчисления высказываний.

1) правило заключения (modus ponens). Если A и  - это выводимые формулы, то B также является выводимой формулой.

2) правило подстановки. Его формальная запись имеет вид:

,

Правило сложного заключения.  Если  - формулы и

 - теорема, то формула B - так же теорема.

Правило двойного отрицания. Если  и  - теоремы, то будет теоремой и формула , иначе   и .

Правило силлогизма (замыкания). Если  и   теоремы, то   так же теорема, иначе .

Правило композиции. Если  теорема, то  так же теорема, иначе .

Определение. Принцип дедукции состоит в следующем. Формула A является логическим следствием конечного множества Е тогда и только тогда, когда  содержит невыполнимые формулы.

. Это правило называется правилом прямой дедукции. Возьмем отрицание от этого выражения, тогда по правилу де Моргана получим . Это правило называется правилом обратной дедукции.

В методе резолюций применяется также приведенное выше правило прямой дедукции: для того, чтобы доказать, что формула С является логическим следствием из гипотез H₁,H₂,…,H_n, следует доказать, что H₁&H₂&…&H_n&  =0 . Так как левая часть последнего равенства представляет собой конъюнкцию, для его выполнения достаточно доказать равенство нулю любой входящей в уравнение формулы. Таким образом, для доказательства выводимости исходной формулы С необходимо доказать, что в множестве {H₁,H₂,_…,H_n, }имеется хотя бы одна невыполнимая формула. Для этого каждый элемент указанного множества рассматривается как элементарная дизъюнкция (дизъюнкт).

Вопрос№2

Определение.Одноместным предикатом P(x) называется произвольная функция переменной x, определенная на множестве М и принимающая значение из множества .

Определение. Предикатом Р называется n-местная функция, определенная на производном множестве М и принимающая в качестве значений элементы из двух элементного множества , где 0 и 1 интерпретируются как ложь и истина соответственно. Выражение вида  можно трактовать так, что переменные  связанны отношением Р.

Определение. Для предиката  можно выделить множество наборов , таких что , которые будут подставленными в предикат P приводят его к значению истина. Объединение всех этих наборов называется множеством истинных наборов предиката Р, обозначим его .

Определение. Предикат  называется тождественно истинным, если его множество  образуют все возможные наборы, которые можно определить на множестве М.

 Определение. Предикат  называется тождественно ложным, если его множество .

1. Квантор всеобщности ( ). Пусть P(x) это предикат определенный на множестве М. Тогда под выражением  - понимается высказывание, которое истинно для любого элемента . Соответствующее этому высказыванию предложение можно сформулировать так: "Для любого х выражение Р(х) истинно".

2. Квантор существования ( ). Пусть Р(х) это предикат определенный на множестве М. Тогда под выражением  понимается высказывание, которое истинно, если существует элемент , для которого Р(х) истинно, и ложно в противном случае. Соответствующее ему предложение: "Существует х, при котором значение Р(х) истинно".

1. Алфавит. В логике предикатов обычно используют следующие категории символов:

- предметные переменные - x, y, z и т.п. которые принимают значение из множества М;

- индивидные константы - a, b, c и т.п. То есть, нульместные функциональные константы или константы предметной области;

- функциональные константы - f, g, h и т.п. Используются для обозначения функций;

- высказывания - p, q, r и т.п.;

- предикатные константы - P, R, H, Q и т.п.;

- символы логических операций - &, ,  и т.д.;

- символы кванторных операций - ;

- вспомогательные символы - ( , ).

2. Правила построения формул. Для начала введем несколько определений, которыми будем оперировать при определении правил построения формул.

· Термом является всякая переменная и всякая функциональная форма;

· Функциональная форма - это функциональная константа, соединенная с некоторым числом термов. Если f - функциональная константа (n-местная) и  - термы, то соответствующая форма записывается так . Если n = 0, то f превращается в индивидную константу;

· Предикатная форма - это предикатная константа, соединенная с соответствующим числом термов. Если Р - предикатная константа m-местная константа и - термы, то соответствующая форма записывается так . Если m = 0, то пишут Р.

· Атом - это предикатная форма или некоторое равенство (выражение вида s=t, где s и t - термы). Для равенства характерно то же, что и для предикатной формы, т.е. о нем можно сказать, что оно истинно или ложно.

3. Определение аксиом. Выбор системы аксиом в исчислении предикатов может быть осуществлен по-разному. Один из наиболее простых способов состоит в том, что берутся уже ранее определенные аксиомы из исчисления высказываний и дополняются еще двумя, связанными с использованием кванторов. ; , где t - не содержит переменной х.

4. Правила вывода. Правила вывода так же полностью заимствуются из логики высказываний, кроме того, к ним добавляются еще два правила следующего вида:

- правило введения квантора существования: ;

- правило введения квантора общности: .

При этом в обоих случаях считается, что F не зависит от х.

Вопрос№3

    Унификация. Так как анализ выражений в формальных системах осуществляется в чисто синтаксической форме, без учета семантики, то возникает необходимость приведения отдельных выражений к единой форме. Эти приведения базируются на использовании унификации.

Например, для создания  из  и  необходимо найти подстановку «A вместо x», которая сделает идентичными W₁(A) и W₂(x). Поиск подстановок термов на место переменных называется унификацией. Унификация основывается на другом понятии - подстановка.

Определение. Подстановочным частным случаем называется подстановка в некоторое выражение термов вместо переменных.

Определение.Говорят, что множество E={E₁, E₂ , …, E_n } унифицируемо, если существует такая подстановка S, что E_1S = E_2S = … =E_nS. В этом случае подстановка S называется унификатором для множества E, т.к. после ее применении множество склеивается в один элемент.

Приведение формулы логики предикатов к множеству предложений. Как отмечалось ранее, рассматриваемый метод применим к множеству предложений. Поэтому, прежде, рассмотрим последовательность действий, которую необходимо реализовать, для приведения любой формулы логики предикатов к множеству предложений.

Шаг 1. Используя правила эквивалентных преобразований, в исходном выражении все логические операции записывают через операции дизъюнкции, конъюнкции и отрицания.

Шаг 2. Используя правила де Моргана, выполняются преобразования обеспечивающие применение операции отрицания только к литералам.

Шаг 3. Разделение переменных. Так как в пределах области действия квантора можно заменить любую переменную на другую, и от этого значение истинности формулы не изменится, можно преобразовать формулу так, чтобы каждый квантор имел свою собственную переменную, например, вместо  пишется .

Шаг 4. Исключение кванторов существования. Общее правило исключения квантора существования, состоит в замене каждого вхождения переменной, относящейся к квантору существования, на сколемовскую функцию, аргументы которой представляют собой те переменные, которые связаны с кванторами общности, в область действия которых попал квантор существования.

Шаг 5. Преобразование выражения в предваренную (префиксную) форму. Так как в формуле кванторы существования отсутствуют, то все кванторы общности можно переместить в начало формулы. Формула в таком виде называется формулой в предварительной форме, а цепочку кванторов перед ней префиксом, а следующее за ним бескванторное выражение – матрицей.

Шаг 6. Приведение матрицы выражения к форме КНФ. Известно, что любая логическая функция может быть представлена в виде КНФ. Для этого чаще всего используется метод эквивалентных преобразований.

Шаг 7. Исключение кванторов общности. Так как в выражении остались кванторы общности, а их порядок несущественен, то можно эти кванторы опустить, то есть удалить у формулы префикс.

Шаг 8. Переход от выражения в виде КНФ к множеству предложений. Для этого требуется убрать все операции конъюнкции, а каждый дизъюнкт представить как отдельное предложение, т.е. перейти от выражения вида  к выражению в котором каждый элемент предложение.

Шаг 9. Переименование переменных. Символы переменных должны быть изменены так, чтобы каждый появлялся не более чем в одном предложении. Этот процесс называется разделением переменных.

Вопрос №4

Продукционные модели

В общем случае продукционное правило представляет собой выражение вида: (i); Q;P;A->B;N

Смысл элементов:

· i – идентификатор продукции, т.е. это уникальное имя позволяющее выделить продукцию из множества других.

· Q – Область применения продукции

· P – Предусловие продукции

· A->B – ядро продукции

· N - Постусловие продукции

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

    Ядра продукции обычно разделяются на детерминированные и недетерминированные.

В первом случае при выполнении условия A, обязательно выполнится условие B

В недетерминированных, при выполнении А, В выполняется не обязательно, а например с некоторой вероятностью.

    Детерминированные ядра продукции разделяются на однозначные и альтернативные.

В однозначных в правой части всегда единственный результат.

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

    В общем случае структуру любой продукционной системы можно описать следующей схемой:

БД – в системах ИИ этот термин имеет иное значение, нежели в теории БД. Это хранилище информации о текущем состоянии решаемой задачи. В нее заносятся исходные данные и в ней же хранятся промежуточные и окончательные результаты.

БЗ – В ней хранятся продукционные правила описывающие предметную область решаемой задачи.

Блок управления – осуществляет управление стратегией вывода, для чего обращается к информации из БД и БЗ.

Диалоговый компонент – средство общения с внешней средой.

Процесс вывода в таких системах идет по следующей схеме:

    Исходные данные помещаются в БД и они считаются исходными истинными фактами, информация из БД сопоставляется с левыми частями продукционных правил из БЗ. Если обнаруживается совпадение, правило считается выполнившимся, и его результат, т.е. значение правой части, помещается в БД. Таким образом, появляются новая исходная информация для продолжения вывода. Процесс продолжается до тех пор пока искомый результат не окажется в базе данный или пока не сложиться ситуация когда невозможно подобрать новых правил для вывода в БЗ для текущих исходных данных из БД.

Управление стратегией вывода в продукционных системах

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

Традиционно различают два способа управления в продукционных системах: Централизованный и децентрализованный.

При централизованном управлении все решения принимаются некоторой внешней системой управления, при децентрализованном управлении стратегией вывода, управление складывается за счет текущей ситуации в системе.

    Различают следующие методы управлением выводом в продукционных системах:

1) Метод стопки книг.

Основная идея этого метода состоит в том, что все правила в БЗ изначально упорядочиваются в порядке убывания частоты (популярности) их использования.

Этот метод, возможно, применить только в том случае, если предметная область хорошо структурирована, и можно заранее упорядочить ее правила.

2) Принцип наиболее длинного условия.

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

3) Принцип мета продукции.

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

4) Метод классной доски.

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

5) Метод приоритетного выбора.

Идея в том, что каждому правилу приписывается некий коэффициент предпочтения, который может быть статическим или динамическим, он может задаваться изначально или формироваться в процессе вывода. Трактовка этого коэффициента также может быть различна. Например, коэффициент предпочтения заданный как оценка эксперта, достоверность правила, или частота обращений к правилу в процессе вывода.

6) Управление на основе специального, формального языка.

Идея в том, что вводится специальные правила, описанные на некотором формальном языке, которые говорят какой порядок применения правил является предпочтительнее в той или иной ситуации.