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

Российская Академия наук ~ г - р дИнститут проблем управления

2 2 ДПР 19%

КУЛИК Борис Александрович

МЕТОДЫ УМЕНЬШЕНИЯ ТРУДОЕМКОСТИ РЕШЕНИЯ СЛОЖНЫХ ИНТЕЛЛЕКТУАЛЬНЫХ ЗАДАЧ НА ОСНОВЕ АЛГЕБРЫ КОРТЕЖЕЙ

Специальность 05.13.11. Математическое и программное обеспечение вычислительных машин, комплексов, систем

и сетей

АВТОРЕФЕРАТ

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

Москва 1996

Работа выполнена в НПО "Аврора" (Санкт-Петербург)

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

О.П. Кузнецов

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

профессор В.Н. Вагин

кандидат технических наук Л.И. Микулич

Ведущая организация: Военно-морская академия

им. адмирала Н.Г. Кузнецова

Защита состоится " /3" ^1996 г. в /^ час на заседании Специализированного совета N 2 (Д002.68.01) Института проблем управления по адресу: 117806, г. Москва, Профсоюзная,65

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

9

Автореферат разослан " " Л^елЛ 1996 г.

Ученый секретарь Специализированного совета

к.т.н.

1Е.В. Юркевич!

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

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

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

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

- отсутствие достаточно надежных и простых методов обоснования полноты и непротиворечивости даже в сравнительно простых СИЗ;

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

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

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

Попытка преодолеть ряд трудностей, возникающих в практических приложениях баз знаний, предпринята в работах автора. Используемый в этих работах подход, названный алгеброй кортежей (Tuple Algebra - ТА), является процедурно-ориентированным вариантом алгебраических систем (в смысле А.И. Мальцева). В основе этого подхода лежат соотношения алгебры множеств, под которой подразумевается алгебраическая система с множеством операций { и, п, - } и множеством соотношений , G , =}•

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

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

Научная новизна. В диссертационной работе получены следующие новые научные результаты:

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

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

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

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

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

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

Практическая ценность и внедрение результатов работы. Результаты исследований в настоящее время используются при разработке автоматизированных систем управления борьбой за живучесть надводных кораблей (АСУ БЖ), а также в системах расчетов надежности и безопасности сложных технических систем управления надводными кораблями. Начаты работы, связанные с использованием методов расчета, основанных на соотношениях алгебры кортежей, в системах, функционирующих в условиях риска.

Апробация работы. Основные положения работы докладывались на Международной конференции по проблемам моделирования в бионике "Биомод-92" (Санкт-Петербург, 1992) и на Национальной конференции с международным участием по искусственному интеллекту "Искусственный интеллект-94" (Рыбинск, 1994).

Публикации. Основные результаты диссертации отражены в 8 публикациях и защищены 3-мя авторскими свидетельствами СССР и патентом Российской Федерации.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и приложения, содержит 108 страниц машинописного основного текста и 18 страниц приложения, 5 рисунков, 1 таблицу и списка литературы из 84 наименований.

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

Во введении дается обоснование актуальности темы и краткое содержание диссертации.

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

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

В современных теоретических обоснованиях теории логических моделей и теории логического вывода практически отсутствуют попытки использовать в качестве теоретической базы соотношения алгебры множеств. Это направление исследований интенсивно развивалось до конца XIX века и связано с такими известными именами как Г.В. Лейбниц, Л. Эйлер, Ж.Д. Жергонн, А. де Морган, Дж. Буль, Э. Шредер, П.С. Порец-кий, Э.В. Хантингтон, Е.Л Буницкий, Дж. Венн и др.

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

Современные попытки вернуться к этому направлению можно найти в работах А.Н. Колмогорова, А.И. Мальцева, В.М. Глушкова, однако подробная систематизация этого направления и попытки найти содержательную связь между современными подходами к обоснованию некоторых соотношений логики на основе алгебры множеств и результатами, полученными до начала нашего века, в современной литературе встречаются редко. Одним из немногих исключений является книга Д.А. Поспелова "Моделирование рассужденийопубликованная в 1987 г. Еще одним из примеров такого рода являются некоторые работы научной школы логико-вероятностных методов (ЛВМ) и логико-вероятностного моделирования (ЛВМОД), возглавляемой И.А. Рябининым, современное развитие которой инициировано работами русского логика П.С. Порецкого (1846-1907).

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

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

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

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

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

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

s

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

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

j F = P(x)&Q(y)&...&R(z). (1)

Если P,Q.....R - множества выполняющих подстановок соответствующих

