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

Московский государственный университет имени М.В. Ломоносова Механико-математический факультет

003494523

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

МАХОРТОВ Сергей Дмитриевич

Теория ЬР-структур для построения и исследования моделей знаний продукционного типа

Специальность 05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

2 5 МАР 2910

Москва-2009

003494523

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

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

профессор

Васенин Валерий Александрович

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

профессор Чечкин Александр Витальевич

доктор физико-математических наук,

профессор Кузнецов Сергей Олегович

доктор физико-математических наук,

профессор

Пальчунов Дмитрий Евгеньевич

Ведущая организация: Вычислительный центр

имени А.А. Дородницына РАН

Защита диссертации состоится 24 марта 2010 года в 16:45 на заседании диссертационного совета Д 501.002.16 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, д.1, МГУ имени М.В. Ломоносова, механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (главное здание, 14 этаж).

Автореферат разослан 2010

г.

Ученый секретарь диссертационного совета, доктор физико-математических наук Корнев А.А.

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

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

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

Однако общая алгебраическая логика, расширяя возможности исследования самих логических теорий, существенно не облегчает их практического применения. В силу своей универсальности она не решает ряда важных частных проблем, связанных с широко распространенными на практике логическими системами продукционного типа. На этот факт указывается в книгах Н.Нильсона и Х.Уэно-Т.Коямы. К подобным проблемам могут быть отнесены вопросы эквивалентности, эквивалентных преобразований, верификации продукционных и подобных им систем, рассматривавшиеся частными методами в работах К.Адапуа1, 8.Ьее-11.М.О'Кее£е, Ы.К.Ьш-Т.ОШоп и других исследователей. Обзоры подходов к верификации знаний содержатся в работах 1Шир1а, а также Г.В.Рыбиной-В.В.Смирнова. Перечисленные вопросы играют существенную роль при создании и исследовании формальных

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

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

Эквивалентные преобразования и минимизация множества унифицированных правил продукционных экспертных систем в некоторых работах изучались на основе пропозициональных хорновых функций (например, E.Boros-O.Cepek-A.Kogan, P.L.Hammer-A.Kogari). В статье AGinsberg для исключения избыточности знаний используется логика первого порядка. В работе F.Glower-H.J.Greenberg рассмотрено несколько частных случаев упрощения множества правил на основе теории графов. Еще один путь минимизации продукционных систем может дать использование представления продукций сетями Петри (R.Agarwal) и решение задачи редукции сетей Петри (П.А.Анишев, G.Berthelot, L.H.Landveber-E.L.Robeitson).

В перечисленных работах нет строго обоснованного алгебраического подхода, универсального в рамках широкого спектра систем продукционного типа, который мог бы быть применен для решения задач эквивалентных преобразований, верификации и минимизации. Имеющиеся на настоящее время алгебраические исследования посвящены частным случаям продукционных систем либо другим их аспектам. В качестве примера можно привести связанную с теорией очевидности (G.Shafer) алгебраическую теорию «демпстероидов» (P.Häjek-J.V.Valdes). Она предназначена для вычислений результатов вывода в продукционных системах с функциями доверия (J.Gordon-E.H.Shortliffe).

В работе J.G.Shmolze-W. Snyder продукционная система сводится к системе переписывания термов (C11I). В семантике последней предлагается процедура обнаружения избыточных правил. Как это принято в системах переписывания термов, требуется «завершаемость» СПТ и, соответственно, исходного множества правил, иначе нет гарантии завершаемое™ процедуры. Этот интересный метод не охватывает продукционные системы, множества правил которых содержат циклы.

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

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

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

В первую очередь в контексте настоящей работы имеются в виду продукционные экспертные системы. Они остаются актуальными, что подтверждается значительным числом публикаций последних лет, посвященных как их теоретическим исследованиям, так и решению прикладных задач. База знаний распространенного класса продукционных систем представляет собой совокупность правил вида «если ..., то ...», где в предпосылке и заключении фигурируют множества так называемых фактов. Эти множества независимо от правил также образуют иерархию как элементы булеана - множества подмножеств. Правила расширенной продукционной системы в предпосылке и заключении могут содержать пропозициональные формулы (см. R.Davis-J.King). Такие формулы кроме правил связаны еще и иерархией в рамках алгебры Линденбаума-Тарского. В подобном виде хранятся математические знания -теоремы записываются в виде «дано ..., требуется доказать ...», где предпосылка и заключение являются интерпретациями формул исчисления предикатов.

Широко применяемые в теории программирования условные системы переписывания термов (N.Dershowitz, J.W.Klop, С.Г.Воробьев) также основываются на правилах продукционного вида, связывающих пары элементов из некоторой иерархии термов. Существуют и другие области информатики, на первый взгляд далекие от продукций, но интерпретируемые ими. В частности, элементы иерархии типов объектно-ориентированной программной системы можно рассматривать как множество, на котором задано продукционное отношение агрегирования. Даже в императивных программах просматриваются продукционные связи между состояниями данных до и после выполнения каждой операции.

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

• адекватно отражала вторичные продукционные связи в различных иерархических системах широкого спектра применения;

• обосновывала автоматизированные формальные исследования таких систем в плане их эквивалентных преобразований, верификации и оптимизации;

• допускала эффективную компьютерную реализацию.

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

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

Научная новизна диссертации заключается в следующих положениях.

• Предложен новый подход для автоматизированной разработки и исследования систем продукционного типа, выраженный в создании основанной на решетках алгебраической теории LP-структур (Lattice-Production Structure). Предполагается, что информация о некоторой предметной области может быть формально представлена в виде решетки. Описание методов использования решеток для представления знаний можно найти в работе F.J.Oles, монографиях J.F.Sowa, А.Тейза-П.Грибомона и др. Основная идея теории LP-структур состоит в моделировании продукционных связей (совокупности правил) дополнительным бинарным отношением с заданными свойствами (рефлексивность, транзитивность и некоторые другие свойства, зависящие от конкретной модели). При этом определяющий решетку частичный порядок

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

• Впервые введено и обосновано понятие эквивалентности продукционно-логических систем на основе их логического замыкания. Доказаны возможности автоматических локально-эквивалентных преобразований ЬР-структур и соответственно моделируемых ими продукционных систем.

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

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

• Новым является распространение единого алгебраического подхода на достаточно широкий спектр различных систем: стандартные и расширенные продукционные экспертные системы; формальные системы математических знаний; условные системы переписывания термов; иерархии типов в объектно-ориентированном программировании. В частности, новым является введенный и использованный в диссертации тезис о продукционной семантике иерархии типов с отношением агрегирования. В результате на базе ЬР-структур обоснованы автоматизированные решения некоторых важных задач верификации типов и рефакторинга. Показана возможность применения продукционно-логических структур к новым исследованиям свойств императивных алгоритмов.

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

• Сформулирована новая концепция трехмерной структуры расширяемой программной системы, которая в дополнение к актуальной ранее двумерной модели (А.Л.Фуксман, М.М.Горбунов-Посадов) содержит набор взаимосвязанных уровней программирования от системного до пользовательского, завершающийся на верхнем уровне продукционной экспертной системой.

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

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

Данные идеи не пересекаются с известными методами быстрого вывода, а дополняют их. Во-первых, алгоритмы RETE (C.L.Forgy) и TREAT (D.Miranker), базирующиеся на специальных сетевых представлениях множеств правил, изначально разрабатывались для стратегии прямого вывода и использовались в продукционных системах с прямым выводом (например, OPS5, CLIPS). Алгоритм LEAPS (D.Miranker, D.Brant) осуществляет компиляцию в язык С множества правил той же продукционной системы OPS5. В последующих исследованиях наиболее популярный алгоритм RETE адаптировался для смешанного (двунаправленного) вывода (Y.H.Lee-S.I.Yoo, P.V.Homeier-T.C.Le). Изложенная в настоящей работе концепция уравнений предназначена для исключительно обратного вывода и не требует для своей реализации громоздких динамических структур, свойственных указанным выше алгоритмам, в случаях, когда нет никакой потребности в прямом (и соответственно смешанном) выводе. Во-вторых, ничто не мешает адаптировать имеющиеся быстрые алгоритмы обратного вывода для нахождения рассмотренных в диссертации решений продукционно-логических уравнений. Этот подход может оказаться интересным направлением развития результатов настоящей работы.

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

Новая теория LP-структур занимает собственную нишу, однако при этом она соприкасается с некоторыми другими исследованиями.

Отметим в частности, что бирешетки (M.Ginsberg) также предполагают наличие двух отношений на общем множестве, однако в прочих аспектах теория LP-структур имеет с ними мало общего, как с точки зрения формального определения, так и возможных применений. В ряде работ (см. статью J.Czelakowski и библиографию в ней) рассматриваются общетеоретические вопросы о свойствах бинарных отношений на частично упорядоченных множествах (в том числе и решетках), такие как монотонность, неподвижные (рефлексивные) точки, рекурсии. Однако эти исследования не учитывают специфики моделей продукционных систем.

Задача логического вывода на LP-структурах перекликается с проблемой нахождения функциональных зависимостей в реляционных базах данных (см., например, монографию Г.Г.Молины-Д.Ульмана—Д.Уидом). При выводе функциональных зависимостей в базе данных используются дедуктивные правила Армстронга, применяемые к элементам булеана. Однако в этой теории из «решеточных» операций используется лишь операция объединения, а набор правил Армстронга существенно беднее множества правил вывода в LP-структурах. Вполне возможно, что исследование реляционных баз данных может стать одной из новых областей применения теории LP-структур. Имеются также определенные перспективы использования подобных LP-структурам алгебраических систем для моделирования некоторых классов полуструктурированных данных (см., например, работы В.А.Васенина, С.А.Афонина) с целью исследования и оптимизации запросов.

Близким к теории LP-структур может считаться FCA - анализ формальных понятий (R.Wille-B.Ganter, С.О.Кузнецов), имеющий широкую область применения в исследованиях двумерных данных с семантикой «объекты-признаки». Он также основан на решетках и рассматривает бинарные отношения между множествами. Однако LP-структуры и FCA имеют существенные отличия. Как видно из публикаций, общих приложений у этих двух теорий практически нет, несмотря на иногда похожие формулировки решаемых в их рамках задач. Например, минимальный базис

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

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

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

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

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

Апробация. Результаты диссертации докладывались на следующих научных конференциях и семинарах: совместном заседании семинара им. И.Г. Петровского и Московского математического общества (Москва, МГУ имени М.В. Ломоносова, 1986); IX конференции молодых ученых и специалистов УДН им. П. Лумумбы (Москва, 1986); XIII Всесоюзной школе по теории операторов в функциональных пространствах (Куйбышев, 1988); XIV Всесоюзной школе по теории операторов в функциональных пространствах (Новгород, 1989); XV Всесоюзной школе по теории операторов в функциональных пространствах (Ульяновск, 1990); международном семинаре «Дифференциальные уравнения и их приложения» (Самара, 1995); международной конференции «Образование, наука, производство и управление в XXI веке» (С.Оскол, 2004); 7-й международной конференции «Информатика: проблемы, методология, технологии» (Воронеж, В ГУ, февраль 2007); международной школе-семинаре «Современные проблемы механики и прикладной математики» (Воронеж,

ВГУ, сентябрь 2007); семинаре «Теоретические проблемы программирования» кафедры математической кибернетики МГУ имени М.В. Ломоносова, рук. Р.И. Подловченко, В.А.Захаров (ноябрь 2007); объединенном семинаре по компьютерной алгебре ф-та ВМК и НИИ ядерной физики МГУ имени М.В. Ломоносова, рук. С.А. Абрамов (январь 2008, март 2009); научно-исследовательском семинаре по автоматизации программирования кафедры системного программирования МГУ имени М.В. Ломоносова, рук. М.Р. Шура-Бура (февраль 2008); XLIV Всероссийской конференции по проблемам математики, информатики, физики в РУДН (апрель 2008); на XII Международной научно-практической конференции-выставке «Актуальные проблемы информатики и информационных технологий» (Тамбов, сентябрь 2008); IX Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, май 2008; Волжский, октябрь 2008); X Всероссийском симпозиуме по прикладной и промышленной математике (Санкт-Петербург, май 2009); Общемосковском научном семинаре «Проблемы искусственного интеллекта» (июнь 2009); международной конференции «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, ВГУ, июнь 2009); международной конференции Mathematical Modeling and Computational Physics (Dubna, July 7-11, 2009); международной конференции «Мальцевские чтения» (Новосибирск, ИМ СО РАН, август 2009); научном семинаре отдела систем математического обеспечения ВЦ имени А.А. Дородницына РАН, рук. В.А. Серебряков (Москва, октябрь 2009); научном семинаре «Проблемы современных вычислительных систем» механико-математического факультета МГУ имени М.В. Ломоносова, рук. В.А. Васенин (октябрь 2009); Ш Всероссийской научной конференции «Методы и средства обработки информации» (Москва, МГУ имени М.В. Ломоносова, октябрь 2009); научном семинаре «Теоретическое программирование» Института систем информатики им. А.П. Ершова СО РАН, рук. Н.В. Шилов (октябрь 2009); П Всероссийской конференции с международным участием «Знания - Онтологии - Теории» (30HT-09) (ИМ СО РАН, октябрь 2009); а также научных сессиях Воронежского госуниверситета (1987-2009). Имеются 2 акта о внедрении результатов работы.

Публикации. По теме диссертации опубликовано 49 научных работ, в том числе 1 монография и 18 работ, соответствующих Перечню ВАК РФ. Опубликованные работы отражают содержание диссертации. Получены 2 свидетельства о регистрации компьютерных программ.

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

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

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

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

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

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

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

Начальный раздел главы посвящен обсуждению новой концепции трехмерной структуры расширяемой программной системы. Эта концепция развивает двумерную модель, описанную в работах АЛ.Фуксмана и М.М.Горбунова-Посадова. Согласно двумерной модели, каждое расширение функциональности программы можно рассматривать как добавление определенного компонента (вертикального слоя), относящегося к некоторым ранее сформированным образованиям (горизонтальным слоям). Изъятие вертикального слоя не приводит к «катастрофическим» последствиям для программы, а лишь обедняет ее функциональность. Каждый же горизонтальный слой программы является ее неотъемлемой частью.

Анализ особенностей современных программных систем приводит к идее о целесообразности ввода в модель описания структуры программ ее третьего измерения, содержащего параллельные уровни разработки. Согласно данной концепции, программная система разрабатывается сразу на нескольких взаимосвязанных уровнях, от нижнего системного до верхнего пользовательского. При этом самый верхний уровень разработки содержит интеллектуальную часть для поддержки пользовательского программирования («настройка» программы), которая может быть представлена в виде специальной продукционной системы. Изложенная концепция изначально стала одной из отправных посылок для введения ЬР-структур.

Далее в главе 1 вводится основная терминология, связанная с бинарными отношениями, решетками, ЬР-структурами и продукционными системами.

Отношение Д на произвольном множестве ^ называется рефлексивным, если для любого а&Г справедливо (а,а)еИ; транзитивным, если для любых я,6,ceF из (а,Ь),{Ь,с) е К следует (а,с)еК. Существует замыкание Л' произвольного отношения Л относительно свойств рефлексивности и транзитивности (рефлексивно-транзитивное замыкание). Пара элементов а,Ъе.Р называется транзитивной в Я, если (а,Ъ) б Л", где И' - транзитивное замыкание отношения й, = Л\ {(а,Ъ)}.

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

