Логический анализ систем на основе алгебраического подхода Кулик Борис Александрович

Содержание к диссертации

Введение

1 Обзор методов логического анализа 24

1.1 Логический анализ на основе силлогистики Аристотеля 24

1.2 Алгебра множеств и логика 30

1.3 Формальный подход в логическом анализе 36

1.4 Логический анализ в искусственном интеллекте 40

2 Алгебра множеств и теория отношений 48

2.1 Отношения в математике и информационных системах 48

2.1.1 Введение 48

2.1.2 Отношения в алгебраических системах 50

2.1.3 Бинарные отношения 52

2.1.4 Отношения в реляционной алгебре 53

2.1.5 Отношения в логике и искусственном интеллекте 54

2.2 Отношения и операции в алгебре множеств 55

2.3 Алгебра множеств и булева алгебра 69

2.4 Декартово произведение множеств 81

2.5 Алгебра кортежей и многоместные отношения 85

2.5.1 Основы алгебры кортежей 85

2.5.2 Операции с многоместными отношениями 93

2.6 Бинарные отношения, соответствия и отображения 97

2.7 Представление графов с помощью структур АК 102

3 Структуры: от полисиллогистики к нечеткой логике 106

3.1 Частично упорядоченные множества 106

3.2 Введение в gC-структуры 113

3.2.1 Определение и примеры 113

3.2.2 Вывод в gC-структурах 117

3.2.3 Основные закономерности )С-структур 123

3.2.4 Программное и алгоритмическое представление ?С-структур 126

3.2.5 Операции "сложения" и "умножения" в QC-структурах 129

3.3 Полисиллогистика через призму ^-структур 132

3.3.1 Суждения и рассуждения в ^-структурах 132

3.3.2 Анализ совместимости рассуждений 135

3.3.3 Проблема существования в ^-структурах 140

3.3.4 Сравнение силлогистики Аристотеля и ії-структур 143

3.3.5 Модифицируемые рассуждения 145

3.3.6 Абдуктивные заключения 151

3.3.7 Структуры и исчисление высказываний 155

3.3.8 Представление Е-структур в системах множеств и чисел 157

3.4 Структуры и нечеткие множества 164

4 Интерпретация и приложения алгебры кортежей 173

4.1 Интерпретация 173

4.1.1 Интерпретация алгебры кортежей 173

4.1.2 Логические исчисления и их интерпретация 176

4.1.3 Сравнение интерпретаций АК и логических исчислений 170

4.2 Сводка операций и соотношений в АК 181

4.2.1 Операции алгебры множеств 181

4.2.2 Преобразования АК-объектов в альтернативные классы 183

4.2.3 Ортогонализация 186

4.2.4 Кванторы в алгебре кортежей 191

4.3 Возможности использования АК в базах данных и интеллектуальных системах 197

4.3.1 Использование АК в дедуктивных базах данных 197

4.3.2 Использование АК в интеллектуальных системах 204

4.4 Логический вывод и анализ 212

4.4.1 Обзор методов логического вывода в математической логике 212

4.4.2 Логический вывод в АК 218

4.4.3 Модифицируемые рассуждения 224

4.5 Алгоритмы и методы сокращения перебора 231

4.5.1 Матричные свойства АК-объектов 231

4.5.2 Алгоритм проверки включения С-системы в С-систему 236

4.5.3 Алгоритм решения задачи выполнимость КНФ 238

4.5.4 Алгоритмы вычисления кванторных операций 243

4.5.5 Оценка вычислительной сложности алгоритмов 247

4.6 Метрические аспекты алгебры кортежей 248

4.6.1 Мера множеств 248

4.6.2 Представление в алгебре кортежей измеримых систем 253

4.6.3 Логико-вероятностные методы и алгебра кортежей 260

4.6.4 Вероятностная логика на основе АК 267

4.7 Использование естественного параллелизма структур АК 273

Заключение 278

Литература 279

• Логический анализ в искусственном интеллекте
• Декартово произведение множеств
• Модифицируемые рассуждения
• Преобразования АК-объектов в альтернативные классы

Введение к работе

Актуальность проблемы. В системном анализе часто возникает необходимость использовать логические методы для того, чтобы оценить логическую совместимость моделируемой системы, проверить корректность выводов и предположений, сформулировать и оценить возможные гипотезы и т.д. Логика лежит в основе системного анализа, так как многие известные специалисты по теории систем (Р.Акофф, Л. Берталанфи, Дж. Клир, М. Месарович, Н.Н. Моисеев, В.Н. Садовский, А.И. Уемов, Ю.А. Урманцев, Ю.А. Шрейдер и др.) тесно связывали с эту теорию с логикой и методологией науки. Методологические основания теории систем в основном рассматривают конструктивные определения и оценки взаимосвязи основных понятий системного анализа («система», «цель», «целостность», «элемент», «множество», «системные связи», «отношения», «вход-выход», «обратная связь» и т.д.) и их соответствие природным и создаваемым в процессе человеческой деятельности объектам. Однако на этом этапе используется лишь элементарная логика.

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

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

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

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

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

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

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

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

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

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

1) анализ и обобщение математических структур и программных средств, использующихся при формализации БД и БЗ;

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

3) разработка алгоритмической базы для логического и логико-вероятностного анализа систем;

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

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

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

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

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

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

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

1) определение основных структур алгебры кортежей;

2) нахождение соотношений между структурами алгебры кортежей и законами математической логики.

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

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

1) переименование атрибутов;

2) перестановка атрибутов;

