Теория lp-структур для построения и исследования моделей знаний продукционного типа
На правах рукописи
МАХОРТОВ Сергей Дмитриевич Теория LP-структур для построения и исследования моделей знаний продукционного типа Специальность 05.13.17 – теоретические основы информатики
АВТОРЕФЕРАТ
диссертации на соискание ученой степени доктора физико-математических наук
Москва – 2009
Работа выполнена на кафедре математического обеспечения ЭВМ факультета прикладной математики, информатики и механики Воронежского государственного университета.
Научный консультант: доктор физико-математических наук, профессор Васенин Валерий Александрович
Официальные оппоненты: доктор физико-математических наук, профессор Чечкин Александр Витальевич доктор физико-математических наук, профессор Кузнецов Сергей Олегович доктор физико-математических наук, профессор Пальчунов Дмитрий Евгеньевич
Ведущая организация: Вычислительный центр имени А.А. Дородницына РАН
Защита диссертации состоится 24 марта 2010 года в 16:45 на заседании диссертационного совета Д 501.002.16 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, д.1, МГУ имени М.В. Ломоносова, механико математический факультет, аудитория 14-08.
С диссертацией можно ознакомиться в библиотеке механико-математи ческого факультета МГУ (главное здание, 14 этаж).
Автореферат разослан «»_2010 г.
Ученый секретарь диссертационного совета, доктор физико-математических наук Корнев А.А.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Тематика и актуальность исследования. Современное состояние информационных технологий характеризуется многоуровневой структурой – технологии, технологии для технологий и так далее. Соответственно и процесс программирования давно поддерживается собственными технологическими средствами, которые, в свою очередь, реализуются в виде специальных программных систем (см. монографии С.Р.Палмера–Дж.М.Фелсинга, А.Л.Фуксмана и др.). Объемы и сложность решаемых на данном направлении задач быстро растут, и естественной в этой связи выглядит потребность в автоматизации и переносе как можно большей части процесса производства программ на ЭВМ. Однако, чем сложнее процесс, тем выше ответственность разработчиков, риски ошибок, следующих за ними неблагоприятных ситуаций и различного рода потерь. Особое значение отмеченное обстоятельство имеет для информатизации объектов критически важных инфраструктур (см. монографию В.А.Васенина и соавторов), где допущенные «промахи» могут привести к чрезвычайным ситуациям, экологическим катастрофам, материальным и другим потерям государственного масштаба. В результате национально значимой становится проблема создания математической базы, с помощью которой можно было бы теоретически обосновывать корректность и надежность программного обеспечения, а также поддерживать процессы его автоматической оптимизации.
Эффективным средством формального построения и исследования программ, основанных на самых различных парадигмах, являются алгебраические системы (см.
работы Р.И.Подловченко, А.В.Замулина, С.А.Нигияна–С.А.Аветисяна и других авторов). Это положение в полной мере относится и к логическому программированию. Алгебраическим методам представления знаний посвящены работы F.J.Oles, J.F.Sowa, а также монографии А.Тейза–П.Грибомона, Е.М.Бениаминова. Математическую основу для создания и исследования моделей знаний предоставляет алгебраическая логика. Ее начала были заложены в работах А.Линденбаума, А.Тарского, систематическое изложение дано в монографиях П.Халмоша и Е.Расёвой–Р.Сикорского. Теория Линденбаума–Тарского рассматривает логику нулевого порядка как универсальную алгебру, операции которой соответствуют логическим связкам пропозиционального языка. Примеры алгебраизации исчисления предикатов первого порядка представляют полиадические алгебры Халмоша и цилиндрические алгебры Хенкина–Тарского. Обзор методов алгебраизации кванторов содержится в монографии И.Немети.
Однако общая алгебраическая логика, расширяя возможности исследования самих логических теорий, существенно не облегчает их практического применения. В силу своей универсальности она не решает ряда важных частных проблем, связанных с широко распространенными на практике логическими системами продукционного типа. На этот факт указывается в книгах Н.Нильсона и Х.Уэно–Т.Коямы. К подобным проблемам могут быть отнесены вопросы эквивалентности, эквивалентных преобразований, верификации продукционных и подобных им систем, рассматривавшиеся частными методами в работах R.Agarwal, S.Lee–R.M.O’Keefe, N.K.Liu–T.Dillon и других исследователей. Обзоры подходов к верификации знаний содержатся в работах U.Gupta, а также Г.В.Рыбиной–В.В.Смирнова. Перечисленные вопросы играют существенную роль при создании и исследовании формальных методов работы со знаниями, а также определяют принципы построения программных средств автоматизации управления знаниями.
Особое место в ряду названных проблем занимает минимизация, поскольку в любой парадигме программирования действует золотое правило – избегать неоправданного дублирования кода или данных. В общей математической логике минимальная система аксиом называется базисом. Проблемы существования базисов допустимых правил для различных логик рассматривались В.В.Рыбаковым и его последователями. Однако продукционные системы имеют особенности, дающие дополнительные возможности минимизации.
Эквивалентные преобразования и минимизация множества унифицированных правил продукционных экспертных систем в некоторых работах изучались на основе пропозициональных хорновых функций (например, E.Boros–O.epek–A.Kogan, P.L.Hammer–A.Kogan). В статье A.Ginsberg для исключения избыточности знаний используется логика первого порядка. В работе F.Glower–H.J.Greenberg рассмотрено несколько частных случаев упрощения множества правил на основе теории графов.
Еще один путь минимизации продукционных систем может дать использование представления продукций сетями Петри (R.Agarwal) и решение задачи редукции сетей Петри (П.А.Анишев, G.Berthelot, L.H.Landveber–E.L.Robertson).
В перечисленных работах нет строго обоснованного алгебраического подхода, универсального в рамках широкого спектра систем продукционного типа, который мог бы быть применен для решения задач эквивалентных преобразований, верификации и минимизации. Имеющиеся на настоящее время алгебраические исследования посвящены частным случаям продукционных систем либо другим их аспектам. В качестве примера можно привести связанную с теорией очевидности (G.Shafer) алгебраическую теорию «демпстероидов» (P.Hjek–J.V.Valdes). Она предназначена для вычислений результатов вывода в продукционных системах с функциями доверия (J.Gordon–E.H.Shortliffe).
В работе J.G.Shmolze–W.Snyder продукционная система сводится к системе переписывания термов (СПТ). В семантике последней предлагается процедура обнаружения избыточных правил. Как это принято в системах переписывания термов, требуется «завершаемость» СПТ и, соответственно, исходного множества правил, иначе нет гарантии завершаемости процедуры. Этот интересный метод не охватывает продукционные системы, множества правил которых содержат циклы.
Возможности алгебраического исследования продукционно-логических систем содержит теория ультраоператоров А.В.Чечкина. В приложении к математической логике она предлагает рассматривать импликации в виде отдельного соответствия.
Однако в печати не представлены исследования ультраоператоров, связанные со свойством транзитивности логического вывода.
Интересная алгебраическая модель, позволяющая формализовать широкий круг логических задач, предложена Б.А.Куликом. Введенная им алгебра кортежей представляет собой еще одну алгебраическую интерпретацию математической логики.
В монографии Б.А.Кулика описываются также возможности применения изложенной теории к моделированию экспертных систем. Не вдаваясь в подробности, отметим, что опубликованные для алгебры кортежей результаты не связаны с решением перечисленных выше задач для продукционных систем.
Выше наряду с продукционными системами недаром были упомянуты также «подобные им» системы. Многие модели в информатике имеют продукционный характер, а структуры представления информации часто являются иерархическими.
В первую очередь в контексте настоящей работы имеются в виду продукционные экспертные системы. Они остаются актуальными, что подтверждается значительным числом публикаций последних лет, посвященных как их теоретическим исследованиям, так и решению прикладных задач. База знаний распространенного класса продукционных систем представляет собой совокупность правил вида «если …, то …», где в предпосылке и заключении фигурируют множества так называемых фактов. Эти множества независимо от правил также образуют иерархию как элементы булеана – множества подмножеств. Правила расширенной продукционной системы в предпосылке и заключении могут содержать пропозициональные формулы (см.
R.Davis–J.King). Такие формулы кроме правил связаны еще и иерархией в рамках алгебры Линденбаума–Тарского. В подобном виде хранятся математические знания – теоремы записываются в виде «дано …, требуется доказать …», где предпосылка и заключение являются интерпретациями формул исчисления предикатов.
Широко применяемые в теории программирования условные системы переписывания термов (N.Dershowitz, J.W.Klop, С.Г.Воробьев) также основываются на правилах продукционного вида, связывающих пары элементов из некоторой иерархии термов. Существуют и другие области информатики, на первый взгляд далекие от продукций, но интерпретируемые ими. В частности, элементы иерархии типов объектно–ориентированной программной системы можно рассматривать как множество, на котором задано продукционное отношение агрегирования. Даже в императивных программах просматриваются продукционные связи между состояниями данных до и после выполнения каждой операции.
С учетом изложенного выше можно констатировать, что актуальной научной проблемой является создание алгебраической теории, которая бы · адекватно отражала вторичные продукционные связи в различных иерархических системах широкого спектра применения;
· обосновывала автоматизированные формальные исследования таких систем в плане их эквивалентных преобразований, верификации и оптимизации;
· допускала эффективную компьютерную реализацию.
Основная цель диссертации – разработка такой теории, а также описание и демонстрация возможностей ее применения на примерах из различных прикладных областей.
Использованные в работе методы исследований основаны на теориях множеств, решеток, бинарных отношений, универсальных алгебр, алгебраической логики, теории графов. При описании приложений применяются методы анализа алгоритмов, теории и технологий программирования. Использованы методы обобщенных функций, функционального анализа, псевдодифференциальных операторов.
Научная новизна диссертации заключается в следующих положениях.
· Предложен новый подход для автоматизированной разработки и исследования систем продукционного типа, выраженный в создании основанной на решетках алгебраической теории LP-структур (Lattice-Production Structure). Предполагается, что информация о некоторой предметной области может быть формально представлена в виде решетки. Описание методов использования решеток для представления знаний можно найти в работе F.J.Oles, монографиях J.F.Sowa, А.Тейза–П.Грибомона и др.
Основная идея теории LP-структур состоит в моделировании продукционных связей (совокупности правил) дополнительным бинарным отношением с заданными свойствами (рефлексивность, транзитивность и некоторые другие свойства, зависящие от конкретной модели). При этом определяющий решетку частичный порядок отражает универсальные тавтологии и является фиксированным. Второе отношение порождается логическими связями конкретной предметной области и может подвергаться эквивалентным преобразованиям.
· Впервые введено и обосновано понятие эквивалентности продукционно логических систем на основе их логического замыкания. Доказаны возможности автоматических локально-эквивалентных преобразований LP-структур и соответственно моделируемых ими продукционных систем.
· Введено понятие продукционно-логического уравнения и обоснован способ его решения, что в применении соответствует полному обратному выводу. Концепция уравнений может быть также применена для верификации знаний. Интересные классы логических уравнений рассматривались в работах А.Д.Закревского, С.Н.Васильева, В.И.Левина, однако представленные в них уравнения имеют отличную от систем продукций природу. На нечетких бинарных отношениях основаны реляционные уравнения, рассматривавшиеся в работах B. De Baets и других авторов. Основные трудности исследования здесь порождаются нечеткостью отношений, и процесс решения соответствует лишь единственному шагу вывода.
· Доказано существование и получен эффективный способ построения логической редукции LP-структур. В приложениях он означает минимизацию соответствующих баз знаний, то есть построение эквивалентной продукционной системы с минимальным набором правил.
· Новым является распространение единого алгебраического подхода на достаточно широкий спектр различных систем: стандартные и расширенные продукционные экспертные системы;
формальные системы математических знаний;
условные системы переписывания термов;
иерархии типов в объектно ориентированном программировании. В частности, новым является введенный и использованный в диссертации тезис о продукционной семантике иерархии типов с отношением агрегирования. В результате на базе LP-структур обоснованы автоматизированные решения некоторых важных задач верификации типов и рефакторинга. Показана возможность применения продукционно-логических структур к новым исследованиям свойств императивных алгоритмов.
· В качестве примера для иллюстрации приложения LP-структур первого порядка в диссертации изложены элементы теории неклассических псевдодифференциальных операторов. Они содержат новые результаты автора в соответствующей области.
· Сформулирована новая концепция трехмерной структуры расширяемой программной системы, которая в дополнение к актуальной ранее двумерной модели (А.Л.Фуксман, М.М.Горбунов-Посадов) содержит набор взаимосвязанных уровней программирования от системного до пользовательского, завершающийся на верхнем уровне продукционной экспертной системой.
· Разработаны и реализованы оригинальные эффективные методы компьютерного представления основанных на решетках алгебраических структур.
· Предложены и реализованы новые методы обратного вывода и верификации для систем продукционного типа, базирующиеся на решении логических уравнений.
Концепция LP-вывода направлена на минимизацию количества запросов к внешнему источнику. Запросы по возможности отправляются только для тех фактов, которые необходимы при выводе. Отрицательный ответ на единственный запрос исключает все последующие запросы об элементах целого множества. Кроме того, при LP-выводе предпочтение отдается тестированию множества фактов минимальной мощности.
Данные идеи не пересекаются с известными методами быстрого вывода, а дополняют их. Во-первых, алгоритмы RETE (C.L.Forgy) и TREAT (D.Miranker), базирующиеся на специальных сетевых представлениях множеств правил, изначально разрабатывались для стратегии прямого вывода и использовались в продукционных системах с прямым выводом (например, OPS5, CLIPS). Алгоритм LEAPS (D.Miranker, D.Brant) осуществляет компиляцию в язык C множества правил той же продукционной системы 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-структур в виде объектно ориентированного класса LPStructure. Этот класс был применен при разработке интегрированной среды логического программирования 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);
второй Всероссийской конференции с международным участием «Знания – Онтологии – Теории» (ЗОНТ-09) (Новосибирск, ИМ СО РАН, октябрь 2009);
а также научных сессиях Воронежского госуниверситета (1987–2009).
Публикации. По теме диссертации опубликовано 50 научных работ, в том числе монография и 19 работ, соответствующих Перечню ВАК РФ. Опубликованные работы отражают содержание диссертации.
Личный вклад автора. В диссертации изложены результаты, полученные лично автором, включая исследование проблематики, постановки задач, методы их решения, алгоритмы и программные реализации. Из совместно опубликованных работ в диссертацию вошли только результаты автора.
Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, двух приложений и списка литературы. Общий объем диссертации 552с., список литературы содержит 219 наименований.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Поскольку в автореферате приводится лишь часть доказанных в работе теорем, непрерывность нумерации формулируемых здесь математических утверждений может не соблюдаться.
Во введении содержатся общий обзор тематики исследований и ее ретроспектива, показана актуальность работы, представлены цели и задачи исследований, описаны методы решения задач, сформулированы полученные в работе новые научные результаты, показано научное и практическое значение работы.
Глава 1 носит вводный характер. В ней перечисляются задачи из различных областей информатики, описание которых может быть сведено к системам продукционного типа, моделируемым LP-структурами. Одна из целей данной главы – сделать более ясными как происхождение теории LP-структур, так и общие возможности ее применения.
Начальный раздел главы посвящен обсуждению новой концепции трехмерной структуры расширяемой программной системы. Эта концепция развивает двумерную модель, описанную в работах А.Л.Фуксмана и М.М.Горбунова-Посадова. Согласно двумерной модели, каждое расширение функциональности программы можно рассматривать как добавление определенного компонента (вертикального слоя), относящегося к некоторым ранее сформированным образованиям (горизонтальным слоям). Изъятие вертикального слоя не приводит к «катастрофическим» последствиям для программы, а лишь обедняет ее функциональность. Каждый же горизонтальный слой программы является ее неотъемлемой частью.
Анализ особенностей современных программных систем приводит к идее о целесообразности ввода в модель описания структуры программ ее третьего измерения, содержащего параллельные уровни разработки. Согласно данной концепции, программная система разрабатывается сразу на нескольких взаимосвязанных уровнях, от нижнего системного до верхнего пользовательского.
При этом самый верхний уровень разработки содержит интеллектуальную часть для поддержки пользовательского программирования («настройка» программы), которая может быть представлена в виде специальной продукционной системы. Изложенная концепция изначально стала одной из отправных посылок для введения LP-структур.
Далее в главе 1 вводится основная терминология, связанная с бинарными отношениями, решетками, LP-структурами и продукционными системами.
Отношение R на произвольном множестве F называется рефлексивным, если для любого a F справедливо (a, a ) R ;
транзитивным, если для любых a, b, c F из (a, b), (b, c ) R следует (a, c) R. Существует замыкание R* произвольного отношения R относительно свойств рефлексивности и транзитивности (рефлексивно транзитивное замыкание). Пара элементов a, b F называется транзитивной в R, если (a, b) R1*, где R1* – транзитивное замыкание отношения R1 = R \ {( a, b)}.
Обратная задача – нахождение транзитивной редукции: ищется минимальное отношение R ' такое, что его транзитивное замыкание совпадает с транзитивным замыканием исходного R. Здесь минимальность подразумевается в смысле частично упорядоченных множеств, то есть различаются понятия минимального элемента (для него нет меньшего элемента) и наименьшего элемента (он меньше всех).
Решеткой F называется множество с частичным порядком («не больше», «содержится»), на котором для любой пары элементов a, b F определены операции («пересечение») и («объединение»). Элемент a b – точная нижняя грань элементов a, b в смысле отношения, a b – точная верхняя грань a, b. Пример решетки – множество l ( F ) всех конечных подмножеств некоторого универсума F.
Решетка F называется · ограниченной, если она содержит общие нижнюю и верхнюю грани, а именно – такие два элемента O, I, что O a I для любого a F ;
· полной, если каждое ее подмножество имеет в F обе точные грани.
Пример полной ограниченной решетки – булеан 2 F. В полной решетке для любого подмножества элементов (конечного или бесконечного) можно определить (многоместные) пересечение и объединение. Для таких операций используются обозначения и (с соответствующими индексами, если они необходимы).
Решетка называется дистрибутивной, если в ней при любых a, b, c выполняются равенства a (b c ) = (a b) (a c) ;
a (b c ) = (a b) (a c). Дополнением элемента a в ограниченной решетке F называют элемент a ' F такой, что a a ' = O и a a ' = I.
Решетка, в которой любой элемент имеет дополнение, называется решеткой с дополнениями. Дистрибутивная решетка с дополнениями называется булевой.
Под LP-структурой будем подразумевать алгебраическую систему, представляющую решетку, на которой задано бинарное отношение, обладающее продукционно-логическими свойствами. К ним относятся рефлексивность, транзитивность и другие свойства, определяемые конкретной моделью.
Одно из таких свойств – дистрибутивность. Неформально оно означает возможность логического вывода по частям и объединения его результатов на основе «решеточных» операций и. Заданное на абстрактной решетке отношение R называется: -дистрибутивным, если из (a, b1 ), (a, b2 ) R следует (a, b1 b2 ) R, дистрибутивным, если из (a1, b), (a2, b) R следует (a1 a2, b) R. Отношение называется дистрибутивным при наличии обоих указанных свойств. На полной решетке (полная) дистрибутивность отношения определяется аналогично, однако с использованием бесконечноместных операций пересечения и объединения.
В некоторых разделах диссертации в качестве основы LP-структур рассматриваются решетки с семантикой подмножеств. Соответственно вместо символов,, и используются знаки теоретико-множественных операций,, I и U, а элементы решетки обозначаются большими буквами. В этих случаях будем иметь в виду лишь второе из двух указанных выше свойств. В такой нотации U дистрибутивность трактуется в следующем смысле: из ( A, B1 ), ( A, B2 ) R следует ( A, B1 U B2 ) R. Это свойство будем называть дистрибутивностью.
Подобно транзитивному замыканию и редукции отношения на обычном множестве, в теории LP-структур решаются более сложные задачи нахождения логического замыкания и логической редукции отношений на иерархических множествах – решетках. Логическим замыканием заданного на решетке отношения R называется наименьшее продукционно-логическое отношение, содержащее R. Два отношения R1, R2 эквивалентны, если их логические замыкания совпадают (обозначается R1 ~ R2 ).
Эквивалентным преобразованием отношения называется замена его подмножества, приводящая к эквивалентному отношению. Логической редукцией отношения называется минимальное эквивалентное ему отношение.
Последующие разделы главы посвящены возможным применениям LP-структур к системам продукционного типа. В связи с этим вводится также основная терминология, связанная с экспертными продукционными системами. Указанные системы манипулируют множествами фактов и правил (продукций). Факт представляет собой единицу декларативной информации – некоторое суждение о внешнем мире или состоянии системы. Стандартным представлением факта является триплет вида «объект.атрибут = значение» (например, «термометр.температура = высокая»). В некоторых работах (например, книге B.Sowyer–D.Foster) триплет редуцируется к паре «параметр = значение». Это означает, что объект и атрибут интегрируются в единый параметр. В данной связи «термометр.температура» и «термометр.изготовитель» считаются разными параметрами. В некоторых разделах данной работы пойдем дальше, интегрируя в факт параметр и его значение, считая факт независимым элементом общего множества фактов. Упрощение делается там, где необходимо больше сосредоточиться на основных идеях применения LP-структур. В дальнейшем можно реализовать и более сложную конструкцию фактов, скорректировав соответствующим образом описание LP-структуры.
Продукционная система содержит так называемую рабочую память. Это некоторое подмножество фактов, которые на текущий момент времени считаются выполненными.
Правило (продукция) состоит из предпосылки и заключения. Предпосылка обычно представляет собой выражение над фактами (например, их конъюнкцию или дизъюнкцию). Предпосылка может быть выполненной (истинной) или невыполненной (ложной) при текущем состоянии рабочей памяти. Если предпосылка верна, то правило может быть применено. Заключение – это действие, которое можно осуществить, если верна предпосылка (например, добавить к рабочей памяти некоторый новый факт). Применение правила состоит в выполнении действия заключения. В контексте настоящей работы рассматриваются приложения, в которых заключение, как и предпосылка, является выражением над фактами, и соответствующее заключению действие интерпретируется как «считать истинным».
Таким образом, в данном случае применение правила означает некоторую модификацию рабочей памяти. Обычно – это запись в нее тех фактов, справедливость которых вытекает из истинности выражения в заключении правила. Совокупность правил называется базой знаний.
Прямым выводом называется процесс циклического применения правил к содержимому рабочей памяти (его исходное состояние задано в начале работы), и соответственно получение в результате новых фактов, которые считаются справедливыми. Прямой вывод может производиться до тех пор, когда получение новых фактов станет невозможным. Обратный вывод – противоположный процесс. В нем по некоторому набору результирующих фактов – гипотезе, путем анализа правил в направлении от заключения к предпосылке, подтверждается или опровергается справедливость гипотезы при заданном исходном содержимом рабочей памяти. В процессе обратного вывода содержимое рабочей памяти также меняется.
Далее в главе 1 в качестве возможных приложений LP-структур рассматриваются несколько видов систем продукционного типа, различающихся используемой формой правила, точнее – выражений для его предпосылки и заключения. В каждом случае продукционную систему можно формально представить LP-структурой на основе решетки, элементами которой являются предпосылки и заключения правил.
В стандартной продукционной системе правила в качестве предпосылки и заключения могут содержать наборы элементарных фактов ({a}, {a, b}, {a, b, c}, …).
Общий вид продукции в данном случае таков: {a1,..., an } ® {b1,..., bm }, где ai и b j – факты. Смысл подобного правила состоит в следующем: если верны все ai, i = 1,..., n, то верны и все b j, j = 1,..., m. В этой модели основой LP-структуры является решетка конечных подмножеств F = l( F ), где F – исходное множество атомарных фактов.
Теоретически возможны продукционные системы с бесконечными множествами правил. Они могут быть описаны правилами с использованием в них переменных, имеющих формально бесконечные области определения. Эквивалентные преобразования таких систем приводят к правилам с бесконечными предпосылками и заключениями. Стандартная продукционная система с бесконечными правилами моделируется на основе булеана F = 2 F – полной ограниченной решетки.
В правилах расширенной продукционной системы могут присутствовать пропозициональные формулы (без импликаций, которые можно исключить с использованием дизъюнкции и отрицания). Данную систему можно назвать продукционной системой нулевого порядка. Соответствующую ей LP-структуру можно описать на основе булевой решетки Линденбаума–Тарского, элементами которой являются формулы пропозиционального исчисления. Логическим операциям конъюнкции, дизъюнкции и отрицания будут соответствовать определенные на булевой решетке алгебраические операции, и '. Для любых двух формул a, b F справедливо a b, если из истинности формулы a следует истинность формулы b.
Продукционная система первого порядка в качестве элементов правил допускает формулы исчисления предикатов. Такая система может формально представлять математические знания. Для построения соответствующей ей LP-структуры требуется алгебраическое описание логических кванторов, которое дополнило бы булеву решетку. Можно воспользоваться алгебраизацией кванторов из монографии Е.Расевой и Р.Сикорского. Согласно этой работе, кванторы общности и существования соответственно моделируются в общем случае бесконечноместными операциями пересечения и объединения на полной булевой решетке.
Еще одним направлением применения LP-структур являются некоторые проблемы эквациональных теорий и систем переписывания термов (СПТ). Эти системы служат математической основой многих исследований в различных областях теории программирования. Важными задачами, связанными с СПТ, являются эквивалентные преобразования и оптимизация их множеств правил. В то время как для обычных СПТ подобные проблемы уже решались в ряде работ (например, Y.Toyama), для условных СПТ они еще остаются открытыми. При определении СПТ отправной точкой является эквациональная теория, множество правил которой состоит из равенств. Поскольку обычно именно эквациональная теория является критерием эквивалентности систем переписывания, исследование в этом плане условных СПТ можно начать с рассмотрения эквивалентности условных эквациональных теорий.
Эквациональная теория может содержать набор позитивно-условных правил вида s1 = t1,..., sn = tn : s = t. Смысл такого правила в следующем: если имеют место все равенства термов si = ti, i = 1,..., n, то выполнено и s = t. Если вместо термов рассматривать независимые элементы, то упрощение множества правил может быть сведено к логической редукции LP-структуры, которая соответствует стандартной продукционной системе. Этот же метод применим и в случае равенств между термами, однако оптимизация при этом может оказаться лишь частичной.
Таким образом, можно ввести новую LP-структуру – алгебраическую модель условной эквациональной теории. Множество правил можно задать как бинарное отношение на решетке – конечных наборах равенств вида {si = ti }. На этой решетке необходимо ввести дополнительные операции, отражающие использования функциональных символов и подстановок в термах. Такая модель даст теоретическую основу для автоматического преобразования и минимизации множества правил условной эквациональной теории.
Перечисленные выше возможности применения LP-структур ограничены системами с монотонным выводом. Однако, существуют практические задачи, модели которых подобным свойством не обладают. Одна из таковых основана на использовании решетки типов. Структура типов объектно-ориентированной системы образует математическую решетку. При этом частичный порядок задается следующим образом: если тип b является наследником a, то b a. Для двух типов объединением считается их ближайший общий тип-предок, пересечением – ближайший общий тип-потомок. Для ограниченности полученной решетки можно добавить к ней два специальных элемента: I – универсальный тип (общий предок, имеется во многих современных системах) и O – фиктивный потомок всех типов.
На такой решетке рассматривается отношение R, соответствующее агрегации типов: если объект типа a в качестве атрибута содержится в типе b, то (b, a ) R. Оба отношения ( и R ) имеют общую семантику: в каждом случае, b a или (b, a ) R, тип b получает возможности типа a в виде доступа к его атрибутам. Семантически ясно, что данное общее отношение «обладания набором возможностей» обязано быть рефлексивным и транзитивным. В диссертации показано, что это продукционно логическое отношение еще обладает ограниченным свойством дистрибутивности. Оно содержит семантику автоматического решения задачи «поднятия» общих атрибутов по иерархии типов – одной из задач рефакторинга в объектно-ориентированном программировании (ООП).
Построенная таким образом LP-структура позволит производить автоматизированные исследования иерархий типов, включая эквивалентные преобразования, верификацию и минимизацию. Она может служить основой для практической реализации или модернизации типов.
К немонотонным продукционным системам в диссертации сводится еще одна предметная область – анализ свойств и преобразования императивных алгоритмов. Во время их работы информация не только накапливается, но и замещается.
Используемые в программе значения переменных можно считать фактами базы знаний. Инициализация переменной может рассматриваться как добавление нового факта к базе знаний. Присвоение же переменной нового значения можно интерпретировать как модификацию имеющегося факта.
Классическое понятие решетки оказывается недостаточно выразительным для моделирования немонотонного продукционно-логического вывода. В связи с этим обстоятельством будут введены некоммутативные решетки как обобщение классических решеток. В новых решетках операция объединения выполняется с частичным замещением одного из операндов. Для построения соответствующих LP структур рассматриваются логические бинарные отношения на этих решетках, а также описываются возможности применения этой модели к формальному исследованию логических свойств императивных алгоритмов.
Глава 2 содержит описание общей теории LP-структур. Теория названа общей, поскольку результаты последующих глав работы основываются на тех же положениях, развивая их в том или ином специальном направлении.
Предварительно в разделе 2.1 формулируется частная конечная теоретико множественная модель продукционной системы, без использования аппарата решеток.
Вводится ряд математических понятий, базовым среди которых является минимальное порождающее множество. Затем показывается, как эта теория может быть применена для исследования свойств продукционных систем и разработки связанных с ними алгоритмов. Использование предлагаемого подхода позволяет:
· математически обосновывать возможности эквивалентных преобразований баз знаний;
· оптимизировать и исследовать алгоритмы обратного вывода;
· строго формулировать критерии корректности баз знаний, а также разрабатывать методы их верификации.
Обобщение этой модели и связанных с ней результатов приводит в дальнейшем к теории LP-структур, которая излагается в разделах 2.2–2.6. В главе 2 в качестве основы LP-структур рассматриваются решетки с семантикой множества l( F ). В разделе 2.2 вводятся еще некоторые термины, которые понадобятся в дальнейшем изложении, а также доказываются некоторые вспомогательные утверждения из общей теории решеток и отношений.
Точкой ограниченной (снизу) решетки F называется минимальный элемент ее подмножества F \ {O}. Точки обычно обозначаются маленькими буквами. Решетка называется точечной, если каждый ее элемент является объединением точек.
Например, в булеане точками являются все подмножества, состоящие ровно из одного элемента универсума. Для точки a элемента A иногда используется обозначение a A (наряду с a A ). В точечной решетке, если она по определению не является полной, каждый элемент полагается состоящим из конечного числа точек, поскольку в такой решетке бесконечноместные операции не определены.
В разделе 2.3 вводится понятие LP-структуры, которое обобщает теоретико множественную модель продукционной системы раздела 2.1 и выводит ее на более абстрактный уровень. Это достигается использованием решетки конечных множеств в качестве основы алгебраической системы. На решетке вводятся бинарные отношения, содержащие семантику продукционно-логического вывода. Доказывается существование логического замыкания произвольного отношения, что позволяет определить понятие эквивалентного отношения. Согласно рассматриваемой в данной главе модели, отношение на решетке называется продукционно-логическим, если оно содержит, дистрибутивно и транзитивно.
Теорема 2.3.1. Для произвольного отношения R на решетке F существует логическое замыкание. ® R Теорема 2.3.1 позволяет ввести понятие эквивалентных отношений, что служит основой формальных преобразований и оптимизации продукционных баз знаний.
Раздел 2.4 посвящен обоснованию эквивалентных преобразований LP-структур.
Теорема 2.4.1. Пусть R1, R2, R3, R4 – отношения на F. Если при этом R1 ~ R2 и R3 ~ R4, то R1 U R3 ~ R2 U R4.
Она обосновывает принцип локальности эквивалентных преобразований: заменяя некоторое подмножество данного отношения на эквивалентное множество, мы получаем эквивалентное общее отношение.
Теорема 2.4.2. Если в отношении R на решетке F каждую пару вида ( A, B), где B = U Bi – конечное объединение элементов Bi F (1 i n), заменить парами {( A, B1 ),..., ( A, Bn )}, то полученное отношение R будет эквивалентно исходному R.
Теоремы 2.4.1–2.4.2 могут быть применены для приведения отношений к каноническому виду. Некоторыми исследователями (например, R.Agarwal) рассматриваются множества хорновых правил. В данной диссертации такой системе соответствует каноническое отношение. Отношение R на точечной решетке F называется каноническим, если оно задано множеством пар вида ( A, a ), где A F, a – точка F. Из теоремы 2.4.2 следует, что для любого отношения на точечной решетке существует эквивалентное ему каноническое отношение.
Раздел 2.5 посвящен минимизации LP-структур. Вначале рассматривается вопрос о том, является ли логическое замыкание отношения R транзитивным замыканием % некоторого другого отношения R R. Положительный ответ на него полезен для разработки алгоритмов построения логического замыкания и редукции. Он позволяет свести исследование вопросов о нахождении логического замыкания и редукции отношений к рассмотрению соответствующих свойств транзитивных отношений.
% Для отношения R на решетке F вводится отношение R, построенное последовательным выполнением следующих шагов:
· добавить к R все пары вида ( A, A), где A F (рефлексивные пары), и обозначить новое отношение R1 ;
· добавить к R1 всевозможные пары ( A, B) с элементами вида A = U Ai, B = U Bi, где все ( Ai, Bi ) ( i = 1,..., n ) принадлежат R1 ;
· объединить полученное отношение с отношением включения.
Теорема 2.5.1. Для отношения R на решетке F логическое замыкание ® R % соответствующего отношения R.
% * представляет собой транзитивное замыкание R Далее рассматривается вопрос о существовании логической редукции отношений.
Для отношения R вводится отношение R, построенное последовательным % % выполнением шагов, обратных построению R, а именно:
· исключить из R содержащиеся в нем пары вида A B и обозначить новое отношение R-1 ;
· исключить из R-1 все пары ( A, B) с элементами вида A = U Ai, B = U Bi, где ( Ai, Bi ) ( i = 1,..., n ) принадлежат R-1 и не совпадают с ( A, B) ;
· исключить из полученного отношения все рефлексивные пары.
Аналогичный подход к построению транзитивной редукции («удалить все транзитивные пары») был бы ошибочным. Причина в том, что в некоторых ситуациях (наличие циклов) транзитивная редукция не единственна, и одновременное удаление всех транзитивных пар может привести к потере связей. Однако, поскольку решетка ациклична, удаление отмеченных выше «объединенных» пар ( A, B) приводит к одному и тому же результату независимо от порядка удаления. В связи с данным обстоятельством можно говорить об одновременном удалении всех таких пар.
Следующая теорема указывает достаточное условие существования и способ построения логической редукции данного отношения.
% Теорема 2.5.2. Пусть для отношения R построено соответствующее отношение R.
% Тогда, если для R существует транзитивная редукция R, то соответствующее ей R % представляет собой логическую редукцию исходного отношения R.
% Заметим, что требование существования транзитивной редукции отношения R может оказаться избыточным для существования логической редукции исходного отношения R. При конечном R из него всегда можно удалить «лишние» пары, получив в результате логическую редукцию. Однако если при этом решетка бесконечна и имеет соответствующую структуру, то, объединяя R с отношением, % можно построить не имеющее транзитивной редукции отношение R. Таким образом, возникает вопрос об усилении теоремы 2.5.2. Одно из возможных направлений такого усиления – использование вместо отношения вида R, содержащего лишь необходимое для получения логической редукции R подмножество. В этом случае утверждения и доказательства настоящей главы будут более громоздкими, однако принципиальных новшеств не принесут. По этой причине данные идеи оставлены лишь в качестве рекомендации для конкретных приложений.
% Следует также отметить, что на практике при построении R не обязательно физически добавлять указанные пары. Достаточно реализовать эффективный механизм проверки того, относится ли заданная пара к теоретически добавляемым.
В разделе 2.6 вводится и изучается связанный с LP-структурами специальный класс уравнений. Рассматриваются вопросы о разрешимости и количестве решений этих уравнений, а также методы их решения.
Пусть дано некоторое отношение R на решетке F и имеет место A B. Тогда ® R B называется образом A, а A – прообразом B при отношении. Каждый ® R элемент из F может иметь много образов и прообразов. Более того, в данном случае в силу определения логического отношения любой B1 B является образом A и каждый A1 A является прообразом B. По этой причине при изучении образов и прообразов логических отношений необходимо уточнение рассматриваемых понятий.
Для элемента B F минимальным прообразом при отношении называется такой ® R элемент A F, что A B и A является минимальным, то есть не содержит ® R никакого другого A1 F, для которого A1 B. В оставшейся части данного раздела ® R рассматриваются лишь точечные решетки.
Определение 2.6.1. Точка x решетки F называется начальной при отношении R, если в R нет ни одной такой пары ( A, B), что x содержится в B и не содержится в A.
Элемент X точечной решетки F называется начальным, если все его точки являются начальными (при отношении R ). Подмножество F0 ( R) (обозначается F0, если это не вызывает неоднозначностей) точечной решетки F, состоящее из всех начальных элементов F, называется начальным множеством решетки F (при отношении R ).
Рассматривается уравнение R( X ) = B, (2.6.1) где B F – заданный элемент, X F – неизвестный.
Определение 2.6.2. Частным решением X уравнения (2.6.1) называется любой минимальный прообраз элемента B, содержащийся в F0. Приближенным (частным) решением X уравнения (2.6.1) называется любой прообраз элемента B, содержащийся в F0. Общим решением уравнения (2.6.1) называется совокупность всех его частных решений { X s }, s S.
Исследуется вопрос о том, как меняются решения уравнений вида (2.6.1) при объединении их правых частей. С этой целью вводится также уравнение R( X ) = B1 U B2 (2.6.2) Теорема 2.6.1. Пусть { X s }, s S1 – общее решение уравнения вида (2.6.1) с правой частью B1, а {Yp }, p S 2 – общее решение уравнения того же вида с правой частью B2.
Тогда общее решение уравнения (2.6.2) представляет собой множество всех элементов вида X s U Yp, из которого исключены элементы, содержащие другие элементы этого же множества.
Рассматриваются методы решения уравнений. В оставшейся части раздела 2. предполагается, что R является каноническим отношением на точечной решетке F, не содержащим пар отношения, а правая часть B уравнения (2.6.1) представляет собой конечное объединение точек. Вводится понятие расслоения {Rt | t T } отношения R.
Оно упрощает изучение отношения и построение алгоритмов решения ® R уравнений. С этой целью вначале R разбивается на непересекающиеся подмножества R p, p P, образованные парами вида ( A, x p ) с общим элементом x p.
Определение 2.6.3. Слоем Rt в отношении R называется подмножество R, образованное упорядоченными парами, взятыми по одной из каждого непустого R p, p P. Решение X уравнения (2.6.1) порождается слоем Rt, если X B.
® R t Теорема 2.6.2. Для нахождения общего решения уравнения (2.6.1) достаточно найти частное решение X t в каждом слое Rt, если оно существует, после чего из полученного множества решений исключить элементы, содержащие другие элементы этого же множества.
Следствие 2.6.3. Количество частных решений уравнения (2.6.1) оценивается сверху выражением N = N p, где N p – кардинальное число подмножества пар отношения R с правой частью x p.
Теорема 2.6.2 позволяет свести решение уравнения (2.6.1) к нахождению частного решения уравнения Rt ( X ) = B, (2.6.3) где B – неначальный элемент решетки F, Rt – произвольный слой в R.
Исследования раздела 2.6 показывают, что для решения уравнения (2.6.3) достаточно решить уравнение с каждой точкой элемента B в качестве правой части. В связи с данным обстоятельством рассматривается задача нахождения частного решения следующего уравнения:
Rt ( X ) = b, (2.6.4) где b – неначальная точка решетки F, Rt – произвольный слой в R.
Доказывается, что она эквивалентна задаче на ориентированном графе перечисления входных вершин, из которых достижима данная вершина. Каждой точке решетки F, участвующей в отношении R, сопоставляется вершина графа. Далее для каждой пары ( A, a ) рассматриваемого слоя Rt проводятся дуги, ведущие из каждой вершины, соответствующей точке A, в вершину, соответствующую данной a. Для краткости точки F и соответствующие им вершины в графе отождествляются.
В полученном графе GR выбирается вершина b. Рассматривается подграф t GR,b GR, содержащий все вершины, из которых достижима вершина b (включая t t саму b ), и все дуги, соединяющие такие вершины.
Теорема 2.6.3. Уравнение (2.6.4) имеет не более одного решения. Если граф GR,b не t содержит циклов, то единственное решение уравнения состоит из всех точек, соответствующих входным вершинам графа. Если GR,b содержит хотя бы один цикл, t то уравнение решений не имеет.
Данная теорема завершает обоснование пошагового процесса решения исходного логического уравнения (2.6.1).
В главе 3 определяются LP-структуры на решетках, обладающих свойством полноты. Вводятся отношения, содержащие семантику продукционно-логического вывода со свойством нетеровости, то есть транзитивной завершаемости. Заметим, что условие нетеровости LP-структуры слабее аналогичного свойства систем переписывания термов, так как в отличие от них допускает циклы. Приводится обоснование необходимости введения в модель ограничений, соответствующих этому свойству. Данные исследования обобщают материал главы 2. Они предназначены для моделирования продукционных систем, правила которых могут содержать бесконечные множества фактов. Некоторые определения по форме выглядят подобными соответствующим определениям главы 2, однако теперь их содержание связано с полными решетками, и это обстоятельство усложняет как смысл данных понятий, так и доказательство их свойств. Получены результаты, соответствующие изложенным в разделах 2.3–2.6, но относящиеся к нетеровым продукционно логическим отношениям на полных решетках.
Важной общей особенностью глав 2–3 является нерекурсивный подход при определении понятий продукционно-логических связей и доказательстве их свойств.
Этот подход усложняет математические выкладки, но предоставляет больше возможностей для использования параллельных вычислений. Параллельным методам в продукционных системах посвящены, например, работы A.Gupta, D.E.Neiman, J.G.Schmolze. Описанные в них методы могут быть применены на более абстрактном уровне при компьютерной реализации LP-структур.
Глава 4 диссертации посвящена развитию теории LP-структур применительно к некоторым расширенным моделям продукционных систем. Ввиду усложнения механизмов вывода при определении соответствующих понятий и доказательстве их свойств в данной главе используется рекурсивный подход, аналогичный принятому подходу в пропозициональном исчислении (например, С.Клини, Ч.Чень–Р.Ли).
В разделе 4.1 исследуется LP-структура, логика которой расширена до набора связок пропозиционального языка. Отсюда происходит название – «LP-структура нулевого порядка». В качестве ее основы используется булева решетка. Изучены следующие основные вопросы: существование LP-замыкания, его архитектура, эквивалентные преобразования. Доказана теорема о существовании логической редукции произвольного отношения и описан процесс ее построения, один из этапов которого связан с нахождением транзитивной редукции отношения.
В разделе 4.2 определяются LP-структуры на полных булевых решетках. В данных алгебраических системах определены бесконечно-местные операции пересечения и объединения, которые для модели продукционной логики реализуют кванторы общности и существования. Как и в главе 3, переход к полным решеткам привел к необходимости введения дополнительного ограничения модели в виде свойства нетеровости.
Рассматриваются вопросы, связанные с существованием логического замыкания, его архитектурой, эквивалентными преобразованиями. Доказаны новые теоремы об архитектуре логического замыкания и о существовании логической редукции рассматриваемой LP-структуры. Полученные результаты полностью соответствуют разделу 4.1, однако относятся к нетеровым продукционно-логическим отношениям на полных булевых решетках.
Раздел 4.3 посвящен модели эквациональных LP-структур. Она возникает в качестве алгебраической интерпретации условной эквациональной теории и соответствующей условной системы переписывания термов. Определяется основанная на решетках модель условной эквациональной теории, учитывающая связи между термами, которые обусловлены применениями функций и подстановок. Исходная теория состоит из условных соотношений s1 = t1,..., sn = tn : u1 = v1,..., um = vm («если имеют место равенства термов si = ti, i = 1,..., n, то выполнены и все u j = v j, j = 1,..., m »). Такие соотношения называются (условными) эквациональными правилами. В предложенной модели условные эквациональные правила реализуются бинарным отношением R на решетке, порожденной множествами равенств {si = ti }.
В начале раздела приводятся связанные с термами базовые определения. Пусть S – алфавит, представляющий объединение непересекающихся множеств: V – множество переменных;
S n, n = 0,1,... – множества n -арных функций. Стандартным образом определяется множество термов T (S) (J.W. Klop). Отображение s : V ® T (S) называется подстановкой. Это понятие распространяется на все t T (S).
Эквациональной теорией называется пара (S, E ), где S – алфавит, состоящий из счетного множества переменных и непустого множества функциональных символов, а E T (S) T (S) – множество равенств вида s = t ( s, t T (S)). Для данного множества равенств E рассматривается множество конечных подмножеств l( E ). В нем заданы отношения включения,, а также «решеточные» операции I и U – теоретико множественные пересечение и объединение. Кроме них задаются еще две группы операций, связанных соответственно с функциями и подстановками термов:
1) если a = {si = ti | i = 1,..., n} и f Sn, то f (a) = { f (s1,..., sn ) = f (t1,..., tn )} ;
2) если a = {s j = t j | j = 1,..., m}, то s (a) {s ( s j )= s (t j ) | j = 1,..., m} для любой = подстановки s.
Определение 4.3.1. Пусть задана эквациональная теория (S, E ). Эквациональной решеткой называется решетка, полученная пополнением l( E ) относительно определенных выше операций 1)–2).
Как говорилось выше, в данной модели рассматривается условная эквациональная теория с правилами вида s1 = t1,..., sn = tn : u1 = v1,..., um = vm. Таким образом, предпосылка и заключение правила являются элементами эквациональной решетки.
По аналогии с известными работами (J.W.Klop), вводятся аксиомы и правила условной эквациональной дедукции. Аксиомы порождаются правилами вывода равенств: a : f (a ) для любых a = {s1 = t1,..., sn = tn } и f Sn ;
a : s (a) для любых a F и подстановки s. Такие условные правила можно назвать тавтологиями. Еще одной очевидной тавтологией является правило a : b, a, b F при a b.
Правила вывода в условной эквациональной логике таковы:
· a : b s (a) : s (b) (a, b F) для любой подстановки s (следуя J.W.Klop);
· a : b, a : c a : b U c (a, b, c ) F (возможность вывода по частям);
· a : b, b : c a : c (a, b, c ) F (транзитивность).
Далее вводится понятие продукционно-логического отношения, которое соответствует условной эквациональной логике. Во-первых, логическое отношение R должно содержать все тавтологии. Для тавтологий вводится общее обозначение: a µ b, если a b, b = s (a ) или b = f (a ). Таким образом, для логического отношения R справедливо µ R. Другие свойства логического отношения вытекают из правил дедукции. В частности, отношение R называется применимым, если для любой подстановки s из (a, b) R следует (s (a ), s (b)) R.
Бинарное отношение на эквациональной решетке называется продукционно логическим, если оно содержит тавтологии, а также является применимым, U дистрибутивным и транзитивным.
Кроме построенной модели, материалы раздела содержат исследование стандартного для настоящей диссертации круга вопросов: существование логического замыкания, возможности локально-эквивалентных преобразований, исследование архитектуры логического замыкания, существование и построение логической редукции бинарного отношения.
Применение рассмотренных выше моделей LP-структур ограничено системами с монотонным выводом, то есть таких систем продукционного типа, логический вывод в которых означает монотонное накопление знаний. Однако существуют системы, предполагающие не только накопление, но и модификацию знаний.
В главе 5 рассматриваются две задачи, исследование которых может быть осуществлено на основе LP-структур с немонотонным выводом.
Модель раздела 5.1 содержит семантику продукционно-логического вывода на иерархии типов в объектно-ориентированной системе с дополнительным отношением.
Анализируется стандартный набор свойств таких структур, а именно – замкнутость, эквивалентные преобразования, существование логической редукции. Показано, как изложенная теория может быть применена для верификации и автоматической оптимизации иерархий типов, в частности, при рефакторинге – модернизации устаревшего кода. Одним из важных направлений в этом плане является устранение дублирования кода «подъемом» общих атрибутов по иерархии типов. Такая задача решается автоматически при построении логической редукции LP-структуры.
Решение родственных задач методами FCA предлагается в статье R.Godin– P.Valtchev. В этой работе элементам множества классов требуется в определенном смысле оптимальным образом назначить наборы атрибутов – элементов другого независимого множества. В соответствии с выбранными назначениями формируется иерархия классов. В постановке раздела 5.1 атрибуты сами относятся к исследуемой иерархии классов (типов). Это обстоятельство усложняет решение задачи и вряд ли оставляет возможность применения FCA.
Рассматривается некоторая иерархия типов F в смысле ООП. Между парами типов могут существовать два вида связей – наследование (тип наследует атрибуты типа предка) и агрегация (тип содержит в качестве атрибута представителя другого типа).
На множестве F вводится отношение частичного порядка, а именно – если тип b является наследником a (соответственно a – предком b ), то b a. Для любых a, b F определены две операции: пересечение a b – наибольший общий потомок и объединение a b – наименьший общий предок a, b. Для ограниченности F добавляются два специальных элемента: I – универсальный тип (общий предок, имеется во многих современных системах) и O – фиктивный потомок всех типов.
На решетке F рассматривается второе (соответствующее агрегации) отношение R :
если объект типа a в качестве атрибута содержится в типе b, то (b, a ) R. Оба отношения ( и R ) имеют общую семантику. Она состоит в том, что в каждом из случаев, b a или (b, a ) R, тип b получает возможности типа a в виде доступа к его атрибутам. Это общее отношение ¬ обязано быть рефлексивным и транзитивным.
R Рассматривается еще одно свойство введенных отношений. Пусть для a, b1, b2 F справедливо b1 a, b2 a. Тогда в соответствии с определением решетки имеем b1 b2 a. Это естественное для отношения свойство называется дистрибутивностью.
Пусть теперь b1 ¬ a и b2 ¬ a, то есть каждый тип b1 и b2 обладает R R возможностями типа a. Тогда, если предположить -дистрибутивность отношения ¬, справедливо b1 b2 ¬ a. Этот факт означает, что тип b1 b2 также обладает R R возможностями a. С точки зрения проектирования типов это не обязательно. Однако в случае, если более одного наследника ( b1 и b2 ) содержат одинаковые атрибуты, по принципам рефакторинга нужно «поднять» общие атрибуты, то есть поместить один атрибут в общий тип-предок b1 b2. В результате каждый b1 и b2 получит возможности a в порядке наследования. В данном случае -дистрибутивность отношения ¬ R определяет решение одной из задач рефакторинга – устранение дублирования кода.
Отношение ¬, обладая свойством транзитивности вне зависимости от R контекста, не может аналогично во всех ситуациях удовлетворять дистрибутивности, иначе это приведет к некорректным результатам. Для иллюстрации можно привести пример b ¬ a и a ¬ a. При дистрибутивности ¬ R R R выполнялось бы b a ¬ a. По идеологии ООП тип b a не имеет права знать о R своих наследниках. По этой причине b a, являясь общим предком типов a и b, может обладать возможностями типа a лишь в случае, если он совпадает с a ( b a ).
В остальных вариантах соотношение b a ¬ a будет некорректным.
R Существуют ситуации, когда выполнение -дистрибутивности отношения ¬ R теоретически возможно, но нецелесообразно с точки зрения качества кода. Пусть при элементы b1 b b1 ¬ a, b2 ¬ a и имеют непустое пересечение:
R R a (b1 b2 ) a d O, причем d b1 b2 и d a. Если в данном случае допустить = (b1 b2, a) R, то окажется, что тип d обладает возможностями типа a одновременно по двум линиям, а именно – как его наследник и как наследник типа b1 b2, также имеющего возможности a. Другая подобная ситуация – наличие конфликта. Пусть имеет место (b1, a ), (b2, a ), (b3, a ) R, причем b1 b2 b2 b3. Тогда пары (b1, a ),(b2, a) «конфликтуют» с парами (b2, a), (b3, a ). Это означает, что если в обоих случаях «поднять» атрибуты, то тип b2 унаследует атрибут типа a от двух различных предков – b1 b2 и b2 b3, что также ухудшит код. Принятая в работе стратегия предполагает отказ от «поднятия» общих атрибутов при наличии подобных ситуаций (невыполнение -дистрибутивности). В дальнейшем возможны другие подходы, тоньше учитывающие особенности конкретной системы.
Из приведенных соображений дается определение логического отношения на ограниченной решетке. Логическое замыкание произвольного отношения R на решетке F предоставляет все такие пары (b, a ), что в типе b доступны возможности типа a. Логическая редукция строит иерархию с минимальным эквивалентным набором связей и в определенном смысле минимальным дублированием кода.
Формулируются определения и условия, связанные с ограничением свойства дистрибутивности продукционно-логических отношений. Пара (b, a ) элементов ограниченной решетки F называется простой, если a b = O – нижняя грань F.
Определение 5.1.1.1. Пусть R – отношение на ограниченной решетке F. Две пары вида (b1, a ), (b2, a ) R называются -совместимыми в R, если существуют такие c1, c2 F, что b1 b2 c1 c2, причем пара (c1 c2, a) простая, а пары (c1, a ), (c2, a ) R нетранзитивны в R U. При этом набор элементов C = (b1, b2, c1, c2, a) называется дистрибутивным кортежем, а T = (c1, c2, a) – -дистрибутивной тройкой (в R ).
Пусть имеются -дистрибутивная тройка T = (c1, c2, a), а также тройка T ' = (c1', c2, a ' ), ' проверяемая на аналогичное свойство. Тройку T будем называть нейтрализующей для T ' (обозначается T ' p T ), если выполнено одно из следующих условий:
1) a = a ', c1 c2 c1' c2 и справедливо хотя бы одно из неравенств ci' c1 c2 ;
' 2) a a ', c1 c2 c1' c2 и выполнено хотя бы одно из неравенств ci' c1 c2 ;
' 3) a a ', c1 c2 = c1' c2. ' С позиции неформальной эти условия описывают ситуации, когда присутствие нейтрализующей тройки T «угрожает» свойству -дистрибутивности тройки T '.
Тройка T ' = (c1', c2, a ' ) называется неконфликтной, если для нее не существует ни одной ' нейтрализующей -дистрибутивной тройки.
Понятия, введенные выше для троек вида T = (c1, c2, a) и T ' = (c1', c2, a ' ), ' автоматически распространяются и на связанные с ними кортежи C = (b1, b2, c1, c2, a) и C ' = (b1', b2, c1', c2, a ' ). Две -совместимые пары (b1, a ), (b2, a) называются неконфликтно ' ' -совместимыми, если для них существует неконфликтный -дистрибутивный кортеж (b1, b2, c1, c2, a ). Отношение R на решетке называется ограниченно дистрибутивным, если для любых неконфликтно -совместимых в R пар (b1, a ), (b2, a) справедливо (b1 b2, a) R.
Отношение называется продукционно-логическим с ограничением объединений, если оно содержит, транзитивно и ограниченно -дистрибутивно. Логическим замыканием отношения R называется наименьшее логическое отношение, содержащее R и его множество неконфликтно совместимых пар.
В новой модели рассматриваются стандартные для LP-структур вопросы:
существование логического замыкания, возможности локально-эквивалентных преобразований, архитектура логического замыкания, построение логической редукции бинарного отношения. Установлены аналогичные результаты, за одним исключением. Его суть в том, что в данной модели эквивалентное преобразование части исходного множества пар не всегда приводит к эквивалентному общему отношению. Однако имеет место эквивалентность ряда преобразований.
Теорема 5.1.3.2. Пусть R – отношение на ограниченной решетке F. Тогда каждая из следующих операций над R приводит к эквивалентному отношению:
· добавление или исключение пары (b, a ), если b a ;
· добавление пары (c1 c2, a), если тройка T = (c1, c2, a) -дистрибутивна и неконфликтна в R ;
· добавление или исключение пары при наличии пар (c, a ) (c, b), (b, a ) ( R U ), c b, b a.
Заключительный подраздел посвящен оценкам сложности построения логического замыкания и логической редукции LP-структур на решетках типов. Решетка типов обычно не является дистрибутивной, и число ее элементов не так велико по сравнению с другими моделями (например, булеаном или решеткой Линденбаума–Тарского). По этой причине в данном случае в качестве основы анализа сложности можно выбрать общее число элементов решетки, а также хранить саму решетку и бинарные отношения на ней в виде матриц смежности.
Теорема 5.1.5.1. Задачи нахождения логического замыкания и логической редукции LP-структуры на решетке типов решаются за полиномиальное время, не превышающее O ( N 6 ), где N – общее число элементов решетки.
Существуют области искусственного интеллекта, предполагающие не только накопление, но и модификацию получаемых знаний. В работе к ним добавлена еще одна – анализ свойств и преобразования императивных алгоритмов. Соответствующая LP-структура исследуется в п. 5.2. Как обобщение классических решеток определяются некоммутативные решетки. В некоммутативной решетке FX операция объединения U X выполняется с частичным замещением одного из операндов.
Операции на некоммутативной решетке формализуют как накопление, так и замещение знаний. Вводятся действующие на этих решетках продукционно логические отношения. Доказана теорема о существовании логического замыкания отношений на некоммутативных решетках.
В заключение рассматривается пример приложения теории некоммутативных LP структур к исследованию логических свойств императивных алгоритмов – сопоставляются возможности императивного и логического программирования.
r Логическая цепочка rAB = ( B1,..., Bm ) называется полной, если при добавлении к ней в любую позицию любого элемента Bm +1 FX, не совпадающего с соседними элементами, она перестает быть цепочкой, логически связывающей пару ( A, B).
r Логическая цепочка rAB называется терминальной, если она не может быть продолжена: не существует такого элемента C FX, что пара ( A, C ) логически связана r r R, C B и цепочка rAB содержится в начале цепочки rAC.
Определение 5.2.4.1. Логической программой на решетке FX называется тройка PR = ( F0, FRe s, R), где F0, FRe s – два фиксированных подмножества решетки FX, называемые соответственно множеством начальных элементов и множеством результатов, R – некоторое бинарное отношение на FX. Выполнением логической программы PR с данным начальным элементом A0 F0 называется нахождение совокупности всех таких максимальных элементов At FRe s, что пара ( A0, At ) логически связана полной терминальной цепочкой в R. Полученная совокупность элементов { At } называется результатами программы PR, соответствующими данному начальному элементу A0 (t T ). Если T состоит из единственного элемента, то результат логической программы называется однозначным.
Далее устанавливается связь логических программ с императивными алгоритмами.
Для этого рассматривается подкласс – детерминированные логические программы на FX = решетках. Логическая программа на называется PR ( F0, FRe s, R) детерминированной при данном AM FX, если для любого A0 F0 при начальном элементе A0 U X AM ее результат ARe s FRe s однозначен и достигается единственной (с точностью до порядка элементов в подцепочках) логической цепочкой в R.
Для таких программ можно выделить еще одно подмножество решетки FX – множество управляющих элементов FM, не пересекающееся с F0 и FRe s. Их роль состоит в обеспечении детерминированности действий. Таковым является указанный выше управляющий начальный элемент AM FM. В связи с этим обстоятельством для детерминированных программ также используется обозначение PR, M = ( FM, F0, FRe s, R).
Проводится формализация императивного алгоритма в терминах отношений на решетках. Она опирается на структурную теорему Дейкстры, согласно которой любой алгоритм может быть преобразован в эквивалентный, содержащий лишь действия, управляемые структурами трех видов: цепочкой, альтернативой и циклом while. В качестве (императивных) элементарных действий на некоммутативной решетке FX рассматриваются применения операции некоммутативного объединения. В частности, результатом действия над некоторым элементом A FX можно считать C = A U X B, где B FX.
Для выполнения императивной программы необходимы исходные данные – совокупность начальных элементов F0 решетки FX. При выполнении действий (операций U X ) начальный элемент A0 F0 последовательно трансформируется в некоторый новый. На заключительном этапе получается результат программы – результирующий элемент ARe s FRe s FX. Следуя изложенным соображениям, обозначим ACurr переменную со значениями текущего элемента, который имеется на некотором шаге после выполнения всех предыдущих операций программы. Таким образом, до выполнения программы ACurr = A0, после – ACurr = ARe s.
Далее необходимо формализовать понятия управляющих структур.
Императивной цепочкой длины m будем называть произвольный упорядоченный набор I = ( BC,..., BC ) элементов решетки FX. Индекс « C » означает возможную 1 m зависимость каждого элемента цепочки от текущего значения ACurr. Результатом последовательного применения императивной цепочки I = ( BC,..., BC ) к исходному 1 m значению ACurr назовем элемент ACurr U X BC U X... U X BC – новое значение ACurr.
1 m Для определения альтернативы и цикла необходимо понятие условия.
Предполагается, что вычисление логических выражений не вызывает побочных эффектов. В рассматриваемой модели условие эквивалентно принадлежности одного из заданных элементов решетки { ACond | t T } текущему элементу ACurr. Символами t { ACond | t T } обозначается набор элементов, соответствующих отрицанию условия с t элементами { ACond | t T }.
t Альтернативой называется выражение вида if { ACond } then BC else BC. Результат ее t 1 альтернативы – новое значение ACurr, вычисляемое по формуле ACurr U X BC, если при некотором t T справедливо ACond ACurr, и ACurr U X BC – в противном случае. Циклом t называется конструкция while { ACond } do BC. Ее выполнение заключается в t рекуррентном вычислении нового значения ACurr := ACurr U X BC, пока существует такое t T, что ACond ACurr.
t Введенные определения расширяются предположением о том, что управляющие конструкции могут быть вложенными. Этот факт означает, что в качестве их содержимого ( BC, BC,..., BC, BC ) могут фигурировать не только элементы решетки, но и, 1 2 m в свою очередь, другие цепочка, альтернатива или цикл. Для перечисленных конструкций используется общее название – императивная структура.
Определение 5.2.4.2. Императивной программой на некоммутативной решетке FX называется тройка PI = ( F0, FRe s, I ), где F0, FRe s – два фиксированных подмножества элементов решетки FX (множества начальных элементов и результатов), а I – любая императивная структура на FX. Выполнением императивной программы PI с данным начальным элементом A0 F0 называется применение конструкции I к элементу A0.
Получаемый после этого элемент ARe s FRe s называется результатом программы PI, соответствующим данному начальному A0.
Сравнивая представленные определения логических и императивных программ, нетрудно заметить, что каждый из этих видов программ по исходному элементу решетки вычисляет некоторый результирующий. Таким образом, правомерна постановка вопроса о сравнении их выразительных возможностей.
Теорема 5.2.4.1. Для любой императивной программы PI = ( F0, FRe s, I ) на решетке FX можно построить детерминированную логическую программу PR, M = ( FM, F0, FRe s, R), которая при любом начальном элементе A0 F0 и результате ARe s FRe s программы PI выдает для своего начального элемента вида A0 U X AM тот же результат ARe s, сохраняя при этом порядок и содержание действий PI.
Основная цель главы 6 – продемонстрировать возможность применения теории LP-структур на практике. Описывается созданная автором интегрированная среда разработки продукционных экспертных систем, а также анализируются реализация и применение LP-структуры для верификации и оптимизации созданных с ее помощью баз знаний.. В заключительной части главы демонстрируется применение теории LP структур для алгебраической формализации математических знаний.