Решеткой Г называется множество с частичным порядком < («не больше», «содержится»), на котором для любой пары элементов а,Ье¥ определены операции Л («пересечение») и V («объединение»). Элемент аЛЬ - точная нижняя грань элементов а,Ь в смысле отношения <, аУЪ - точная верхняя грань а,Ъ. Пример решетки -множество всех конечных подмножеств некоторого универсума ^.

Решетка ¥ называется

• ограниченной, если она содержит общие нижнюю и верхнюю грани, а именно -такие два элемента 0,1, что О<,а<,1 для любого аер;

• полной, если каждое ее подмножество имеет в К обе точные грани.

Пример полной ограниченной решетки - булеан 2Г. В полной решетке для любого подмножества элементов (конечного или бесконечного) можно определить (многоместные) пересечение и объединение.

Решетка называется дистрибутивной, если в ней при любых а, Ъ, с выполняются равенства а /\{ЬЧ с) = (а Г\Ь)У (а Ас)\ а\/(ЬАс)~(аЧЬ)Л(а\/с). Дополнением элемента а в ограниченной решетке Г называют элемент а е¥ такой, что аЛа=0 и аУа -I. Решетка, в которой любой элемент имеет дополнение, называется решеткой с дополнениями. Дистрибутивная решетка с дополнениями называется булевой.

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

Одно из таких свойств - дистрибутивность. Неформально оно означает возможность логического вывода по частям и объединения его результатов на основе «решеточных» операций Л и V. Заданное на абстрактной решетке отношение Л называется: Л-дистрибутивным, если из (а,Ь,),(а,Ь2)еЯ следует (а,Ь,дЬ2)еЛ, V-дистрибутивным, если из (а,,Ь),(а2,Ь)еЯ следует (а, Vа2,Ь)еП. Отношение называется дистрибутивным при наличии обоих указанных свойств. На полной решетке (полная) дистрибутивность отношения определяется аналогично, однако с использованием бесконечноместных операций пересечения и объединения.

В некоторых разделах диссертации в качестве основы ЬР-струкгур рассматриваются решетки с семантикой подмножеств. Соответственно вместо символов <, Л и V используются знаки теоретико-множественных операций с, э, П и и, а элементы решетки обозначаются большими буквами. В этих случаях будем иметь в виду лишь второе из двух указанных выше свойств. В такой нотации дистрибушвность трактуется в следующем смысле: из {А,В,),(А,В2)еЯ следует (А,В, ЦВг) е Л. Это свойство будем называть дистрибутивностью.

Подобно транзитивному замыканию и редукции отношения на обычном множестве, в теории ЬР-структур решаются более сложные задачи нахождения логического замыкания и логической редукции отношений на иерархических множествах -решетках. Логическим замыканием заданного на решетке отношения Д называется наименьшее продукционно-логическое отношение, содержащее К. Два отношения эквивалентны, если их логические замыкания совпадают (обозначается Л, ~Л!). Эквивалентным преобразованием отношения называется замена его подмножества, приводящая к эквивалентному отношению. Логической редукцией отношения называется минимальное эквивалентное ему отношение.

Последующие разделы главы посвящены возможным применениям ЬР-структур к системам продукционного типа. В связи с этим вводится также основная терминология, связанная с экспертными продукционными системами. Указанные системы манипулируют множествами фактов и правил (продукций). Факт представляет собой единицу декларативной информации - некоторое суждение о внешнем мире или состоянии системы. Стандартным представлением факта является триплет вида «объект.атрибут = значение» (например, «термометр.температура = высокая»). В некоторых работах (например, книге В.Зо\ууег-В.Ро81ег) триплет редуцируется к паре «параметр = значение». Это означает, что объект и атрибут интегрируются в единый параметр. В данной связи «термометр.температура» и

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

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

Правило (продукция) состоит из предпосылки и заключения. Предпосылка обычно представляет собой выражение над фактами (например, их конъюнкцию или дизъюнкцию). Предпосылка может быть выполненной (истинной) или невыполненной (ложной) при текущем состоянии рабочей памяти. Если предпосылка верна, то правило может быть применено. Заключение - это действие, которое можно осуществить, если верна предпосылка (например, добавить к рабочей памяти некоторый новый факт). Применение правила состоит в выполнении действия заключения. В контексте настоящей работы рассматриваются приложения, в которых заключение, как и предпосылка, является выражением над фактами, и соответствующее заключению действие интерпретируется как «считать истинным». Таким образом, в данном случае применение правила означает некоторую модификацию рабочей памяти. Обычно - это запись в нее тех фактов, справедливость которых вытекает из истинности выражения в заключении правила. Совокупность правил называется базой знаний (БЗ).

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

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

В стандартной продукционной системе правила в качестве предпосылки и заключения могут содержать наборы элементарных фактов ({а}, {а,Ъ}, {а,Ь,с}, ...). Общий вид продукции в данном случае таков: {а,,...,а„}->{Ь1,...,й„}, где а, и Ь] -

факты. Смысл подобного правила состоит в следующем: если верны все а,,1 = 1.....п, то

верны и все = 1.....т. В этой модели основой ЬР-структуры является решетка

конечных подмножеств ? = ЦГ), где F - исходное множество атомарных фактов.

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

заключениями. Стандартная продукционная система с бесконечными правилами моделируется на основе булеана И? = 2Г - полной ограниченной решетки.

В правилах расширенной продукционной системы могут присутствовать пропозициональные формулы (без импликаций, которые можно исключить с использованием дизъюнкции и отрицания). Данную систему можно назвать продукционной системой нулевого порядка. Соответствующую ей ЬР-структуру можно описать на основе булевой решетки Линденбаума-Тарского, элементами которой являются формулы пропозиционального исчисления. Логическим операциям конъюнкции, дизъюнкции и отрицания будут соответствовать определенные на булевой решетке алгебраические операции л, V и '. Для любых двух формул а,Ье¥ справедливо а < Ъ, если из истинности формулы а следует истинность формулы Ъ.

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

Еще одним направлением применения ЬР-структур являются некоторые проблемы эквациональных теорий и систем переписывания термов (СПТ). Эти системы служат математической основой многих исследований в различных областях теории программирования. Важными задачами, связанными с СПТ, являются эквивалентные преобразования и оптимизация их множеств правил. В то время как для обычных СПТ подобные проблемы уже решались в ряде работ (например, У.Тоуата), для условных СПТ они еще остаются открытыми. При определении СПТ отправной точкой является эквациональная теория, множество правил которой состоит из равенств. Поскольку обычно именно эквациональная теория является критерием эквивалентности систем переписывания, исследование в этом плане условных СПТ можно начать с рассмотрения эквивалентности условных эквациональных теорий.

Эквациональная теория может содержать набор позитивно-условных правил вида . Смысл такого правила в следующем: если имеют место все равенства термов = = 1,...,л, то выполнено и 5 = Если вместо термов рассматривать независимые элементы, то упрощение множества правил может быть сведено к логической редукции ЬР-структуры, которая соответствует стандартной продукционной системе. Этот же метод применим и в случае равенств между термами, однако оптимизация при этом может оказаться лишь частичной.

Таким образом, можно ввести новую ЬР-структуру - алгебраическую модель условной эквациональной теории. Множество правил можно задать как бинарное отношение на решетке - конечных наборах равенств вида {.у, = (,}. На этой решетке необходимо ввести дополнительные операции, отражающие использование функциональных символов и подстановок в термах. Такая модель даст теоретическую основу для автоматического преобразования и минимизации множества правил условной эквациональной теории.

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

использовании решетки типов. Структура типов объектно-ориентированной системы образует математическую решетку. При этом частичный порядок ^ задается следующим образом: если тип Ъ является наследником а, то Ъ<а. Для двух типов объединением считается их ближайший общий тип-предок, пересечением -ближайший общий тип-потомок. Для ограниченности полученной решетки можно добавить к ней два специальных элемента: I - универсальный тип (общий предок, имеется во многих современных системах) и О - фиктивный потомок всех типов.

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

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

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

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

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

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

• математически обосновывать возможности эквивалентных преобразований БЗ;

• оптимизировать и исследовать алгоритмы обратного вывода;

• строго формулировать критерии корректности БЗ, а также разрабатывать методы их верификации.

Обобщение этой модели и связанных с ней результатов приводит в дальнейшем к теории LP-структур, которая излагается в разделах 2.2-2.6. В главе 2 в качестве основы LP-структур рассматриваются решетки с семантикой множества X(F). В разделе 2.2 вводятся еще некоторые термины, которые понадобятся в дальнейшем изложении, а также доказываются некоторые вспомогательные утверждения из общей теории решеток и отношений.

Точкой ограниченной (снизу) решетки F называется минимальный элемент ее подмножества F\{0}. Точки обычно обозначаются маленькими буквами. Решетка называется точечной, если каждый ее элемент представляется объединением точек. Например, в булеане точками являются все подмножества, состоящие ровно из одного элемента универсума. Для точки а элемента А иногда используется обозначение а е А (наряду с а с А). В точечной решетке, если она по определению не является полной, каждый элемент полагается состоящим из конечного числа точек, поскольку в такой решетке бесконечноместные операции не определены.

В разделе 2.3 вводится понятие LP-струюуры, которое обобщает теоретико-множественную модель продукционной системы раздела 2.1 и выводит ее на более абстрактный уровень. Это достигается использованием решетки конечных множеств в качестве основы алгебраической системы. На решетке вводятся бинарные отношения, содержащие семантику продукционно-логического вывода. Доказывается существование логического замыкания произвольного отношения. Согласно рассматриваемой в данной главе модели, отношение на решетке называется продукционно-логическим, если оно содержит э, дистрибутивно и транзитивно.

Теорема 2.3.1. Для произвольного отношения R на решетке F существует логическое замыкание —.

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

Раздел 2.4 посвящен обоснованию эквивалентных преобразований LP-структур.

Теорема 2.4.1. Пусть Ri,R1,Ri,RA - отношения на F. Если при этом Д, ~ А, и

л,~л4,то д,ид3~д2ид,-

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

Теорема 2.4.2. Если в отношении R на решетке F каждую пару вида (Л,В), где В = UВ, - конечное объединение элементов В, е F (1 < / < п), заменить парами {(Л,В,),...,(/),£„)}, то полученное отношение R' будет эквивалентно исходному R.

Теоремы 2.4.1-2.4.2 могут быть применены для приведения отношений к каноническому виду. Некоторыми исследователями (например, R.Agarwal) рассматриваются множества хорновых правил. В данной диссертации такой системе соответствует каноническое отношение. Отношение R на точечной решетке F называется каноническим, если оно задано множеством пар вида (А,а), где Asi, а -точка F. Из теоремы 2.4.2 следует, что для любого отношения на точечной решетке существует эквивалентное ему каноническое отношение.

Раздел 2.5 посвящен минимизации LP-структур. Вначале рассматривается вопрос о том, является ли логическое замыкание отношения R транзитивным замыканием

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

Для отношения Л на решетке ¥ вводится отношение Я, построенное последовательным выполнением следующих шагов:

• добавить к Л все пары вида (А,А), где Ае¥ (рефлексивные пары), и обозначить новое отношение Л,;

• добавить к Л1 всевозможные пары (А, В) с элементами вида А = Щ, В = ЦВ,, где все (ДД) (1=1,...,я) принадлежат Д,;

• объединить полученное отношение с отношением включения э.

Теорема 2.5.1. Для отношения Л на решетке Р логическое замыкание —

представляет собой транзитивное замыкание Л' соответствующего отношения Л.

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

• исключить из Л содержащиеся в нем пары вида Л г> В и обозначить новое отношение

• исключить из все пары (А,В) с элементами вида Л = Щ> 5 = 11 В,, где (А,,В,) (:' = 1,...,и) принадлежат и не совпадают с (А,В);

• исключить из полученного отношения все рефлексивные пары.

Аналогичный подход к построению транзитивной редукции («удалить все

транзитивные пары») был бы ошибочным. Причина в том, что в некоторых ситуациях (наличие циклов) транзитивная редукция не единственна, и одновременное удаление всех транзитивных пар может привести к потере связей. Однако, поскольку решетка ациклична, удаление отмеченных выше «объединенных» пар (А, В) приводит к одному и тому же результату независимо от порядка удаления. В связи с данным обстоятельством можно говорить об одновременном удалении всех таких пар.

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

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

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

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

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

Пусть дано некоторое отношение Л на решетке Ж и имеет место А—£->2?. Тогда В называется образом А, а А - прообразом В при отношении —Каждый элемент из Р может иметь много образов и прообразов. Более того, в данном случае в силу определения логического отношения любой Я, с В является образом А и каждый А1 з А является прообразом В. По этой причине при изучении образов и прообразов логических отношений необходимо уточнение рассматриваемых понятий. Для элемента В е¥ минимальным прообразом при отношении —£-> называется такой элемент ЛеР, что А—и А является минимальным, то есть не содержит никакого другого Л, е Р, для которого А, —. В оставшейся части данного раздела рассматриваются лишь точечные решетки.

Определение 2.6.1. Точка х решетки К называется начальной при отношении Я, если в Л нет ни одной такой пары (А,В), что х содержится в В и не содержится в А. Элемент X точечной решетки К называется начальным, если все его точки являются начальными (при отношении Я). Подмножество Ж0(Л) (обозначается Р0, если это не вызывает неоднозначностей) точечной решетки Р, состоящее из всех начальных элементов Р, называется начальным множеством решетки Р (при отношении Я).

Рассматривается уравнение

Л(Х)=В, (2.6.1)

где В е ¥ - заданный элемент, X е Г - неизвестный.

Определение 2.6.2. Частным решением X уравнения (2.6.1) называется любой минимальный прообраз элемента В, содержащийся в Р0. Приближенным (частным) решением X уравнения (2.6.1) называется любой прообраз элемента В, содержащийся в . Общим решением уравнения (2.6.1) называется совокупность всех его частных решений {X,}, л е Я.

Исследуется вопрос о том, как меняются решения уравнений вида (2.6.1) при объединении их правых частей. С этой целью вводится также уравнение

Л(Х)=В,иВ2 (2.6.2)

Теорема 2.6.1. Пусть {X,}, хе^,- общее решение уравнения вида (2.6.1) с правой частью В,, а {Ур}, р^З^ - общее решение уравнения того же вида с правой частью Вг. Тогда общее решение уравнения (2.6.2) представляет собой множество всех элементов вида X, II Ур, из которого исключены элементы, содержащие другие элементы этого же множества.

Рассматриваются методы решения уравнений. В оставшейся части раздела 2.6 предполагается, что Л является каноническим отношением на точечной решетке Р, не содержащим пар отношения а правая часть В уравнения (2.6.1) представляет собой конечное объединение точек. Вводится понятие расслоения {Л, 11 е Г] отношения Л. Оно упрощает изучение отношения —>• и построение алгоритмов решения

уравнений. С этой целью вначале Л разбивается на непересекающиеся подмножества Лр,реР, образованные парами вида {А,хр) с общим элементом хр.

Определение 2.6.3. Слоем В, в отношении Я называется подмножество Я, образованное упорядоченными парами, взятыми по одной из каждого непустого Л', р б Р. Решение X уравнения (2.6.1) порождается слоем Л,,если X >В.

Теорема 2.6.2. Для нахождения общего решения уравнения (2.6.1) достаточно найти частное решение X, в каждом слое Л,, если оно существует, после чего из полученного множества решений исключить элементы, содержащие другие элементы этого же множества.

Следствие 2.6.3. Количество частных решений уравнения (2.6.1) оценивается сверху выражением # = , где - кардинальное число подмножества пар отношения Я с правой частью хр.

Теорема 2.6.2 позволяет свести решение уравнения (2.6.1) к нахождению частного решения уравнения

Я,{Х) = В, (2.6.3)

где В - неначальный элемент решетки У, Л, - произвольный слой в Д.

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

= (2-6-4)

где Ъ - неначальная точка решетки Ж, Я, - произвольный слой в К.

Доказывается, что она эквивалентна задаче на ориентированном графе перечисления входных вершин, из которых достижима данная вершина. Каждой точке решетки Р, участвующей в отношении В, сопоставляется вершина графа. Далее для каждой пары (А, а) рассматриваемого слоя Л, проводятся дуги, ведущие из каждой вершины, соответствующей точке А, в вершину, соответствующую данной а. Для краткости точки Р и соответствующие им вершины в графе отождествляются.

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

саму Ъ ), и все душ, соединяющие такие вершины.

