Материал: Алгебра_кортежей

Мы с детства приучены к тому, что Шерлок Холмс использовал дедуктивный метод. А так ли это? По определению дедукция – это когда имеются какие-то посылки или аксиомы и какие-то правила вывода, с помощью которых мы получаем следствия. Но мысль Холмса работала в другом направлении. Он знал некоторые факты, связанные с преступлением. Эти факты мало что говорили о мотивах преступления или о том, кто это преступление совершил. Если принять факты за аксиомы, то следствием этих фактов должно было стать некое утверждение, которое прямо указывает на того, кто преступник. Но по всем правилам логики из известных фактов такое утверждение получить было невозможно. Поэтому Холмс на первых этапах не пытался найти доказательства, а домысливал некоторые гипотезы или факты, которые позволяли бы построить строгую логическую цепочку между известными и пришедшими в голову фактами и самим преступлением. Таким образом, в данном случае дедукция была завершением мыслительной деятельности, а основная работа заключалась в том, чтобы найти не само следствие, а нечто, позволяющее его получить. Это нечто в логике называется не дедукцией, а абдукцией. Таким образом, метод Шерлока Холмса скорее абдуктивный, чем дедуктивный.

Классический пример абдукции – открытие нейтрино. Предполагалось, что одним из результатов эксперимента, связанного с изучением бета-распада, будет выполнение закона сохранения энергии. Расчеты показали, что при бетараспаде этот закон не соблюдается. Физик Вольфганг Паули в 1930 году предложил гипотезу о существовании некоторых "невидимых" частиц, которые образуются в ходе бета-распада и забирают часть энергии. В 1932 году Э. Ферми назвал эту частицу "нейтрино". Экспериментально существование нейтрино (точнее, его двойника – антинейтрино) было подтверждено лишь в

1953 году.

Дадим формальное определение абдукции. Пусть B – предполагаемое следствие из посылок A1, …, An, причем известно, что утверждение A G B, где по-прежнему A = A1 G … G An, неверно. Тогда формула H является допустимым абдуктивным заключением, если соблюдаются два условия:

1)H – корректная гипотеза (т.е. H G A не содержит коллизий);

2)(H G A) G B (т.е. при добавлении H в систему посылок

150

предполагаемое следствие B становится выводимым).

Рассмотрим интерпретацию абдукции с помощью диаграмм Эйлера. Когда B не является следствием A, то возможны два варианта: пересечение этих множеств пусто или не пусто (рис. 4.1). Обозначим закрашенную часть A, равную A \G B, как R.

Рис. 4.1. Соотношения между посылками (A) и невыводимым

следствием (B)

Вариант справа на рис. 4.1 – вырожденный. В таком случае никакое добавление посылок ни к чему не приведет. При непустом пересечении A и B (левая часть рисунка) получение абдуктивного заключения возможно, для этого область R должна быть полностью исключена из области допустимых гипотез, в противном случае H G A не будет включено в B. Значит, область

допустимых гипотез есть дополнение R, т.е. H G R.

Пусть Ri – некоторое надмножество R (на рис. 4.2 оно ограничено прерывистой линией), тогда возможны два случая (рис. 4.2). Ri можно рассматривать как некоторую гипотезу Нi.

Рис. 4.2. Варианты ситуаций при выборе гипотез

В первом случае (на рисунке слева) Ri не охватывает полностью A, значит, при пересечении Ri G A получим непустое множество, включенное в B, и Ri будет формально корректным абдуктивным заключением. Вырожденный случай, когда Ri G A = , показан на рисунке справа. Здесь видно, что Ri

151

полностью покрывает не только R, но и A. К такой ситуации применимо правило Дунса-Скотта: из лжи можно вывести все, что угодно. Поэтому при формировании Ri надо не только обеспечивать R G Ri, но и следить за тем, чтобы не выполнялось A G Ri.

Из вышесказанного следует

Алгоритм поиска абдуктивных заключений:

