Введение к работе
Актуальность проблемы. В составе информационных технологий одно из ведущих мест занимают системы со сложными интеллектуальными задачами (СИЗ), в которые ;ходят многие системы, основанные на логических соотношениях, системы расчетов надежности и безопасности структурно-сложных комплексов на основе логико-вероятностных методов и ряд практических приложений систем искусственного интеллекта. Растет интерес к СИЗ, интенсивно расширяется область их применения. Содержание СИЗ охватывает не только проблемы, связанные с информатизаиией общества, но и проблемы, связанные с когнитивными процессами и структурсй мышления. Однако бурное развитие СИЗ в последние десягилетия сопровождается рядом возрастающих трудностей при решении некоторых проблем, что дает основание для предположений о наступлении кризисной ситуации в методологии СИЗ. К этим трудностям, в частности, относятся:
трудности, связанные с математической формулировкой задач и с поискам^ эффективных алгоритмов решений во многих случаях, ког^а требуется оценивать не только полноту или выполнимость, но и значения параметров СИЗ, удовлетворяющих заданным ограничениям;
неэффективность декларативных средств отображения и обработки информации (систем на базе языков Лисп и Пролог, оболочек экспертных систем и т.д.) при решении прикладных задач в базах знаний с большим объемом данных и правил;
отсутствие достаточно надежных и простых методов обоснования полноты и непротиворечивости даже в сравнительно простых СИЗ;
несовместимость структур данных и математических методов обработки и анализа знаний в комбинированных СИЗ, объединяющих логические, продукционные, сетевые и реляционные модели представления знаний, и отсутствие единого теоретического обоснования для этих моделей.
Последствиями такой кризисной ситуации является чрезмерное усложнение программно-аппаратных средств - это приводит к тому, что в самих системах программно-аппаратной поддержки СИЗ из-за несовместимости структур данных и методов их обработки возникают многие специфические трудноразрешимые, а порой и неразрешимые проблемы. Поэтому актуальной является задача преодоления этих трудностей путем разработки математического аппарата для представления и анализа прикладных СИЗ, достаточно простого, чтобы более ясно формулировать и ре-
шать проблемы непротиворечивости и полноты конкретных логических моделей и быть основой для разработки эффективных алгоритмов, но в то же время достаточно универсального, чтобы стать общей теоретической основой для моделей СИЗ, которые в настоящее время представлены как принципиально различные. Настоящая работа посвящена разработке этого аппарата и обоснованию на его основе методов уменьшения трудоемкости алгоритмов решения СИЗ, используемых в практических приложениях логических исчислений.
Попытка преодолеть ряд трудностей, возникающих в практических приложениях баз знаний, предпринята в работах автора. Используемый в этих работах подход, названный алгеброй кортежей (Tuple Algebra ТА), является процедурно-ориентированным вариантом алгебраических систем (в смысле А.И. Мальцева). В основе этого подхода лежат соотношения алгебры множеств, под которой подразумевается алгебраическая
система с множеством операций { и, п, - } и множеством соотношений
{^ . S . =}
Цель работы. Разработка методов уменьшения трудоемкости вычислительных алгоритмов решения для спожных в вычислительном отношении задач, возникающих при разработке и эксплуатации прикладных логических систем, на основе исследований выразительных и алгоритмических возможностей математических систем, основанных на соотношениях алгебры множеств.
Методы исследования. В основу проведенных исследований положены методы алгебры множеств, математической логики, теории алгебраических систем, теории меры и теории конечных графов.
Научная новизна. В диссертационной работе получены следующие новые научные результаты:
разработаны теоретические основы алгебры кортежей, являющейся процедурно ориентированным вариантом алгебраических систем, доказан изоморфизм алгебры кортежей и алгебры множеств;
обоснована достаточность выразительных средств алгебры кортежей для отображения всех выразительных средств теории моделей (в рамках исчисления предикатов);
разработаны более эффективные по сравнению с существующими методы проверки полноты и непротиворечивости логических систем, преобразуемых в структуры алгебры кортежей;
разработаны новые методы уменьшения трудоемкости алгоритмов решения задач, которым соответствуют некоторые классы NP-полных задач переборного тип з в исчислении высказываний и предикатов;
определены основные соотношения, связывающие структуры алгебры кортежей и соответствующие им логические формулы и модели с системами, погруженными в метрические пространства, в частности, с вероятностными системами;
на основе соотношений алгебры множеств построена математическая модель системы логического вывода из произвольной совокупности простых суждений, которая является расширением силлогистики Аристотеля и может быть также использована для моделирования нетривиальных вариантов импликативных и паранепротиворечивых логик (эта система в силу ее независимости от математического аппарата алгебры кортежей вынесена в приложение).
Практическая ценность и внедрение результатов работы. Результаты исследований в настоящее время используются при разработке автоматизированных систем управления борьбой за живучесть надводных кораблей (АСУ БЖ), а также в системах расчетов надежности и безопасности сложных технических систем управления надводными кораблями. Начаты работы, связанные с использованием методов расчета, основанных на соотношениях алгебры кортежей, в системах, функционирующих в условиях риска.
Апробация работы. Основные положения работы докладывались на Международной конференции по проблемам моделирования в бионике "Биомод-92" (Санкт-Петербург, 1992) и на Национальной конференции с международным участием по искусственному интеллекту "Искусственный интеллект-94" (Рыбинск, 1994).
Публикации. Основные результаты диссертации отражены в 8 публикациях и защищены 3-мя авторскими свидетельствами СССР и патентом Российской Федерации.
Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и приложения, содержит 108 страниц машинописного основного текста и 18 страниц приложения, 5 рисунков, 1 таблицу и списка литературы из 84 наименований.
