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

На правах рукописи

Томчук Максим Николаевич

РАЗРАБОТКА МЕТОДА И СИСТЕМЫ

ЛОГИЧЕСКОГО ВЫВОДА МОДИФИЦИРУЕМЫХ ЗАКЛЮЧЕНИЙ

Специальность 05 13 01 - Системный анализ, управление и обработка информации (промышленность) в технических науках

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Киров 2007

003175207

Работа выполнена на кафедре электронных вычислительных машин Вятского государственного университета

Научный руководитель доктор технических наук, профессор

Дмитрий Алексеевич Страбыкин

Официальные оппоненты: доктор технических наук, профессор

Александр Вениаминович Частиков,

кандидат технических наук, профессор Станислав Михайлович Окулов

Ведущая организация Научно-исследовательский институт

средств вычислительной техники, г Киров

Защита состоится 9 ноября 2007 г. в 12 час 00 мин. на заседании диссертационного совета К212 042 01 при Вятском государственном университете по адресу 610000, Киров, ул. Московская, 36 (ауд 1-310)

С диссертацией можно ознакомиться в библиотеке Вятского государственного университета

Автореферат разослан 8 октября 2007 г

Ученый секретарь

диссертационного совета К212 042 01 кандидат технических наук, доцент

В Г Ланских

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Одним из многообещающих направлений в вычислительных системах" сегодня являются системы обработки знаний (СОЗ), моделирующие поведение естественного интеллекта Они имеют широкое распространение, а в перспективе смогут применяться практически повсеместно, повышая интеллектуальный уровень вычислительных систем Однако, несмотря на имеющиеся успехи, современные СОЗ имеют ряд недостатков В частности, они не способны решать задачи, требующие наличия достоверного заключения при имеющемся недостоверном Кроме того, современные СОЗ работают неэффективно на параллельных платформах

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

Моделирование рассуждений средствами логики осуществляется при помощи логического вывода (JIB) Исходными данными для логического вывода служат формулы посылок и заключения Посылки представляют собой набор фактов и правил вывода и составляют базу знаний (БЗ) Заключение записывается в виде формулы логики и поступает извне в систему JIB

Обычно выделяют следующие основные виды логического вывода дедуктивный, абдуктивный и индуктивный Дедуктивный вывод позволяет ответить на вопрос о выводимости заключения Абдуктивный вывод невыводимого заключения позволяет пополнить набор исходных посылок фактами так, чтобы заключение стало следствием БЗ Индуктивный вывод, в отличие от абдуктив-ного, позволяет пополнить набор исходных посылок общими правилами

Данные виды вывода известны достаточно давно и могут применяться для решения широкого круга задач Однако существует класс задач, решить которые применением указанных видов вывода невозможно или затруднительно Данный класс задач предполагает наличие корректной и полной БЗ для некоторой предметной области и недостоверное заключение, требующее преобразования Следовательно, появляется принципиально новая постановка задачи JIB модифицировать исходно невыводимое заключение с целью сделать его следствием исходных посылок Данная задача решается посредством применения нового вида ЛВ - логического вывода модифицируемых заключений

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

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

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

Таким образом, является актуальной задача разработки метода и системы параллельного логического вывода модифицируемых заключений на знаниях, представленных в виде формул исчисления высказываний и исчисления предикатов первого порядка, что позволит расширить класс задач, решаемых СОЗ, построенных на основе системы JTB, и повысить скорость их работы

Диссертационные исследования выполнялись в рамках НИР «Теория и применение логического вывода с модификацией заключений» (грант Министерства Образования РФ Е02-2 0-93), а также в рамках НИР «Разработка среды декларативного логического программирования для кластерной вычислительной системы» (ВятГУ, НИР №412)

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

Предметом исследований являются методы и средства логического вывода модифицируемых заключений, а также СОЗ различного назначения, использующие представление знаний в виде логических формул и основанные на логическом выводе модифицируемых заключений

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

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

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

3. Разработать систему логического вывода на основе MJIB модифицируемых заключений

4 Разработать критерии эффективности работы машины и системы логического вывода модифицируемых заключений

Методы исследования/ Для достижения' поставленной в работе цели использовались методы системного анализа и синтеза, теории множеств, теории графов, математической логики, теории логического и объектно-ориентированного программирования

На научную новизну претендуют

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

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

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

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

Практическая ценность исследования состоит в следующем

1 Разработана структура машины логического вывода модифицируемых заключений В отличие от существующих, разработанная МЛВ позволяет распараллелить процесс вывода вплоть до уровня операций унификации литералов, что повышает скорость логического вывода на параллельных вычислительных платформах Кроме того, МЛВ способна выполнять три вида вывода дедуктивный, абдуктивный и вывод модифицируемых заключений

2 Разработана система логического вывода модифицируемых заключений, отличительными особенностями которой являются применение параллельных методов и машины ЛВ, использование двухуровневой базы знаний, наличие блока интерпретации формул, что позволяет строить на основе системы логического вывода высокопроизводительные СОЗ различного назначения

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

ния вычислительными процессами, в интеллектуальных обучающих системах, в экспертных системах

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

Внедрение результатов исследования. Полученные теоретические и практические результаты использованы в НИР «Теория и применение логического вывода с модификацией заключений» (грант Министерства Образования РФ Е02-2 0-93), в НИР «Разработка среды декларативного логического программирования для кластерной вычислительной системы» (ВятГУ, НИР №412), а также в учебном процессе в Вятском государственном гуманитарном и Вятском государственном университетах

Апробация работы. Основные положения и результаты исследования докладывались и обсуждались на 5-й международной конференции «Interactive Systems The Problems of Human-Computer Interaction», Ульяновск, 2003, 9-й «Национальной конференции по Искусственному Интеллекту КИИ-2004», Тверь, 2004, Всероссийской ежегодной научно-технической конференции ВятГУ «Наука-производство-технологии-экология», г Киров (2004, 2007 гг)

Публикации. Результаты исследования представлены в 10 работах, из них 5 статей, 4 тезисов докладов

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка сокращений и библиографического списка (включающего 150 наименований) Основная часть работы изложена на 166 страницах и содержит 33 рисунка и 6 таблиц

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Приводится классификация видов логического вывода Рассматриваются основные виды JIB дедуктивный, абдуктивный и индуктивный Задачей дедук-

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

Рассматривается ЛВ модифицируемых заключений, который преобразует невыводимое из исходных посылок заключение, в результате чего заключение становится следствием исходных посылок В отличие от абдуктивного и индуктивного видов вывода, ЛВ модифицируемых заключений не пополняет БЗ, то есть не происходит обучение БЗ При этом не предъявляется требование достоверности к заключению, но требуется наличие свойства полноты у базы знаний (в пределах предметной области СОЗ) В противном случае возможна модификация корректного с точки зрения здравого смысла заключения

Приводится классификация методов ЛВ Методы могут различаться формой представления знаний, законами логики, принципом вывода, направлением, тактикой и стратегией От формы представления знаний зависит, в каком виде представляются исходные посылки и заключение Законы логики во многих методах вывода используются в качестве правил вывода либо правил, позволяющих выполнить преобразования логических формул Принцип вывода определяет, каким образом будет производиться вывод Направленность задает направление поиска решения, тактика вывода определяет способ просмотра графа состояний, стратегия вывода задает общую процедуру вывода

Недостатком большей части методов вывода является последовательный принцип обработки знаний, что сильно снижает производительность СОЗ Применять подобные методы на многопроцессорных и многомашинных вычислительных системах не имеет смысла Наиболее удобен для параллельной реализации метод, основанный на принципе деления дизъюнктов (ДД), поскольку позволяет распараллелить процесс вывода вплоть до элементарных операций Поэтому данный метод выбран в работе в качестве базового

Метод ДД основан на операции ДД, которая может быть записана следующим образом 0-с1=Ь Операция представляет собой исключение из дизъюнкта Б литералов, содержащихся в дизъюнкте <1 Если исключены все литералы, Ь принимается равным нулю, если ни одного - единице Суть метода ДД заключается в применении процедуры ДД ко всем выводимым дизъюнктам данного шага При этом возможно образование дизъюнктов, требующих вывода Данные дизъюнкты обрабатываются на следующем шаге ДД-вывода