3) добавление нового фиктивного атрибута (+Atr);

4) элиминация атрибута из АК-объекта {—Atr).

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

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

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

Гибкий универсум состоит из некоторой совокупности частных универсумов — декартовых произведений доменов для заданной последовательности атрибутов. Последовательность имен атрибутов, определяющих данный частный универсум, называется схемой отношения. АК-объекты, сформированные в одной и той же схеме отношения, называются однотипными.

Далее в разделах 2.5.2, 2.6, 2.7 показаны возможности алгебры кортежей при моделировании и анализе различных типов бинарных и многоместных отношений. Устанавливается, что операции с атрибутами позволяют сравнительно легко вычислять для отношений, представленных в структурах АК, операции соединения и композиции, которые часто используются как в информационных, так и в интеллектуальных системах.

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

Силлогистика Аристотеля на протяжении многих столетий была непревзойденным образцом анализа рассуждений. Заслуживает внимания многовековая история поиска математических оснований силлогистики. Трудами Г.В. Лейбница, Л. Эйлера, Ж.-Д. Жергонна, А. де Моргана, Д. Буля, Л. Кэрролла, Дж. Венна и др. бьши математические системы, в основе которых оказались законы созданной в процессе этих поисков алгебры множеств. Математическая логика в начале XX столетия развивалась самостоятельно как символическая логика. Связь между силлогистикой и математической логикой была найдена лишь в середине XX столетия Я. Лукасевичем, который предложил рассматривать силлогистику как одну из теорий математической логики, в которой используются только одноместные предикаты [83]. При этом оказалось, что классическая силлогистика может быть воспроизведена, если к аксиомам исчисления предикатов добавить некоторые «собственные» аксиомы. В силу этого некоторые правильные заключения силлогистики, которые выводимы из этой системы аксиом, не являются следствиями с точки зрения «чистого» исчисления предикатов.

В то же время до сих пор классический вариант описания силлогистики, который почти без изменений сохранился со времен Аристотеля, не ушел со сцены, поскольку по сравнению с открытыми в XIX и XX столетиях математическими основаниями он кажется более простым и доступным для усвоения. Анализ полисиллогистики на основе диаграмм Эйлера и Венна оказался весьма трудоемким и требовал для поиска заключений применения алгоритмов экспоненциальной сложности. Решение задач полисиллогистики с использованием предложенных Я. Лукасевичем, В.А. Смирновым и др. моделей с одноместными предикатами требует для своего усвоения хорошей математической подготовки и практически не пригоден для анализа без специальных компьютерных программ.

В 1996 г. автором был предложен новый вариант математического моделирования силлогистики на основе іі-структур [45, 48, 51, 54, 60]. Этот вариант оказался сравнительно простым и наглядным, в настоящее время используется в учебном процессе в Санкт-Петербургском Государственном Политехническом Университете и Санкт-Петербургском Государственном Университете Культуры и Искусств и, кроме того, обладает более широкими аналитическими возможностями по сравнению с предшествующими системами анализа. Эти новые возможности (анализ коллизий, поиск и проверка корректности гипотез, поиск абдуктивных заключений), как оказалось, можно при определенных условиях применить и в более широких, т.е. выходящих за рамки силлогистики, системах анализа рассуждений, предназначенных для логического анализа систем.

Новый подход к моделированию силлогистики основан на теории частично упорядоченных множеств (сокращенно у-множеств) [93, 104]. Примерами отношений частичного порядка являются отношение «меньше или равно» для чисел; отношение включения множеств; отношение делимости (т п, если т - делитель я); отношение доминирования для непрерывных функций на отрезке. С точки зрения общепринятой классификации у-множество является моделью, т.е. алгебраической системой без операций. Частными случаями являются у-множества с операциями. Наиболее известны в этом отношении решетки, т.е. у-множества с двумя операциями: inf (или л) - точная нижняя грань и sup (или v) - точная верхняя грань. В теории решеток есть термин дополнение, но здесь это не операция, а определенное свойство некоторых пар элементов решетки (элементы А и В являются взаимно дополнительными, если и только если соблюдаются два условия inf(,4, В) - наименьший элемент и s\xp(A, В) - наибольший элемент решетки). При таком определении дополнения существуют решетки, у которых некоторые элементы имеют два или более разных дополнений.

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

(і) для любого элемента у-множества А существует или может быть вычислен единственный элемент А, который называется квазидополнением А; (и) для любого элемента А соблюдается равенство А — А;

(ііі) для любых двух элементов А и В, связанных отношением А В, верна контрапозиция В А; (iv) для любого элемента А отношение А А допустимо лишь для случая, когда А = О

иА=1.

Системы, у которых соблюдаются свойства (і) — (ііі), но необязательно свойство (iv), называются QC-структурами (сокращение слова quasi-complement — квазидополнение). Подкласс gC-структур, в которых всегда выполняется свойство (iv), выделен как их частный случай и назван логической структурой Эйлера или сокращенно Е-структурой. В этом случае квазидополнение называется просто дополнением. Оно соответствует дополнению алгебры множеств, но не дополнению в решетках.

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

Основными структурными элементами этой системы логического анализа являются суждения двух видов:

1) общие суждения типа

Z,o - (1,1, La,..., L,„) и (1)

2) частные (или экзистенциальные) суждения типа

Wj - (Lji, Lj7,..., Ljm), (2)

