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

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

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

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

Специальности: 05.13.17 - Теоретические основы информатики; 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

ПЕНЗА 2009

003465131

Работа выполнена на кафедре «Электронные вычислительные машины» государственного образовательного учреждения высшего профессионального образования «Вятский государственный университет», г. Киров.

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

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

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

Кулагин Владимир Петрович;

кандидат технических наук, доцент Зинкин Сергей Александрович.

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

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

Защита диссертации состоится «_/£_» О^ 2009 г., в # часов, на заседании диссертационного совета Д 212.186.01 в государственном образовательном учреждении высшего профессионального образования «Пензенский государственный университет» по адресу: 440026, г. Пенза, ул. Красная, 40.

С диссертацией можно ознакомиться в библиотеке государственного образовательного учреждения высшего профессионального образования «Пензенский государственный университет». Автореферат размещен на сайте www.pnzgu.ru

Автореферат разослан « // » О 5 2009 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор Гурин Е. И.

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

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

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

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

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

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

Г

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

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

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

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

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

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

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

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

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

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

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

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); Девятой Национальной конференции по искусственному интеллекту с международным участием КИИ-2004 (Тверь, 2004); Всероссийской ежегодной научно-технической конференции ВятГУ «Наука-производство-технологии-экология» (Киров,2004,2007,2008 гг.)

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

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

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

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

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

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

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

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

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

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

Приводится постановка задачи в следующем виде.

Пусть исходные посылки заданы в виде множества дизъюнктов М = {Ои Вг, ..., А}, а заключение - в виде множества дизъюнктов т = [с1\, с¡2, ..., <//}• Обозначим множества литералов, входящих в

дизъюнкты 4 как ^ ]■ Задачу логического вывода модифицируемых заключений можно сформулировать следующим образом. Требуется:

а) найти множества литералов dj {¡ = 1, ..., J), добавляемых к d j, чтобы формула 1 ->d* (здесь dj =dj vjdJ) являлась следствием исходных посылок М, а формула 1-> dj не являлась их следствием;

б) найти множества литералов dj (j = 1, ..., J), исключаемых j ,** j** j* "j—

из dj, такие, чтобы формула 1—>«, (здесь dj = a j - a j ) следовала

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

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

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

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

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

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

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

I

Входная гН, информация Ц/

I

I

Выходная А информация\р

—»

Классификация входной информации

<

Е, И, К

Управляющие! воздействия

Блок построения интерпретации

1иГ 1мГ"

Интерфейс

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

Блокобщих операций

О

Блок управления процессами МЛВ

вани

Блок согласо-I решений

о

жж

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

Блок оценки

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

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

ь

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

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

База данных /(уровень 1

База знаний уровень 1

Блок преобразования дизъюнктов

| Блок преобразования формул

/1-

V

н\

V

Состояние системы и статистика

Блок управления синхронизацией

База База

данных знаний

уровень 2 уровень 2

Подсистема хранения данных и знаний I

Исходное заключение 1

Исходное заключение 2

Модифицированное заключение 1

Подсистема заключений

Модифицированное заключение 2

Рисунок 1 - Структура системы логического вывода

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

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

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

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

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

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

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

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

л

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

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

\7

Блок дедуктивного вывода | УУ | ■ • •

л> :

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

у)управления[у ["¡~| [~Ё~| [~е~] |е| . ■ •

Блок

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

И И И13 • • •

и

ификации литералов

иПППГй

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

Блок отбора__

ишии

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

Г&1 ГЙ] Г&1 [ИП ■ • •

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

шшшш

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

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

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

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

Твмз Тр1? Тмиц

(1)

где Тр - время расширения заключения; Тмин - время минимизации заключения; Т0 - время отбора вариантов модификации.

Время расширения заключения можно рассчитать по формуле

1

ТР=

2> ;=1

т„ твп+ТВ(

р'

(2)

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

Для расчета времени минимизации заключения вводятся обозначения: и — общее количество дизъюнктов, полученное после вывода с расширением заключения; Ьи - длина (количество литералов м-го дизъюнкта, где и = 1,..., Ц); Еи - количество исключенных из м-го дизъюнкта литералов; Яи - количество полученных минимальных решений для м-го дизъюнкта.

Тогда время минимизации можно рассчитать по формуле и ((2Ь -Е \ Л

-^^и-^И^-1) <Еи+\) , (3) и=1\Л ^ у

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

Время отбора вариантов рассчитывается по формуле

ТФ = (Т0 + х) ■] У/Щ + (Тфф + Т)-] Ж/Щ, (4)

где Т0 - время выполнения функции оценки для одного дизъюнкта; Тфф - время формирования результатов отбора для одного исходного дизъюнкта заключения; Ж - количество исходных дизъюнктов; V -общее количество модификаций дизъюнктов; ]...[- операция округления до ближайшего большего целого.

Степень модификации заключения может быть оценена по формуле

IV

Щ = (5)

№=1

где Мд„ - степень модификации дизъюнкта м> (^ = 1,IV); ¡V - количество дизъюнктов в заключении.

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

МДи,= кх • М]№+ к2 ■ М2„+ к3 ■ Мъ, (6)