■ предикатов, то декартово произведение PxQx... xR в точности равно i множеству выполняющих подстановок формулы F. Чтобы отобразить, !

" используя декартово произведение, дизъюнкцию тех же предикатов, не- | обходимо ввести множества X,Y,...,Z областей значений соответствую- '

■ щих переменных х,у.....z и некоторый универсум Ut =XxYx... xZ. Тогда

j множество S(G) выполняющих подстановок формулы

4 i

G = Р(х) vQ(y) v.., vR(z), (2) I

1 i если воспользоваться соотношением де Моргана

; Р(х) vQ(у) v... vR(z) = -,(-,Р(х)& -iQ(y)&...& -^R(z)),

будет равно множеству выполняющих подстановок

: S(G) = U \(PxQx...xR), (3)

; где P.Q.....R равны соответственно X\P,Y\Q.....Z\R. Этот же результат

можно получить, не используя операцию разности множеств:

\ S(G) = (PxYx...xZ)у (XxQx...xZ) v... V (XxYx...xR). (4)

8 С учетом этих и некоторых других соотношений было решено ис-

< следовать алгебраическую систему, названную алгеброй корте-

] жей(ТА), основными структурами которой являются кортежи произволь-

] ных подмножеств некоторых основных множеств (эти основные множе-

' ства названы координатами) и в которой в качестве операций и соотно-1 шений используются основные операции и соотношения алгебры мно-

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

числении предикатов можно сопоставить классы эквивалентных координат ТА.

В ТА используются три типа кортежей и два типа матричных структур. Рассмотрим вначале типы кортежей.

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

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

Третий тип - D-кортеж, который, как и С-кортеж, является n-кой подмножеств координат, но его интерпретацией является n-местное отношение, которое можно рассматривать как множество выполняющих подстановок дизъюнкции типа (2) и которое может быть развернуто с использованием соотношений (3) или (4).

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

Важным понятием ТА является схема отношения, содержащая имя . TA-объекта и последовательность координат, в пространстве которых он задан. Схема отношения соответствует формальному обозначению многоместного предиката. Например, предикат P(x,y,z) в ТА интерпретируется как ТА-объекг Р, заданный в координатах X,Y,Z. Если последовательность координат в схемах отношений двух TA-объектов совпадает, то они являются однотипными, в противном случае - разно-

ю

типными. Чтобы осуществлять операции и сравнения с разнотипными ТА-объектами, вводятся две фиктивные компоненты: * - множество, эквивалентное соответствующей координате и 0 - пустое множество.

Компонента * может быть вставлена в любой С-кортеж при условии, • что соответствующая ей координата не содержится в его схеме отноше-; ния, а компонента 0 - в любой D-кортеж при тех же условиях. В случае, когда ТА-объект содержит не менее двух кортежей, то все фиктивные компоненты в одном столбце должны соответствовать одной и той же ко-i ординате. Если принять к сведению, что компонента * и универсум соответствуют в исчислении предикатов константе True, а компонента 0 и пустой кортеж - константе False, то можно доказать, что любую пару ТА-объектов с помощью добавления фиктивных компонент и перестановки координат можно привести к однотипным схемам отношения, сохраняя при этом логическую эквивалентность (при этом эквивалентность са-; мих отношений при таких преобразованиях в общем случае не сохраня-; ется).

( Если в С-кортеже или в С-системе удалить некоторое множество координат, то полученный ТА-объект в точности равен проекции исходного | TA-объекта на оставшееся множество координат при условии, что в мат: рице исходного TA-объекта в удаляемых координатах не содержалось '» компонент, эквивалентных 0. При наличии таких компонент соответст-: вующие С-кортежи можно безболезненно удалить, так как они эквива-! лентны пустому кортежу. Отсюда навешивание квантора существования (3) на любой TA-объе т класса С- сводится к удалению соответствующей координаты, при условии, что в ней не содержатся пустые компоненты TA-объекта, а навешивание того же квантора на любой ТА-объекг сводится к вычислению его проекции. Навешивание квантора всеобщ-j , ности (V) легко осуществляется на ТА-объектах класса D- и сводится к Г : удалению соответствующей координаты, при условии, что в ней не со-1 - держатся компоненты, эквивалентные этой координате (в противном слу-| чае соответствующий D-кортеж равен универсуму и может быть удален 5 j из D-системы). В произвольном случае навешивание квантора V сводит-j ' ' ся к вычислению дополнения проекции дополнения исходного ТА-| ; объекта.

| ' В диссертации построена аксиоматика ТА - к аксиомам алгебры мно-] жеств добавлены три аксиомы:

] AS: система подмножеств (компонент) для любой координаты яв

j, ляется алгеброй множеств;

| •■ АСР: ДП множеств, среди которых имеется хотя бы одно nycroi

j • множество, является пустым (аксиома пустого ДП);

« I i -,

AFU\ все частные универсумы ТА принадлежат одному и тому же классу эквивалентности (аксиома гибкого универсума).

Смысл AFU заключается в том, что для любого частного универсума Ut системы ТА, равного ДП некоторой последовательности координат, в исчислении предикатов можно соотнести произвольную общезначимую формулу, в которой состав переменных соответствует составу координат частного универсума Ut. Другими словами, класс всех частных универсумов произвольной системы ТА в данной аксиоме отождествляется с классом всех общезначимых формул соответствующей модели исчисления предикатов. Класс всех частных универсумов в системе ТА назван гибким универсумом (FU - flexible universe).

На основе этих аксиом сформулировано и доказано более 20 теорем, которые являются основным инструментарием ТА. В исчислении высказываний и исчислении предикатов этим теоремам соответствует множество часто (или весьма редко) используемых известных соотношений. На основе этих теорем получены эффективные методы преобразования произвольных ТА-объектов в эквивалентные ТА-объекты альтернативного класса, а также установлено:

1) все операции и сравнения с ТА-объектами сводятся к алгоритмам, в которых реализуются последовательности операций или сравнений над множествами, являющимися компонентами этих ТА-объектов;