где Ls, - базовые литералы (т.е. термины или их отрицания), содержащиеся в рассуждении, wr— неопределенные литералы, используемые для обозначения не предусмотренных изначально терминов в данном рассуждении (в естественном языке неопределенным литералам соответствует выражение типа «некоторые X»). Символом "-»" обозначается отношение частичного порядка, которое в -структурах изоморфно включению множеств. В левой части суждений (1) и (2) содержатся субъекты суждений, в правой — предикаты суждений. Частными случаями этих суждений являются известные типы суждений силлогистики Аристотеля:

1) А - В (всем А присуще В);

2) А - В (ни одному А не присуще В);

3) w\ - (А, В) (некоторым А присуще В);

4) м 2 — (А, В) (некоторым А не присуще В).

Если литералы представить как множества, то формуле (1) соответствует выражение L,o с (X,iO La n ... nZ,„), а формуле (2) - (Lnn La n ... nLin) 0.

Рассуждением в данной системе является произвольная совокупность суждений вида (1) или (2), называемых посылками рассуждения. Для анализа рассуждений используется два правила вывода, которые являются свойствами ОС-структур:

1) правило контрапозиции (если А- -В, то В - А) и

2) правило транзитивности (из суждений А— В и В- С следуете— С).

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

Задачу вывода всех возможных следствий можно легко решать вручную с помощью построения графов - в этом случае процесс решения задачи оказывается наглядным. В то же время этих правил недостаточно для того, чтобы получить некоторые заключения аристотелевой силлогистики - те самые, для получения которых в системе Я. Лукасевича введены дополнительные «собственные» аксиомы. В -структурах для получения таких заключений используется другой метод - с помощью вычисления верхних конусов литералов. Верхний конус литерала Lt (обозначается Lf) — это множество, содержащее L, и все литералы, являющиеся потомками Z,,. Тогда заключение строится как частное суждение, в правой части которого содержится некоторое подмножество литералов из Lf. Такие заключения не являются формальными следствиями, но оказываются вполне обоснованными при условии, что литерал, для которого построен верхний конус, соответствует непустому множеству.

Установлено, что введение дополнительных аксиом в систему логического вывода сужает аналитические возможности системы. Так, из аксиом Я. Лукасевича следует, что некоторые литералы системы не должны быть пустыми множествами. Но тогда в системе невозможно решать задачу существования объектов (т.е. проверять, являются ли эти объекты пустыми множествами), так как они изначально определены как непустые.

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

1) анализ логической совместимости рассуждения;

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

3) моделирование и анализ подтверждающих или опровергающих аргументов в полемике;

4) моделирование антитез;

5) поиск «скрытых аксиом» и абдуктивных заключений.

Рассмотрим методы анализа совместимости рассуждения. В математической логике сформулирован только один критерий противоречивости рассуждений: когда из посылок выводится некоторое следствие и его отрицание. В то же время и в повседневных, и в неформализованных научных рассуждениях одним из бесспорных критериев парадоксальности системы является вывод контрарных следствий (например, из посьшок следует, что «всем Л присуще В» и «всем А не присуще 5»). Тем не менее, формально эти два суждения не являются отрицаниями друг друга, поэтому определению противоречия в математической логике они не соответствуют. Чтобы устранить это несоответствие между формальной логикой и естественными рассуждениями, в систему анализа на основе -структур вводится понятие коллизия. Здесь определены два типа формальных коллизий: коллизия парадокса, когда одним из следствий посылок является суждение типа «всем А не присуще А», и коллизия цикла, когда из посылок следует, что различные литералы эквивалентны (интерпретацией этой коллизии является круг в обосновании или подмена тезиса).

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

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

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

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

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

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

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

Рассмотрим некоторые аспекты моделирования с помощью АК технических систем. Пусть задана система S с множеством возможных состояний Y- {t\, /2, —, tr}. Кроме того, в состав S входит некоторое множество V узлов или подсистем V = {V\, V2, ... , V„). В свою очередь каждому узлу Vt соответствует некоторое множество ХІ={С[, с 2, ... , с\ } его состояний, где kj — число состояний, в котором может находиться узел Vh а множества X, — произвольные множества. При этом Xt могут быть конечными или бесконечными множествами.

Точной моделью системы S является соответствие между всеми возможными наборами состояний всех узлов и состояниями системы. Каждому состоянию tj-eY системы соответствует некоторое множество элементарных кортежей из декартова произведения D =Х\хХ2Х ... хХп. Математически это соотношение можно отобразить как соответствие:

S:D- Y. (3)

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

Ограничение СГ. соответствие D— Y является однозначным (или функциональным) отображением. Это означает, что ни одному элементарному кортежу из D не может соответствовать более одного элемента из Y.

Ограничение С2: множество Y содержит ровно два элемента.

Ограничение СЗ: все атрибуты и множество Y являются двухэлементными множествами {0, 1}.

Используя эти ограничения, можно получить следующие системы.

1) Система, удовлетворяющая ограничениям С1 и С2, оказывается изоморфной некоторой модели многосортного исчисления предикатов; в этом случае заданные отношения на любой проекции пространства D интерпретируются как многоместные предикаты или логические формулы. В этой системе каждая формула рассматривается как отображение соответствующего ей частного универсума на множество {Т (true), F (false)} логических констант: если некоторый элементарный кортеж является элементом отношения, то он одновременно является выполняющей подстановкой соответствующей логической формулы и ему соответствует константа Т.