Теорема 2.6.3. Уравнение (2.6.4) имеет не более одного решения. Если граф (7^ не содержит циклов, то единственное решение уравнения состоит из всех точек, соответствующих входным вершинам графа. Если содержит хотя бы один цикл, то уравнение решений не имеет.

Данная теорема завершает обоснование пошагового процесса решения исходного логического уравнения (2.6.1).

В главе 3 определяются ЬР-структуры на решетках, обладающих свойством полноты. Вводятся отношения, содержащие семантику продукционно-логического вывода со свойством нетеровости, то есть транзитивной завершаемое™. Заметим, что условие нетеровости ЬР-структуры слабее аналогичного свойства систем переписывания термов, так как в отличие от них допускает циклы. Приводится обоснование необходимости введения в модель ограничений, соответствующих этому свойству. Данные исследования обобщают материал главы 2. Они предназначены для

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

Важной общей особенностью глав 2-3 является нерекурсивный подход при определении понятий продукционно-логических связей и доказательстве их свойств. Этот подход усложняет математические выкладки, но предоставляет больше возможностей для использования параллельных вычислений. Параллельным методам в продукционных системах посвящены, например, работы А.Сир1а, В.Е.№ш1ап, .Ш.ЗсЬтсЯге. Описанные в них методы могут быть применены на более абстрактном уровне при компьютерной реализации ЬР-структур.

Глава 4 диссертации посвящена развитию теории ЬР-структур применительно к некоторым расширенным моделям продукционных систем. Ввиду усложнения механизмов вывода при определении соответствующих понятий и доказательстве их свойств в данной главе используется рекурсивный подход, аналогичный принятому подходу в пропозициональном исчислении (например, С.ЬСлини, Ч.Чень-РЛи).

В разделе 4.1 исследуется ЦР-структура, логика которой расширена до набора связок пропозиционального языка. Отсюда происходит название - «ЬР-структура нулевого порядка». В качестве ее основы используется булева решетка. Изучены следующие основные вопросы: существование ЬР-замыкания, его архитектура, эквивалентные преобразования. Доказана теорема о существовании логической редукции произвольного отношения и описан процесс ее построения, один из этапов которого связан с нахождением транзитивной редукции отношения.

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

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

Раздел 4.3 посвящен модели эквациональных ЬР-структур. Она возникает в качестве алгебраической интерпретации условной эквациональной теории и соответствующей условной системы переписывания термов. Определяется основанная на решетках модель условной эквациональной теории, учитывающая связи между термами, которые обусловлены применениями функций и подстановок. Исходная теория состоит из условных соотношений я, = (,,...,!„= г„:к,= у,,...,и„= («если имеют место равенства термов я, = г,, ¡=1,...,п, то выполнены и все и) j = l,..,,т»). Такие

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

В начале раздела приводятся связанные с термами базовые определения. Пусть Б -алфавит, представляющий объединение непересекающихся множеств: V - множество переменных; л = 0,1,... - множества п-арных функций. Стандартным образом определяется множество термов Т(Т) К1ор). Отображение а:У Щ)

называется подстановкой. Это понятие распространяется на все г е Т(Т).

Эквациональной теорией называется пара (£,£), где £ - алфавит, состоящий из счетного множества переменных и непустого множества функциональных символов, а £сГ(£)хГ(£) - множество равенств вида 1=1(«,(бЩ)). Для данного множества равенств Е рассматривается множество конечных подмножеств Х(Е). В нем заданы отношения включения с, э, а также «решеточные» операции П и и - теоретико-множественные пересечение и объединение. Кроме них задаются еще две группы операций, связанных соответственно с функциями и подстановками термов:

1) если а = {!,= |/= 1,...,л} и /е£„,то /(а) = {/(у,.....

2) если а = |у=1,...,ш), то <т{а) = ст(^) | _/= \,...,т] для любой подстановки ст.

Определение 4.3.1. Пусть задана эквациональная теория (£,£)• Эквациональной решеткой называется решетка, полученная пополнением относительно

определенных выше операций 1)-2).

Как говорилось выше, в данной модели рассматривается условная эквациональная теория с правилами вида I, = („ :м,=у, . Таким образом, предпосылка и

заключение правила являются элементами эквациональной решетки.

По аналогии с известными работами (Д^.Юор), вводятся аксиомы и правила условной эквациональной дедукции. Аксиомы порождаются правилами вывода

равенств: а: /(о) для любых а = (.....,■?„=/„} и /е!,; а: а(а) для любых аеР и

подстановки ст. Такие условные правила можно назвать тавтологиями. Еще одной очевидной тавтологией является правило а:Ь,а,Ье¥ при йэб.

Правила вывода в условной эквациональной логике таковы:

• а: Ь Ь сг{а): сгф) (а,Ье¥) для любой подстановки сг (следуя Х\У.К1ор);

• а: Ь, а: с 1- а: ЪII с (я, Ь, с) е ¥ (возможность вывода по частям);

• а:Ь, Ь:сЬа;с (а,Ь,с)е¥ (транзитивность).

Далее вводится понятие продукционно-логического отношения, которое соответствует условной эквациональной логике. Во-первых, логическое отношение X должно содержать все тавтологии. Для тавтологий вводится общее обозначение: а ^ Ь, если аэЬ, Ь = а (а) или Ь = /(а). Таким образом, для логического отношения Л справедливо Другие свойства логического отношения вытекают из правил

дедукции. В частности, отношение Л называется применимым, если для любой подстановки а из {а,Ь)еЯ следует (а(_а),а(Ь))еЯ.

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

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

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

В главе 5 рассматриваются две предметные области, исследование которых может быть осуществлено на основе ЬР-структур с немонотонным выводом.

Модель раздела 5.1 содержит семантику продукционно-логического вывода на иерархии типов в объектно-ориентированной системе с дополнительным отношением. Анализируется стандартный набор свойств таких структур, а именно - замкнутость, эквивалентные преобразования, существование логической редукции. Показано, как изложенная теория может быть применена для верификации и автоматической оптимизации иерархий типов, в частности, при рефакторинге - модернизации устаревшего кода. Одним из важных направлений в этом плане является устранение дублирования кода «подъемом» общих атрибутов по иерархии типов. Такая задача решается автоматически при построении логической редукции ЬР-структуры.

Решение родственных задач методами БСА предлагается в статье 11.0ос1ш-Р.УаИсЬеу. В этой работе элементам множества классов требуется в определенном смысле оптимальным образом назначить наборы атрибутов - элементов другого независимого множества. В соответствии с выбранными назначениями формируется иерархия классов. В постановке раздела 5.1 атрибуты сами относятся к исследуемой иерархии. Это обстоятельство усложняет решение задачи и вряд ли оставляет возможность применения БСА.

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

На решетке Р рассматривается второе (соответствующее агрегации) отношение й: если объект типа а в качестве атрибута содержится в типе Ъ, то (Ь,а) е Л. Оба отношения и й) имеют общую семантику. Она состоит в том, что в каждом из случаев, Ь < а или (Ь,а) е Л, тип Ъ получает возможности типа а в виде доступа к его атрибутам. Это общее отношение *— обязано быть рефлексивным и транзитивным.

Рассматривается еще одно свойство введенных отношений. Пусть для а,Ъ^Ъг е¥ справедливо \< а, Ь2<а. Тогда в соответствии с определением решетки имеем Ь,\/Ьг<,а. Это естественное для отношения < свойство называется V-дистрибутивностъю.

Пусть теперь Ь,*-^—а и Ь2<~—а, то есть каждый тип Ь, и Ь2 обладает возможностями типа а. Тогда, если предположить V-дистрибутивность отношения

^-—, справедливо VЬг—а. Этот факт означает, что тип 6,УЬг также обладает возможностями а. С точки зрения проектирования типов это не обязательно. Однако в случае, если более одного наследника (Ь, и Ь2) содержат одинаковые атрибуты, по принципам рефакторинга нужно «поднять» общие атрибуты, то есть поместить один

атрибут в общий тип-предок b¡vb2. В результате каждый Ь, и Ъ2 получит возможности а в порядке наследования. В данном случае V-дистрибутивность отношения — определяет решение одной из задач рефакторинга - устранение дублирования кода.

Отношение —, обладая свойством транзитивности вне зависимости от контекста, не может аналогично во всех ситуациях удовлетворять V-дистрибутивности, иначе это приведет к некорректным результатам. Для иллюстрации можно привести пример Ь—а и —а. При дистрибутивности — выполнялось бы ЬУа*-*—а. По идеологии ООП тип ЬУа ничего не знает о своих наследниках. По этой причине ЬЧа, являясь общим предком типов а и Ь, может обладать возможностями типа а лишь в случае, если он совпадает с а (Ь<а). В других вариантах соотношение -—а будет некорректным.

Существуют ситуации, когда выполнение V-дистрибутивности отношения — теоретически возможно, но нецелесообразно с точки зрения качества кода. Пусть при ¿15—а,Ъ2*г~-—а элементы 6, и а имеют непустое пересечение:

(Ь,\/Ь2)Ла-с1*0, причем < Ь, V Ь2 и с1<а. Если в данном случае допустил, (Л, УЬ2,а)еН, то окажется, что тип с/ обладает возможностями типа а одновременно по двум линиям, а именно - как его наследник и как наследник типа ¿, также имеющего возможности а. Другая подобная ситуация - наличие конфликта. Пусть имеет место (Ь|,о),(62,а),(6],а)еЛ, причем Ь, V 62 * Ь2 V ¿3. Тогда пары (6,,а),(й2,а) «конфликтуют» с парами (Ь2,а),(Ь3,а). Это означает, что если в обоих случаях «поднять» атрибуты, то тип Ъг унаследует атрибут типа а от двух различных предков - V и Ь2 , что также ухудшит код. Принятая в работе стратегия предполагает отказ от «поднятия» общих атрибутов при наличии подобных ситуаций (невыполнение V-дистрибутивности). В дальнейшем возможны другие подходы, тоньше учитывающие особенности конкретной системы.

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

Формулируются определения и условия, связанные с ограничением свойства V-дистрибутивности продукционно-логических отношений. Пара (Ь,а) элементов ограниченной решетки Р называется простой, если аЛЬ-О - нижняя грань Р.

Определение 5.1.1.1. Пусть Л - отношение на ограниченной решетке Р. Две пары вида (Ь,,а), (Ьг,а) е Л называются V-совместимыми в Л, если существуют такие с,,с2еР, что 6, V Ь2 с, V с2, причем пара (с, V с2, а) простая, а пары (с,,а), (с2,а)е Д нетранзитивны в При этом набор элементов С = (ЬпЬг,с1Ус2,а) называется V-

дистрибутивнымкортежем, а Т = (с^с2,а) - V-дистрибутивнойтройкой (в Л).

Пусть имеются V-дистрибутивная тройка Т = (с,, с2, а), а также тройка Т'-(с\,сг,а), проверяемая на аналогичное свойство. Тройку Т будем называть нейтрализующей для Т (обозначается Т' ч Г), если выполнено одно из следующих условий:

1) а = а, с, V сг ф с1 V с2 и справедливо хотя бы одно из неравенств с| < с, V с2;

2) а < а, с, V с2 * с, V ¿г и выполнено хотя бы одно из неравенств с] < с, V с2;