2) любая модель, построенная как система ТА-объектов, изоморфна некоторой алгебре множеств; при этом изоморфизм сохраняется и в тех случаях, когда некоторые координаты являются многомерными дискретными, непрерывными или дискретно-непрерывными пространствами;

3) в произвольной системе ТА-объектов, представляющей какую-либо логическую модель, реализуются все выразительные средства теории моделей на базе исчисления предикатов;

4) все логические аксиомы и правила вывода исчисления высказываний и исчисления предикатов выводимы из аксиом ТА.

Решение логических уравнений, например, типа F = G сводится в ТА к изоморфному преобразованию формул F и G в ТА- объекты S(F ) и S(G ) с однотипными схемами отношения и к вычислению ТА-объекта класса С-, равного пересечению S(F) n S(G).

Полнота и непротиворечивость произвольных систем ТА следует из изоморфизма этих систем алгебре множеств. Однако в систему ТА могут преобразовываться логические системы, у которых некоторые альтернативные формулы F и ~F формируются независимо. Тогда при преобразовании этих формул в ТА-объекты S(F) и S(~F) возможны ситуации, ко-

[ гда: 1) Э(Р) г> Б(~Р) * 0 и 2) Б(Р) и Э(~Р) * I). Ситуация 1 соответствует противоречию - в этом случае предположение о взаимной дополнительности Р и ~Р не подтверждается и исходные логические соотношения ; должны быть откорректированы. Ситуация 2 соответствует неполноте | альтернативных формул. В этом случае возможна не только коррекги-| ровка, но допускается возможность определить множество и\(8(Р)иЗ(~Р)) как промежуточное (переходное) множество, если в моделируемой систе-I ме такая ситуация имеет смысл (например, переходное состояние ме>кду " нормальным и аварийными состояниями).

В третьей главе раса ¡атриваются основанные на соотношениях ; ТА методы уменьшения трудоемкости решения переборных задач, кото; рые часто возникают при моделировании и поиске решений в логических | системах. В теории сложности вычислений эти задачи относятся к классу ЫР-полных задач, но в ТА эти задачи могут быть сформулированы не : только как задачи распознавания (т.е. задачи, у которых возможны только ] два варианта ответа - "да" или "нет"), но и как задачи перебора, когда ] при ответе на вопрос в случае позитивного решения выводится некоторое 1 (в некоторых случаях исчерпывающее) множество выполняющих под-\ становок.

| Специфичные для ТА методы уменьшения трудоемкости алгоритмов 1 обусловлены следующими тремя ее особенностями:

1) Увеличение регулярности структур по сравнению с изоморфными структурами исчисления высказываний и исчисления предикатов за счет матричного представления ТА-объектов. Матричное представление позволяет не -только выбирать более экономичные структуры данных, но и ; использовать при сокращения перебора некоторые соотношения, кото-I ; • рые специфичны для некоторых регулярных алгебр, в частности, для алгебры полуколец.