2) Если отказаться от ограничения С2, то получим систему с произвольным числом состояний, что означает переход к одному из вариантов многозначной логики. При этом в такой системе справедливы все законы алгебры множеств. Здесь можно рассматривать объединенное пространство DxY. Тогда множество элементарных кортежей этого пространства можно разделить на два непересекающихся множества: множество допустимых (true) и множество недопустимых (false) состояний, определяемых в соответствии с конструктивными или технологическими особенностями моделируемой системы. Тогда соответствие Sc:DxY- {T,F} окажется изоморфным модели многосортного исчисления предикатов, в которой отсутствуют ограничения на число состояний узлов и системы в целом.

3) Система с ограничениями С1 и СЗ соответствует модели исчисления высказываний.

Таким образом, можно утверждать, что с точки зрения интерпретации АК имеет более широкий класс применений, чем соответствующая система многосортного исчисления предикатов, которая образуется из модели (3) с использованием ограничений С1 и С2.

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

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

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

Алгоритмы ортогонализации АК-объектов используются в логико-вероятностном моделировании (ЛВМ) [100]. В ЛВМ ортогональной называется дизъюнкция вида FivF2V...vF„ такая, что для любых / j формула F,AFJ является тождественно ложной формулой. В этом случае, если известна вероятность каждой формулы Ft, то вероятность формулы F\vF2V...vF„ вычисляется как сумма вероятностей входящих в нее подформул.

В АК ортогональной является С-система, у которой пересечение каждой пары входящих в нее С-кортежей пусто. В теории логико-вероятностного моделирования разработаны методы ортогонализации только для формул исчисления высказываний, что соответствует структурам АК, у которых домены всех атрибутов являются двухэлементными множествами. В то же время в АК разработаны методы ортогонализации для АК-объектов, у которых домены атрибутов содержат произвольное число элементов, что соответствует формулам исчисления предикатов. Этот результат базируется на доказанных автором теоремах [39, 41, 42, 43, 58, 59, 62, 69].

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

В этой главе приведены результаты исследований по обобщению структур данных БД и БЗ с помощью структур АК.

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

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

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

Далее рассматривается представление в АК экспертных систем (ЭС). Базы знаний ЭС содержат модели и правила. Известно четыре типа моделей: логические модели, предикаты, семантические сети и фреймы. Выше было показано, что логические модели можно выразить в структурах АК. Рассмотрим другие модели.

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

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

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

Правіша в ЭС - это выражения типа «если В то G». Здесь В является телом правила и содержит некоторую логическую формулу (чаще всего в качестве такой формулы используется конъюнкция предикатов), a G — целью (или головой) правила и содержит предикат или значение некоторого предиката. При реализации базы знаний используются факты, являющиеся значениями некоторых предикатов, содержащихся в теле правила. При вводе фактов в базу знаний инициируется процедура поиска новых фактов. Эта процедура продолжается до тех пор, пока не будет установлено, что больше никаких новых фактов из этой базы знаний извлечь невозможно.

Во многих руководствах по ЭС в качестве примеров используется набор правил вывода, в которых атрибуты предикатов явно не указаны. Но если ввести в описание системы атрибуты, то оказывается, что ЭС - это система, которая во многом сходна с СУБД, а процедуры вывода на основе поступивших фактов аналогичны реализациям запросов в БД. Основным отличием является то, что в процедурах вывода ЭС используется больше аналитических средств, чем при реализации запросов СУБД. Но это как раз те аналитические средства логического вывода, которые отсутствуют в современных СУБД, но разработаны в АК.

В последние годы по мере усложнения прикладных ЭС стало ясно, что для их разработки явно недостаточно средств, которые используются в «интеллектуальных» языках программирования (Пролог, Лисп и др.). Поэтому разработчики вынуждены переходить на программирование ЭС с помощью языков высокого уровня, таких как С , Object Pascal, Perl и т.д., в которых используются и средства управления базами данных, и методы объектно-ориентированного программирования. Вызвано это необходимостью совмещения структур данных и знаний. Использование АК позволяет более просто решить эту проблему, так как в ней данные и знания органично выражаются в одних и тех же структурах и обеспечены соответствующими алгоритмами.

Далее рассматриваются алгоритмы поиска корректных гипотез и абдуктивных заключений. При реализации этих алгоритмов в структурах АК используются следующие отличительные особенности: 1) основными являются операции и отношения алгебры множеств, модифицированные в АК за счет использования операций добавления фиктивных атрибутов; 2) вводится новое понятие «коллизия».

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

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

1) «вырождение» знаний - знание оказывается тождественно ложным при вводе новых знаний (в АК эта ситуация распознается как равенство знания пустому множеству, в логике данная ситуация соответствует правилу Дунса Скотта «из лжи можно вывести все, что угодно»);

2) «вырождение» атрибутов (при вводе новых знаний из некоторых атрибутов исчезают элементы, которые по смыслу должны присутствовать в новом знании). Другими словами, при проверке оказывается, что некоторые значимые атрибуты или их значения оказываются равными пустому множеству;

3) при вводе новых знаний некоторые различные атрибуты становятся тождественными по составу элементов, что противоречит семантике системы и соответствует ситуации «порочного круга» в обосновании.

С учетом этих особенностей можно сформулировать простые алгоритмы логического анализа на структурах АК. Пусть К — не содержащая коллизий система аксиом или посылок. Если каждая посылка является АК-объектом, то К можно вычислить как АК-объект, равный пересечению этих АК-объектов с использованием правила обобщения, которое в АК

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

Проверка корректности вывода:

В соответствии с доказанными в диссертации теоремами А выводимо из К, если и только если К с А (в АК проверка вьшодимости соответствует проверке включения одного АК-объекта в другой).

Отличительный признак гипотез:

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

Проверка корректности гипотез:

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