Основным компонентом СОЗ является машина логического вывода В работе приводится классификация МЛВ В качестве классифицирующих при-

знаков выделяются назначение СОЗ, модель знаний, вид вывода, реализация, методы вывода

Как правило, СОЗ состоит из следующих основных подсистем подсистемы интерфейса, подсистемы хранения данных и знаний, подсистемы логического вывода и подсистемы обучения Подсистема интерфейса включает блоки для взаимодействия с пользователем и с внешней средой Подсистема хранения данных и знаний состоит из базы данных и базы знаний Подсистема логического вывода содержит основное решающее устройство системы - MJIB Подсистема обучения создает и пополняет БЗ на основе данных, поступающих от пользователя или внешней среды, например, с использованием индуктивного и абдуктивного видов вывода На рисунке 1 приведена схема СОЗ, в которой добавлены блоки, обеспечивающие взаимодействие с внешним миром, исключена подсистема обучения (ее роль на себя берет МЛВ)

ВНЕШНЯЯ ПОЛЬЗОВАТЕЛЬ ВНЕШНЯЯ

Рисунок 1 - Структура СОЗ на основе МЛВ

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

В работе приводится пример классификации СОЗ Выделяются следующие классы экспертные системы, интеллектуальные базы данных, интеллектуальные системы поддержки принятия решений, интеллектуальные САПР и САНИ, интеллектуальные роботы, обучающие системы В данную классификацию также можно включить многоагентные системы

Для оценки эффективности работы СОЗ в работе приведены общие критерии

- критерии пользователей понятность, прозрачность, удобство интеллектуального интерфейса,

- критерии экспертов оценка решений, предлагаемых системой, сравнение решений системы с собственными решениями, оценка подсистем,

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

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

Во второй главе разрабатывается метод логического вывода модифицируемых заключений

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

Приводится постановка задачи в следующем виде Пусть исходные посылки заданы в виде множества дизъюнктов M={Db D2, , Di}, а заключение - в виде множества дизъюнктов m={db d2, , dj} Обозначим множества литералов, входящих в дизъюнкты D, и dj, через D ,={8,1, S,2, , Sm, , SlN_}, dj={ Lji, Lj2, , Ljk, , LjKj}, соответственно

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

а) найти (для всех j=l, , J) множества d L*2, , L*K } (здесь d*

- множество литералов, которые нужно добавить к dj) такие, что выполняются следующие условия

1) формула 1 ы> dj является следствием исходных посылок М, где d;=djud;,

2) формула 1 ьн> d* (дизъюнкт d* составлен из литералов множества d j) не является следствием из исходных посылок.

б) найти (для всехj=l, , J) множества d , L~2, , L~K| } (здесь d~

— множество литералов, исключаемых из dj) такие, что выполняются условия

1) формула lh->d" является следствием из исходных посылок М, где d"=d

2) исключение любого литерала из формулы d" приведет потере выводимости данной формулы

Задача расширения заключения решается путем применения к заключению метода абдуктивного логического вывода, основанного на процедуре деления дизъюнктов Если вывод завершается успешно, то заключение выводимо, и его модификация не требуется (при необходимости заключение может быть минимизировано) Если вывод неуспешен (например, полученные дополнительные посылки вступают в противоречие с БЗ), ЛВ модифицируемых заключений для данного заключения невозможен

Если получены дополнительные посылки, то они не добавляются в базу знаний, а подвергаются следующему преобразованию Производится перемножение дополнительных дизъюнктов Р=01+1&01+2& &01+к Затем формула инвертируется и приводится к конъюнктивной нормальной форме. Полученные дизъюнкты содержат варианты дополнительных множеств литералов для расширения дизъюнктов заключения При этом каждый дизъюнкт может быть дополнен любым из полученных дополнительных дизъюнктов

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

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

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

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

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

Разработка машины логического вывода модифицируемых заключений. В настоящее время существует достаточно большое количество МЛВ, отличающихся способами представления знаний, видами и методами вывода, назначением, способами реализации и т д Недостатком большинства является реализация вывода по принципу 8ЬЭ-резолюции, который является последовательным, и потому не позволяет обеспечить высокой производительности В связи с этим в работе рассматривается вопрос построения МЛВ для параллельных методов вывода делением дизъюнктов Структура разработанной МЛВ приведена на рисунке 2

Блок расширения формулы заключения

А

Ч

Блок абдуктивного вывода

i

Блок управления

Блок согласования решений

шшшн

Блок дедуктивного вывода

А51

Блок полного деления дизъюнктов

П

П

О

п

Блок унификации литералов

Ш00Ш

Блок минимизации формулы заключения

д

Блок фильтрации

1Ш

Блок частичного деления дизъюнктов

Н00Н

Блок минимизации

ииии

Рисунок 2 - Структура МЛВ модифицируемых заключений

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

в состав СОЗ универсальную ЭВМ В настоящее время МЛВ реализуются именно таким способом

МЛВ состоит из нескольких блоков, выполняющих однотипные операции Каждая операция может выполняться отдельным вычислительным процессом Поскольку процессы могут формироваться динамически в любом количестве, проблема нехватки (или избытка) вычислителей отсутствует Процессорное же время реальных процессоров распределяет диспетчер задач операционной системы Это позволяет упростить конфигурацию МЛВ и в большинстве случаев избежать простоев процессоров, в том числе и при ожидании процедурой результатов выполнения дочерних операций Однако если количество процессов значительно превышает количество вычислителей, эффективность вывода падает, так как увеличивается доля дополнительных расходов времени на организацию процессов, передачу параметров и возврат результатов

Критерии оценки эффективности работы МЛВ. Для оценки эффективности работы МЛВ вводятся два критерия время вывода и степень модификации заключения

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

В общем случае время вывода модифицируемых заключений можно рассчитать по формуле (1)

Твмз Тр+тмин+тф, О)

где Тр - время расширения формулы заключения, Тми„ - время минимизации формулы заключения, Тф - время фильтрации вариантов модификации Время расширения заключения можно рассчитать по формуле (2)

Тр=1>р1+Трз+Трп+Трф, (2)

1=1

где 1р1 - время выполнения 1-го шага вывода, I — общее количество шагов вывода,

Трз - время согласования решений и формирования вариантов формул дополнительных посылок,

Трл - время подготовки и выполнения проверочного дедуктивного

вывода,

ТРф — время формирования результата Для расчета времени минимизации заключения вводятся следующие обозначения

и - общее количество дизъюнктов, полученное после вывода с расширением заключения,

Ьи - длина (количество литералов и-го дизъюнкта, где и=1, , и), Еи - количество исключенных из и-го дизъюнкта литералов,

Яи - количество полученных минимальных решений для и-го дизъюнкта (последние два параметра заранее неизвестны)

Тогда время минимизации можно рассчитать по формуле (3)

