6.1. Подстановки и унификация.

Определение 6.1. Подстановка – это конечное множество вида {t₁/v₁, …,t _n/v_n}, где каждая v _i – переменная, а каждый t_i – терм, отличный от v_i и все v_i различны. Подстановка, которая не содержит элементов, называется пустой и обозначается .

Определение 6.2. Пусть  = {t₁/v₁, …,t _n/v_n} – подстановка и Е –выражение. Тогда Е - выражение, полученное из Е одновременной заменой всех вхождений переменной v_i на терм t_i.

Е называют примером Е.

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

{E₁,E₂,…,E _k } тогда и только тогда, кода E₁ = E₂=…= E_k. Если для множества Е существует унификатор, то оно называется унифицируемым.

Определение 6.4. Унификатор  для множества {E₁,E₂,…,E _k } будет наиболее общим унификатором тогда и только тогда, когда для каждого унификатора  этого множества найдется такая подстановка , что =

Пример. Множество {P(a,y), P(x,f(b))} унифицируемо, так как подстановка  = {a/x, f(b)/y} является его унификатором.

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

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

Пример. 2.2.3. Если W = {P(x, f(y, z)), P(x, a), P(x, g(h(k(x))))}, то первой позицией, в которой появляются различные символы, является пятая (символы P(x, первых четырех позиций во всех выражениях из W совпадают); таким образом, множеством рассогласований будет являться множество W = {f(y, z), a, g(h(k(x)))}.

6.2. Алгоритм унификации.

Перейдем теперь к алгоритму унификации:

Алгоритм унификации.

Шаг 1. Положим k=0, W_k= W и  _k= .

Шаг 2. Если W_k – единичный дизъюнкт, то _k–наиболее общий унификатор для W. В противном случае – поиск множества D_k рассогласований для W_k.;

Шаг 3. Если существуют такие элементы v_k и t _k в D_k, что v_k - переменная, не входящая в t _k, то перейти к п.4.

Иначе W не унифицируемо;

Шаг 4. Пусть _k+1=_k{t_k / v_k} тогда W_k+1= W _k{t_k / v_k};

Шаг 5. k := к+1; переход к п. 2.

Приведем некоторые примеры применения унификации.

Пример 1. Пусть W = {Q(f(a), g(x)), Q(y, y)}

1. Положим ₀ =  и W₀ = W;

2. Множество рассогласований для W₀ – D₀ = {f(a), y}, т.е.

v₀ = y и t₀ = f(a);

3. Тогда ₁=₀{t₀ / v₀} = {f(a)/y} = {f(a)/y};

4. W₁= W₀{ t₀ / v₀} = {Q(f(a), g(x), Q(y, y)} {f(a)/y}=

{Q(f(a), g(x), Q(f(a), f(a))};

5. Множество рассогласований для W₁ – D₁= {g(x), f(a)},

6. Так как подстановки, исключающей последнее рассогласование не существует, то множество W не унифицируемо.

1. Пример 2. Пусть W={P(x,f(y)), P(a,u)}. На первом проходе алгоритма будет найдена подстановка ₁= a/x , так как множество рассогласований D₀={x,a}. Множество W₁ будет равно {P(a,f(y)),P(a,u)}. На втором проходе алгоритма подстановка будет расширена до ₂={ a/x, f(y)/u)} и W₂={P(a,f(y))}. Так как W₂ состоит из одного литерала, то алгоритм закончит работу и выдаст s₂.

2. Пример 3. Пусть W={P(x,f(y)), P(a,b)}. На первом проходе алгоритма будет найдена подстановка ₁= a/x и W₁={P(a,f(y)), P(a,b)}. На третьем шаге второго прохода будет выдано сообщение о том, что множество W неунифицируемо, так как множество рассогласования D₁={f(y),a} не содержит переменной.

3. Отметим, что при выполнении шага 4 из множества W_k удаляется одна из переменных (переменная v_k), а никакой новой переменной не возникает. Это означает, что алгоритм унификации всегда заканчивает работу. Ясно также, что если алгоритм заканчивает работу на шаге 3, то множество М неунифицируемое. Также понятно, что если алгоритм заканчивает работу на шаге 2, то _k – унификатор множества W.

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

1. Взятие отрицания исходной формулы;

2. Приведение формулы к Сколемовской нормальной форме;

3. Нахождение унифицирующих подстановок и унификация множества дизъюнктов формулы;

4. Резольвирование множества дизъюнктов и нахождение пустого дизъюнкта (если таковой существует).

Примеры.

В заключение параграфа рассмотрим несколько примеров применения метода резолюций в исчислении высказываний (Пример 1) и в исчислении предикатов (Примеры 2,3).

Пример 1. Даны 4 утверждения:

Преобразуем все утверждения в стандартную форму:

(1)

Докажем путем опровержения, что - логическое следствие из (1), (2) и (3). Отрицаем (4) и получаем:

отрицание заключения,

резольвента (3) и (1),

резольвента (5) и (2),

резольвента (6) и (4).

Пример 2. Дано множество формул:

Доказать, что является логическим следствием и . Преобразуем и в стандартную форму и подучим следующие пять дизьюнктов:

(1)

(2) из

(3) (4) O из (5) из Это множество дизьюнктов невыполнимо. Докажем при помощи метода резолюций:

(6) резольвента (3) и (2),

(7) резольвента (5) и (4),

(8) □ резольвента (7) и (6).

Т.о - логическое следствие и .

Пример 3.

Дано множество формул:

Преобразуем , и в следующие дизъюнкты:

(1)

(2) из ,

(3) из ,

(4)

(5) из

Используя метод резолюций, получим:

(6) резольвента (4) и (2),

(7) резольвента (3) и (1),

(8) резольвента (5) и (7),

(9) □ резольвента (6) и (8).

Лекция 7. Правдоподобные рассуждения. Автоматизация индуктивных расуждений.

7.1. Понятие квазиаксиоматической теории.

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

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

А, АВ  ВА. Далее, для них характерна контекстная зависимость от условий применения посылок; следующей их характеристикой является неполнота информации, часто приводящая к использованию посылок с неопределенным истинностным значением. Это последнее обстоятельство означает, в частности, многозначность используемой для формализации подобных рассуждений логики.

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

Логическим уточнением понятия открытого мира является понятие квазиаксиоматической теории, введенное В.К. Финном [20].

Квазиаксиматическая теория K = <, `, R > , где

 - некоторое множество аксиом предметной области, не полностью её харатеризующее;

`- множество фактов предметной области или гипотез;

R –множество правил вывода (как достоверного так и правдоподобного).

Пусть К_n– состояние квазиаксиоматической теории, полученное в результате n последовательных применений правил правдоподобного вывода из R, К_n= <_n, `<sub>n</sub>, R > , а К<sub>0</sub>– начальное состояние ( к которому ещё не применялись правила правдоподобного вывода), тогда пара <, ` > , где = и `= `_n соответствуют n-му состоянию базы знаний.

Последовательность состояний К₀ , К₁ ,…, К_n квазиаксиоматической теории К, такая, что К₀– начальное состояние, К_n– заключительное состояние, такое, что применение правил правдоподобного вывода к К_n порождает К_n+1, причем К_n+1 = К_n называется р – рассуждением. Применение правил достоверного вывода из R к результатам р - рассуждения называется pr – рассуждением.

Вывод называется монотонным, если имеет место:

Если Ф выводима из Г, где Г – некоторое множество формул, то Ф выводима из Г и  - где  - формула. В противном случае, вывод называется немонотонным.

Рассмотрим правило индуктивного вывода А(а₁), …, А(а_n)  хА(х), введенное в 2.1.2. Если элементы а₁, …,а_n не исчерпывают U, то новый индивид а_n+1 U может не обладать свойством А и заключение хА (х) оказывается несправедливым. Это означает, что хА (х) не выводится из

А(а₁), …, А(а_n) и В (а_n+1) (где В – какое либо свойство а_n+1), т.е. индуктивный вывод не является монотонным.

7.2. ДСМ - метод индуктивного вывода.

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

Индуктивные рассуждения можно рассматривать как инструмент для порождения гипотез. При этом порождаемые гипотезы не обязаны быть достоверными и требуют дальнейшего анализа, результатом которого должно явиться их обоснование (либо опровержение). Но это задача других методов, один из которых, рассуждения на основе аргументации, будет рассмотрен в следующем параграфе, а пока займемся изучением индуктивного метода порождения гипотез в том виде, в каком его предложил В.К.Финн [22].

Идея метода восходит к 1900 году. Она была предложена в начале XX века английским логиком и философом Джоном Стюартом Милем. Эта идея такова: пусть задано множество структур типа объект – свойство. Пусть задача состоит в том, что для некоторого нового объекта требуется установить его неизвестное свойство. В основе подхода лежит предположение о том, что за каждое свойство объекта отвечает некоторая его составная часть или фрагмент. Поэтому на первом этапе для заданного свойства выполняется поиск фрагментов объектов, «ответственных» за это свойство. Для этого анализируются структуры объектов и выполняется поиск объектов, имеющих совпадающие свойства и структурное сходство. Полагается, что именно общие фрагменты объектов, обладающих совпадающими свойствами, являются причиной этих свойств. Затем выполняется поиск такого рода фрагментов в новых объектах и если такие фрагменты обнаружены, объектам приписываются свойства, причинами которых являются обнаруженные фрагменты. В простейшем случае полагается, что свойства, за которые ответственны те или иные фрагменты, порождаются только этими фрагментами и никак не зависят от окружения или контекста. Иначе говоря, предполагается, что свойства целого сводятся к сумме свойств его частей Метод, основанный на указанных соображениях, был назван ДСМ - методом. Здесь мы изложим формализацию ДСМ – метода в интерпретации [23]. Опишем вначале кратко его схему.

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

Определим далее отображение , так что f(p_j, o_i) = F_ij, где F_ij  V.

Полагаем , если достоверно известно, что объект обладает свойством ; а именно, , означает, что гипотеза «объект обладает свойством » опровергается (имеются только аргументы "против" и ни одного аргумента "за"). Если , то это означает фактическую противоречивость, то есть гипотеза имеет как аргументы "за", так и аргументы "против". Если , то это значит, что гипотеза не имеет ни одного аргумента "за" и ни одного аргумента "против"., т.е. оценка её значения - «неопределённость».

Таким образом, функция F задана следующей матрицей:

_{где FijV}

Эту матрицу можно считать базой экспериментальных фактов. Задача состоит в том, чтобы преобразовать матрицу в матрицу , такую что , если ; в противном случае следует доопределить матрицу F, заполнив её клетки значениями, отличными от .

Эта задача решается следующим образом:

А) вначале следует найти связи фрагментов объектов со свойствами последних. Эти связи будут представлены в матрице .

где H_ij V.

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

Теперь опишем шаги А и Б более подробно.

Для этого введем правила 1-го и 2-го рода.

Правила 1-го рода служат для порождения гипотез о причинах свойств объектов.

Пусть , и является фрагментом , то есть .

Определение 7.1. Пусть - некоторое свойство . Будем называть о положительным примером для относительно , если .

Обозначение: - множество положительных примеров

Определение 7.2.. Пусть - некоторое свойство . Будем называть о отрицательным примером для относительно , если .

Обозначение: - множество отрицательных примеров

Определение 7.3. Пусть - некоторое свойство . Будем называть о неявным примером для относительно , если .

Обозначение: - множество неявных примеров

Определение 7.4. Пусть - некоторое свойство, - некоторый фрагмент , т. е. . Будем говорить, что удовлетворяет - условию для относительно , если , так что

1. 

2. содержит больше одного элемента, то есть .

Обозначение: -: обладает - условием для относительно .

Аналогичным образом вводятся определения для - условия и - условия:

Определение 7.5. Пусть - некоторое свойство, - некоторый фрагмент o, то есть . Будем говорить, что удовлетворяет - условию для относительно , если , так что

3. 

содержит больше одного элемента, то есть .

Обозначение: -: обладает - условием для относительно .

Определение 7.6. Пусть - некоторое свойство, - некоторый фрагмент o , то есть . Будем говорить, что удовлетворяет - условию для относительно , если , так что

4. 

содержит больше одного элемента, то есть .

Обозначение: -: обладает - условием для относительно .

Построим матрицу - матрицу гипотез – следующим образом:

По существу, это правило вывода, которое и называется правилом вывода 1-го рода.

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

Правила 2-го рода служат для порождения гипотез о наличии свойств у объектов или, иначе говоря, для доопределения матрицы F.

Пусть - некоторый объект, - некоторое свойство.

Будем говорить, что объект удовлетворяет -условию для относительно , если и . Обозначим её через .

Будем говорить, что объект удовлетворяет -условию для относительно , если и . Обозначим её через: .

Будем говорить, что объект удовлетворяет -условию для относительно , если и . Обозначим её через: .

Матрица <sub>`</sub> определяется следующим образом: F<sub>ij</sub>`= F_ij если и только если

F_ij # τ; в противном случае:

Эта последняя матрица, собственно, и дает ответ на поставленный в начале вопрос. Затем процедура повторяется для следующего свойства и так до вычисления всех неопределённых в F значений. Однако, для вычисления некоторых неопределенных значений в исходной матрице, т. е. в базе фактов может оказаться недостаточно информации. Тогда матрицу F следует пополнить новыми фактами. Может оказаться, что при таком пополнении матрицы F значения F_ij, подсчитанные на предыдущих итерациях, могут измениться. Тогда процесс пополнения и пересчета значений F_ij следует продолжить до стабилизации матрицы F^/ (если таковая произойдет).

Лекция 8. Правдоподобные рассуждения. Автоматизация аргументационных рассуждений и расуждений на основе прецедентов.