Поиск абдуктивных заключений:

Пусть В - предполагаемое следствие из К, которое не удовлетворяет условию К В. Тогда АК-объект А является допустимым абдуктивным заключением, если соблюдаются два условия: 1) А является корректной гипотезой и 2) (Кг\А) с: В (т.е. при добавлении А в систему посылок предполагаемое следствие В становится выводимым). Классическим примером абдукции является открытие нейтрино. Предполагалось, что одним из результатов эксперимента, связанного с изучением бета-распада, является выполнение закона сохранения энергии. Расчеты показали, что при бета-распаде этот закон не выполнялся. Физик В. Паули в 1930 году предложил гипотезу о существовании некоторых «невидимых» частиц, принятие которой означало, что закон сохранения энергии не нарушается. В 1932 году Э. Ферми предложил назвать эту частицу «нейтрино». Экспериментально существование нейтрино (точнее, его двойника- антинейтрино) было подтверждено лишь в 1953 году.

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

Вероятностное моделирование в АК было разработано как продолжение и модернизация идей и методов логико-вероятностного моделирования (ЛВМ), развитых в трудах И.А. Рябинина и его учеников [100, 101]. Основные задачи, решаемые с помощью ЛВМ, — это вычисление вероятности отказа системы на основе заданных вероятностей отказа узлов системы и оценка влияния надежности отдельных узлов на надежность системы. Аналогичная постановка задачи решается и при оценке безопасности систем.

Рассмотрим, как решаются эти задачи с помощью АК. Основным структурообразующим понятием АК является С-кортеж. Если известны вероятностные меры компонент С-кортежа, то мера самого С-кортежа вычисляется как произведение мер его компонент. Если С-кортеж R = [А В С] задан в измеримых атрибутах, и меры его компонент равны соответственно (ЖА), pi(B) и //(С), то /4R) = /и(А) /л{В) • //(С).

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

Применение АК позволяет также решать обратную задачу логико-вероятностного моделирования, когда заданы оценки вероятности некоторых сложных событий, выраженных логическими формулами, и требуется оценить вероятность более простых событий, или событий, выраженных с помощью других логических формул. Такая постановка задачи содержится в рамках вероятностной логики, развитие которой было инициировано статьей известного специалиста по искусственному интеллекту Н. Нильсона [143]. В этой статье анализируется следующая задача: дана совокупность событий, заданных формулами A nAz B исчисления высказываний, при этом р(А) = р\ и р(А з В) - рг-Требуется оценить вероятность р(В) события В.

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

Метод решения этих задач заключается в следующем:

1) исходные формулы, для которых заданы вероятности, преобразуются в ортогональные С-системы;

2) вероятности компонент в этих формулах приобретают статус переменных;

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

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

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

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

Машинная реализация АК-объектов позволяет использовать три уровня параллелизма: 1) на уровне компонент; 2) на уровне строк и 3) на уровне матриц. На уровне компонент можно представить домены и их подмножества в виде совокупности логических векторов и для реализации операций алгебры множеств и проверок включения использовать логические операции с целыми векторами. На уровне строк можно одновременно осуществлять операции или проверки включения со всеми парами компонент С-кортежей или )-кортежей. На уровне матриц можно одновременно выполнять операции алгебры множеств и проверки включения для множества пар, элементами которых являются строки (С-кортежи или D-кортежи) из разных АК-объектов. Например, при вычислении пересечения С-системы с С-системой все используемые в этом алгоритме операции пересечения С-кортежей можно выполнять параллельно. Распараллеливание операций 2-го и 3-го уровней можно осуществить с помощью вычислительных комплексов параллельной обработки данных. Если для реализации алгоритмов логического анализа систем использовать многопроцессорные вычислительные комплексы, то в качестве единичных процессоров можно применять разработанные при участии автора вычислительные устройства, защищенные патентом и авторскими свидетельствами на изобретение [1, 2, 3, 40, 94].

Научная новизна диссертационной работы заключается в том, что впервые:

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

2) С позиций системного анализа разработан новый класс частично упорядоченных множеств (ОС-структуры), с помощью которого осуществляется детальный логический анализ систем следующих типов: 1) «объекты — свойства»; 2) системы подмножеств, заданные некоторыми соотношениями между некоторыми подмножествами; 3) системы рассуждений типа полисиллогистики; 4) системы нечетких множеств.

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

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

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

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

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

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

a) структуры данных и знаний представлены на основе общего теоретического подхода, хорошо согласованы с архитектурой современных компьютеров и совместимы по многим параметрам;

b) имеется возможность эффективного распараллеливания операций на программном и аппаратном уровнях;

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

3. В учебном процессе при изучении математических методов логического анализа систем и рассуждений.

Основные положения диссертации, выносимые на защиту.

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

2) Новый класс частично упорядоченных множеств (ОС-структуры), с помощью которого осуществляется детальный логический анализ систем следующих типов: 1) «объекты - свойства»; 2) системы подмножеств, заданные некоторыми соотношениями между некоторыми подмножествами; 3) системы рассуждений типа полисиллогистики; 4) системы нечетких множеств.

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

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

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

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

Реализация результатов. Результаты исследований нашли свое применение в работах по выполнению Программы Фундаментальных Исследований ОММПУ РАН «Динамика и устойчивость многокомпонентных машиностроительных систем с учетом техногенной безопасности» (2003-2006 гг.), по гранту РФФИ № 04-07-90064 «Методология частично упорядоченного моделирования и информационная технология нечеткой (возможностной) оценки риска уникальных систем» и в учебном процессе Санкт-Петербургского Государственного Университета Культуры и Искусств и Санкт-Петербургского государственного Технического Университета.