3) а<а , с, Vс2=с[\!с2.

С позиции неформальной эти условия описывают ситуации, когда присутствие нейтрализующей тройки Т «угрожает» свойству V-дистрибутивности тройки Г'. Тройка Т' = (с[,с2,а) называется неконфликтной, если для нее не существует ни одной нейтрализующей V-дистрибутивной тройки.

Понятия, введенные выше для троек вида Т = (с,,с2,а) и Т' = (с\,с2,а), автоматически распространяются и на связанные с ними кортежи С = (Ь1,Ъ2,с,,с1,а) и С' Две V-совместимые пары (Ь,,а), (Ь2,а) называются неконфликтно

V -совместимыми, если для них существует неконфликтный V -дистрибутивный кортеж (брА^СрС^а). Отношение Я на решетке называется ограниченно V-дистрибутивным, если для любых неконфликтно V-совместимых в Л пар (6,,а), (Ь2,а) справедливо (6, У Ь1,а)е Л.

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

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

Теорема 5.1.3.2. Пусть Я - отношение на ограниченной решетке Р. Тогда каждая из следующих операций над Л приводит к эквивалентному отношению:

• добавление или исключение пары (Ь,а), если Ь<.а\

• добавление пары (с, Чсг,а), если тройка Т = (с„с2,а) V-дистрибутивна и неконфликтна в Л;

• добавление или исключение пары (с, а) при наличии пар (с, Ъ), (Ь, а) е (Л I) <), с Ф Ъ, Ь * а.

Заключительный подраздел посвящен оценкам сложности построения логического замыкания и логической редукции ЬР-структур на решетках типов. Решетка типов обычно не является дистрибутивной, и число ее элементов не так велико по сравнению с другими моделями (например, булеаном или решеткой Линденбаума—Тарского). По этой причине в данном случае в качестве основы анализа сложности можно выбрать общее число элементов решетки, а также хранить саму решетку и бинарные отношения на ней в виде матриц смежности.

Теорема 5.1.5.1. Задачи нахождения логического замыкания и логической редукции ЬР-структуры на решетке типов решаются за полиномиальное время, не превышающее 0{Ы6), где N - общее число элементов решетки.

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

и, выполняется с частичным замещением одного из операндов. На таких решетках вводятся продукционно-логические отношения. Определяется понятие логической цепочки глв = (£,,...,£„,), связывающей пару элементов (А,В). Доказана теорема о существовании логического замыкания отношений на некоммутативных решетках.

В заключение рассматривается пример приложения теории некоммутативных LP-структур к исследованию логических свойств императивных алгоритмов -сопоставляются возможности императивного и логического программирования.

Логическая цепочка гАВ = (2?,,...,2?„) называется полной, если при добавлении к ней в любую позицию нового элемента е ¥х, не совпадающего с соседними элементами, она перестает быть цепочкой, логически связывающей пару (А,В). Логическая цепочка гЛВ называется терминальной, если она не может быть продолжена: не существует такого элемента CeFx, что пара (А,С) логически связана, С*В и цепочка гАВ содержится в начале цепочки rJC.

Определение 5.2.4.1. Логической программой на решетке называется тройка Р„ = {F0,FUi,R), где F0,FR„ - два фиксированных подмножества решетки F^, называемые соответственно множеством начальных элементов и множеством результатов, R - некоторое бинарное отношение на F^. Выполнением логической программы Р„ с данным начальным элементом Аа е F0 называется нахождение совокупности всех таких максимальных элементов At е FRtj, что пара (Л,,^) логически связана полной терминальной цепочкой в R. Полученная совокупность элементов {А,) называется результатами программы PR, соответствующими данному начальному элементу А^ (/ е Г). Если Т состоит из единственного элемента, то результат логической программы называется однозначным.

Далее устанавливается связь логических программ с императивными алгоритмами. Для этого рассматривается подкласс - детерминированные логические программы на решетках. Логическая программа Р„ = {Fa,Fl±,,R) на F^ называется детерминированной при данном Аи е¥х, если для любого Аа е F0 при начальном элементе A, Аи ее результат ARe, е FRzI однозначен и достигается единственной (с точностью до порядка элементов в подцепочках) логической цепочкой в R.

Для таких программ можно выделить еще одно подмножество решетки F, -множество управляющих элементов Fu, не пересекающееся с F0 и FUl. Их роль состоит в обеспечении детерминированности действий. Таковым является указанный выше управляющий начальный элемент Аи е Fu. В связи с этим обстоятельством для детерминированных программ также используется обозначение Ркм = (Fu,F„,FRci,R) .

Проводится формализация императивного алгоритма в терминах отношений на решетках. Она опирается на структурную теорему Дейкстры, согласно которой любой алгоритм может быть преобразован в эквивалентный, содержащий лишь действия, управляемые структурами трех видов: цепочкой, альтернативой и циклом while. В качестве (императивных) элементарных действий на решетке F^ рассматриваются применения операции некоммутативного объединения. В частности, результатом действия над некоторым элементом A eFx можно считать C = AUX В, где BeFx.

Для выполнения императивной программы необходимы исходные данные — совокупность начальных элементов F0 решетки При выполнении действий

(операций (J*) начальный элемент А0 &F0 последовательно трансформируется в некоторый новый. На заключительном этапе получается результат программы — результирующий элемент е F^, с F,. Следуя изложенным соображениям, обозначим АСагг переменную со значениями текущего элемента, который имеется на некотором шаге после выполнения всех предыдущих операций программы. Таким образом, до выполнения программы ЛСигг = А^, после - А^ = Af tl.

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

Императивной цепочкой длины т будем называть произвольный упорядоченный набор I = (В'С,...,В") элементов решетки Fj.. Индекс «С» означает возможную зависимость каждого элемента цепочки от текущего значения АСигг. Результатом последовательного применения императивной цепочки I =(Bj-,...,B") к исходному значению АСип. назовем элемент ACurr U* Blc U^ ...l)* В" - новое значение А^.

Для определения альтернативы и цикла необходимо понятие условия. Предполагается, что вычисление логических выражений не вызывает побочных эффектов. В рассматриваемой модели условие эквивалентно принадлежности одного из заданных элементов решетки {A'ConJ | г е Г} текущему элементу А^. Символами {A'Cand \ tef) обозначается набор элементов, соответствующих отрицанию условия с элементами {A'Cond 11 е Г}.

Альтернативой называется выражение вида if {А'Са^} then Blc else Вгс. Результат альтернативы - новое значение Аагг1 вычисляемое по формуле АСт\)хВ]:, если при некотором t е Т справедливо Ас Ас„, и ACwr Uх%с ~ в противном случае. Циклом называется конструкция while {А'^} do Вс. Ее выполнение заключается в рекуррентном вычислении нового значения А^ := ACurr U^ Вс, пока существует такое 1еТ, что S АСигг,

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

Определение 5.2.4.2. Императивной программой на некоммутативной решетке называется тройка Р, = (F0,F^t,I), где F0,FKci - два фиксированных подмножества элементов решетки F^ (множества начальных элементов и результатов), а 1 - любая императивная структура на F^. Выполнением императивной программы Р, с данным начальным элементом A0eF0 называется применение конструкции I к элементу А„. Получаемый после этого элемент ЛКе, е FKcj называется результатом программы Р,, соответствующим данному начальному А^.

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

Теорема 5.2.4.1. Для любой императивной программы Р, =(F0,FRcs,I) на решетке F.y можно построить детерминированную логическую программу PR и

которая при любом начальном элементе е Р] и результате AKtl eFR„ программы Р, выдает для своего начального элемента вида А0 (J^ Аи тот же результат АЯс1, сохраняя при этом порядок и содержание действий Р,.

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

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

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

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

Для хранения канонических отношений на решетках при реализации ряда алгоритмов в работе применяется еще одно новое представление - в виде вектора множеств. Напомним, что каноническое отношение на точечной решетке состоит из пар «хорновского» типа. Правая часть такой пары представляет собой точку решетки, а левая - объединение точек. Для данного отношения строится специальный массив. Индексом массива служит номер точки решетки, содержимым компоненты массива -множество элементов решетки, составляющих с данной точкой пары в качестве их левых частей. Указанное представление весьма эффективно как с точки зрения использования памяти - хранятся лишь левые части пар, так и быстродействия -доступ к ним осуществляется по индексу в массиве. Этот способ применяется для реализации в LP-структуре алгоритмов обратного вывода.

Далее в главе 6 описывается интерфейс класса LPStructure, разработанного автором и реализованного на языке С++ с использованием библиотеки STL. Класс LPStructure инкапсулирует наиболее важные свойства и методы описанных в главе 2 стандартных LP-структур, включая нахождение логической редукции и решение продукционно-логических уравнений.

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

расширяет возможности создания БЗ. К основным преимуществам данной системы логического программирования можно отнести следующие возможности:

• исчерпывающее выявление избыточных правил в БЗ;

• проверка непротиворечивости БЗ;

• новые методы обратного логического вывода (релевантный и кластерно-релевантный LP-выводы);

• исследование образов и прообразов подмножеств фактов.

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

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

В п.б.4.5 описываются функциональные возможности и интерфейс пользователя пакета LPExpert. В п.6.4.6. его возможности экспериментально демонстрируются на ряде тестовых примеров. Первый из них - база знаний «Здоровье» из книги B.Sowyer-D.Foster. Выбор данного примера сделан в силу его популярности в некоторых других исследованиях (например, работа C.G.Giraud-Carrier и T.R Martinez). Для тестовой БЗ получены следующие новые результаты:

• выявлено три избыточных правила (в работе C.G.Giraud-Carrier и T.R Martinez отмечено лишь одно таковое);

• показано, что LP-вывод по сравнению с обычным обратным выводом дает аналогичные результаты, но при этом пользователю задается меньше вопросов (в тестовой экспертизе - на 20%);

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

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

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

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

Приложение А диссертации содержит тексты трех демонстрационных баз знаний.

В Приложении В приведены элементы разработанной автором теории весовых ПДО. Кроме новых результатов, относящихся к области неклассических уравнений с частными производными, оно иллюстрирует возможности применения ЬР-структур к моделированию математических знаний.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ И ПЕРСПЕКТИВЫ

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

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

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

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

1. Введено и обосновано понятие эквивалентности продукционно-логических систем на основе их логического замыкания.

2. Доказаны возможности автоматических локально-эквивалентных преобразований систем продукционного типа.

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

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

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

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

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

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

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

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

К числу практических результатов диссертации относятся следующие.

11. Представлена компьютерная реализация теории ЬР-структур; проведенные эксперименты показали ее работоспособность и эффективность.

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

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

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

Теория ЬР-структур имеет возможности дальнейшего развития, а ее применения могут охватить более широкие области информатики. В этом плане можно назвать следующие направления.

Усложнение моделей. Это, в частности, относится к ЬР-структурам на решетках типов. В работе принята стратегия отказа от «подъема» общего атрибута при наличии конфликта, однако возможен более тонкий учет особенностей конкретных иерархий типов. Также при использовании в данных структурах свойства Л-дистрибутивности окажется доступным моделирование других методов рефакторинга. Усложняя эквациональные ЬР-системы, можно ввести дополнительные операции, которые позволят учитывать структуру термов в равенствах. Класс ЬР80я1с(ше может быть реорганизован в абстрактный класс и применен в качестве основы иерархии типов, охватывающих теорию ЬР-структур целиком.

Построение новых моделей. Например, функциональные зависимости в реляционных базах данных можно описать ЬР-структурой с продукционно-

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

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

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

Нечеткие ЬР-структуры. Это направление способно существенно расширить области применения разработанных в диссертации методов.

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

(в изданиях Перечня ВАК РФ)

1. Махортов С. Д. ЬР-структуры на решетках типов и некоторые задачи рефакторинга / С. Д. Махортов // Программирование. - 2009. - Т. 35, № 4. - С. 5-14.

2. Махортов С. Д. Интегрированная среда логического программирования ЬРЕхреЛ / С. Д. Махортов // Информационные технологии. - 2009. - № 12. - С. 65-66.

3. Махортов С. Д. Алгебраический подход к исследованию и оптимизации баз знаний продукционного типа / С. Д. Махортов, С. Л. Подвальный // Информационные технологии. - 2008. - № 8. - С. 55-60.

В работе [3] Махортову С.Д. принадлежат постановки задач, формулировки и доказательства теорем.

4. Глушко В. П. Операторы неглавного типа и задача с косой производной / В. П. Глушко, С. Д. Махортов // Успехи мат. наук. - 1986. - Т. 41, № 4. - С. 202-203.

В работе [4] Махортову С.Д. принадлежат формулировки и доказательства теорем.

5. Махортов С. Д. Продукционная логика первого порядка и ее алгебраическая интерпретация / С. Д. Махортов // Системы управления и информационные технологии. - 2007. - № 3(29). - С. 21-26.

6. Махортов С. Д. Продукционно-логические отношения на полных решетках / С. Д. Махортов // Системы управления и информационные технологии. - 2008. - № 3(33). - С. 44-48.

7. Махортов С. Д. ЬР-струкгуры и возможности их применения для эквивалентных преобразований условных систем переписывания термов / С. Д. Махортов // Обозрение прикладной и промышленной математики. - 2008. - Т. 15, вып. 3. - С. 504-505.

8. Махортов С. Д. ЬР-структуры на полных решетках и возможности их применения в системах продукционного типа / С. Д. Махортов // Обозрение прикладной и промышленной математики. - 2008. -Т. 15, вып. 4. - С. 671-672.

9. Махортов С. Д. Продукционно-логические уравнения на полных решетках / С. Д. Махортов // Обозрение прикладной и промышленной математики. - 2009. - Т. 16, вып. 2.-С. 368-369.

10. Махортов С. Д. О технологии многоуровневой разработки программных систем / С. Д. Махортов // Вестник ВГУ. Серия Физика, математика. - Воронеж. - 2002. - № 1.-С. 159-162.

11 .Махортов С. Д. Порождающие множества в продукционных системах / С. Д. Махортов // Вестник ВГУ. Серия Физика, математика. - Воронеж. - 2002. - № 2. -С. 69-76.

12. Махортов С. Д. Логические отношения на решетках / С. Д. Махортов // Вестник ВГУ. Серия Физика, математика. - Воронеж. - 2003. - № 2. - С. 203-209.

Ii.Махортов С. Д. Логические уравнения на решетках / С. Д. Махортов // Вестник ВГУ. Серия Физика, математика. - Воронеж. -2004, № 2. - С. 170-178.

14.Махортов С. Д. Некоммутативные решетки и немонотонные логические отношения / С. Д. Махортов // Вестник ВГУ. Серия Физика, математика. -Воронеж,-2006.-№ 1.-С. 166-173.

15.Махортов С. Д. О сравнении возможностей императивного и логического программирования / С. Д. Махортов // Вестник ВГУ. Серия Системный анализ и информационные технологии. - Воронеж. - 2006. - № 1. - С. 78-86.

16. Махортов С. Д. Методы исследования и преобразования иерархий типов на основе логических структур / С. Д. Махортов // Вестник ВГУ. Серия Системный анализ и информационные технологии. - Воронеж. - 2006. - № 2. - С. 24-27.

П. Махортов С. Д. Алгебры весовых и вырождающихся псевдодифференциальных операторов / С. Д. Махортов // Вестник ВГУ. Серия Физика, математика. -Воронеж. - 2007. - № 1. - С. 73-80.

18.Махортов С. Д. Об алгебраической интерпретации продукционной логики нулевого порядка / С. Д. Махортов II Вестник ВГУ. Серия Системный анализ и информационные технологии. - Воронеж. - 2007. - № 1. - С. 56-63.

(монографии)

19. Махортов С. Д. Математические основы искусственного интеллекта: теория LP-структур для построения и исследования моделей знаний продукционного типа / С.Д. Махортов ; под ред. В. А. Васенина. - М. : МЦНМО, 2009. - 304 с.

(прочие публикации)

20.Махортов С. Д. Продукционно-логические уравнения на полных решетках / С.Д.Махортов II Проблемы информатики. - 2009. - № 2. - С. 28-38.

21 .Makhortov S. Multi-level LP-Structures in Rewriting Systems / S. Malchortov // Mathematical Modelling and Computational Physics (MMCP'2009): Book of Abstracts of the International Conference (Dubna, July 7-11, 2009). - Dubna : Щ 2009. -P.123.

22.Махортов С. Д. Модели логических систем продукционного типа, основанные на решетках / С. Д. Махортов II Международная конференция «Мальцевские чтения», посвященная 100-летию со дня рождения академика А.И.Мальцева (Mal'tsev Meeting, August 24-28, 2009): Тезисы докладов. - Новосибирск, 2009. - С. 228.

23.Махортов С. Д. Релевантный обратный вывод и верификация логических программ на основе решения уравнений в LP-структурах / С. Д. Махортов // Методы и средства обработки информации: Третья Всероссийская научная конференция. Москва, 6-8 октября 2009 г.: Труды конференции / Под ред. Л.Н. Королева. - М. : ВМиК МГУ, 2009. - С. 143-148.

24. Махортов С.Д. LP-структуры представления знаний и принципы их реализации / С. Д. Махортов // Вторая Всероссийская конференция с международным участием «Знания - Онтологии - Теории» (30HT-09). Новосибирск, 22-24 октября 2009г.:

Материалы конференции. - Новосибирск: Институт математики им. С.Л. Соболева СО РАН, 2009. - Т.2. — С. 11-19.

25.Калечиц В. Е. Система интерактивной и пакетной отладки в режиме эмуляции / В. Е. Калечиц, Н. И. Лободин, С. Д. Махортов // Математическое моделирование и программное обеспечение САПР. - Горький, 1984. - С. 42-47.

В работе [25] Махортову С.Д. принадлежат разработка алгоритмов и про1раммная реализация.

26. Махортов С. Д. Об одном классе псевдодифференциальных операторов неглавного типа / С. Д. Махортов // Операторные уравнения в функциональных пространствах. -Воронеж : ВГУ, 1986. - С. 127-129.

21. Махортов С. Д. Разрешимость некоторых вырождающихся граничных задач для эллиптических уравнений / С. Д. Махортов // Неклассические уравнения математической физики. - Новосибирск, 1986. - С. 171-175.

28.Махортов С. Д. О задаче с косой производной при произвольном множестве вырождения / С. Д. Махортов // Тезисы ХШ Всесоюзной школы по теории операторов в функциональных пространствах. - Куйбышев, 1988. - С. 128-129.

29. Махортов С. Д. Алгебра вырождающихся псевдодифференциальных операторов / С. Д. Махортов // Применение методов функционального анализа к неклассическим уравнениям математической физики. - Новосибирск, 1988. - С. 93-101.

30 .Махортов С. Д. О разрешимости одной некоэрцитивной задачи для вырождающегося эллиптического уравнения / С. Д. Махортов // Тезисы XIV Всесоюзной школы по теории операторов в функциональных пространствах. -Новгород, 1989.-С. 71.

31. Махортов С. Д. О задаче с косой производной / С. Д. Махортов // Краевые задачи для неклассических уравнений математической физики. - Новосибирск, 1989. - С. 141-143.

32.Махортов С. Д. О фредгольмовости одного псевдодифференциального оператора неглавного типа / С. Д. Махортов // Тезисы XV Всесоюзной школы по теории операторов в функциональных пространствах. - Ульяновск, 1990. - С. 11.

33. Махортов С. Д. О задаче с косой производной / С. Д. Махортов II Материалы международного семинара «Дифференциальные уравнения и их приложения». -Самара, 27-30 июня 1995 г. - С. 63.

34. Махортов С. Д. О задаче с косой производной со специальным случаем вырождения / С. Д. Махортов // Материалы межвузовской научно-практической конференции «Актуальные проблемы борьбы с преступностью в современных условиях». - Воронеж : ВИ МВД, 2000. - С. 185.

35.Махортов С. Д. О теоретико-множественном подходе к формализации логического вывода / С. Д. Махортов // Вестник факультета ПММ. - Воронеж : ВГУ. - 2003. -Вып. 4.-С. 178-185.

36. Махортов С. Д. О редукции логических отношений на решетках / С. Д. Махортов // Вестник факультета ПММ. -Воронеж : ВГУ, 2004. -Вып. 5. - С. 172-179.

37.Махортов С. Д. О разрешимости логических уравнений на решетках / С. Д. Махортов // Материалы Международной конференции «Образование, наука, производство и управление в XXI веке». - Ст. Оскол, 2004. - С. 308-311.

38. Махортов С. Д. Алгебраическая интерпретация продукционной логики / С. Д. Махортов // Вестник факультета ПММ. - Воронеж : ВГУ. - 2006. - Вып. 6. - С. 8698.

39. Махортов С. Д. Теория LP-структур и возможности ее применения в интеллектуальных системах / С. Д. Махортов // Материалы 7-й международной конференции «Информатика: проблемы, методология, технологии». - Воронеж : ВГУ, 2007. - С. 269-272.

40.Махортов С. Д. Алгебраический подход к исследованию и оптимизации продукционных баз знаний / С. Д. Махортов // Сб. трудов международной школы-семинара «Современные проблемы механики и прикладной математики». — Воронеж : ВГУ, 2007. - С. 237-241.

41 .Махортов С. Д. О приложениях LP-структур в теории программирования / С. Д. Махортов I/ Вестник ВГУ. Серия Системный анализ и информационные технологии. - Воронеж. - 2007. - № 2. - С. 40-49.

42. Махортов С. Д. О логической редукции условных систем переписывания термов / С. Д. Махортов // Сб. трудов XLIV Всероссийской конференции по проблемам математики, информатики, физики. - Москва : РУДН, 2008. - С. 5D-51.

43.Махортов С. Д. О редукции продукционно-логических отношений на полных решетках / С. Д. Махортов // Современные проблемы информатизации в анализе и синтезе технологических и программно-телекоммуникационных систем : сб. трудов / под ред. О. Я. Кравца. - Воронеж : Научная книга, 2009. - Вып. 14. - С. 322-325.

44. Махортов С. Д. Модель немонотонной продукционной логики для систем компьютерной алгебры / С. Д. Махортов // Вестник факультета ПММ. — Воронеж : ВГУ, 2009. - Вып. 7. - С. 127-141.

45. Махортов С. Д. Кластерно-релевантный обратный вывод на основе решения логических уравнений / С. Д. Махортов // Сб. трудов Международной конференции «Актуальные проблемы прикладной математики, информатики и механики». -Воронеж : ВГУ, 2009. - Ч. 2. - С. 37-41.

46. Махортов С. Д. LP-структуры и возможности их применения в некоторых задачах рефакторинга / С. Д. Махортов, В. А. Погореленко // Сб. трудов XLIV Всероссийской конференции по проблемам математики, информатики, физики. -Москва : РУДН, 2008. - С. 52-53.

47. Махортов С. Д Решение некоторых задач рефакторинга на основе алгебраических структур / С. Д. Махортов, В. А. Погореленко // Сб. трудов ХП Международной научно-практической конференции-выставки «Актуальные проблемы информатики и информационных технологий». - Тамбов : ТГУ, 2008. - С. 147-149.

48. Махортов С. Д. Алгебраический подход к решению некоторых задач рефакторинга / С. Д. Махортов, В. А. Погореленко // Вестник ВГУ. Серия Системный анализ и информационные технологии. - Воронеж. - 2008. - К» 2. - С. 28-36.

В работах [46-48] Махортову С.Д. принадлежат постановки задач, формулировки и доказательства теорем.

49.Морозова И. С. Программы понижения и повышения уровня структурного описания сложной системы / И. С. Морозова, С. Д Махортов // Математическое обеспечение ЭВМ вузов. - Воронеж : ВГУ, 1980. - С. 115-120.

В работе [49] Махортову С.Д. принадлежат разработка алгоритмов и программная реализация.

Подписано в печать М. 02.2010 Формат 60x90 1/16. Усл. печ. л. 2,5 Тираж {00 экз. Заказ (О

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета МГУ имени М. В. Ломоносова

Введение.

Обзор содержания.

Глава 1. Задачи, приводящие к ЬР-структурам.

1.1.0 многоуровневом программировании.

1.2. Основная терминология решаемых задач.

1.3. Стандартная продукционная система.

1.4. Расширенная продукционная система.

1.5. Продукционная система первого порядка.

1.6. Условная эквациональная теория.

1.7. Модель иерархии типов.

1.8. Продукционная модель императивных алгоритмов.

Глава 2. Общая теория ЬР-структур.

2.1. Порождающие множества в продукционных системах.

2.1.1. Основные определения и обозначения.

2.1.2. Эквивалентные преобразования баз знаний.

2.1.3. Построение минимальных порождающих множеств.

2.1.4. Корректность и верификация баз знаний.

2.2. Дополнительные сведения о бинарных отношениях и решетках.

2.3. Понятие ЬР-структуры. Логические отношения.

2.4. Эквивалентные преобразования.

2.5. Логическая редукция.

2.6. Логические уравнения на решетках.

Глава 3. ЬР-структуры на полных решетках.

3.1. Определение ЬР-структуры на полной решетке.

3.2. Эквивалентные преобразования.

3.3. Логическая редукция.

3.4. Логические уравнения на полных решетках.

Глава 4. Расширенные модели.

4.1. LP-структуры нулевого порядка.

4.1.1. Логическое замыкание и эквивалентные преобразования.

4.1.2. Структура логических связей.

4.1.3. Логическая редукция.

4.2. LP-структуры первого порядка.

4.2.1. Логическое замыкание и эквивалентные преобразования.

4.2.2. Структура логических связей.

4.2.3. Логическая редукция.

4.3. Эквациональные LP-структуры.

4.3.1. Модель условной эквациональной теории.

4.3.2. Логическое замыкание и эквивалентные преобразования.

4.3.3. Структура логических связей.

4.3.4. Логическая редукция.

4.3.5. Некоторые итоги.

Глава 5. Немонотонные LP-структуры.

5.1. LP-структуры на решетках типов.

5.1.1. Определение основных понятий.

5.1.2. Свойства дистрибутивных троек и совместимых пар.

5.1.3. Логическое замыкание и эквивалентные преобразования.

5.1.4. Структура логических связей и редукция.

5.1.5. Алгоритмические вопросы.

5.2. LP-структуры на некоммутативных решетках.

5.2.1. Некоммутативные решетки.

5.2.2. Некоммутативные решетки с расширенным множеством X

5.2.3. Немонотонные логические отношения.

5.2.4. О продукционной модели императивных алгоритмов.

Глава 6. Компьютерная реализация и применение

LP-структур.

6.1. Общие принципы реализации.

6.2. Кодирование LP-структур.

6.3. Класс LPStructure.

6.4. LPExpert — интегрированная среда логического программирования

6.4.1. Структура базы знаний.

6.4.2. Синтаксис базы знаний.

6.4.3. Структура пакета LPExpert и принципы реализации.

6.4.4. Релевантный LP-вывод.

6.4.5. Функциональные возможности и интерфейс пользователя.

6.4.6. Исследование и оптимизация тестовых баз знаний.

6.5. Моделирование математических знаний.

Современное состояние информационных технологий характеризуется многоуровневой структурой - технологии, технологии для технологий и так далее. Соответственно и процесс программирования давно поддерживается собственными технологическими средствами, которые, в свою очередь, реализуются в виде специальных программных систем [141, 159]. Объемы и сложность решаемых на данном направлении задач быстро растут, и естественной в этой связи выглядит потребность в автоматизации и переносе как можно большей части процесса производства программ на ЭВМ. Однако, чем сложнее процесс, тем выше ответственность разработчиков, риски ошибок и следующих за ними неблагоприятных ситуаций и различного рода потерь. Особое значение отмеченное обстоятельство имеет для информатизации объектов критически важных инфраструктур [118-119], где допущенные «промахи» могут привести к чрезвычайным ситуациям, экологическим катастрофам, материальным и другим потерям государственного масштаба. В результате национально значимой становится проблема создания математической базы, с помощью которой можно было бы теоретически обосновывать корректность и надежность программного обеспечения, а также поддерживать процессы его автоматической оптимизации.

Эффективным средством формального построения и исследования программ, основанных на самых различных парадигмах и технологиях, являются алгебраические системы ([113, 138, 144] и другие). Это положение в полной мере относится и к логическому программированию, особенно в части представления теорий и знаний. Алгебраическим методам представления знаний посвящены работы [65, 77], а также монографии [91, 153].

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

А.Линденбаума, А.Тарского, систематическое изложение дано в монографиях [38, 146]. Теория Линденбаума-Тарского рассматривает логику нулевого порядка как универсальную алгебру, операции которой соответствуют логическим связкам пропозиционального языка. Примеры алгебраизации исчисления предикатов первого порядка представляют полиадические алгебры Халмоша [37] и цилиндрические алгебры Хенкина-Тарского [41]. Обзор методов алгебраизации кванторов содержится в монографии [62].

Однако общая алгебраическая логика, расширяя возможности исследования самих логических теорий, существенно не облегчает их практического применения. В силу своей универсальности она не решает ряда важных частных проблем, связанных с широко распространенными на практике логическими системами продукционного типа. На этот факт указывается в книгах [139, 156]. К проблемам такого рода могут быть отнесены вопросы эквивалентности, эквивалентных преобразований, верификации продукционных и подобных им систем, рассматривавшиеся частными методами в работах [1, 27, 48, 52, 63, 145] и других исследованиях. Обзоры имеющихся подходов к верификации знаний содержатся в [34, 150].

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

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

Эквивалентные преобразования и минимизация множества унифицированных правил продукционных экспертных систем в некоторых работах изучались на основе пропозициональных хорновых функций (например, [7, 39-40]). В статье [27] для исключения избыточности знаний используется логика первого порядка. В работе [30] рассмотрено несколько частных случаев упрощения множества правил на основе теории графов. Еще один путь минимизации продукционных систем может дать использование представления продукций сетями Петри [1] и решение задачи редукции сетей Петри [6, 47, 84].

В перечисленных работах нет строго обоснованного алгебраического подхода, универсального в рамках широкого спектра систем продукционного типа, который мог бы быть применен для решения задач эквивалентных преобразований, верификации и минимизации. Имеющиеся на настоящее время алгебраические исследования посвящены частным случаям продукционных систем либо другим их аспектам. В качестве примера можно привести связанную с теорией очевидности [75] алгебраическую теорию «демпстероидов» [35]. Она предназначена для вычислений результатов вывода в продукционных системах с функциями доверия [32].

В работе [73] расширенная продукционная система сводится к системе переписывания термов (СПТ). В семантике последней предлагается процедура обнаружения избыточных правил. Как это принято в системах переписывания термов, требуется «завершаемость» СПТ и, соответственно, исходного множества правил, иначе нет гарантии завершаемости процедуры. Этот интересный метод не охватывает продукционные системы, множества правил которых содержат циклы.

Возможности алгебраического исследования продукционно-логических систем содержит теория ультраоператоров А.В.Чечкина [163]. В приложении к математической логике она предлагает рассматривать импликации в виде отдельного соответствия. Однако в печати не представлены исследования ультраоператоров, связанные со свойством транзитивности логического вывода.

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

Выше наряду с продукционными системами недаром были упомянуты также «подобные им» системы. Многие модели в информатике по своей сути имеют продукционный характер [163]. Кроме того, структуры представления информации часто являются иерархическими.

В первую очередь в контексте настоящей работы имеются в виду продукционные экспертные системы. Они остаются актуальными, что подтверждается значительным числом публикаций последних лет, посвященных как их теоретическим исследованиям, так и решению прикладных задач [5, 12, 13, 44, 45, 50, 51, 54, 68, 79, 110, 137]. База знаний одного из распространенных классов продукционных систем представляет собой совокупность правил вида «если ., то .», где в предпосылке и заключении фигурируют множества так называемых фактов. Эти множества независимо от правил также образуют иерархию как элементы булеана -множества подмножеств. Правила расширенной продукционной системы в предпосылке и заключении могут содержать пропозициональные формулы [15]. Такие формулы кроме правил связаны еще и иерархией в рамках соответствующей алгебры Линденбаума-Тарского. В подобном же виде могут храниться и математические знания - большинство теорем записывается в виде «дано ., требуется доказать .», где предпосылка и заключение являются интерпретациями формулами исчисления предикатов.

Широко применяемые в теории программирования условные системы переписывания термов [17, 46, 101] также основываются на правилах продукционного вида, связывающих пары элементов, которые принадлежат некоторой иерархии термов. Существуют и другие области информатики, на первый взгляд далекие от продукций, но интерпретируемые ими. В частности, элементы иерархии типов объектно-ориентированной программной системы [93] можно рассматривать как множество, на котором задано продукционное отношение агрегирования [158]. Даже в императивных программах просматриваются продукционные связи между состояниями данных до и после выполнения каждой операции.

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

• адекватно отражала вторичные продукционные связи в различных иерархических системах широкого спектра применения;

• обосновывала автоматизированные формальные исследования таких систем в плане их эквивалентности, эквивалентных преобразований, верификации и оптимизации;

• допускала эффективную компьютерную реализацию.

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

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

Научная новизна диссертации заключается в следующих положениях.

• Предложен новый подход для автоматизированной разработки и исследования систем продукционного типа, выраженный в создании основанной на решетках алгебраической теории LP-структур (Lattice-Production Structure). Предполагается, что информация о некоторой предметной области может быть формально представлена в виде решетки. Описание методов использования решеток для представления знаний можно найти в [65, 77, 153]. Основная идея теории LP-структур состоит в моделировании продукционных связей (совокупности правил) дополнительным бинарным отношением с заданными свойствами (рефлексивность, транзитивность и некоторые другие свойства, зависящие от конкретной модели). При этом определяющее решетку исходное отношение частичного порядка отражает универсальные тавтологии и является фиксированным. Второе отношение порождается логическими связями конкретной предметной области и может подвергаться эквивалентным преобразованиям.

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

• Введено новое понятие продукционно-логического уравнения и обоснован способ его решения, что в применении соответствует полному обратному выводу. Концепция уравнений может быть также применена для верификации знаний. Ранее интересные классы логических уравнений рассматривались в работах [96-97, 112, 129], однако представленные в них уравнения имеют отличную от систем продукций природу. На нечетких бинарных отношениях основаны реляционные уравнения, рассматривавшиеся в [16] и ряде других работ. Основные трудности исследования здесь порождаются нечеткостью отношений, поэтому процесс решения соответствует всего лишь единственному шагу обратного вывода.

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

• Новым является распространение единого алгебраического подхода на достаточно широкий спектр различных систем: стандартные и расширенные продукционные экспертные системы; формальные системы математических знаний; условные системы переписывания термов; иерархии типов в объектно-ориентированном программировании. В частности, новым является введенный и использованный в диссертации тезис о продукционной семантике иерархии типов с отношением агрегирования. В результате на базе ЬР-структур обоснованы автоматизированные решения некоторых важных задач верификации типов и рефакторинга. Показана возможность применения продукционно-логических структур к новым исследованиям свойств императивных алгоритмов.

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

• Сформулирована новая концепция трехмерной структуры расширяемой программной системы, которая в дополнение к актуальной ранее двумерной модели [105, 159] содержит набор взаимосвязанных уровней программирования, от системного до пользовательского, завершающийся на верхнем уровне продукционной экспертной системой.

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

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

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

Данные идеи не пересекаются с известными методами быстрого вывода, а дополняют их. Во-первых, алгоритмы RETE [25] и TREAT [57], базирующиеся на специальных сетевых представлениях множеств правил, изначально разрабатывались для стратегии прямого вывода и использовались в продукционных системах с прямым выводом (например, OPS5 [24], CLIPS [42]). Алгоритм LEAPS [58] осуществляет компиляцию в язык С множества правил той же продукционной системы OPS5. В последующих исследованиях наиболее популярный алгоритм RETE адаптировался для смешанного (двунаправленного) вывода [42, 49]. Изложенная в настоящей книге концепция уравнений предназначена для исключительно обратного вывода и не требует для своей реализации громоздких динамических структур данных, свойственных указанным выше алгоритмам, в случаях, когда нет никакой потребности в прямом (и соответственно смешанном) выводе. Во-вторых, ничто не мешает адаптировать имеющиеся быстрые алгоритмы обратного вывода для нахождения рассмотренных в работе решений продукционно-логических уравнений. Этот подход может оказаться интересным направлением развития теории LP-структур.

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

Новая теория LP-структур занимает собственную нишу, однако при этом она соприкасается с некоторыми другими исследованиями.

Отметим в частности, что бирешетки [28] также предполагают наличие двух отношений на общем множестве, однако в прочих аспектах теория LP-структур имеет с ними мало общего, как с точки зрения формального определения, так и возможных применений. В ряде работ (см. [14] и библиографию в ней) рассматриваются общетеоретические вопросы о свойствах бинарных отношений на частично упорядоченных множествах (в том числе и решетках), такие как монотонность, неподвижные (рефлексивные) точки, рекурсии. Однако эти исследования не учитывают специфики моделей продукционных систем.

Задача логического вывода на ЬР-структурах перекликается с проблемой нахождения функциональных зависимостей в реляционных базах данных (см., например, [102]). При выводе функциональных зависимостей в базе данных используются дедуктивные правила Армстронга (они впервые введены в работе [4]), применяемые к элементам булеана. Однако в этой теории из «решеточных» операций используется лишь операция объединения, а набор правил Армстронга существенно беднее множества правил вывода в ЬР-структурах. Вполне возможно, что исследование реляционных баз данных может стать одной из новых областей применения теории ЬР-структур. Имеются также определенные перспективы использования подобных ЬР-структурам алгебраических систем для моделирования некоторых классов полуструктурированных данных (см., например, [67, 95]) с целью исследования и оптимизации запросов.

Близким к теории ЬР-структур может считаться БСА - анализ формальных понятий [26, 123], имеющий широкую область применения в исследованиях двумерных данных с семантикой «объекты-признаки». Он также основан на решетках и рассматривает бинарные отношения между множествами. Существенные отличия двух теорий состоят в следующих положениях.

• В ЬР-структуре бинарное отношение задается на единственном общем множестве - абстрактной решетке. В теории БСА оно действует из одного множества в другое, причем эти два множества имеют различное происхождение (множество объектов и множество признаков). По этой причине в ЬСА не может идти речь о транзитивном или логическом замыкании заданного отношения. При таком подходе рассматриваются лишь замыкания множеств объектов и признаков.

• В ЬР-структуре имеется произвольная решетка элементов, на которой задано еще одно отношение. В БСА элементами рассматриваемой решетки являются пары отношения, что, тем не менее, сводится к решетке множеств на первом универсуме (сопряженно — на втором).

• БСА рассматривает одно единственное отношение. Импликация генерируется самим отношением, порождающим решетку, и в конечном счете сводится к вложению множеств (объектов или признаков). Данная импликация, как и сама решетка понятий, ациклична, что используется соответствующими алгоритмами. В ЬР-структуре импликация заменена вторым независимым отношением произвольной структуры.

• БСА имеет собственную обширную и менее абстрактную терминологию («объекты», «признаки», «понятия» и другие).

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

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

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

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

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

Результаты диссертации докладывались на следующих научных конференциях и семинарах: совместном заседании семинара им. И.Г. Петровского и Московского математического общества (Москва, МГУ имени М.В. Ломоносова, 1986);

IX конференции молодых ученых и специалистов УДН им. П. Лумумбы (Москва, 1986);

XIII Всесоюзной школе по теории операторов в функциональных пространствах (Куйбышев, 1988);

XIV Всесоюзной школе по теории операторов в функциональных пространствах (Новгород, 1989);

XV Всесоюзной школе по теории операторов в функциональных пространствах (Ульяновск, 1990); международном семинаре «Дифференциальные уравнения и их приложения» (Самара, 1995); международной конференции «Образование, наука, производство и управление в XXI веке» (С.Оскол, 2004);

7-й международной конференции «Информатика: проблемы, методология, технологии» (Воронеж, ВГУ, февраль 2007); международной школе-семинаре «Современные проблемы механики и прикладной математики» (Воронеж, ВГУ, сентябрь 2007); семинаре «Теоретические проблемы программирования» кафедры математической кибернетики МГУ имени М.В. Ломоносова, рук. Р.И.Подловченко, В.А.Захаров (ноябрь 2007г.); объединенном семинаре по компьютерной алгебре ф-та ВМК и НИИ ядерной физики МГУ имени М.В. Ломоносова, рук. С.А. Абрамов (январь 2008, март 2009); научно-исследовательском семинаре по автоматизации программирования кафедры системного программирования МГУ имени М.В. Ломоносова, рук. М.Р. Шура-Бура (февраль 2008);

XLIV Всероссийской конференции по проблемам математики, информатики, физики в РУДН (апрель 2008);

XII Международной научно-практической конференции-выставке «Актуальные проблемы информатики и информационных технологий» (Тамбов, сентябрь 2008);

IX Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, май 2008; Волжский, октябрь 2008);

X Всероссийском симпозиуме по прикладной и промышленной математике (Санкт-Петербург, май 2009);

Общемосковском научном семинаре «Проблемы искусственного интеллекта» (июнь 2009); международной конференции «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, ВГУ, июнь 2009); международной конференции Mathematical Modeling and Computational Physics (Dubna, July 7-11, 2009); международной конференции «Мальцевские чтения» (Новосибирск, ИМ СО РАН, август 2009); научном семинаре отдела систем математического обеспечения ВЦ имени А.А. Дородницына РАН, рук. В.А. Серебряков (Москва, октябрь 2009); научном семинаре «Проблемы современных вычислительных систем» механико-математического факультета МГУ имени М.В. Ломоносова, рук. В.А. Васенин (октябрь 2009);

III Всероссийской научной конференции «Методы и средства обработки информации» (Москва, МГУ имени М.В. Ломоносова, октябрь 2009); научном семинаре «Теоретическое программирование» Института систем информатики им. А.П. Ершова СО РАН, рук. Н.В. Шилов (октябрь 2009);

• II Всероссийской конференции с международным участием «Знания -Онтологии - Теории» (ЗОНТ-09) (ИМ СО РАН, октябрь 2009); а также научных сессиях Воронежского госуниверситета (1985-2009).

Имеются 2 акта о внедрении результатов работы.

По теме диссертации опубликовано 49 научных работ, список которых приведен в заключительной части. Он включает 1 монографию и 18 работ, соответствующих Перечню ВАК РФ. Опубликованные работы отражают содержание диссертации. Получены 2 свидетельства о регистрации компьютерных программ.

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

Обзор содержания

Диссертация состоит из введения, шести глав, двух приложений и списка литературы (для удобства пользования публикации автора перечислены отдельно). Работа разбита на разделы и подразделы (пункты, сокращенно — п.). В пределах каждого пункта формулы, определения и так далее нумеруются автономно натуральными числами, начиная с 1. При ссылках на текущий раздел указываются только эти номера. При ссылках на другие разделы в качестве префикса добавляется полный номер раздела. Например, лемма 5 - пятая лемма текущего пункта; теорема 3.1.2 - вторая теорема первого пункта третьей главы.

Заключение

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

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

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

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

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

1. Введено и обосновано понятие эквивалентности продукционно-логических систем на основе их логического замыкания.

2. Доказаны возможности автоматических локально-эквивалентных преобразований систем продукционного типа.

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

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

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

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

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

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

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

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

К числу практических результатов диссертации относятся следующие.

11. Представлена компьютерная реализация теории ЬР-структур; проведенные эксперименты показали ее работоспособность и эффективность.

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

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

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

Теория ЬР-структур имеет возможности дальнейшего развития, а ее применения могут охватить более широкие области информатики. В этом плане можно назвать следующие направления.

Усложнение представленных моделей. Это, в частности, относится к ЬР-структурам на решетках типов. В настоящей работе принята стратегия отказа от «подъема» общего атрибута по иерархии типов при наличии конфликта, однако возможен более тонкий учет особенностей иерархий типов. При использовании в данных структурах свойства д -дистрибутивности окажется доступным моделирование других методов рефакторинга. Усложняя эквациональные ЬР-системы, можно ввести дополнительные операции, которые позволят учитывать структуру термов в равенствах. Класс ЬР81гисШге может быть реорганизован в абстрактный класс и применен в качестве основы иерархии, охватывающей теорию ЬР-структур целиком.

Построение новых моделей. Например, функциональные зависимости в реляционных базах данных можно описать специальной ЬР-структурой с продукционно-логическими свойствами отношений, основанными на правилах Армстронга [102]. Представляются возможными построения аналогичных моделей для мультиагентных систем, некоторых классов полуструктурированных данных и так далее.

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

Динамические ЬР-структуры. Данная идея связана с возможностями динамического преобразования самой решетки, в то время как в моделях, представленных в настоящей работе, может изменяться лишь вторичное отношение. Таким образом, например, можно более полно реализовать методы рефакторинга в иерархиях типов [55].

Нечеткие ЬР-структуры. Это направление способно существенно расширить области применения разработанных в диссертации методов.

1. Agarwal R. A Petri-Net based approach for verifying the integrity of production systems / R. A. Agarwal // International Journal of Man-Machine Studies. 1992. - № 36. - P. 447-^168.

2. Aho A. V. The transitive reduction of a directed graph. SIAM J. Computing 1 : 2 / A. V. Aho, M. R. Garey, J. D. Ulman, 1972. P. 131-137.

3. Andreka H. Algebraic Logic / H. Andreka, J. D. Monk, I. Nemeti. Dordrecht : North-Holland Publ. Co, 1991.

4. Armstrong W. W. Dependency Structure of Database Relationships / W. W. Armstrong // Proc. IFIP Congress. Geneva, 1974. - P. 580-583.

5. Berthelot G. Transformations and decompositions of nets. Lect. Notes Comput. Sci. Springer-Verlag / G. Berthelot. Berlin, 1987. - P. 359-377.V

6. Boros E. Horn minimization by iterative decomposition / E. Boros, O. Cepek, A. Kogan // Annals of Mathematics and Artificial Intelligence 23, 3—4 Jan., 1998.-P. 321-343.

7. Buchanan B. G. Rule-Based Expert Systems: The MYCIN Experiments of the Stanford Heuristic Programming Project / B. G. Buchanan, E. H. Shortliffe. -Addison-Wesley, 1984.

8. Buchberger B. Algebraic Simplification / B. Buchberger, R. Loos // Computer Algebra Symbolic and Algebraic Computation / eds. B. Buchberger,

9. G. E. Collins, R. Loos. Vienna - New York : Springer-Verlag, 1982. -P. 11-43.

10. Buod T. Blending imperative and relational programming / T. Buod // IEEE Software. 1991.-V. 8.-№ l.-P. 58-65.

11. Chen G. Executing Pascal programs on a Prolog architecture / G. Chen, M. H. Williams // Inf. and Software Technology. 1987. - V. 29. - № 6. -P. 285-290.

12. Cheng A. M. Self-Stabilizing Real-Time OPS5 Production Systems / A. M. Cheng, S. Fujii // IEEE Transactions on Knowledge and Data Engineering.-2004.-V. 16.-№. 12.-P. 1543-1554.

13. Cheng A. M. A Graph-Based Approach for Timing Analysis and Refinement of OPS5 Knowledge-Based Systems / A. M. Cheng, H.-Y. Tsai // IEEE Transactions on Knowledge and Data Engineering. 2004. - Vol. 16. - № 2. -P. 271-288.

14. Czelakowski Janusz Monotone Relations, Fixed Points and Recursive Definitions / Janusz Czelakowski // Towards Mathematical Philosophy / eds. David Makinson, Jacek Malinowski, Heinrich Wansing. Berlin : Springer, 2009.-P. 125-164.

15. Davis R. An overview of production systems / R. Davis, J. King // Mahine Intelligence. Chichester : Ellis Horwood Limited. - 1977. - Vol 8. - P. 300332.

16. De Baets B. Analytical Solution Methods for Fuzzy Relational Equations / B. De Baets // Fundamentals of Fuzzy Sets / eds. D. Dubois, and H. Prade. -Boston : Kluwer Academic Publishers, 2000. P. 291-340.

17. Dershowitz N. Termination of rewriting / N. Dershowitz // J. Symbolic Comput. 1987. - V. 3. - P. 69-116.

18. Dershowitz N. A Taste of Rewrite Systems. In Functional Programming, Concurrency, Simulation and Automated Reasoning: international Lecture Series 1991-1992, Mcmaster University, Hamilton, Ontario, Canada /

19. Dershowitz N. ; ed. P. E. Lauer // Lecture Notes In Computer Science. -London : Springer-Verlag. V. 693. - P. 199-228.

20. Doorenbos R. B. Production Matching for Large Learning Systems. Doctoral Thesis. UMI Order Number: UMI Order No. GAX95-22942., Carnegie Mellon University / R. B. Doorenbos, 1995.

21. Erwing M. Specifying Type Systems with Multi-Level Order-Sorted Algebra. 3rd Int. Conf. On Algebraic Method, and Software Technol / M. Erwing, 1993, P. 179-188.

22. Erwing M., Guting R. Explicit Graphs in a Functional Model for Spatial databases. Report 110, Fern University Hägen. — 1991. Revised Version. 1993.

23. Fokkink W. Lazy rewriting on eager machinery / W. Fokkink, J. Kamperman P. Walters // ACM Trans. Program. Lang. Syst. 22, 1 (Jan. 2000). P. 45-86.

24. Forgy C. L. OPS5 user's manual. Technical Report CMU-CS-81-135, Computer Science Department, Carnegie Mellon University, 1981.

25. Forgy C. L. Rete: A fast algorithm for the many pattern/many object pattern match problem / C. L. Forgy // Artificial Intelligence. 1982. - № 19(1). -P. 17-37.

26. Ganter B. Formal Concept Analysis: mathematical foundations / B. Ganter, R. Wille. Heidelberg : Springer, 1999.

27. Ginsberg A. Knowledge-Base Reduction: A New Approach to Checking Knowledge Bases for Inconsistency & Redundancy / A. Ginsberg // Proceedings of the Seventh National Conference on Artificial Intelligence, 1988.-P. 585-589.

28. Ginsberg M. Multivalued logics / M. Ginsberg // Proceedings of AAAI-86. Fifth National Conference on Artificial Intellegence. — Los Altos : Morgan Kaufman Publishers, 1986. P. 243-247.

29. Giraud-Carrier C. G. An Integrated Framework for Learning and Reasoning / C. G. Giraud-Carrier, T. R. Martinez // Journal of Artificial Intelligence Research.- 1995.- V. 3. P. 147-185.

30. Glower F. Logical Testing for Rule-Based Management / F. Glower, H. J. Greenberg // Annals of Operations Research. 1988. - № 12. - P. 199215.

31. Gordon J. The Dempster-Shaffer Theory of Evidence / J. Gordon, E. H. Shortliffe ; eds. B. G. Buchanan and E. H Shortliffe // Rule-Based Expert Systems: MYCIN Experiments, Addison-Wesley Reading, 1984.

32. Gupta A. Parallelism in Production Systems / A. Gupta. Los Altos : Morgan Kaufmann, CA, 1987.

33. Gupta U. G. Validation and verification of knowledge-based systems: A survey / U. G. Gupta // Journal of Applied Intelligence. 1993. - V. 3. - P. 343-363.

34. Hájek P. A generalized algebraic approach to uncertainty processing in rule-based expert systems (dempsteroids) / P. Hájek, J. V. Yaldes // Comput. Artif. Intell. — 1991. V. 10, N. 1. -P. 29-42.

35. Halib M. Bit-vector encoding for partially ordered sets / M. Halib, L. Nourine // Lect. Notes Comput. Sci. 1994. -V. 831. - P. 1-12.

36. Halmos P. Algebraic logic, IV: Equality in polyadic algebras / P. Halmos // Trans. Amer. Math. Soc. 1957. -N. 86. - P. 1-27.

37. Halmos P. Algebraic Logic / P. Halmos. New York : Chelsea Publishing Co, 1962.

38. Hammer P. L. Optimal compression of propositional Horn knowledge bases: complexity and approximation / P. L. Hammer, A. Kogan // Artif. Intell. -1993.-V. 64, N. l.-P. 131-145.

39. Henkin L. Cylindric algebras / L. Henkin, A. Tarski // Proc. of Symposia in Pure Mathematics II (1961), Lattice theory. P. 83-113.

40. Homeier P. V. ECLIPS: An extended CLIPS for backward chaining and goal-directed reasoning / P. V. Homeier, T. C. Le // NASA. Johnson Space Center, Second CLIPS Conference Proceedings. 1991. - Vol. 2. - P. 273-283.

41. Hsiang J. Refutational theorem proving using term-rewriting systems / J. Hsiang // Artif. Intell. 1985. - V. 25. - P. 255-300.

42. Kang J. A. Shortening Matching Time in OPS5 Production Systems / J. A. Kang, A. M. Cheng // IEEE Transactions on Software Engineering. -July 2004. Vol. 30, № 7. - P. 448^57.

43. Landveber L. H., Robertson E. L. Properties of conflict-free and persistent Petri nets / L. H. Landveber, E. L .Robertson // J. ACM. 1978. - Vol. 25, №3.-P. 352-364.

44. Lee S. Developing a strategy for expert system verification and validation / S. Lee, R. M. O'Keefe // IEEE Trans, on Systems, Man and Cybernetics. -1994. Vol. 24. - P. 643-655.

45. Lee Y. H. Optimizing Real-Time Equational Rule-Based Systems / Y.-H. Lee, A. M. Cheng // IEEE Transactions on Software Engineering. Feb. 2004. -Vol. 30, №2.-P. 112-125.

46. Liberatore P. Redundancy in logic II: 2CNF and Horn prepositional formulae / P. Liberatore // Artificial Intelligence. Feb. 2008. - Vol. 172, № 2-3. -P. 265-299.

47. Liu N. K. An Approach Towards the Verification of Expert Systems Using Numerical Petri Nets / N. K. Liu, T. Dillon // International Journal of Intelligent Systems. 1991. - № 6. - P. 255-276.

48. Lock H.C.R. Issues in the implementation of Prolog and their optimization / H.C.R. Lock, A. Martins // Microprocess and Microprogram. 1991. -Vol. 32, № 2-5. - P. 505-514.

49. Maciol A. An application of rule-based tool in attributive logic for business rules modeling / A. Maciol // Expert Systems with Applications. April 2008. -Vol. 34, №.3.-P. 1825-1836.

50. Mens T. A Survey of Software Refactoring / T. Mens, T. Tourw'e // IEEE Trans, on Software Engineering. Feb. 2004. - Vol. 30(2). - P. 126-139.

51. Metivier Y. About the Rewriting Systems Produced by the Knuth-Bendix Completion Algorithm / Y. Metivier // Information Processing Letters 16, 1983.

52. Miranker D. Performance estimates for the DADO machine: A comparison of TREAT and Rete / D. Miranker // Fifth Generation Computer Systems, ICOT. -Tokyo, 1984.

53. Miranker D. On the Performance of Lazy Matching in Production Systems / D. Miranker, D. Brant, B. Lofaso and D. Gadbois // Proc. National Conference on Artificial Intelligence, 1990.

54. Monk J. D. Handbook of Boolean Algebras / J. D. Monk. Amsterdam : North-Holland Co, 1989. - Vols. I-III

55. Munro I. Efficient determination of the transitive closure of a directed graph / I. Munro // Inf. Processing. Letters. 1971. - V. 1. - P. 56-58.

56. Neiman D. E. Issues in the Design and Control of Parallel Rule-Firing Production Systems / D. E. Neiman // J. Parallel Distrib. Comput. 1994. -№23.-P. 338-363.

57. Nemeti /. Algebraization of Quantifier Logics; an Overview / I. Nemeti // Studia Logica L. 1991. - nos 3/4. - P. 485-569.

58. Nguyen T. A. Knowledge Base Verification / T. A. Nguyen, W. A. Perkins, T. J. Laffey and D. Pecora // AI Magazine. 1987. - V. 8, № 2. - P. 69-75.

59. Oies F. J. An Application of Lattice Theory to Knowledge Representation / F. J. Oles //Theor. Comput. Sci. 249, 1 (Oct. 2000). P. 163-196.

60. Pederson K. Well-structured knowledge bases / K. Pederson // AI Expert. -1989.-№ 4.-P. 44-55.

61. Poincaré H. Leçons de Mechanique céleste / H. Poincaré. Paris, 1910. -V. 3.

62. Poli R. Backward-chaining evolutionary algorithms / R. Poli, W. B. Langdon // Artificial Intelligence. August 2006. - Vol. 170, № 11. - P. 953-982.

63. Purdom P. A transitive closure algorithm / P. Purdom // BIT. 1970. -Vol. 10.-P. 76-94.

64. Sahni S. Computationally related problems / S. Sahni // SIAM J. Computing 3 : 2.- 1974.-P. 262-279.

65. Schmölze J. G. Guaranteeing Serializable Results in Synchronous Parallel Production Systems / J. G. Schmölze // J. Parallel Distrib. Comput. 1991. -№ 13(4).-P. 348-365.

66. Schmölze J. G. Detecting redundancy among production rules using term rewrite semantics / J. G. Schmölze, W. Snyder // Knowledge-Based Systems. 1999. -№ 12.-P. 3-11.

67. Scott D. Data Types as Lattices / D. Scott // SIAM J. Comput. 1976. -Vol. 5, Issue 3.-P. 522-587.

68. Shafer G. A Mathematical Theory of Evidence / G. Shafer. Princeton University Press, 1976.

69. Sowa J. F. Conceptual Structures: Information Processing in Mind and Machine / J. F.Sowa. Reading, MA : Addison-Wesley, 1984.

70. Sowa J. F. Knowledge Representation: Logical, Philosophical and Computational Foundations / J. F. Sowa. Brooks Cole Publishing Co., Pacific Grove, CA, 1999.

71. Sowyer B. Programming Expert Systems in Pascal / B. Sowyer, D. Foster. -John Wiley & Sons, Inc., 1986.

72. Tomic B. JavaDON: an open-source expert system shell / B. Tomic, H. Jovanovic, V. Devedzic // Expert Systems with Applications. October 2006.-Vol. 31. — № 3. - P. 595-606.

73. Warren H. S. A modification of Warshall's algorithm for transitive closure of binary relations / H. S. Warren // Communs. ACM. 1975. - Vol.18, № 4. -P. 218-220.

74. Warshall S. A Theorem on Boolean matrices / S. Warshall // J. Assoc. Computing Machinery. 1962. - Vol. 9. - P. 11-12.

75. Zimmermann T. Toward intelligent object-oriented scientific applications / T. Zimmermann, P. Bomme ; eds. В. H. Topping and Z. Bittnar // Engineering Computational Technology. — Edinburgh : Civil-Comp Press, UK, 2002. — P. 271-311.

76. Анишев П. А. Редуцируемость сетей Петри / П. А. Анишев // Программирование. 1982. -№ 4. - С. 36-43.

77. Ануреев И. С. Системы переписывания формул / И. С. Ануреев. -Новосибирск, 1997. 22 с. - (Препр./РАН. Сиб. отд-ние. ИСИ; № 40).

78. Арлазаров В. Л. Об экономичном построении транзитивного замыкания ориентированного графа / В. JI. Арлазаров, Е. А. Диниц, М. А. Крон-форд, И. А. Фараджев // Докл. АН СССР. 1970. - Т. 194, № 3. - С. 487488.

79. Афонин С. А. Алгоритмы эффективного вычисления конъюнктивных регулярных путевых запросов / С. А. Афонин // Вычислительные технологии. 2007. - № 12(2). - С. 23-32.

80. Ахо А. В. Компиляторы: принципы, технологии и инструменты : пер. с англ. / А. В. Ахо, Р. Сети, Дж. Д. Ульман. М. : Вильяме, 2001. - 768 с.

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

82. Агиинянц Р. А. Проект гибридной экспертной системы ОХРАНА / Р. А. Ашинянц, А. В. Засыпкин // Тез. докл. 2-й Всесоюзной школы-семинара «Экспертные системы и Пролог в учебном процессе». -Йошкар-Ола, 1990. С. 4-9.

83. Вениаминов Е. М. Алгебраические методы в теории баз данных и представлении знаний / Е. М. Вениаминов. — М. : Научный мир, 2003. -184 с.

84. Биркгоф Г. Теория решеток : пер. с англ. / Г. Биркгоф. — М. : Наука, 1984. 568 с.

85. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++ : пер. с англ. / Г. Буч. М. : Бином, 2000. - 560 с.

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

87. Васенин В. А. К разработке моделей эффективного поиска информации в сети Интернет / В. А. Васенин, С. А. Афонин // Сб. трудов Всероссийской научной конференции «Научный сервис в сети Интернет-2003». М. : МГУ, 2003. - С. 252-255.

88. Васильев С. Н. Метод редукции и качественный анализ динамических систем, I / С. Н. Васильев // Изв. РАН. ТиСУ. 2006. - № 1. - С. 21-29.

89. Васильев С. Н. Метод редукции и качественный анализ динамических систем, II / С. Н. Васильев // Изв. РАН. ТиСУ. 2006. - № 2. - С. 5-17.

90. Вишик М. И. Эллиптические псевдодифференциальные операторы на замкнутом многообразии, вырождающиеся на подмногообразии / М. И. Вишик, В. В. Грушин // Докл. АН СССР. 1969. - Т. 189, № 1. -С. 16-19.

91. Владимиров В. С. Уравнения математической физики / В. С. Владимиров. -М. : Наука, 1981. 512 с.

92. Воеводин В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. СПб. : БХВ-Петербург, 2002. - 608 с.

93. Воробьев С. Г. Условные системы подстановок термов и их применение в проблемно-ориентированной верификации программ / С. Г. Воробьев : автореф. дис. . к. ф.-м. н. Новосибирск : ВЦ СО АН СССР, 1987.

94. Гарсиа Молина Г. Системы баз данных. Полный курс : пер. с англ. / Г. Гарсиа Молина, Д. Ульман, Д. Уидом. М. : Вильяме, 2002. - 1088 с.

95. Глушко В. 77. Пространства функций с дробными весовыми производными и граничные задачи переменного порядка / В. П. Глушко // Корректные краевые задачи для неклассических уравнений математической физики. — Новосибирск, 1981. — С. 46—53.

96. Гмурмаи В. Е. Теория вероятностей и математическая статистика : учеб. пособие для вузов / Гмурман В. Е. — 9-е изд. М.: Высш. шк., 2003. - 479 с.

97. Горбунов-Посадов М. М. Расширяемые программы / М. М. Горбунов-Посадов. -М.: Полиптих, 1999. 336 с.

98. Грушин В. В. Псевдодифференциальные операторы / В. В. Грушин. — М. : МИЭМ, 1975.- 107 с.

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

100. Джосьютис Н. С++ Стандартная библиотека. Для профессионалов : пер. с англ. / Н. Джосьютис. СПб. : Питер, 2004. - 730 с.

101. ЕгоровЮ. В. Линейные дифференциальные уравнения главного типа / Ю. В. Егоров. М. : Наука, 1984. - 400 с.

102. Засыпкин А. В. Экспертная система поддержки решений по рациональной организации охранно-пожарной сигнализации : автореф. дис. . канд. техн. наук: 05.13.11 / А. В. Засыпкин. М. : МИП, 1993. -20 с.

103. Захаров В. А. О преобразовании операторных процедур в логические программы / В. А. Захаров, С. И. Маневич // Программирование. -1994.-№ 6.-С. 23-38.

104. Касьянов В. Н. Графы в программировании: обработка, визуализация и применение / В. Н. Касьянов, В. А. Евстигнеев. — СПб. : БХВ-Петербург, 2003.-1104 с.

105. П.Клини С. Математическая логика / С. Клини. — М. : Мир, 1973. 480 с.

106. Критически важные объекты и кибертерроризм. Часть 1. Системный подход к организации противодействия / О. О. Андреев и др. ; под ред. В. А. Васенина. М. : МЦНМО, 2008. - 398 с.

107. Критически важные объекты и кибертерроризм. Часть 2. Аспекты программной реализации средств противодействия / О. О. Андреев и др.; под ред. В. А. Васенина. М. : МЦНМО, 2008. - 607 с.

108. Кормен Т. Алгоритмы: построение и анализ : пер. с англ. / Т. Кормен, Ч. Лейзерсон, Р. Ривест. М. : МЦНМО, 2001. - 960 с.

109. Крылов Г. Н. Классические задачи прикладной электродинамики / Г. Н. Крылов. СПб. : СПбГУ, 2005. - 260 с.

110. Кузнецов С. О. Быстрый алгоритм построения всех пересечений объектов из конечной полурешетки / С. О. Кузнецов // НТИ. Сер. 2. -1993.-№ 1.-С. 17-20.

111. Кузнецов С. О. Автоматическое обучение на основе анализа формальных понятий / С. О. Кузнецов // Автоматика и телемеханика. 2001. -№ 10.-С. 3-27.

112. Кулик Б. А. Система логического программирования на основе алгебры кортежей / Б. А. Кулик // Изв. РАН. Техн. кибернетика. 1993. - № 3. -С. 226-239.

113. Кулик Б. А. Логика естественных рассуждений / Б. А. Кулик. — СПб. : Невский Диалект, 2001. — 128 с.2в.Куратовский К. Теория множеств : пер. с англ. / К. Куратовский,

114. A. Мостовский. М. : Мир, 1970. - 416 с.

115. Кучеров Г. А. Системы подстановок термов / Г. А. Кучеров. — Новосибирск, 1985. — 46 с.

116. Левендорский С. 3. Вырождающиеся эллиптические уравнения и краевые задачи / С. 3. Левендорский, Б. П. Панеях // Итоги науки и техн. Соврем, пробл. матем. Фундам. направления. М. : ВИНИТИ, 1990. - Т. 63. -С. 131-200.

117. Левин В. И. Бесконечнозначная логика в задачах кибернетики /

118. B. И. Левин. -М. : Радио и связь, 1982. 176 с.

119. Лингер Р. Теория и практика структурного программирования : пер. с англ. / Р. Лингер, X. Миллс, Б. Уитт. М. : Мир, 1982. - 406 с.131 .Лишнер Р. Секреты Delphi 2 : пер. с англ. / Лишнер Р. К. : Диасофт Лтд, 1996.-800 с.

120. Макконнелл С. Совершенный код. Мастер-класс : пер. с англ. /

121. C. Макконнелл. М. : Русская редакция ; СПб. : Питер, 2005. - 896 с.

122. Махортов С.Д. Непрерывные операции в весовых пространствах основных и обобщенных функций / С.Д. Махортов // Некоторые приложения функционального анализа к задачам математической физики: тр. семинара С.Л. Соболева. Новосибирск, 1984. - №2. -С.109-121.

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

124. Найханова JI.B. Технология создания методов автоматического построения онтологий с применением генетического и автоматного программирования: Монография / JT.B. Найханова. Улан-Удэ: Изд-во БНЦ СО РАН, 2008. - 244 с.

125. ХЪЪ.Нигиян С. А. О семантике бестиповых функциональных программ / С. А. Нигиян, С. А. Аветисян // Программирование. — 2002. № 3. -С. 5-14.

126. Нилъсон Н. Принципы искусственного интеллекта : пер. с англ. / Н. Нильсон. М. : Радио и связь, 1985. - 376 с.

127. Орлик C.B. Секреты Delphi на примерах / С. В. Орлик. М. : Бином, 1996.-316 с.

128. Подловченко Р. И. Иерархия моделей программ / Р. И. Подловченко // Программирование. 1981. — № 2. - С. 3-14.

129. Попов Э. В. Статические и динамические экспертные системы : учебное пособие / Э. В. Попов, И. Б. Фоминых, М. Д. Шапот. М. : Финансы и статистика, 1996.

130. Расёва Е. Математика метаматематики : пер. с англ. / Е. Расёва, Р. Сикорский. М. : Наука, 1972. - 591 с.147 .Рыбаков В. В. Базисы допустимых правил логик S4 и Int / В. В. Рыбаков // Алгебра и логика. 1985. - Т. 24, № 1. - С. 87-107.

131. Рыбаков В. В. Базисы допустимых правил модальной системы Grz и интуиционистской логики / В. В. Рыбаков // Матем. сборник. — 1985. — Т. 128 (170), № 3. С. 321-338.

132. Рыбаков В. В. Независимые базисы для правил, допустимых в предтабличных логиках / В. В. Рыбаков // Алгебра и логика. — 2000. — Т. 39, № 2. С. 206-226.

133. Рыбина Г. В. Верификация баз знаний в интегрированных экспертных системах / Г. В. Рыбина, В. В. Смирнов // Новости искусственного интеллекта. 2005. - № 3. - С. 7-19.151 .Сикорский Р. Булевы алгебры : пер. с англ. / Р. Сикорский. М. : Мир, 1969.-375 с.

134. Таненбаум Э. Архитектура компьютера : пер. с англ. / Э. Таненбаум. — СПб. : Питер, 2002. 704 с.

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

136. Тыугу Э. X. Концептуальное программирование / Э. X. Тыугу. М. : Наука, Гл. ред. физ.-мат. лит., 1984 - 256 с.

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

138. Уэно X. Представление и использование знаний : пер. с яп. / X. Уэно, Т. Кояма, Т. Окамото, Б. Мацуби, М. Исидзука. М. : Мир, 1989. - 220 с.

139. Фаулер М. Рефакторинг: улучшение существующего кода : пер. с англ. / М. Фаулер. СПб. : Символ-Плюс, 2004. - 432 с.

140. Фаулер M. UML. Основы : пер. с англ. / М. Фаулер, К. Скотт. СПб. : Символ-Плюс, 2002. - 192 с.

141. Фуксман А. Л. Технологические аспекты создания программных систем. / А. Л. Фуксман. — М. : Статистика, 1979. — 184 с.

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

143. Чечкин А. В. Математическая информатика / А. В. Чечкин. М. : Наука, Гл. ред. физ.-мат. лит., 1991. - 416 с.

144. Щупак Ю. А. Win32 API. Эффективная разработка приложений / Ю. А. Щупак. СПб. : Питер, 2007. - 572 с.

145. Публикации автора по теме диссертации (в изданиях Перечня ВАК РФ)

146. Махортов С. Д. LP-структуры на решетках типов и некоторые задачи рефакторинга / С. Д. Махортов // Программирование. 2009. - Т. 35, № 4. -С. 5-14.

147. Махортов С. Д. Интегрированная среда логического программирования ЬРЕхрег! / С. Д. Махортов // Информационные технологии. 2009. - № 12. - С. 65-66.

148. Махортов С. Д. Алгебраический подход к исследованию и оптимизации баз знаний продукционного типа / С. Д. Махортов, С. Л. Подвальный // Информационные технологии. 2008. - № 8. — С. 55-60.

149. В работе 3. Махортову С. Д. принадлежат постановки задач, формулировки и доказательства теорем.

150. Глушко В. П. Операторы неглавного типа и задача с косой производной /

151. B. П. Глушко, С. Д. Махортов // Успехи мат. наук. — 1986. Т. 41, № 4.1. C. 202-203.

152. В работе 4. Махортову С.Д. принадлежат формулировки и доказательства теорем.

153. Махортов С. Д. Продукционная логика первого порядка и ее алгебраическая интерпретация / С. Д. Махортов // Системы управления и информационные технологии. 2007. - № 3(29). - С. 21—26.

154. Махортов С. Д. Продукционно-логические отношения на полных решетках / С. Д. Махортов // Системы управления и информационные технологии. 2008. - № 3(33). - С. 44-48.

155. Махортов С. Д. ЬР-структуры и возможности их применения для эквивалентных преобразований условных систем переписывания термов / С. Д. Махортов // Обозрение прикладной и промышленной математики. — 2008. Т. 15, вып. 3. - С. 504-505.

156. Махортов С. Д. ЬР-структуры на полных решетках и возможности их применения в системах продукционного типа / С. Д. Махортов // Обозрение прикладной и промышленной математики. 2008. - Т. 15, вып. 4.-С. 671-672.

157. Махортов С. Д. Продукционно-логические уравнения на полных решетках / С. Д. Махортов // Обозрение прикладной и промышленной математики. 2009. - Т. 16, вып. 2. - С. 368-369.

158. Махортов С. Д. Некоммутативные решетки и немонотонные логические отношения / С. Д. Махортов // Вестник ВГУ. Серия Физика, математика. -Воронеж. 2006. - № 1.-С. 166-173.

159. Махортов С. Д. О сравнении возможностей императивного и логического программирования / С. Д. Махортов // Вестник ВГУ. Серия Системный анализ и информационные технологии. Воронеж. — 2006. - № 1. - С. 7886.

160. Махортов С. Д. Методы исследования и преобразования иерархий типов на основе логических структур / С. Д. Махортов // Вестник ВГУ. Серия Системный анализ и информационные технологии. Воронеж. - 2006. — №2.-С. 24-27.

161. Махортов С. Д. Математические основы искусственного интеллекта: теория LP-структур для построения и исследования моделей знаний продукционного типа / С. Д. Махортов ; под ред. В. А. Васенина. М. : МЦНМО, 2009. - 304 с.прочие публикации)

162. Махортов С.Д. LP-структуры представления знаний и принципы их реализации / С. Д. Махортов // Вторая Всероссийская конференция с международным участием «Знания Онтологии - Теории» (30HT-09).

163. В работе 25. Махортову С.Д. принадлежат разработка алгоритмов и программная реализация.

164. Махортов С. Д. Об одном классе псевдодифференциальных операторов неглавного типа / С. Д. Махортов // Операторные уравнения в функциональных пространствах. Воронеж : ВГУ, 1986. — С. 127-129.

165. Махортов С. Д. Алгебра вырождающихся псевдодифференциальных операторов / С. Д. Махортов // Применение методов функционального анализа к неклассическим уравнениям математической физики. -Новосибирск, 1988. С. 93-101.

166. Ъй.Махортов С. Д. О разрешимости одной некоэрцитивной задачи для вырождающегося эллиптического уравнения / С. Д. Махортов // Тезисы XIV Всесоюзной школы по теории операторов в функциональных пространствах. Новгород, 1989. - С. 71.

167. Махортов С. Д. О задаче с косой производной / С. Д. Махортов // Краевые задачи для неклассических уравнений математической физики. — Новосибирск, 1989.-С. 141-143.

168. Ъ2.Махортов С. Д. О фредгольмовости одного псевдодифференциального оператора неглавного типа / С. Д. Махортов // Тезисы XV Всесоюзной школы по теории операторов в функциональных пространствах. — Ульяновск, 1990.-С. 11.

169. ЗЪ.Махортов С. Д. О задаче с косой производной / С. Д. Махортов // Материалы международного семинара «Дифференциальные уравнения и их приложения». — Самара, 27-30 июня 1995 г. — С. 63.

170. Ъ1.Махортов С. Д. О разрешимости логических уравнений на решетках / С. Д. Махортов // Материалы Международной конференции «Образование, наука, производство и управление в XXI веке». — Ст. Оскол, 2004. С. 308-311.

171. ЪЛ.Махортов С. Д. Алгебраическая интерпретация продукционной логики / С. Д. Махортов // Вестник факультета ПММ. Воронеж : ВГУ. - 2006. -Вып. 6. - С. 86-98.

172. Ъ9.Махортов С. Д. Теория LP-структур и возможности ее применения в интеллектуальных системах / С. Д. Махортов // Материалы 7-й международной конференции «Информатика: проблемы, методология, технологии». Воронеж : ВГУ, 2007. - С. 269-272.

173. Махортов С. Д. Модель немонотонной продукционной логики для систем компьютерной алгебры / С. Д. Махортов // Вестник факультета ПММ. — Воронеж : ВГУ, 2009. Вып. 7. - С. 127-141.

174. Махортов С. Д. ЬР-структуры и возможности их применения в некоторых задачах рефакторинга / С. Д. Махортов, В. А. Погореленко // Сб. трудов ХЫУ Всероссийской конференции по проблемам математики, информатики, физики. Москва : РУДН, 2008. - С. 52-53.

175. Махортов С. Д. Алгебраический подход к решению некоторых задач рефакторинга / С. Д. Махортов, В. А. Погореленко // Вестник ВГУ. Серия Системный анализ и информационные технологии. — Воронеж. — 2008. — № 2. С. 28-36.

176. В работах 46—48. Махортову С.Д. принадлежат постановки задач, формулировки и доказательства теорем.

177. Морозова И. С. Программы понижения и повышения уровня структурного описания сложной системы / И. С. Морозова, С. Д. Махортов // Математическое обеспечение ЭВМ вузов. — Воронеж : ВГУ, 1980. С. 115-120.

178. В работе 49. Махортову С.Д. принадлежат разработка алгоритмов и программная реализация.

179. Хухрянский М.Ю. Ефремов М.С.1. СВИДЕТЕЛЬСТВОо государственной регистрации программы для ЭВМ2010610647

180. Объектно-ориентированная библиотека Ы^гис^ге

181. Правообладателе ли). Государственное образовательное учреждение высшего профессионального образования <*Воронежский государственный университет» (Ш1)

182. Автор(ы): Махортов Сергей Дмитриевич (КС)1. Заявка № 2009614961

183. Дата поступления 14 сентября 2009 Г. Зарегистрировано в Реестре программ для ЭВМ19 января 2010 г.

184. Интегрированная среда логического программирования1. ЬРЕхреН;

185. Правообладатель(ли): Государственное образовательное учреждение высшего профессионального образования «Воронежский государственный университет» (К11)

186. Автор(ы): Махортов Сергей Дмитриевич (ЦЦ)•гл'-эку.-:у: ■ ■.■:1. Заявка №2009614962

187. Дата поступления 14 сентября 2009 Г.

188. Зарегистрировано в Реестре программ для ЭВМ19 января 2010 г.

189. Руководитель Федеральной службы по интеллектуальной собственности, патентам и товарным знакам1. БЛ. СимоновЖж ж ж ж ж ж ж ж ж ж жж ж ж ж ж ж жж ж ж ж ж ж жж ж ж ж ж ж жжжжжжжжжжжжжжжжжжжжжжжжжжжжжжжжж^