Суживающие стратегии поиска логического вывода на основе метода абстракций

2005 ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА Сер. 10 Вып. 1

ИНФОРМАТИКА

УДК 539.3

И. Л. Братчиков

СУЖИВАЮЩИЕ СТРАТЕГИИ ПОИСКА ЛОГИЧЕСКОГО ВЫВОДА НА ОСНОВЕ МЕТОДА АБСТРАКЦИЙ

Одним из широко используемых методов представления баз знаний (БЗ) в системах искусственного интеллекта является модель, основанная на исчислении предикатов первого порядка. Поиск выводов в логических БЗ осуществляется различными резо-люционными методами. Наиболее часто применяется входная линейная резолюция. На основе логического представления БЗ и входной линейной резолюции был разработан язык логического программирования Пролог, используемый для создания систем искусственного интеллекта.

Существенный недостаток резолюционных методов поиска логического вывода заключается в их невысокой эффективности, связанной с необходимостью перебора большого числа вариантов вывода, большинство из которых оказываются тупиковыми. В связи с этим актуальной является задача разработки суживающих (сокращающих перебор) стратегий. В настоящей статье представлены результаты исследований, выполненных автором совместно с рядом аспирантов и студентов Санкт-Петербургского государственного университета [1-5]. Их целью было создание суживающих стратегий, основанных на методе абстракций, который впервые предложен в [6]. Неформальное описание этого метода таково. По исходной задаче А строится более простая задача В так, чтобы для каждого решения задачи А имелось решение задачи В, структура которого в определенном смысле подобна решению задачи А. Найденные решения простой задачи В обычно называются схемами и используются для поиска соответствующих им решений исходной задачи. При этом некоторые решения задачи В могут не привести к цели, и такие схемы называются непродуктивными. Задача В строится с помощью так называемых абстракционных отображений, формально определенных в [7], и называется абстракционной, или абстракцией задачи А. Для успешного применения данного метода необходимо, чтобы, во-первых, абстракционная задача решалась существенно проще исходной и, во-вторых, решения абстракционной задачи позволяли найти все решения исходной задачи, сократив необходимый для этого перебор. Предлагаемые ниже суживающие стратегии удовлетворяют обоим требованиям.

Для формулировки интересующей нас исходной задачи необходимо определить понятие хорновских дизъюнктов. Это дизъюнкты, содержащие не более одной позитивной литеры. Обозначим позитивные литеры через Ь, негативные - через и определим 3 группы хорновских дизъюнктов:

1) унитарные позитивные или единичные дизъюнкты, состоящие из одной позитивной литеры и имеющие вид Ь;

© И. Л. Братчиков, 2005

2) точные дизъюнкты, состоящие из позитивной и хотя бы одной негативной литер и имеющие вид (Ьх,]Ь2,... ,]ЬП), п ^ 2;

3) негативные дизъюнкты, состоящие лишь из негативных литер и имеющие вид СЬх.....1ЬП).

Литеры хорновских дизъюнктов в исчислении предикатов являются предикатами или их отрицаниями, а в исчислении высказываний - высказываниями или отрицаниями высказываний.

Исходная задача в рассматриваемом случае может быть сформулирована следующим образом. Заданы:

- некоторая БЗ, состоящая из фактов и правил, представленных соответственно унитарными позитивными и точными дизъюнктами исчисления предикатов; обозначим множество дизъюнктов, входящих в БЗ, через Э' = { Их, ... , Оп }.

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

Дополним БЗ целью: 8 = 8' и {С}. Для решения задачи выполняется поиск выводов в расширенной БЗ Э пустого дизъюнкта Л. Поиск осуществляется алгоритмом, включающим две основные процедуры: унификации и резолюции.

Наиболее простой абстракцией, которую можно применить в качестве суживающей стратегии для решения сформулированной задачи, является пропозициональная. Она подробно рассматривается в [5], поэтому ограничимся лишь ее кратким описанием. По исходным БЗ и цели в исчислении предикатов строятся абстракции в исчислении высказываний. Построение выполняется следующим образом.