Апробация работы. Основные положения диссертации докладывались на следующих конференциях: Пятая национальная конференция по искусственному интеллекту (Казань, 1996); Международная конференция "Смирновские чтения" (Москва, 1997); V Общероссийская научная конференция «Современная логика: проблемы теории, истории и применения в науке» (Санкт-Петербург, 1998); Вторая международная конференция "Логико-лингвистическое управление динамическими объектами (DOLLC99), (Санкт-Петербург, 1999); Международная конференция «Интеллектуальное управление: новые интеллектуальные технологии в задачах управления (1С1Т 99)», (Переславль-Залесский, 1999); VI, VII, VIII, IX Общероссийские научные конференции «Современная логика: проблемы теории, истории и применения в науке» (Санкт-Петербург, 2000, 2002, 2004, 2006); Международная научно-практическая конференция «Проблемы преподавания логики и дисциплин логического цикла» (Киев, 2004); Международные научные школы "Моделирование и анализ безопасности и риска в сложных системах» (Санкт-Петербург, 2001, 2002, 2003, 2004, 2005, 2007); Идентификация систем и задачи управления -SICPRO 07 (Москва, 2007); Международная научная конференция «Философия математики: актуальные проблемы» (Москва, 2007).

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

Логический анализ в искусственном интеллекте

Традиционно считается, что искусственный интеллект берет свое начало от первых попыток осуществить машинное доказательство теорем. Пионерскими в этой области являются работы А.Ньюэла, Дж. Шоу и Х.Саймона [142], Ван Хао [148]. В качестве объектов исследования в этих работах использовались теоремы из классической работы Б.Рассела и А.Н.Уайтхеда [146]. Основными результатами, полученными в ходе этих исследований и оказавшими существенное влияние на последующее развитие систем искусственного интеллекта, были следующие:

а) формальные системы, основанные на исчислении высказываний или исчислении предикатов, представляются в виде набора правил типа «Если...то...», в основе которых лежит разработанная Г. Генценом [12] теория секвенционального исчисления;

б) основными синтаксическими структурами являются древовидные структуры, узлами которых являются слова некоторого алфавита — прототипами этих структур являются сформулированные в работе А.Черча основы лямбда-исчисления.

В ходе многочисленных исследований в дальнейшем эти результаты стали основой для создания универсальных языков программирования систем искусственного интеллекта - Пролога, разработанного в 1972 г. А.Кольмрауэром [126], и ЛИСПа, основные принципы которого были сформулированы Дж.Маккарти [141] в 1958 г. Символьные преобразования положены также в основу разработанного В.Ф. Турчиным [114] языка Рефал, предназначенного для решения задач функционального программирования. Стоит отметить, что в основе этого языка лежит математическая теория нормальных алгоритмов, разработанная А.А.Марковым [85].

Уже на первых этапах разработки систем ИИ начали появляться задачи, которые даже при небольшом числе исходных данных были практически нереализуемыми из-за громадного объема требуемых вычислительных операций. Возникла проблема классификации задач по степени сложности. Первые результаты в этом направлении были получены Г.С. Цейтиным в конце 50-х годов [122], но по ряду причин не стали широко известными. Исходным пунктом дальнейших исследований по теории сложности вычислений стала работы М.О.Рабина [144], Ю.Хартманиса и Р.Е.Стирнза [131], в которых достаточно четко обозначилась постановка проблемы. Интенсивное развитие этой теории началось после опубликования в 1971 и 1972 гг. двух статей С.А.Кука [127] и Р.М.Карпа [132].

Кратко результат работы С.А.Кука заключается в следующем. В основу теории NP-полноты положен класс задач NP (Nondeterministically Polynomial), для которых проверка правильности решения, если оно каким-то образом получено, занимает полиномиальное время от длины предложения, содержащего условие задачи. Класс NP состоит из задач распознавания, т.е. в задач, в которых возможны только два варианта ответа ("да» или «нет») и содержит не только задачи, которые решаются за время, выраженное полиномом фиксированной степени от длины входного предложения задачи, но и задачи, для которых полиномиальный алгоритм решения в общем случае неизвестен. В своей статье С.А.Кук доказал, что любую задачу класса NP можно при использовании рациональной системы кодирования представить в виде некоторой КНФ (конъюнктивной нормальной формы), при этом преобразование условий любой задачи класса NP в КНФ занимает полиномиальное время. Таким образом, основной NP-полной задачей, стала считаться задача проверки выполнимости заданной КНФ (сокращенно SAT), решением которой является ответ на вопрос: «Существует ли в заданной КНФ хотя бы одна выполняющая подстановка?». Эта задача может быть преобразована из задачи распознавания в переборную задачу, если при положительном ответе на первый вопрос может быть найдена хотя бы одна выполняющая подстановка для заданной КНФ.

Теперь, чтобы доказать, что некоторая задача Т относится к классу NP-полных задач, необходимо: 1) доказать ее принадлежность классу NP; 2) выбрать известную NP-полную задачу и доказать, что эта задача может быть за полиномиальное время преобразована в Т. В работе С.А.Кука было также доказано, что к классу NP-полных задач помимо SAT относятся еще две задачи класса NP. Р.М.Карп в своей статье дополнил этот список еще 20-ю широко известными задачами.