где М{К, М2н, М2„ - степени модификации соответственно констант и переменных, функторов, литералов; к\-кз - коэффициенты.

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

Лг3, • N, + ¿32 ■ N+ + ¿33 ■ N_, (7)

где Nr - количество инвертированных литералов; N+ - количество добавленных литералов; JVL - количество исключенных литералов; - коэффициенты.

Сравнение времени вывода (рисунок 3) традиционных МЛВ и разработанной MJIB показывает, что на однопроцессорных ЭВМ разработанная МЛВ работает несколько быстрее традиционных последовательных МЛВ за счет двунаправленного характера логического вывода. При увеличении количества процессоров разработанная МЛВ значительно обгоняет по производительности традиционные МЛВ.

5000 4500 4000

о

5 3500 га

g: 3000 m

3 2500 m

| 2000

о. 1500 СО

1000 500 0

| —-Традиционные последовательные^ДЛВ - - Разработанная МЛВ |

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, рекомендованных ВАК

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

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

C. 89-95.

3 Tomchuk, M. N. A Method of Logical Inference of Modified Conclusions [Text] /

D. A. Strabykin, M. N. Tomchuk // Journal of Computer and Systems Sciences International, -Pleiades Publishing, Ltd., 2008. - Vol. 47, No. 2. - P. 245-251.

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

Публикации в прочих изданиях

5 Tomchuk, M. N. The Method of Minimization of Conclusion / M. N. Tomchuk, D. A. Strabykin // Interactive Systems : The Problems of Human - Computer Interaction. Proceedings of the International Conférence, 23-27 September 2003. - Ulyanovsk : U1STU, 2003.-P. 168-173.

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

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

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

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

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

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

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

13 Томчук, М. Н. Исследование производительности логического вывода делением дизъюнктов / М. Н. Томчук // Всероссийская научно-техническая конференция. «Наука-производство-технологии-экология» : сб. материалов : в 7 т. - Киров : Изд-во ВятГУ, 2008. - Т. 2. - ФАВТ, ФПМТ. - С. 81-83.

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

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

Специальности: 05.13.17 - Теоретические основы информатики; 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Редактор О. Ю. Ещина Технический редактор Я. А. Вьялкова Корректор С. Я. Сухова Компьютерная верстка Р. Б. Бердниковой

ИД№ 06494 от 26.12.01 Сдано в производство 02.03.09. Формат 60x841/16. Бумага писчая. Печать офсетная. Усл. печ. л. 1,0. Заказ № 115. Тираж 100.

Издательство Пензенского государственного университета. 440026, Пенза, Красная, 40.

Введение.

Глава 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]. Каждый шаг такого вывода может включать достаточно много операций, большинство из которых может выполняться параллельно. Это особенно актуально в настоящее время, поскольку сейчас в большинстве случаев производительность ЭВМ наращивается не только и не столько за счет улучшения архитектуры и микроархитектуры процессоров, повышения тактовых частот, сколько за счет увеличения количества процессорных элементов (процессоров и ядер).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Разработана программная реализация машины логического вывода модифицируемых заключений для исчисления высказываний. Для этого были разработаны программные реализации следующих методов вывода:

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

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

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

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

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. Т. 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., Mooncy 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. oflJCAI 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 Текст. / И. Братко. М.: Вильяме, 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. Растригин, JI. А. Адаптация сложных систем Текст. / JI. А. Растригин. -Рига: Зинатне, 1981.-375 с.

113. Растригин, JI. А., Эренштейн М. X. Адаптивное обучение с моделью обучаемого Текст. / JI. А. Растригин, М. 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. Цетлин, М. JI. Исследования по теории автоматов и моделированию биологических систем Текст. / М. JI. Цетлин. -М.: Наука, 1969. 316 с.

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

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

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

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

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

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

152. Декан факультета информатики1. Председатель УМС1. Н.И. Исупова1. Зав. кафедрой информатики1. Е.В. Котельников