Пусть Ю - дизъюнкт вида (Гц, Ь2, ..., 1^). Тогда его пропозициональная абстракция определяется абстракционным отображением ^О) = В', где Ю' - дизъюнкт вида (Ц , Ц, ..., Ь 'к), Ц = Р, если и = Р( ..., Ьп),/Ц = "|Р, если = ..., Ьп), 1 ^^к. //

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

Сформулированная абстракционная задача решается значительно проще исходной. Известно, что в исчислении предикатов задача поиска логического- вывода в общем случае является КР-полной и лишь в случае существенных ограничений на хорнов-ские дизъюнкты (например, при использовании лишь одноместных предикатов) удается получить полиномиальные оценки. В то же время в исчислении высказываний большинство резолюционных методов имеют оценку трудоемкости Сп2, где п - число литер, присутствующих в БЗ, и С - коэффициент, не зависящий от п. В [1] предложен метод, имеющий оценку Сп. . *

Алгоритм поиска логического вывода в исчислении высказываний, который используется для решения абстракционной задачи, несколько отличается. от стандартного революционного метода. В исходной задаче литерами некоторого «дизъюнкта может оказаться один и тот же предикат, но с различными термами в качестве аргументов. Отображение пропозициональной абстракции поставит им в соответствие одинаковые литеры. Например, дизъюнкту Ю = (Р(а), С$(а,Ь), ]С^(с,с1)) исходной задачи пропозициональная абстракция поставит в соответствие дизъюнкт исчисления высказываний Б ' = (Р,](3,]С5). Обычно в подобных дизъюнктах повторяющиеся литеры сокращаются и, следовательно, Б' будет преобразован в (Р,]С^ ). Более того, пропозициональная абстракция дизъюнкта Б == (Р(а), ] Р(Ь), ](а,Ь))'окажется тавтологией И' = (Р, ]Р, и, , согласно стандартному алгоритму, должна быть исключена из рас-

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

. В связи со сказанным для абстракционной задачи вводятся понятия мулътидизъ-юнкта, т-абстракции и тп-резолюции. Мультидизъюнкт - это дизъюнкт, который может содержать несколько экземпляров одного и того же высказывания. М-абстракция - абстракция, ставящая в соответствие БЗ исходной задачи множество мультидизъ-юнктов. М-резолюция - резолюция, примененная к мультидизъюнктам. Алгоритмы поиска логического вывода, работающие с мультидизъюнктами, аналогичны стандартным, что будет видно из приведенного ниже примера. Введенные понятия будут нами использоваться не только для пропозициональной абстракции, но и для других ее типов, о которых речь пойдет далее.

Предложенный в [5] метод поиска решений в абстракционной задаче основан на формально-грамматической модели БЗ в исчислении высказываний и представлении выводов в БЗ выводами в моделирующей ее контекстно-свободной грамматике. Для поиска решений в исходной задаче был разработан алгоритм параллельного формирования выводов в абстракционной и исходной задачах, который выявляет непродуктивные схемы в процессе их построения. Работа алгоритма не зависит от порядка, в котором располагаются дизъюнкты БЗ, и, таким образом, он позволяет отказаться от используемых в системах, основанных на Прологе, понятиях декларативной и процедурной семантик. Кроме того, при некоторых ограничениях на БЗ алгоритм осуществляет построение выводов в порядке увеличения их длины. Эти особенности имеют немаловажное значение как с теоретической, так и с прикладной точек зрения.