-Е„) (Я. -1)) (Е„ +1^, (3)

где Тд - время дедуктивного вывода - рассчитывается по формуле расчета времени Тр (2)

Время фильтрации вариантов рассчитывается по формуле (4)

Тф=(Т0-К)]У/Ыв[+(Тфф+т)]ТУ/Нв[, (4)

где Т0 - время выполнения функции оценки для одного дизъюнкта,

Тфф - время формирования результатов фильтрации для одного исходного дизъюнкта заключения,

— количество исходных дизъюнктов заключения, V - общее количество модификаций дизъюнктов,

V, - количество модификаций для 1-го исходного дизъюнкта заключения (1=1, ,

] [ - операция округления до ближайшего большего целого Степень модификации заключения может быть оценена по формуле (5)

IV

Мз=£мд„ , (5)

где Мд„ - степень модификации дизъюнкта w (\у=1, ,

- количество дизъюнктов в заключении

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

МДи(=к, М,и+к2 М2и+к3 М3„, (6)

где М]„, М2и, М3и, - степени модификации, соответственно, констант и переменных, функторов, литералов,

к] - к3 - поправочные коэффициенты Степени модификации термов можно определить как количество измененных термов Модификация набора литералов оценивается несколько сложнее Возможно три варианта модификации литерала добавление (исчезновение) инверсии, добавление литерала, удаление литерала Для учета данных видов модификации автор предлагает ввести поправочные коэффициенты Тогда степень модификации уровня литералов следует рассчитывать по формуле (7)

М3«=к3| Н,+к32 Ы++к33 (7)

где N1 - количество инвертированных литералов,

14+ - количество добавленных литералов; М_— количество исключенных литералов; кз1 - к33 - поправочные коэффициенты.

В общем случае 4000 следует считать, что

^ , ' 3500

качество модификации

и 3000

тем выше, чем меньше = ее степень, рассчитан- ™2500 ная по формуле (5). Ее- §2ооо ли нет специальных ог- к.,.„

^ 1оии

раничений или требо- й_

„ со юоо

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

Сравнение времени вывода (рисунок 3) традиционных МЛВ и разработанной МЛВ показывает, что разработанная МЛВ за счет большей вычислительной сложности работает медленнее на однопроцессорных системах, однако значительно обгоняет традиционные МЛВ по производительности на системах, содержащих более двух процессоров (N>2).

В третьей главе разрабатывается система логического вывода. Детализованная структура системы приведена на рисунке 4.

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

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

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

Подсистема заключений осуществляет хранение формул и дизъюнктов исходного и вариантов модифицированного заключений.

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

\ О

X ............................~........."""" ;

\

_____________ чх......._..............................

_ . . ..................

Ч __

12 3 4 5 10 20 50 100

—Традиционные МЛВ-- Разработанная МЛВ

Рисунок 3 - Сравнение времени вывода

блоки дедуктивного вывода и абдуктивного вывода (последний является частью блока расширения заключения), можно использовать дополнительные режимы работы модуля логического ¡вывода режим дедуктивного вывода и режим абдуктивного вывода Кроме этих режимов можно выделить также режим настройки и режим непосредственной работы с базой знаний ! гг,-:-! Машина логического вывода

Входная р-*\ информация'—у/

Рисунок 4 - Детализованная структура системы логического вывода

Оценку эффективности работы системы можно проводить с использованием разработанных во второй главе критериев оценки эффективности работы МЛВ При этом формула (1) модифицируется к общему времени добавляется время преобразования заключения во множество дизъюнктов Тпрз (формула (8))

Твмз ТПрз+Тр+Тмин+Тф,

Разработанная система обладает некоторыми преимуществами по отношению к существующим позволяет решать задачи модификации заключений, выполняет ЛВ параллельным способом, что позволяет повысить производительность системы (рисунок 3), выполняет интерпретацию формул на естест-

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

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

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

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

ЛВ модифицируемых заключений может применяться для интеллектуального управления вычислительными процессами В этом случае производится управление распределением вычислительными процессами в вычислительной сети с динамической архитектурой Особенности процессов и архитектуры сети описываются в терминах логики Заключение представляет собой вариант распределения процессов по вычислителям В случае, если заключение становится невыводимым (изменяется архитектура сети), оно модифицируется, и, в соответствии с модификацией, часть процессов перераспределяется При этом минимальное отличие модифицированного заключения от исходного позволяет минимизировать перераспределение процессов В данном случае имеется преимущество перед алгоритмическими методами в простоте описания правил поведения процессов (достаточно нескольких десятков строк исходного кода, тогда как на алгоритмическом языке требуются тысячи строк), а также в возможности децентрализованного управления при наличии нескольких копий БЗ

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

Разработана учебная система, которая позволяет выполнять следующие функции ввод и правка БЗ, преобразование формул к виду множеств дизъюнктов, отображение исходных и преобразованных .формул, JIB дедуктивный (двумя способами), абдуктивный, с модификацией заключений, вывод и печать подробного отчета о ходе вывода В системе может быть выбран один из шести критериев отбора дизъюнктов заключения Программа имеет настраиваемый многодокументный интерфейс MDI и снабжена справочной системой

Основные результаты работы

1 Разработан метод параллельного логического вывода модифицируемых заключений для логики высказываний и логики предикатов первого порядка, основанный на ЛВ делением дизъюнктов и позволяющий модифицировать изначально невыводимое заключение с целью сделать его выводимым из исходных посылок

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

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

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

5 Разработана структура MJIB Особенностями МЛВ являются параллельная реализация, значительно повышающая производительность вывода при исполнении на современных параллельных вычислительных платформах, возможность реализации аппаратным и программным способом, использование двухуровневой базы знаний

6 Разработаны обобщенная и детализованная структуры системы логического вывода Определены режимы функционирования системы Модуль, помимо основного метода JIB модифицируемых заключений, способен реализовать дедуктивный и абдуктивный виды вывода Кроме того, модуль содержит средства построения на основе логических формул фраз на естественном языке

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

8 Разработана учебная система логического вывода, которая предоставляет пользователю возможность выполнения ЛВ модифицируемых заключений, дедуктивного и абдуктивного видов вывода, имеет удобный интерфейс для исследования свойств систем JIB и изучения ЛВ делением дизъюнктов

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Tomchuk, MN The Method of Minimization of Conclusion [Text] / M N Tomchuk, D A Strabykin // Interactive Systems The Problems of Human -Computer Interaction Proceedings of the International Conference, 23-27 September

2003 Ulyanovsk U1STU, 2003 -pp 168-173

2 Томчук, M H Программа логического вывода с модификацией заключений в исчислении высказываний [Текст] / М Н Томчук // Всероссийская научно-техническая конференция «Наука - производство -технологии - экология» Сборник материалов В 5 т - Киров Изд-во ВятГУ,

2004 - Том 2 - ФАВТ, ФПМТ - С 16-19

3 Страбыкин, Д А Логический вывод с модификацией заключений в исчислении высказываний [Текст] /ДА Страбыкин, М Н Томчук // Вестник Вятского научного центра Верхне-Волжского отделения Академии технологических наук РФ Серия Проблемы обработки информации Выпуск 1(4)/2003 Сборник научных трудов - Киров Вятский научный центр, 2003 -С 9-16

4 Страбыкин, Д А Метод модификации заключений в исчислении высказываний [Текст] /ДА Страбыкин, М Л Долженкова, М Н Томчук // Девятая Национальная конференция по искусственному интеллекту с международным участием КИИ-2004 (28 сентября - 2 октября 2004 г, Тверь) Труды конференции, в 3-х т М Физматлит, 2004 — Т1 -С 263-271

5 Страбыкин, Д А Метод и программа логического вывода с модификацией заключений с использованием дедукции [Текст] / Д А Страбыкин, М Н Томчук, М М Шихов // Вестник Вятского научного центра Верхне-Волжского отделения Академии технологических наук РФ Серия Проблемы обработки информации Выпуск 1(4)/2004 Сборник научных трудов -Киров Вятский научный центр, 2004 -С 8-15

6 Томчук, М Н Применение логического вывода для интеллектуального управления вычислительными процессами [Текст] / М Н Томчук // Вестник Вятского научного центра Верхне-Волжского отделения Академии технологических наук Российской Федерации Серия Проблемы обработки информации Выпуск 1(7)/2006 Сборник научных трудов — Киров Вятский научный центр, 2006 - С 17-24

7 Томчук, М Н Построение машин логического вывода модифицируемых заключений [Текст] / МН Томчук // Всероссийская научно-техническая конференция «Наука - производство - технологии - экология» Сборник материалов В 5 т - Киров Изд-во ВятГУ, 2007 - Том 2 - ФАВТ, ФПМТ - С 16-19

8 Томчук, М Н Применение программы логического вывода модифицируемых заключений в процессе обучения [Текст] М Н Томчук // Сборник трудов метод конференции ВятГУ - Киров, 2007

9 Томчук, М Н Система логического вывода модифицируемых заключений [Текст] / М Н Томчук // Программные продукты и системы №4 (2007) - Тверь, 2007 (в печати)

ТОМЧУК Максим Николаевич

РАЗРАБОТКА МЕТОДА И СИСТЕМЫ ЛОГИЧЕСКОГО ВЫВОДА МОДИФИЦИРУЕМЫХ ЗАКЛЮЧЕНИЙ

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 4 10 07 Формат бумаги 60x84 1/16 Бумага писчая. Уел печ л 1,0 Тираж 100 экз

Текст напечатан с готового оригинал-макета, предоставленного автором

Вятский государственный университет 610000, г Киров, ул Московская, 36

Введение.

Глава 1. Анализ методов и машин логического вывода и систем обработки знаний.

1.1 Методы и машины логического вывода.

1.1.1 Классификация видов логического вывода.

1.1.2 Классификация методов логического вывода.

1.1.3 Метод деления дизъюнктов.

1.1.4 Машины логического вывода

1.2 Системы обработки знаний (СОЗ).

1.2.1 Определение и структура.

1.2.2 Классификация.

1.2.3 Режимы функционирования.

1.2.4 Оценка эффективности.

1.3 Выводы по главе 1.

Глава 2. Разработка метода логического вывода модифицируемых заключений.

2.1 Формальные системы.

2.2 Постановка задачи логического вывода.

2.3 Расширение формулы заключения.

2.3.1 Унификация литералов.

2.3.2 Согласование решений.

2.3.3 Согласование значений общих переменных в конъюнкциях дизъюнктов.

2.3.4 Частичное деление дизъюнктов.

2.3.5 Полное деление дизъюнктов.

2.3.6 Процедура вывода.

2.3.7 Построение абдуктивных объяснений.

2.3.8 Метод параллельного вывода с расширением формулы заключения

2.4 Минимизация формулы заключения.

2.4.1 Процедура минимизации заключения.

2.4.2 Метод минимизации заключения.

2.5 Выбор вариантов модификации.

2.6 Особенности вывода в исчислении высказываний.

2.7 Пример вывода.

2.8 Выводы по главе 2.

Глава 3. Разработка системы логического вывода модифицируемых заключений.

3.1 Структура системы логического вывода.

3.1.1 Обобщенная структура системы.

3.1.2 Детализованная структура системы.

3.2 Режимы работы системы логического вывода.

3.2.1 Режим вывода модифицируемых заключений.

3.2.2 Режим дедуктивного вывода.

3.2.3 Режим абдуктивного вывода.

3.2.4 Режим настройки.

3.2.5 Режим непосредственного доступа к базам знаний.

3.2.6 Создание базы знаний.

3.3 Машина логического вывода модифицируемых заключений.

3.4 Язык декларативного логического программирования.

3.4.1 Структура логической программы.

3.4.2 Идентификаторы и константы.

3.4.3 Комментарии.

3.4.4 Пример логической программы.

3.5 Оценка эффективности систем логического вывода.

3.5.1 Критерии оценки эффективности.

3.5.2 Расчет времени вывода.

3.5.3 Расчет степени модификации заключения.

3.6 Выводы по главе 3.

Глава 4. Применение систем логического вывода модифицируемых заключений.

4.1 Области применения.

4.2 Интеллектуальные обучающие системы.

4.3 Экспертные системы.

4.4 Интеллектуальное управление вычислительными процессами.

4.5 Модуль логического вывода модифицируемых заключений.

4.5.1 Общая характеристика разрабатываемого программного обеспечения.

4.5.2 Структура модуля вывода.

4.5.3 Язык описания базы знаний и заключения.

4.5.4 Реализация блоков модуля.

4.6 Учебная программа логического вывода «Логика-В».

4.6.1 Структура программы.

4.6.2 Язык описания исходных данных.

4.6.3 Интерфейс пользователя.

4.6.4 Пример использования программы.

4.7 Выводы по главе 4.

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

Актуальность темы исследования. Одним из многообещающих направлений в вычислительных системах сегодня являются системы обработки знаний (СОЗ). Уже сейчас они имеют широкое распространение (особенно это справедливо для экспертных систем (ЭС)), а в перспективе смогут применяться практически повсеместно, повышая интеллектуальный уровень вычислительных систем практически всех видов. Однако, несмотря на имеющиеся успехи, современные СОЗ имеют ряд недостатков. В частности, они не способны решать задачи, требующие наличия достоверного заключения при имеющемся недостоверном. Кроме того, современные СОЗ работают неэффективно на параллельных платформах.

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

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

Моделирование рассуждений средствами логики является одним из приоритетных направлений науки, изучающей методы и средства искусственного интеллекта [86]. Рассуждения, записанные в виде формул логики предикатов первого порядка или логики высказываний, представляются достаточно естественным для человека образом. Интерпретация формулы при этом проста и заключается в замене литералов заранее заданными выражениями, а связок - соответствующими их значению словами.

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

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

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

Данные виды вывода известны достаточно давно и могут применяться для решения широкого круга задач. Однако существует класс задач, решить которые применением указанных видов вывода невозможно или затруднительно. Данный класс задач предполагает наличие корректной и полной БЗ для некоторой предметной области и недостоверное заключение, требующее преобразования. Следовательно, появляется принципиально новая постановка задачи логического вывода: модифицировать исходно невыводимое заключение с целью сделать его следствием исходных посылок. Данная задача решается посредством применения нового вида JIB - логического вывода модифицируемых заключений. В качестве областей применения данного вида вывода можно отметить следующие:

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

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

- грамматический разбор предложений [130]. Логический вывод модифицируемых заключений может быть использован для восстановления предложения и построения новых предложений;

- вычислительные комплексы с динамической архитектурой [139]. Логический вывод модифицируемых заключений может применяться для диспетчеризации вычислительных процессов в системах с динамически изменяющимися составом и связями вычислительных средств;

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

Существует достаточно большое количество методов логического вывода. Основной недостаток значительной их части - последовательный принцип обработки знаний. Это сильно снижает производительность систем логического вывода, использующих данные методы. В связи с этим заслуживают внимания методы параллельного логического вывода, основанные на процедуре деления дизъюнктов [123]. Каждый шаг такого вывода может включать достаточно много операций, большинство из которых может выподняться параллельно. Это особенно актуально в настоящее время, поскольку сейчас в большинстве случаев производительность ЭВМ наращивается не только и не столько за счет улучшения архитектуры и микроархитектуры процессоров, повышения тактовых частот, сколько за счет увеличения количества процессорных элементов (процессоров и ядер).

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

Значительный вклад в разработку и исследование методов и средств логического вывода внесли M. JI. Цетлин, M. М. Бонгард, Я. 3. Цыпкин, Д. А. Поспелов, В. К. Финн, Г. С. Осипов, В. Н. Вагин, Т. А. Гаврилова, В. Ф. Хорошевский, П. Гаек, Т. Гавранек, С. Осуга (S. Osuga), Ю. Саэки (U. Saeki), А. Сэмюэль (A. Samuel), Э. Хант (Е. Hunt), Д. Марин (J. Marin), Ф. Стоун (P. Stone), Р. Михальски (R. Michalski), Д. Карбонелл (J. Carbonell), Т. Митчелл (Т. Mitchell), Д. Куинлан (J. Quinlan).

Абдуктивный JIB исследовался в работах Ч. С. Пирса (С. S. Pierce), В. К. Финна, В. Н. Вагина, Е. Ю. Головиной, Д. А. Страбыкина, M. jl Долженковой, Д. Габбая (D. Gabbay), П. Сметса (P. Smets), К. Бутилье (С. Boutilier), П. Флеча (Р. Flach), А. Какаса (A. Kakas), К. Иноуэ (К. Inoue), Ч. Сакама (С. Sakama), Дж. Джозефсона (J. Josephson), С. МакИлрайта (S. Mcllraith), Дж. Пола (G. Paul) и др.

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

Для достижения цели необходимо решить следующие задачи.

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

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

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

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

Методы исследования. Для достижения поставленной в работе цели исследований использовались методы анализа алгоритмов, теории множеств, теории графов, математической логики, теории логического вывода, логического и объектно-ориентированного программирования.

Научная новизна исследования состоит в следующем.

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

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

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

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

Практическая ценность исследования состоит в следующем:

1. Разработана система параллельного логического вывода модифицируемых заключений, отличительными особенностями которой являются: использование методов и машины параллельного ЛВ, использование двухуровневой базы знаний, наличие блока интерпретации формул, что позволяет строить на основе разработанной системы логического вывода высокопроизводительные СОЗ различного назначения. Процесс вывода может быть распараллелен вплоть до уровня операций унификации литералов, что повышает скорость логического вывода на параллельных вычислительных платформах.

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

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

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

На защиту выносятся:

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

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

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

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

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

Внедрение результатов исследования. Полученные теоретические и практические результаты использованы в НИР «Теория и применение логического вывода с модификацией заключений» (грант Министерства Образования РФ Е02-2.0-93), в НИР «Разработка среды декларативного логического программирования для кластерной вычислительной системы» (ВятГУ, НИР №412). Учебная программа логического вывода внедрена в учебный процесс в Вятском государственном и Вятском государственном гуманитарном университетах.

Апробация работы. Основные положения и результаты исследования докладывались и обсуждались на 5-й международной конференции «Interactive Systems: The Problems of Human-Computer Interaction» («Интерактивные системы: Проблемы взаимодействия человек - компьютер»), Ульяновск, УлГТУ, 2003; 9-й «Национальной конференции по Искусственному Интеллекту КИИ-2004», Тверь, 2004; Всероссийской ежегодной научно-технической конференции ВятГУ «Наука-производство-технологии-экология», Киров (2004,2007,2008 гг.)

Публикации. Результаты исследования представлены в 13 работах, из них 11 статей, 2 тезисов докладов. Четыре работы опубликованы в научных изданиях, рекомендуемых ВАК для опубликования основных научных результатов диссертации (три работы в российских изданиях и одна в зарубежном).

Структура и объем исследования. Диссертационная работа состоит из введения, четырех глав, заключения, списка сокращений, библиографического списка (включающего 163 наименования) и 2 приложений. Основная часть работы изложена на 170 страницах и содержит 33 рисунка и 5 таблиц.

4.7 Выводы по главе 4

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

2. Рассмотрено применение логического вывода модифицируемых заключений в интеллектуальных обучающих системах. В данных системах обучаемый в той или иной форме вводит заключение, и если оно невыводимо (неверно), оно подвергается коррекции и выдается обучаемому. Метод логического вывода модифицируемых заключений позволяет обучаемому формулировать вопросы и получать на них ответ, проводить контроль знаний, сопровождающийся закреплением знаний у обучаемого, и оценивать степень правильности ответа.

3. Рассмотрено применение вывода модифицируемых заключений в экспертных системах. В данном случае модификации подвергается первоначально введенное заключение, что позволяет доопределить признаки и по ним построить окончательное заключение. Данная система позволяет как итеративно строить экспертные заключения по известным пользователю признакам, так и служить средством подготовки экспертов, поскольку позволяет:

- доопределять набор признаков в случае их нехватки;

- корректировать консеквент, если он неверен;

- исключать несущественные признаки.

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

5. Разработана программная реализация машины логического вывода модифицируемых заключений для исчисления высказываний. Для этого были разработаны программные реализации следующих методов вывода:

- дедуктивный логический вывод;

- модифицированный дедуктивный вывод;

- абдуктивный вывод с пополнением базы исходных посылок;

151

- абдуктивный вывод с расширением формулы заключения;

- вывод с минимизацией заключения.

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

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

152

ЗАКЛЮЧЕНИЕ

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

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

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

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

4. Определены два критерия эффективности СОЗ, использующих логический вывод модифицируемых заключений:

- минимальное время вывода;

- минимальная степень модификации заключения.

Время вывода определяет эффективность реализации метода и является критическим параметром для систем некоторого типа (например, для систем управления объектами в реальном времени).

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

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

- параллельная реализация, значительно повышающая производительность вывода при исполнении на современных параллельных вычислительных платформах;

- универсальность - возможность реализации основных видов вывода (кроме индуктивного для исчисления предикатов первого порядка), возможность применения в любых областях;

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

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

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

8. Разработана учебная программа логического вывода модифицируемых заключений в исчислении высказываний. Данная реализация предостав

1. Abductive reasoning and learning Text. // Handbook of defeasible reasoning and uncertainty management systems / Ed. By D. M. Gabbay, P. Smets. V.4 -Kluwer Acad. Publishers, Dordrecht Hardbound, 2000. 448 p.

2. Banerji, R. Theory of problem solving: an approach to artificial intelligence Text. / R. Banerji. American Elsevier Publishing Company, Inc., New York, 1969.

3. Cox, P.T. Causes for events: their computation and applications. Text. / P. T. Cox, T. Pietrzykowski // Proc. CADE86 (1986). P. 608-621.

4. Davies, T. A logical reasoning by analogy Text. / T. Davies, S. Russel // Proc. IJCAI, 1987. -P.264-270.

5. DeJong, G., Mooney R. Explanation-based learning: an alternative view Text. / G. DeJong // Machine Learning, 1986. Vol.1. P. 145-176.

6. Dennis, J. B. Data Flow Supercomputers Text. / J. B. Dennis // Computer. 1992. N. 11.-P. 48-56.

7. Ellman, T. Explanation-based learning: a survey of programs and perspectives Text. / T. Ellman // ACM Computing Survey. Vol.21. June, 1989. P. 163-222.

8. Hennessy, J. Computer Architecture A Quantitative Approach Text. / John L. Hennessy, David A. Patterson - 2003. - 1142 p.

9. Hunt, E. Experiments in induction Text. / E. Hunt, J. Marin, P. Stone. -Acad. Press, New York, 1965.

10. Josephson, J.R., Josephson S.G. (Eds.) Abductive Inference: Computation, Philosophy, Technology Text. New York: Cambridge University Press, 1994.

11. Levesque, H. A knowledge-level account of abduction Text. / H. Levesque // Proc. of the 11th Int. Joint Conf. on Artif. Intell., 1989. P. 1061-1067.

12. Mcllraith, S. A. Logic-Based Abductive Inference Text. / S. A. Mcllraith // Knowledge Systems Laboratory, Stanford Univ., Stanford, CA 94305-9020, July 6, 1998.-29 p.

13. NEXPERT-OBJECT Text. // Tutorial. Nexpert Co. 1990.

14. Nunez, M. The use of Background knowledge in Decision Tree Induction Text. / M. Nunez // Machine Learning. 1991. Vol.6. P. 231-250.

15. Paul, G. AI Approaches to Abduction Text. / G. Paul // Handbook of Defeasible Reasoning and Uncertainty Management Systems. V. 4: Abductive Reasoning and Learning / Ed. by D. M. Gabbay and P. Smets. Kluwer Academic Publishers, 2000. - P.35-99.

16. Pierce, C. S. Collected papers of Charles Sanders Pierce Text. / C. S. Pierce. Vol. 2.1931-1958. Harvard University Press.

17. Quinlan, J. R. Generating production rules from Decision Trees Text. / J. R. Quinlan // Proc. of IJCAI 87. Milan. 1987. P. 304-307.

18. Quinlan, J. R. Improved use of Continuous attributes in C4.5 Text. J. R. Quinlan // Joint of Artificial Intelligence. Res. 1996. V.4. P. 77-90.

19. Quinlan, J. R. Induction of decision trees Text. / J. R. Quinlan // Machine Learning. Vol.1: 81-106. 1986.

20. Shanahan M. Prediction is deduction but explanation is abduction Text. / M. Shanahan / Proc. IICAI89. 1989.

21. Shaw, M. L. Validation of knowledge support system Text. / M. L. Shaw, J. B. Woodward // Proceedings of the 2nd Knowledge Acquisition for Knowledge-Based Workshop. Banff, Canada, 1988.

22. Strabykin, D.A. A Method of Logical Inference of Modified Conclusions / D.A. Strabykin, M.N. Tomchuk // Journal of Computer and Systems Sciences International, 2008, Vol. 47, No. 2, pp. 245-251. Pleiades Publishing, Ltd., 2008.

23. Toussaint, G. T. Course: Skeletons Text. / G. T. Toussaint. Montreal: McGill University, 1997.

24. Utgoff, P. E. Incremental induction of Decision Trees Text. / P. E. Utgoff // Machine Learning. 1989. Vol.4. P. 161-186.

25. Warren, D. H. An Abstract Prolog Instruction Set. Tech. Note 309 Text. / D. H. Warren. AI Research Center, 1983.

26. Амамия, M. Архитектура ЭВМ и искусственный интеллект Текст. / М. Амамия, Ю. Танака. М.: Мир, 1993. - 400 с.

27. Амарел, С. Подход к автоматическому формированию теории Текст. / С. Амарел // Принципы самоорганизации. М.: Мир, 1966. - С. 533-580.

28. Андрейчиков, А. В. Интеллектуальные информационные системы Текст. : учебник / А. В. Андрейчиков, О. Н. Андрейчикова. М.: Финансы и статистика, 2004. - 424 с.

29. Антонюк, Б. Д. Разработка экспертных систем искусственного интеллекта в США Текст. / Б. Д. Антонюк. М.: ВНИИСИ, 1986.

30. Аркадьев, А. Г. Обучение машины классификации объектов Текст. / А. Г. Аркадьев, Э. М. Браверманн. М.: Наука, 1971. - 192 с.

31. Аткинсон, Р. Введение в математическую теорию обучения Текст. / Р. Аткинсон, Г. Бауэр, Э. Кротерс. М.: Мир, 1969.

32. Ашинянц, Р. А. Логические методы в искусственном интеллекте Текст. / Р. А. Ашинянц. М.: МГАПИ, 2001. - 223 с.

33. Баженов, Л. Б. Основные вопросы теории гипотез Текст. / Л. Б. Баженов. -М.: Высш. шк., 1961. 68 с.

34. Барсегян, А. А. Методы и модели анализа данных: OLAP и Data Mining Текст. / А. А. Барсегян, М. С. Куприянов, В. В. Степаненко, И. И. Холод. СПб.: БХВ-Петербург, 2004. - 336 с.

35. Башмаков, А. И. Интеллектуальные информационные технологии Текст. : учеб. пособие / А. И. Башмаков, И. А. Башмаков. М.: Изд-во МГТУ им. Н. Э. Баумана, 2005. - 304 с.

36. Борисов, А. Н. Приобретение знаний для интеллектуальных систем Текст. / А. Н. Борисов, И. П.Федоров, И. Ф. Архипов. Рига: Рижский техн. ун-т, 1991.

37. Браверманн, Э. М. Структурные методы обработки эмпирических данных Текст. / Э. М. Браверманн, И. Б. Мучник. М.: Наука, 1983.

38. Братко, И. Алгоритмы искусственного интеллекта на языке PROLOG Текст. / И. Братко. M.: Вильяме, 2004. - 640 с.

39. Вагин, В. Н. Дедукция и обобщение в системах принятия решений Текст. / В. Н. Вагин. М.: Наука. Гл. ред. физ.-мат. лит., 1988. - 383 с. -(Проблемы искусств, интеллекта.)

40. Вагин, В. Н. Достоверный и правдоподобный вывод в интеллектуальных системах Текст. / В. Н. Вагин, Е. Ю. Головина, А. А. Загорянская, М. В. Фомина. М.: Физматлит, 2004. - 704 с.

41. Вагин, В. Н. Аргументация в правдоподобном выводе Текст. / В. Н. Вагин, А. А. Загорянская // Труды конф. КИИ'2000. Т. 1. М.: Изд. физ.-мат. лит., 2000. - С.165-173.

42. Вагин, В. Н. Организация абдуктивного вывода средствами теории аргументации Текст. / В. Н. Вагин, А. А. Загорянская // Труды конгресса «Искусственный интеллект в XXI веке». М.: Изд. физ.-мат. лит., 2001. -С. 13-20.

43. Вагин, В. Н. Системы аргументации и абдуктивный вывод Текст. / В. Н. Вагин, А. А. Загорянская // Известия РАН. Сер. Теория и системы управления. 2004. № 1. С. 125-137.

44. Вагин, В. Н. Абдуктивный вывод в системах принятия решений Текст. / В. Н. Вагин, К. В. Лукин // Сб. науч. тр. Нац. конф. с междунар. участием «Искусственный интеллект-94». Рыбинск, 1994. Т. 2. - С.251-255.

45. Вагин, В. Н. Методы извлечения и обобщения информации в больших базах данных Текст. / В. Н. Вагин, А. А. Федотов, М. В. Фомина // Известия РАН. Сер. Теория и системы управления. 1999. № 5.

46. Варшавский, П. Р. Применение метода аналогий в рассуждении на основе прецедентов для интеллектуальных систем поддержки принятия решений Текст. / П. Р. Варшавский // Труды конф. КИИ'2004, Тверь, Т. 1. -Тверь, 2004. С. 218-226.

47. Варшавский, П. Р. Поиск решения на основе структурной аналогии для интеллектуальных систем поддержки принятия решений Текст. / П. Р. Варшавский, А. П. Еремеев // Известия РАН. Сер. Теория и системы управления. 2005. № 1. С. 97-109.

48. Вишняков, В. А. Аппаратно-программные средства процессора логического вывода Текст. / В. А. Вишняков, Д. Ю. Буланже, О. В. Герман. -М.: Радио и связь, 1991. 264 с.

49. Гаврилова, Т. А. Базы знаний интеллектуальных систем Текст. / Т. А. Гаврилова, В. Ф. Хорошевский. СПб.: Питер, 2001. - 384 с.

50. Гаврилова, Т. А. Извлечение и структурирование знаний для экспертных систем Текст. / Т. А. Гаврилова, К. Р. Червинская. -М.: Радио и связь, 1992.

51. Гаек, П. Автоматическое образование гипотез: математические основы общей теории Текст. / П. Гаек, Т. Гавранек; пер с англ. М.: Наука, 1984.-280 с.

52. Гладун, В. П. Планирование решений Текст. / В. П. Гладун. Киев: Наукова думка, 1987. - 167 с.

53. Гладун, В. П. Эвристический поиск в сложных средах Текст. / В. П. Гладун. Киев: Наукова думка, 1977. - 166 с.

54. Головина, Е. Ю. Абдуктивный вывод в инструментальных средствах для создания динамических систем принятия решений Текст. / Е. Ю. Головина // Труды конгресса «Искусственный интеллект в XXI веке». М.: Изд. физ.-мат. лит., 2001. - С. 50-60.

55. Горелик, A. JI. Методы распознавания Текст. / A. JI. Горелик, В. А. Скрипкин. М.: Высш. шк., 2004. - 261 с.

56. Грин, Д. Математические методы анализа алгоритмов Текст. / Д. Грин, Д. Кнут. М.: Мир, 1987. - 120 е., ил.

57. Гришкина, М. П. Разработка логических моделей и алгоритмов обучения Текст. : дис. . канд. техн. наук (05.13.11) / М. П. Гришкина. -М.: 2001.

58. Девятков, В. В. Системы искусственного интеллекта Текст. / В. В. Де-вятков. М.: Изд-во МГТУ им. Н. Э. Баумана, 2001. - 352 с.

59. Джексон, П. Введение в экспертные системы Текст. / П. Джексон. М.: Вильяме, 2001. - 622 с.

60. Джонс, М. Т. Программирование ИИ в приложениях Текст. / М. Т. Джонс. М.: ДМК Пресс, 2004. - 312 с.

61. Дюк, В. Data Mining Текст. : учебный курс / В. Дюк, А. Самойленко. -СПб.: Питер, 2001. 368 с.

62. Еремеев, А. П. Архитектура интеллектуальной системы поддержки принятия решений реального времени семиотического типа Текст. /

63. А. П. Еремеев // Научная сессия МИФИ-2002: Сборник научных трудов. Т.З. -М.: МИФИ, 2002.

64. Ерофеев, А. А. Интеллектуальные системы управления Текст. : учеб. пособие для вузов / А. А. Ерофеев, А. О. Поляков. СПб.: Изд-во СПбГТУ, 1999.-264 с.

65. Ершов, Ю. Л. Математическая логика Текст. / Ю. Л. Ершов, Е. А. Па-лютин. М.: Наука. Гл. ред. физ.-мат. лит., 1987. - 336 с.

66. Ефимов, Е. И. Решатели интеллектуальных задач Текст. / Е. И. Ефимов. -М.: Наука, 1982.-316 с.

67. Ефимов, Е. И. Семиотические модели в задачах планирования для систем искусственного интеллекта Текст. / Е. И. Ефимов, Д. А. Поспелов // Известия АН СССР «Техническая кибернетика». 1977. № 5. С. 60-68.

68. Ивашко, В. Г. Экспертные системы и некоторые проблемы их интеллектуализации Текст. / В. Г. Ивашко, В. К. Финн // Семиотика и информатика. 1986. Вып. 27. С. 25-61.

69. Искусственный интеллект Текст. : в 3 кн. Кн.2. Модели и методы: справочник / под ред. Д. А. Поспелова. М.: Радио и связь, 1990.

70. Искусственный интеллект: Применение в интегрированных производственных системах Текст. / под ред. Э. Кьюсиака. М.: Машиностроение, 1991.-539 с.

71. Кнут, Д. Искусство программирования, том 1. Основные алгоритмы, 3-е из. Текст. / Д.Э. Кнут; пер. с англ. М. : Издательский дом «Вильяме», 2007. - 720 с. : ил.

72. Кнут, Д. Искусство программирования, том 2. Получисленные алгоритмы, 3-е из. Текст. / Д.Э. Кнут; пер. с англ. М. : Издательский дом «Вильяме», 2007. - 720 с. : ил.

73. Кнут, Д. Искусство программирования, том 3. Сортировка и поиск, 3-е из. Текст. / Д.Э. Кнут; пер. с англ. М. : Издательский дом «Вильяме», 2007. - 720 с. : ил.

74. Кобринский, Б. А. Искусственный интеллект и медицина: возможности и перспективы систем, основанных на знаниях Текст. / Б. А. Кобринский // Новости искусственного интеллекта. 2001. № 4.

75. Ковальски, Р. Логика в решении проблем Текст. / Р. Ковальски. М.: Наука, 1990. - 290 с.

76. Корнеев, В. В. Базы данных. Интеллектуальная обработка информации Текст. / В. В. Корнеев, А. Ф. Гареев, С. А. Васютин, В. В. Райч. М.: Нолидж, 2000.

77. Кузнецов, С. О. Об одной модели обучения и классификации, основанной на операции сходства Текст. / С. О. Кузнецов, В. К. Финн // Обозрение прикладной и промышленной математики. Т. 3. Вып.1. 1996.

78. Ларичев, О. И. Теория и методы принятия решений Текст. / О. И. Ларичев. М.: Логос, 2000. - 296 с.

79. Левит, В. Е. Структура и поле данных при распознавании образов Текст. / В. Е. Левит, В. С. Переверзев-Орлов. М.: Наука, 1984.

80. Лорьер, Ж.-Л. Системы искусственного интеллекта Текст. / Ж.-Л. Лорь-ер. -М.: Мир, 1991.-568 с.

81. Любарский, Ю. А. Интеллектуальные информационные системы Текст. / Ю. А. Любарский. М.: Наука, 1990. - 227 с.

82. Люгер, Дж. Ф. Искусственный интеллект: стратегии и методы решения сложных проблем Текст. / Дж. Ф. Люгер. М.: Изд. дом «Вильяме», 2003.-864 с.

83. Малпас Дж. Реляционный язык Пролог и его применение Текст. / Дж. Малпас; пер. с англ.; Под ред. В.Н. Соболева. М.: Наука, 1990.

84. Маслов, С. Ю. Обратный метод установления выводимости в классическом исчислении предикатов Текст. / С. Ю. Маслов // ДАН СССР. 1964. Т. 159.-С. 17-20.

85. Маслов, С. Ю. Теория дедуктивных систем и её применение Текст. / С. Ю. Маслов. М.: Радио и связь, 1986. - 135 с.

86. Микони, С. В. Методы и алгоритмы принятия решений Текст. : учеб. пособие / С. В. Микони. СПб.: СПГУПС, 1995. - Ч. 1.

87. Микони, С. В. Методы и алгоритмы принятия решений Текст. : учеб. пособие / С. В. Микони, А. Н. Баушев. СПб.: СПГУПС, 1996. - Ч. 2.

88. Микони, С. В. Модели и базы знаний Текст. : учеб. пособие / С. В. Микони. СПб.: СПГУПС, 2000. - 155 с.

89. Минский, М. Структура для представления знаний Текст. / М. Минский // Психология машинного зрения / под ред. П. Уинстона. М.: Мир, 1978.-С. 249-338.

90. Минский, М. Фреймы для представления знаний Текст. / М. Минский. -М.: Энергия, 1979.-151 с.

91. Моделирование обучения и поведения Текст. М.: Наука, 1975.

92. Моргоев, В. К. Метод извлечения и структуризации экспертных знаний: моделирование консультаций Текст. / В. К. Моргоев // Сб. тр. ВНИИСИ «Человеко-машинные процедуры принятия решений» / под ред. С. В. Емельянова, О. И. Ларичева. М.: ВНИИСИ, 1988.

93. Невзорова, О. А. Машинное обучение и задачи обработки естественного языка Текст. / О. А. Невзорова // Новости искусственного интеллекта. 1998. № 1.

94. Нильсон, Н. Дж. Искусственный интеллект Текст. / Н. Дж. Нильсон. -М.: Радио и связь, 1973. 272 с.

95. Нильсон, Н. Дж. Принципы искусственного интеллекта Текст. / Н. Дж. Нильсон. М.: Радио и связь, 1985. - 373 с.

96. Осипов, Г. С. Информационные технологии, основанные на знаниях Текст. / Г. С. Осипов // Новости искусственного интеллекта. АИИ. 1993. № 1.-С. 7-41.

97. Осипов, Г. С. Приобретение знаний интеллектуальными системами. Основы теории и технологии Текст. / Г. С. Осипов. М.: Наука. Физмат-лит, 1997.- 112 с.

98. Осуга, С. Обработка знаний Текст. / С. Осуга; пер. с яп. М.: Мир,1989.-293 с.

99. ЮЗ.Петрушин, В. А. Экспертно-обучающие системы Текст. / В. А. Петру-шин / под. ред. А. М. Довгяло; АН УССР; Ин-т кибернетики. Киев: Наукова думка, 1992.

100. Пойа, Д. Математика и правдоподобные рассуждения Текст. / Д. Пойа. -М.: Наука, 1975.-463 с.

101. Попов, Э. В. Экспертные системы Текст. / Э. В. Попов. М.: Наука, 1987.-283 с.

102. Попов, Э. В. Статические и динамические экспертные системы Текст. / Э. В. Попов, И. Б. Фоминых, Е. Б. Кисель, М. Д. Шапот. М.: Финансы и статистика, 1996. - 319 с.

103. Поспелов, Г. С. Искусственный интеллект основа новой информационной технологии Текст. / Г. С. Поспелов; АН СССР. - М.: Наука, 1988. -278 с.

104. Поспелов, Г. С. Искусственный интеллект прикладные системы Текст. / Г. С. Поспелов, Д. А. Поспелов. - М.: Знание, 1985. - 48 с.

105. Поспелов, Д. А. Моделирование рассуждений. Опыт анализа мыслительных актов Текст. / Д. А. Поспелов. М.: Радио и связь, 1989. - 182 с.

106. Поспелов, Д. А. Ситуационное управление: теория и практика Текст. / Д. А. Поспелов. М.: Наука, 1986. - 288 с.

107. Поспелов, Д. А. Фантазия или наука: на пути к искусственному интеллекту Текст. / Д. А. Поспелов. М.: Наука, 1982. - 224 с.

108. Поспелов, Д. А. Мышление и автоматы Текст. / Д. А. Поспелов, В. Н. Пушкин. -М.: Сов. радио, 1972.

109. Представление и использование знаний Текст. / под ред. X. Уэно, М. Исидзука. М.: Мир, 1990. - 220 с.

110. Приобретение знаний Текст. / под ред. С. Осуги, Ю. Саэки. М.: Мир,1990.-304 с.

111. Пупков, К. А. Интеллектуальные системы: исследование и создание Текст. / К. А. Пупков. М.: Изд-во МГТУ им. Н. Э. Баумана, 2003. - 348 с.

112. Растригин, Л. А. Адаптация сложных систем Текст. / Л. А. Растригин. -Рига: Зинатне, 1981. 375 с.

113. Растригин, Л. А., Эренштейн М. X. Адаптивное обучение с моделью обучаемого Текст. / Л. А. Растригин, М. X. Эренштейн. Рига: Зинатне, 1988.- 160 с.

114. Рузавин, Г. И. Абдукция как метод поиска и обоснования объяснительных гипотез Текст. / Г. И. Рузавин // Теория и практика аргументации. -М.: Институт философии РАН, 2001.

115. Рыбина, Г. В. Проектирование систем, основанных на знаниях Текст. : учеб. пособие / Г. В. Рыбина. М.: МИФИ, 2000. - 104 с.

116. Сидоренко, Е. А. Логическое следование и условные высказывания Текст. / Е. А. Сидоренко. М.: Наука. АН СССР, 1983.

117. Слэйгл, Дж. Искусственный интеллект Текст. / Дж. Слэйгл. М.: Мир, 1973.-313 с.

118. Стефанюк, В. Л. Локальная организация интеллектуальных систем Текст. / В. Л. Стефанюк. М.: Физматлит, 2004. - 328 с.

119. Страбыкин, Д. А. Логический вывод в системах обработки знаний Текст. / Д. А. Страбыкин; под ред. Д. В. Пузанкова; СПбГЭТУ. СПб., 1998.-164 с.

120. Страбыкин, Д.А. Метод и программа логического вывода с модификацией заключений с использованием дедукции Текст. / Д.А. Страбыкин, М.Н. Томчук, М.М. Шихов // Вестник Вятского научного центра Верхне

121. Волжского отделения Академии технологических наук Российской Федерации. Серия: Проблемы обработки информации. Выпуск 1(4)/2004 : Сборник научных трудов. Киров : Вятский научный центр, 2004. - С. 8-15.

122. Страбыкин, Д.А. Метод логического вывода модифицируемых заключений / Д.А. Страбыкин, М.Н. Томчук // Известия РАН. Теория и системы управления. 2008. №2. с. 89-95

123. Страбыкин, Д. А. Метод параллельных вычислений для абдуктивного вывода на знаниях Текст. / Д. А. Страбыкин // Известия Академии наук. Теория и системы управления. 2000. № 5. С. 101-106.

124. Страбыкин, Д. А. Организация машин параллельного логического вывода Текст. : учеб. пособие для вузов / Д. А. Страбыкин. Киров: Изд-во ВятГТУ, 1999. - 189 с.

125. Сэмюэль, А. Некоторые исследования возможности обучения машин на примере игры в шахматы Текст. / А. Сэмюэль // Вычислительные машины и мышление / под ред. Э. Фейгенбаума и Дж. Фельдмана. М.: Мир, 1967.-С. 71-110.

126. Таусенд, К. Проектирование и программная реализация экспертных систем на персональных ЭВМ Текст. / К. Таусенд, Д. Фохт. М.: Финансы и статистика, 1990.

127. Тейз, А. Логический подход к искусственному интеллекту: от классической логики к логическому программированию Текст. / А. Тейз, П. Гри-бомон, Ж. Луи и др. М.: Мир, 1990. - 429 с.

128. Тейз, А. Логический подход к искусственному интеллекту: от модальной логики к логике баз данных Текст. / А. Тейз, П. Грибомон, Г. Юлен и др. М.: Мир, 1998. - 494 с.

129. Толковый словарь по искусственному интеллекту Текст. / сост.: А. Н. Аверкин, М.Г.Гаазе-Рапопорт, Д.А.Поспелов. М.: Радио и связь, 1992.-256 с.

130. Томчук, М.Н. Оценка эффективности систем логического вывода модифицируемых заключений / М.Н. Томчук, Д.А. Страбыкин // Международный журнал «Программные продукты и системы», №1 (2008), Тверь, с. 47-50.

131. Томчук, М.Н. Система логического вывода модифицируемых заключений Текст. / М.Н. Томчук // Международный журнал «Программные продукты и системы», №4 (2007). Тверь, с. 70-73.

132. Убейко, В. Н. Экспертные системы Текст. / В.Н. Убейко. -М.: МАИ, 1992.

133. Уемов, А. И. Логические основы метода моделирования Текст. / А. И. Уемов. М.: Мысль, 1971.

134. Уинстон, П. Г. Искусственный интеллект Текст. / П. Г. Уинстон. М.: Мир, 1980.-520 с.

135. Уотермен, Д. Руководство по экспертным системам Текст. / Д. Уотер-мен; пер. с англ. М.: Мир, 1989. - 388 с.

136. Фейгенбаум, Э. А. Искусственный интеллект, темы исследования во втором десятилетии развития Текст. / Э. А. Фейгенбаум // Кибернетический сборник, новая серия, вып. 10. М.: Мир, 1973. - С. 171-203.

137. Финн, В. К. Интеллектуальные системы и общество Текст. / В. К. Финн. -М.: РГГУ, 2001.-309 с.

138. Финн, В. К. Интеллектуальные системы: проблемы их развития и социальные последствия Текст. / В. К. Финн // Будущее искусственного интеллекта / под ред. К. Е. Левитина, Д. А. Поспелова. М.: Наука, 1991. — С. 157-177.

139. Финн, В. К. Правдоподобные выводы и правдоподобные рассуждения Текст. / В. К. Финн // Итоги науки и техники. Сер. «Теория вероятностей. Математическая статистика. Теоретическая кибернетика». Т.28. -М.: ВИНИТИ, 1988. С. 3-84.

140. Финн, В. К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ Текст. / В. К. Финн // Итоги науки и техники. Сер. «Информатика». Т. 15. Интеллектуальные информационные системы. М.: ВИНИТИ, 1991.-С. 54-101.

141. Форсайт, Р. Экспертные системы. Принципы работы и примеры Текст. / Р. Форсайт. М.: Радио и связь, 1987.

142. Хант, Э. Искусственный интеллект Текст. / Э. Хант; пер с англ. М.: Мир, 1978.-558 с.

143. Хант, Э. Моделирование процесса формирования понятий на вычислительной машине Текст. / Э. Хант, Д. Марин, Ф. Стоун. М.: Мир, 1970. - 302 с.

144. Хейес-Рот, Ф. и др. Построение экспертных систем Текст. / Ф. Хейес-Рот и др.; под ред. Ф. Хейес-Рота, Д. Уотермена, Д. Лената. М.: Мир, 1987.-441 с.

145. Цетлин, М. Л. Исследования по теории автоматов и моделированию биологических систем Текст. / М. Л. Цетлин. М.: Наука, 1969. - 316 с.

146. Цыпкин, Я. 3. Адаптация и обучение в автоматических системах Текст. /. М.: Наука, 1968.-400 с.

147. Чен, Ч. Математическая логика и автоматическое доказательство теорем Текст. / Ч. Чен, Р. Ли. М.: Наука, 1983. - 360 с.

148. Чери, С. Логическое программирование и базы данных Текст. / С. Чери, Г. Готлоб, Л. Танка. М.: Мир, 1992. - 352 с.

149. Шалютин, С. М. Искусственный интеллект: Гносеологический аспект Текст. / С. М. Шалютин. М.: Мысль, 1985.- 199 с.

150. Шенк, Р. Познать механизмы мышления Текст. / Р. Шенк, Л. Хантер // Реальность и прогнозы искусственного интеллекта. М.: Мир, 1987.

151. Элти, Д., Кумбс М. Экспертные системы: концепции и примеры Текст. / Д. Элти, М. Кумбс. М.: Финансы и статистика, 1987.

152. Ясницкий, Л. Н. Введение в искусственный интеллект Текст. : учеб. пособие для вузов / Л. Н. Ясницкий. М.: Изд. центр «Академия», 2005. - 176 с.171