I . ■ 2) Использование в качестве основных операций в алгоритмах операций и сравнений алгебры множеств. Эта особенность позволяет при про-|граммно-аппаратной реализации логических систем использовать в каче-I | стве основных структур данных логические вектора, которые при реали-] зации операций и сравнений характеризуются максимальным быстродей-! ; ствием, во многих случаях занимают наименьший объем оперативной I ; памяти и позволяют легко реализовать естественный параллелизм опе-] ; раций и сравнений.

• 3) Изоморфизм совокупностей ТА-объектов в структурах ТА алгебре

'{ ■ ; множеств. Это позволяет для решения одной и той же задачи в зависимо] 1 сти от структурных особенностей ее составляющих выбирать наименее ]/;, трудоемкий метод из множества возможных методов. Рассмотрим слу-| { чай, когда в логической системе некоторая формула задана как имплика-

1Ъ

ция двух логических формул Р -» в и необходимо проверить ее общезначимость. Пусть в ТА формулам Р и в соответствуют ТА-объекты Б(Р) и 3(С). Тогда решение задачи может быть сведено к проверке правильности одного из следующих соотношений: _

1)8£)сЗ(С); 2)8£)п8(6) = 0;

3) Э(Р) и Б (С) = и; 4) Б(С) с Б (Я).

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

В данной главе выведенные в ТА методы сокращения перебора применены в алгоритмах решения трех переборных задач, часто встречающихся в приложениях: 1) проверка включения С-сисгемы в С-систему, 2) проверка фиктивности координаты и 3) элиминация квантора, навешенного на ТА-объект, в нетривиальных случая;: (случай является нетривиальным, когда квантор 3 навешивается на 0-систему, или квантор V - на С-систему). Первая задача соответствует ЫР-полной задаче проверки общезначимости импликации ? -> в для случая, когда бескванторные формулы Я и С относятся к одному типу (ДНФ или КНФ). Первые две задачи также используются при минимизации логических формул. Третья задача в настоящее время используется в системах логического вывода, важным и весьма сложным промежуточным этапом которого является элиминация кванторов в выводимой формуле.

Здесь же рассматриваются теоретические основы и методы оценки вычислительной сложности алгоритмов для структур ТА.

В четвертой главе рассматриваются методы и соотношения, связанные с задачей погружения структур ТА в измеримые системы, когда для каждой координаты ТА-объекга выбрана мера ц, такая, что для любых подмножеств § и Б* этой координаты соблюдается соотношение

цф и Эк) = ц(в|) + и^к) - ц(в, п Эк). (5)

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

потому, что меры фиктивных компонент ц(*) и ц(0) для любой координаты равны соответственно 1 и 0, а мера любого универсума равна 1. В этом случае добавление фиктивной координаты в произвольный ТА-объег" или удаление из него фиктивной координаты не приводит к изменению значения меры этого. ТА-объекта.

Погружение любого ТА-объекта в измеримое пространство и расчет его меры основаны на том, что мера любого С-кортежа Я? равна произведению мер его компонент (это следует из свойств ДП), т.е.

где I - множество индексов компонент б, вектора И.

С помощью конечного числа операций алгебры множеств можно любой ТА-объект с конечным числом компонент преобразовать в С-кортежили в ортогональную конечную С-систему, у которой пересечение любой пары С-кортежей пусто. Из (5) и (6) следует, что мера ортогональной С-системы Т может быть вычислена с помощью соотношения:

где I - множество индексов строк, к - множество индексов столбцов матрицы ортогональной С-системы Т, а - компоненты Т.

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

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

(6)

(7)

/е/ кеК

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

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

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

В пятой главе рассмотрено использование разработзнных методов для решения практических задач. Методы и алгоритмы алгебры кортежей используются при разработке программно-аппаратных средств, предназначенных для комплексной системы управления борьбой за живучесть кораблей (КСУ БЖ). Сложность этой системы обусловлена тем, что в ней используются большие структуры данных и знаний трех разнородных типов: 1) реляционные базы данных, 2) сетевые структуры, отображающие системы энергоснабжения и коммуникаций, а также системы причинно-следственных связей между событиями и 3) множества правил типа продукций. Совмещение этих структур при машинной реализации с помощью традиционных программно-аппаратных средств само по себе представляет довольно сложную задачу, но основная проблема заключается в необходимости быстрого решения текущих задач, связанных с классификацией возникающих на корабле аварийных ситуаций и поиском решений, позволяющих избежать больших потерь при их появлении. Кроме того, необходимо учитывать, что состояние корабельных систем в нештатных ситуациях быстро изменяется во времени, а информация о них из-за повреждений или отказов каналов связи часто бывает неполной или недостоверной.

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