Несмотря на очевидные преимущества применения пропозициональной абстракции в качестве суживающей стратегии, у нее имеется и недостаток, заключающийся в зачастую слишком большом числейывсщовв абстракционной задаче. Причина в том, что при замене предикатов высказываниями полностью исключаются из рассмотрения аргументы-термы предикатов. Поэтому нами были разработаны такие абстракции, которые, сохраняя простоту решения абстракционных задач, в той или иной степени учитывают аргументы предикатов исходной БЗ [4]. Эти абстракции осуществляют отображение БЗ и цели из исчисления предикатов в исчисления, которые можно назвать исчислениями псевдо-предикатов. Мы рассмотрим 3 типа абстракций, нумеруя их в порядке от пропозициональной до абстракции, наиболее полно учитывающей особенности ^сходной задачи.

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

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

Пусть дизъюнкт Б = (1ц, Ь2, ..., Ь*), где каждая литера Ь* есть предикат РД^, ..., 1;п) или его отрицание. Тогда ^(Б) = {Б'} - абстракция первого уровня, если Б' - дизъюнкт (Ь;1, Ь'2, .. •, Ь'*) и каждая \ ^ к, определяется следующим

образом:

а) если все термы 1,- (1 ^ ^ п)предиката Р* являются константами, то 1Д=