Аналогичные результаты независимо и немного позднее были получены в СССР Л.А.Левиным [76], который ввел класс универсальных переборных задач. Этот класс аналогичен классу NP-полных задач и, по мнению С.А.Кука [78], является более сильным понятием. Однако интерпретация Л.А.Левина осталась незамеченной. В последующее десятилетие усилиями многочисленных исследователей класс NP-полных задач расширился до нескольких тысяч [18], а к известным классам сложности добавились новые классы [ПО]. Было установлено, что значительная часть прикладных систем, в которых применяются методы искусственного интеллекта, содержит задачи, относящиеся к классу NP-полных. В связи с этим были обозначены следующие основные пути преодоления «проклятия размерности»:

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

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

3) использование нейросетевых систем.

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

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

В основе логических моделей баз знаний лежит исчисление предикатов первого порядка. Вопросы в таких системах ставятся в виде некоторых утверждений (или гипотез), для которых необходимо доказать выполнимость или доказать, что данное утверждение выводимо из исходных данных системы. Важной вехой на пути развития логических моделей стало открытие принципа резолюции Дж.Робинсоном [145]. В дальнейшем этот метод практически во всех реализациях логических моделей стал основным методом доказательства.

Декартово произведение множеств

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

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

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

Пусть задана некоторая совокупность необязательно различных множеств X, Y, ..., Z, общее число которых равно п. Тогда декартовым произведением этих множеств является совокупность всех возможных л-местных элементарных кортежей, у которых на первом месте стоит элемент множества X, на втором — элемент множества Y, ..., а на последнем 82 элемент множества Z. Декартово произведение множестве, Y, ..., Zобозначается какХхУх ... xZ. Декартово произведение для » одинаковых множеств X обозначается как X". Для совокупности множеств, обозначенных одинаковыми символами, отличающимися только индексами (например, S,, S2,..., Sn), используется символ многократного произведения П, в этом случае декартово произведение 5, х S2 х...х Sn можно обозначить как Y\ S,

Рассмотрим несколько примеров декартовых произведений.

1) Для двух множеств X = {а, Ь}, Y = {Ь, с) декартово произведение XxY = {{а, Ь), {а, с), (Ь, b), (Ь, с)}. Здесь упорядоченные пары элементов декартова произведения заключены в круглые скобки, чтобы отличить их от обычных множеств, у которых порядок расположения элементов произвольный.

2) Исходные множества могут быть заданы интервалами, в этом случае декартовым произведением является область, ограниченная соответствующим прямоугольником на координатной плоскости. Например, на рисунке 2.6 затемненный прямоугольник вместе со своими границами является изображением декартова произведения отрезков АВ и CD, находящихся на разных координатных осях. Элементами декартова произведения в этом случае являются координаты всех точек, расположенных в пределах этого прямоугольника.

3) Возможны более сложные структуры, формируемые с помощью декартова произведения (рис. 2.7 и 2.8). На рисунке 2.7 структура из 4-х затемненных прямоугольников является изображением декартова произведения множеств интервалов {АВ, CD}x{EF, GH).

Рис. 2.7. Декартово произведение множеств отрезков На рисунке 2.8 совокупность отрезков на координатной плоскости, обозначенных жирными линиями, является изображением декартова произведения множества {АВ, CD) отрезков одной координатной оси на множество {F, G, Н} точек другой оси. Аналогичные структуры можно строить и в пространствах произвольных размерностей.

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

Обозначим \Х\ — количество элементов или мощность множества X. Тогда количество всех элементов декартова произведения будет в точности равно произведению мощностей всех используемых в этом произведении множеств, т.е. \XXYX...XZ\ = \X\-\Y\- ... -z. (2.7)