1.Вычислить «остаток» R = A \G B;

2.Построить промежуточный объект Ri такой, чтобы соблюдалось R G Ri;

3.Вычислить Hi = Ri (тогда Ri далее можно обозначить как Hi );

4.Вычислить Hi G A и выполнить проверку на наличие коллизий; если коллизии обнаружены, то возвратиться к шагу 2, иначе конец алгоритма.

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

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

Предположим, что вывод правильный. Тогда необходимо найти подходящие гипотезы, которые можно использовать в качестве посылок. Запишем в новых обозначениях промежуточные результаты примера 4.3:

B[X1X2X3X4] = [ {1} ].

Далее используем алгоритм.

152

2.Здесь можно выбрать в качестве Ri любую проекцию R. Пусть это будет R[X4]. Тогда получим Ri = [ {1}].

3.Hi = Ri = [ {0}].

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

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

Рассмотрим более сложные примеры.

Пример 4.8. [Страбыкин, 2008]. База знаний диагностики автомобиля содержит следующие правила.

1)если ИЗ ВЫХЛОПНОЙ ТРУБЫ ЧЕРНЫЙ ДЫМ, то БОГАТАЯ СМЕСЬ или РАННЕЕ ЗАЖИГАНИЕ.

2)если СИНИЙ ДЫМ, то ПОВЫШЕННЫЙ РАСХОД МАСЛА.

3)если ВЫХЛОПНАЯ ТРУБА ЧЕРНАЯ, то БОГАТАЯ СМЕСЬ или РАННЕЕ ЗАЖИГАНИЕ или ПОВЫШЕННЫЙ РАСХОД МАСЛА.

4)если ПОВЫШЕННЫЙ РАСХОД МАСЛА, то ИЗНОС МАСЛОСЪЕМНЫХ КОЛПАЧКОВ или ИЗНОС ПОРШНЕВЫХ КОЛЕЦ или ИЗНОС ЦИЛИНДРОВ.

5)если НОРМАЛЬНАЯ КОМПРЕССИЯ, то нет ИЗНОСА ПОРШНЕВЫХ КОЛЕЦ и нет ИЗНОСА ЦИЛИНДРОВ.

Предполагается, что следствие должно быть таким:

Если НОРМАЛЬНАЯ КОМПРЕССИЯ и ВЫХЛОПНАЯ ТРУБА ЧЕРНАЯ и СИНИЙ ДЫМ, то ИЗНОС ПОРШНЕВЫХ КОЛЕЦ.

Требуется проверить правильность следствия, а в случае неудачи подобрать абдуктивное заключение.

Введем обозначения:

153

x1 – выхлопная труба черная; x2 – богатая смесь;

x3 – раннее зажигание;

x4 – нормальная компрессия; x5 – повышенный расход масла;

x6 – из выхлопной трубы черный дым; x7 – из выхлопной трубы синий дым; x8 – износ маслосъемных колпачков; x9 – износ поршневых колец;

x10 – износ цилиндров.

Выразим правила формулами исчисления высказываний.

1)x6 (x2 x3);

2)x7 x5;

3)x1 (x2 x3 x5);

4)x5 (x8 x9 x10);

5)x4 ( x9 x10).

Предполагаемое следствие описывается формулой (x4 x1 x7) x9. Тогда база знаний, записанная в виде импликаций, есть множество из

шести дизъюнктов, входящих в определенную КНФ (правило 5 преобразуется в конъюнкцию двух дизъюнктов):

( x6 x2 x3) ( x7 x5) ( x1 x2 x3 x5) ( x5 x8 x9 x10)( x4 x9) ( x4 x10).

Данную КНФ можно представить как D-систему

Заключение в данном примере дается формулой (x4 x1 x7) x9, которая равна дизъюнкции ( x1 x4 x7 x9) и моделируется D-кортежем

B[X1X4X7X9] = ]{0} {0} {0} {1}[.

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

154