б) если среди ti есть хотя бы одна переменная или функция, то = Р* или 1/* = ]Р» в зависимости от того, является ли литера Ъ позитивной или негативной.

Абстракция второго уровня отличается от абстракции первого тем, что термы, являющиеся переменными, заменяются знаком «_», т. е. в предикатах остается информация о количестве и расположении таких термов. Формальное определение абстракции второго уровня таково.

Пусть И - дизъюнкт вида (Ьх, Ьг, ..., где каждая литера есть предикат Р^!, <;п) или его отрицание. Тогда Гг(О) = {Ю'} - абстракция второго уровня, если Ю' - дизъюнкт (Ь'х, Ь'г, ..., 1Д) и каждая 1/*, \ ^ к, определяется следующим образом:

а) если все термы ^ (1 ^ .} ^ п) предиката Рг являются константами, то 1/* =

б) если среди tj есть хотя бы одна переменная, то 1Л= Р^'х, ..., </п) или = ТР^'х, ..., 1/п) соответственно, причем, если ^ - константа, то ^ в противном случае « _ » .

Если абстракции предикатов первого и второго уровней имеют термы (константы или знак « _ » ), назовем их псевдо-предикатами. Нетрудно видеть, что абстракции предикатов первого уровня могут быть как высказываниями, так и псевдо-предикатами. Абстракции второго уровня всегда являются псевдо-предикатами. Как уже упоминалось, решение исходной задачи с помощью абстракции выполняется в два этапа. На первом решается абстракционная задача, на втором найденные на первом этапе выводы используются как схемы возможных выводов в исходной задаче. На этом этапе применяется общий алгоритм унификации [7]. Он ищет для унифицируемых литер, представленных одним и тем же предикатом, наиболее общую подстановку (наиболее общий унификатор, НОУ), применение которой обеспечивает равенство аргументов унифицируемых литер. По определению НОУ состоит из наименьшего возможного числа пар вида (х, 1), где х - переменная, а I - терм. Отсутствие унификатора для унифицируемых литер -называется унификационным отказом и означает, что данный вариант вывода является тупиковым.

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

Анализ на соответствие для первого и второго уровней выполняется по-разному. Опишем соответствующие алгоритмы.

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

a) они представлены совпадающими высказываниями или псевдо-предикатами;

b) одна из литер представлена высказыванием Р, а другая - псевдо-предикатом Р^'х, • •.,

В случае второго уровня правила соответствия несколько сложнее. Литеры соответствуют, если

a) они представлены совпадающими псевдо-предикатами;

b) они представлены псевдо-предикатами Р^'х, ..., 1/„) и Р(<;" х, • •., и для

каждой пары термов выполнено одно из следующих двух условий: либо они совпадают, либо один из термов представлен знаком «_» ), а второй - константой.

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

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

Линейным выводом во множестве дизъюнктов Б называется последовательность дизъюнктов С1,С2,-..,СП, в которой Сх 6 Б (Сх называется верхним дизъюнктом), а каждый из дизъюнктов Сг+1, г = 1,2,...,п - 1, является резольвентой дизъюнкта С^, называемого центральным, и дизъюнкта Б*, называемого боковым. При этом Б* должен удовлетворять одному из следующих двух условий: либо Б* 6 Б, либо Б* является некоторым дизъюнктом Спредшествующим в выводе дизъюнкту С*, т. е. э < г. Таким образом, линейный вывод начинается с некоторого дизъюнкта, к нему и другому дизъюнкту применяется правило резолюции для получения резольвенты, затем резолюция применяется к этой резольвенте и некоторому дизъюнкту, и так далее, пока не будет получен пустой дизъюнкт.

Входная линейная резолюция - это линейная резолюция, в которой одна из двух посылок - входной дизъюнкт, т. е. член заданного исходного множества Б дизъюнктов. При реализации входной линейной резолюции в системах искусственного интеллекта в качестве верхнего берется дизъюнкт цели, в качестве центральных дизъюнктов - резольвенты, а боковых дизъюнктов - факты и правила базы знаний. Входная линейная резолюция легла в основу языка логического программирования Пролог. Универсальный алгоритм поиска логического вывода, встроенный в системы программирования на базе языка Пролог, включает процедуры резолюции и унификации, а также бэктрекинг, т. е. перебор с возвратами, которые обычно называются откатами. Эти механизмы позволяют находить все возможные/решения описанной логической программой задачи.

Приведем пример, иллюстрирующий работу алгоритмов поиска логического вывода, реализующих метод входной линейной резолюции и использующих абстракции трех рассмотренных уровней. Будем использовать следующие обозначения: Р1-Р5 -предикаты, а,Ь,с,с1,е - константы, \у,х,у,г - переменные. Пусть база знаний Б'-представлена следующими дизъюнктами:

1. Р1(а); 5. (Р1(х),}Р3(с,у))]

2. Р2(Ь,а^); 6. (Р2(х,2,а), 1Р3(с1,2));

3. Р3(с,а); 7. (Р5(х,е),1Р1(Ь));

4. (Рх(ш), ]Р4(а)); 8. (Р5(х,а), 1Р3(х,у), "|Р2(Ь,а,е)).

Предположим, требуется найти выводы цели Р5(х,у)ДР2(Ь,г,а). Сформируем множество Б, добавив к Б' отрицание цели в виде негативного дизъюнкта: (]Рб(х,у), 1Р2(Ь,г,а)).

Алгоритм входной линейной резолюции, осуществляющий унификацию и бэктрекинг, обнаружит 4 унификационных отказа, один тупик и найдет 2 вывода. В них после каждого центрального дизъюнкта укажем в квадратных скобках номер бокового дизъюнкта, использовавшегося для вычисления резольвенты, а в фигурных скобках -унификатор:

I. (1Р5(х,у), lft(b,z,a)), [7], {(у,е)}; (^(Ь), lP2(b,z,a)), [5], {(x,b)}; (1Р3(с,у), lP2(b,z,a)), [3], {(у,a)}; lP2(b,z,a), [2], {(z,a), (w,a)}; Л.

И. (1Р5(х,у), lP2(b,z,a)), [8], {(у,а)}; С]Р3(х,а), ]Р2 (b,a,c)/|P2(b,z,a)), [3], {(х,с)}; 1Р2(Ь,а,с), ]Р2 (b,z,a)), [2], {(w,c)}; lP2(b,z,a), [2], {(z, a), (w,a)}; Л.

Теперь рассмотрим алгоритмы поиска вывода, использующие абстракции. При построении абстракционной задачи нулевого уровня получим следующую БЗ (в исчислении высказываний):

1. Pi; 5. (Pi, 1Р3);

2. Р2; 6. (Р2,1Р3);

3. Р3; 7. (P5,lPi);

4. (Рь1Р4); 8. (Р5,]Рз,1Р2).

Абстракция цели такова: (\Ръ, 1Р2)- Алгоритм обнаружит один тупик и найдет 8 решений, которые будут использоваться как схемы для поиска выводов в исходной задаче:

1. flft, 1Р2), [7]; (1 ft, 1Р2), [1]; 1Р2, [2]; Л.

2. (1Р5,1Р2), [7]; (1 Рь ]Р2), [1]; ]Р2, [6]; ]Р3, [3]; Л.

3. (1Р5, 1Р2), [7]; (1 Рь 1Р2), [5]; С|Р3, 1Р2), [3]; ]Р2, [2]; Л.

4. (1Р5,1Р2), [7]; (1 Р1( lft), [5]; (1Р3) ]Р2), [3]; 1Р2, [6]; lft, [3]; Л.

5. (]Р5, 1Р2), [8); (1Р3, 1Р2, 1Р2), [3]; С|Р2, 1Р2), [2]; ]Р2, [2]; Л.

6. С|Р5, ]Р2), [8]; С|Р3, ]Р2, 1Р2), [3]; flft, ]Р2), [2]; Щ, [6]; Щ, [3]; Л.

7. (1Р5, 1Р2), [8]; (1Р3, 1Р2, 1Р2), [3]; (]Р2, 1Р2), [6]; (1Р3, lft), [3]; 1Р2, [2]; Л.

8. (1Р5,1Р2), [8]; (1Р3, 1Р2, 1Р2), [3]; flft, lft), [6]; QP3, ]Р2), [3]; ]Р2, [6]; lft, [3]; Л.

Заметим, что в выводах 5-8 имеются мультидизъюнкты (]Р3, ]Р2, ]Р2) и (]Р2,]Р2). Используем приведенные схемы для вычисления выводов в исходной задаче. Для этого/применяем к цели и резольвентам факты и правила исходной БЗ, номера которых указаны в схемах. Схема окажется продуктивной и позволит найти соответствующий вывод, если на каждом шаге вывода будет установлен НОУ. При обнаружении унификационного отказа схема непродуктивна. Легко убедиться, что продуктивными являются схемы 3 и 5, которые позволят найти выводы 1 и 2 исходной задачи. Все остальные схемы окажутся непродуктивными из-за унификационных отказов. Попытаемся, например, найти вывод по схеме 1:

С|Р5(х,у), ]P2(b,z,a)), [7], {(у,е)}, (lft(b),lP2(b,z,a)), [1]. Факт 1 БЗ имеет вид Pi (а) и не унифицируется с первой литерой Pi(b) центрального дизъюнкта. Таким образом, получим унификационный отказ, и поэтому схема 1 оказалась непродуктивной.

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

1. Pi(a);

2. Р2;

3. Р3(с,а);

4. (Pi,lP4(a));

5. (Рь1Рз);

6. (Р2, ~|Р3);

7. (P5,lPi(b));

8. (Р5,1Р3,1Р2(Ь,а,е)).

Абстракция цели такова: (]Р5, ]Р2). Алгоритм обнаружит один тупик, два псевдо-унификационных отказа и найдет 6 решений:

- (lft. [7]; (lft(b), 1Р2), [5]; (lft, lft), [3]; ]ft, [2], A.

2. (1Р5, 1Ра), [7]; (lPi(b), 1P2), [5]; flP3, ]P2), [3]; 1P2, [6], 1P3, [3]; A.

3. (1P5, ]P2), [8]; (1P3, lP2(b,a,e), 1P2), [3]; C|P2(b,a,e), ]P2), [2]; ]Р2, [2]; A.

4. (]P5, ]P2), [8]; (1P3, lP2(b,a,e), 1P2), [3]; (]P2(b,a,e), ]P2), [2]; 1P2, [6]; ]P3, [3]; A.

5. (1P5,1P2), [8]; C|P3, ]P2(b,a,e), ]P2), [3]; C|P2(b,a,e), 1P2), [6]; (1P3, Щ), [3]; -1P2, [2]; A.

6. (]P5, 1P2), [8]; C|P3, 1Р2(Ь,а,е), 1P2), [3]; (1Р2(Ь,а,е), Щ), [6]; (]P3, ]P2), [3]; 1P2, [6]; IPs, [3]; A.

Число найденных схем сократилось на две. Продуктивными являются схемы 1, 3. Применим абстракцию второго уровня. При этом, не теряя общности, будем опускать термы у тех псевдо-предикатов, у которых все термы представлены знаком «_». Например, Pi(_) представим как Рь ]Р3(_,_) как ]Р3 и т. д. С учетом этого соглашения БЗ примет вид

1. Pi (а) ; 5. (РьШО);

2. Р2(Ь,а,_); 6. (P2(-,-,a),]P3(d,_));

3. Р3(с,а); 7. (PsUe^P^b));

4. (Рь 1Р4(а)); 8. (Р5(-,а), ]Р3,1Р2(Ь,а,е)).

Абстракция цели такова: (IPs, ]Р2(Ь,_,а)). Алгоритм обнаружит один тупик, четыре псевдо-унификационных отказа и найдет только два решения:

1. (1Р5, 1Р2(Ь,.,а)), [7]; QP^b), 1Р2(Ь,_,а)), [5]; (]P3(c,_), lP2(b,_,a)), [3]; lP2(b,_,a), [2]; A.

2. QPs, ~|P2(b,_,a)), [8]; (]P3, lP2(b,a,e), lP2(b,_,a)), [3]; (]P2(b,a,e), ]P2(b,_,a)),. [2]; lP2(b,_,a), [2]; A.

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

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

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

Summary

Bratchikov I. L. Restricting strategies of logical inference search based on abstraction method.

Methods of logical inference search with three different levels of abstraction are considered. In the most generic terms an abstraction is a function that maps certain class of problems S onto a simpler class of problems T. In order to solve a problem A € S it is mapped onto a problem В € Т. Then В is solved and the solution of В is used for solving the initial problem A. In this paper levels of abstraction axe defined and exploited for solving deduction problem in the first-order predicate calculus by mapping it onto deduction problem in the propositional or pseudo-predicate calculus. The methods allow improving the efficiency of logical inference search for knowledge bases.

Литература

1. Анисимова И. Н., Братчиков И. Л. Формально-грамматическая модель метода резолюций для исчисления высказываний//Вестн. С.-Петерб. ун-та. Сер. 1: Математика, механика, астрономия. 1996. Вып. 3 (№ 15). С. 3-7.

2. Анисимова И. Н., Братчиков И. Л. Двухэтапный алгоритм логического вывода в ЭОС // Труды Междунар. семинара «Искусственный интеллект в образовании». Казань, 1996. С. 16-19.

3. Анисимова И. Н., Братчиков И. Л. Эффективный метод построения логических выводов в стационарных базах знаний // Учен. зап. Ленингр. обл. гос. ун-та. Сер. Математика и информатика. СПб., 1998. Т. 1. С. 12-16.

4. Братчиков И. Л., Калинина Т. В. Абстракционные модели построения логического вывода // Процессы управления и устойчивость. Труды XXXI науч. конференции. СПб., 2000. С. 281-286.

5. Bratchikov I. L. Application of abstraction method for search of logical inference in knowledge bases // Proc. of FDPW'2001-2002: Advances in methods of modern information technology. Petrozavodsk, 2003. Vol. 4. P. 167-178.

6. Plaisted D. A. Theorem proving with abstraction // Artificial Intelligence. 1981. Vol. 16. N 1. P. 47-108.

7. Тейз А., Гоше P., Грибомон П. и др. Логический подход к искусственному интеллекту: от классической логики к логическому программированию / Пер. с франц.; Под ред. Г. П. Гаврилова. М., 1990. 287 с.

Статья поступила в редакцию 21 апреля 2005 г.