Рассмотрим основные свойства декартовых произведений [9]. Подробные сведения об этих свойствах и об их практическом применении содержатся также в [88]. Пусть X, и Y, (і = 1, 2, 3, ..., п) - совокупность некоторых множеств. Обозначим символом " = " отношение "равносильно" (или "тогда и только тогда", "если и только если"). Также в формальных выражениях этих свойств будем использовать логические символы "v" (или) и "Л" (и). Первое свойство устанавливает условия равенства декартова произведения пустому множеству. f\X, = 0 = ( =0)4 =0)v...v(JSr„ = 0). (2.8) На естественном языке это означает, что равенство декартова произведения пустому множеству равносильно тому, что по крайней мере одно из множеств X, равно пустому множеству. Рассмотрим свойство, позволяющее проверять отношение включения между различными декартовыми произведениями. f[Y, cf[X, = (ГусІ;) л (Y2czX2) л...л (F„cl„) (2.9) ;=I /=1 Данное соотношение позволяет проверить включение одного декартова произведения в другое, не "разворачивая" эти произведения в множества элементарных кортежей. Например, пусть заданы следующие множества:

Модифицируемые рассуждения

Одним из поводов для критики классической логики считается то, что она якобы не приспособлена для анализа модифицируемых рассуждений, т.е. рассуждений у которых по ходу дискуссии меняются исходные посылки, появляются новые доводы и контраргументы. В известной книге французских авторов [82] описывается разные неклассические логики (логика умолчаний, немонотонная, эпистемическая и модальная логики), которые, как считают многие специалисты, предназначены для решения этой проблемы. В основном в [82] даются формальные аспекты этих логик, а в качестве «естественной» иллюстрации для некоторых из них приводится следующее правдоподобное рассуждение: «Большинство птиц могут летать. Тити — птица. Следовательно, Тити может летать». Если это рассуждение дополнить некоторыми новыми посылками, например, «Тити — страус» или «Тити — пингвин», то заключение «Тити может летать» окажется ложным. В этом рассуждении истинность или ложность следствия зависит от значения новой добавленной посылки, в результате чего по мнению авторов книги [82] нарушается свойственная классической логике монотонность вывода.

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

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

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

В математической логике единственным критерием несовместимости является противоречие, т.е. ситуация, когда из одних и тех же посылок выводится некоторое предложение S и вместе с этим — его отрицание —iS. Но ни одна из рассмотренных ранее коллизий в -структурах не является противоречием в этом смысле. Например, коллизия парадокса фиксируется, когда следствиями исходных посылок являются два суждения А-ьВ и А— В. В естественной логике при определенных условиях такая ситуация является признаком несовместимости рассуждения. Но в математической логике такая ситуация не относится к противоречиям. Отсюда ясно, что модифицируемые рассуждения необходимо рассматривать не только через призму формальных критериев несовместимости, но и в ракурсе «естественных» коллизий.

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

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

Определение 3.9. Антитезой рассуждения, заданного is-структурой G, является суждение, которое при добавлении его к G инициирует коллизию парадокса.

Простейшим примером антитезы является отношение «больше» применительно к «меньше». Ясно, что формальным отрицанием отношения «меньше» является отношение «больше или равно». И хотя отношение «больше» не является отрицанием «меньше», тем не менее применительно к каким-либо фиксированным объектам оно несовместимо с ним. Многие антонимы в естественном языке, такие как «молодой — старый», «красивый — безобразный», с точки зрения математической логики также не являются отрицаниями друг друга и относятся к классу антитез. Если же речь идет о суждениях, то контрарные и контрадикторные суждения являются антитезами исходных, хотя с точки зрения математической логики они не являются их отрицаниями.

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

(В - А ) являются контрапозициями ранее построенных антитез.

Для произвольной корректной -структуры антитезой к ней является антитеза к любому суждению, содержащемуся в СГ-замыкании этой структуры. В частности, антитезами к рассуждению из примера 3.7 (см. рисунок 3.17) являются суждения D-+A и

C D, так как они являются антитезами к суждениям —» А и С—» D, содержащимся в СГ-замыкании этой -структуры.

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

Преобразования АК-объектов в альтернативные классы

Доказательство. Каждый D-кортеж эквивалентен С-системе, содержащей п С-кортежей, каждый из которых состоит из всех полных компонент, за исключением qt. Следовательно, учитывая, что С-система является объединением С-кортежей, для того чтобы соблюдалось РсО, необходимо, чтобы соблюдалось /?, cz qt по крайней мере для одного /. Действительно, если один из С-кортежей Qi преобразованного в С-систему 2)-кортежа Q равен [ ... qt... ] и pt cz qh тоРс Qt и, следовательно, Р eg. Докажем достаточность. Предположим, что условие pi cz qt не соблюдается для всех / . Докажем, что в таком случае РсО невозможно. Из предположения следует, что для каждого і существует г І = p,\qi = 0. Отсюда ясно, что для всех / выполняется г, с: р, и г, eg,. Из этого следует, что существует непустой С-кортеж R = [г[ Ґ2 ... г„], такой что RczP и R с: Q, из чего, в свою очередь, следует невозможность Р с 2- Конец доказательства. П14. Для С-кортежа (или D-кортежа) Р и D-системы О справедливо Р сО, если и только если для каждого D-кортежа Oj из О выполняется Р cz Oj. Доказательство. Утверждение является следствием того, что )-система является пересечением множеств элементарных кортежей, содержащихся в D-кортежах, входящих в ее состав. Поскольку Р включено в каждый D-кортеж, то оно включено и в их пересечение и, следовательно, в 2)-систему. Конец доказательства.

Следующие два утверждения в силу их тривиальности приводятся без доказательства. П15. Для С-системы Р и D-системы О справедливо Р CLQ, если и только если каждый С-кортеж из Р включен в каждый D-кортеж из Q.

Проверка эквивалентности АК-объектов Ш б. Два АК-объекта Р uQ эквивалентны, если выполняется как РC.Q, так и Q cz Р.

Приведенные выше операции и алгоритмы проверки включения определены не для всех возможных сочетаний классов АК-объектов. В частности, не приведены алгоритмы выполнения бинарных операций алгебры множеств для случаев, когда операнды относятся к альтернативным классам (например, пересечение )-системы и С-системы). Кроме того, пока то не предусмотрены алгоритмы проверки включения АК-объектов Р czQ, когда Р — D-система или Q - С-система. Эти алгоритмы в отличие от приведенных выше более сложны, поскольку для их реализации часто требуется преобразование одного из АК-объектов в альтернативный класс. Эти алгоритмы в общем случае является не полиномиальными по вычислительной сложности. Ниже будут рассмотрены методы уменьшения трудоемкости их выполнения.

Каждый С-кортеж (D-кортеж) Р преобразуется в эквивалентную ему D-систему (С-систему), в которой каждая нефиктивная компонента р\, соответствующая атрибуту Xt исходного кортежа, представлена D-кортеэюем (С-кортежем), состоящим из компоненты pt в атрибуте Xt и фиктивных компонент во всех остальных атрибутах. Доказательство. Утверждение относительно преобразования D-кортежа в С-систему непосредственно следует из определения D-кортежа, который является сокращенной записью соответствующей С-системы. Алгоритм преобразования С-кортежа в эквивалентную ему D-систему является следствием свойства двойственности альтернативных классов. Конец доказательства. Например, D-кортеж ]А 0 В С[, где А, В, С - непустые компоненты, преобразуется в

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

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

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

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