пешной работы данной системы управления. Использование алгебры кортежей в качестве методологической основы для решения этих проблем позволяет в перспективе значительно сократить ресурсы времени ! и памяти, требуемые для решегия аналогичных задач при использовании | " традиционных методов. Это положение было проверено при разработ- ' ке ряда программных продуктов, позволяющих производить сложные расчеты вероятности сложных систем, состояние которых может быть | описано с помощью формул исчисления высказываний. Проверка этих \ программных продуктов с участием ведущих специалистов по логико- | вероятностным методам расчета надежности и безопасности структурно- I сложных систем показала, что данные программы при решении аналогичных задач выигрывают по сравнению с существующими по ресурсам времени и памяти и, кроме того, позволяют существенно расширить | класс подлежащих обработке задач. [

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

В приложении рассмотрена модель рассуждений, построенная ; на основе соотношений алгебры множеств. Пусть в качестве исходных ! данных в рассуждении используются посылки типа Б*", соответствующие жергонновым отношениям при моделировании силлогизмов. Это означает, что $ и Бк являются подмножествами некоторого множества Ц, | принятого за универсум, а соотношение Б, Б« означает ^ с Б*. Напри-■ мер, суэедение "все А есть В" в жергонновых отношениях соответствует | предложению "А с В", а суждение "некоторые А не есть В" в жергон- ! новыхотношениях можно представить как два предложения: "а с А" и ; " ВТ. где а - некоторое непустое множество, а В.- дополнение В в некотором частном универсуме. , ■ Посылки типа "А -> В " необязательно должны интерпретироваться | как соотношения включения меэду множествами. В рассматриваемой мо- 1 дели рассунодения это соотношение можно также интерпретировать как условное предложение "если А то В ", но оно считается истинным только в том случае, когда В является необходимым условием А или же А является достаточным условием В . Примеры: "если число делится на 6, то оно делится на 3", "если на аварийном корабле обесточены все насосные станции, то система водоотлива не работает".

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

1) правило транзитивности: из истинных посылок А -> В и В С выводится предложение А С ;

2) правило инверсии (или ортообращения): из истинности посылки А -» В выводится предложение"! -> А .

Оба эти правила являются законами алгебры множеств. Кроме того, правило инверсии соответствует формулировке известного математического соотношения о равносильности прямой теоремы и теоремы, противоположной обратной. Применение этих двух правил позволяет построить за полиномиальное время множество всех следствий. Если при этом получено хотя бы одно соотношение типа \Л/ -» (-.Щ, то система исходных посылок является противоречивой.

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

Для данной модели рассуждений обоснованы следующие результаты: 1) модель рассуждения является расширением силлогистики Аристотеля; 2) обе задачи решаются с помощью алгоритмов полиномиальной сложности.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

J.0

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

ПУБЛИКАЦИИ

1. КуликБ.А., Рахов Э.В. Программное обеспечение некоторых классов нечисловых задач на основе матричного представления. - Программирование, 1988, No 2, с.26-31.

2. Кулик Б.А. Быстродействующие ИПС на основе, операций с логическими векторами. -УСиМ, 1989, No 4, с. 14 -19.

3. Кулик Б.А. Особенности реализации систем искусственного интеллекта на биассоциативной машине. - Информационное обеспечение научных исследований. П.: Из-во БАН СССР, 1990, с. 115-128.

4. Кулик Б.А. Использование алгебры кортежей для решения задач искусственного интеллекта //Судостроительная промышленность, Сер. Автоматика и телемеханика. 1992. Вып.14, с.3-16.

5 .Кулик Б.А. Система логического программирования на основе алгебры кортежей. - Известия РАН. Техн. кибернетика, 1993 , No 3, с. 226239.

6. Кулик Б.А. Математическая модель дедуктивной базы данных на основе алгебры кортежей. - Известия РАН. Техн. кибернетика, 1994, No 2, с. 161-169.

7. Кулик Б.А. Новые классы КНФ с полиномиально распознаваемым свойством выполнимости. - Автоматика и телемеханика, 1995, No 2. с.111-124.

8. Кулик Б.А. Логико-вероятностные методы и алгебра кортежей //Теория и информационная технология моделирования безопасности сложных систем. Вып.5. Под ред. И.А. Рябинина и Е.Д. Соложенцева. Препринт 123. СПб., 1995, Ин-т Проблем Машиноведения РАН. С.18-43.

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