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

Санкт-Петербургский государственный университет

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

Кулик Борис Александрович

ЛОГИЧЕСКИЙ АНАЛИЗ СИСТЕМ НА ОСНОВЕ АЛГЕБРАИЧЕСКОГО ПОДХОДА

Специальность 05 13 01 - Системный анализ, управление и обработка информации (по прикладной математике и процессам управления)

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

Санкт-Петербург 2008

Работа выполнена в Институте проблем машиноведения Российской академии наук (ИПМаш РАН)

Официальные оппоненты.

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

Братчиков Игорь Леонидович (Санкт-Петербургский

государственный университет),

Доктор технических наук, почетный профессор Военно-Морской Академии им Н Г Кузнецова Рябинин Игорь Алексеевич

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

Флегонтов Александр-Владимирович (Российский гоеударсхвенный педагогический-университет им А И Герцена). •

Ведущаяорганизация

Санкт-Петербургский государственный политехнический университет

Защита состоится 21 мая 2008 г в 12-00 часов на заседании диссертационного совета Д 212 232 50 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу Санкт-Петербург, 199034, В О, Университетская наб 7/9, Менделеевский центр

С диссертацией можно ознакомиться в библиотеке им М Горького Санкт-Петербургского государственного университета

Автореферат разослан я. 2008 г

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

Г-

Курбатова Г И

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) Новая методология логического анализа систем на основе обобщенного теоретического подхода, в котором структуры и модели данных

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

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

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

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

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

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

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

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

Апробация работы Основные положения диссертации докладывались на следующих конференциях Пятая национальная конференция по искусственному интеллекту (Казань, 1996), Международная конференция "Смирновские чтения" (Москва, 1997), V Общероссийская научная конференция «Современная логика проблемы теории, истории и применения в науке» (Санкт-Петербург, 1998), Вторая международная конференция "Логико-лингвистическое управление динамическими объектами

(DOLLC'99), (Санкт-Петербург, 1999), Международная конференция «Интеллектуальное управление новые интеллектуальные технологии в задачах управления (ICIT'99)», (Переславль-Залесский, 1999), VI, VII, VIII, IX Общероссийские научные конференции «Современная логика проблемы теории, истории и применения в науке» (Санкт-Петербург, 2000, 2002, 2004,

2006), Международная научно-практическая конференция «Проблемы преподавания логики и дисциплин логического цикла» (Киев, 2004), Международные научные школы "Моделирование и анализ безопасности и риска в сложных системах» (Санкт-Петербург, 2001, 2002, 2003, 2004, 2005,

2007), VI международная конференция «Идентификация систем и задачи управления» - SICPRO'07 (Москва, 2007), Международная научная конференция «Философия математики актуальные проблемы» (Москва, 2007)

Публикации По теме диссертационной работы опубликовано 42 работы, в том девять статей в журналах, рекомендованных ВАК РФ, две монографии, три авторских свидетельства на изобретение, один патент на изобретение

Структура и объем работы Диссертация состоит из введения, четырех глав, заключения, библиографического списка и содержит 287 страниц текста, в том числе 48 рисунков и 19 таблиц

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

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

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

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

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

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

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

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

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

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

Рассмотрим эти результаты

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

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

множеств Кроме того, в состав операций АК добавлены четыре операции с атрибутами

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

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

3) добавление нового фиктивного атрибута (+А1г),

4) элиминация атрибута из АК-объекта (-А(г)

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

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

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

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

Имена АК-объектов содержат собственно имя, а в некоторых случаях к имени добавляется заключенная в прямые скобки последовательность имен атрибутов, определяющих схему отношения, в которой задан этот АК-объект Например, ЩХУ7\ означает, что АК-объект Я задан в схеме отношения \ХТ2\

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

Например, если задан элементарный кортеж Т[ХУ1] = (я, Ь, с), то подразумевается, что аеХ, ЬеУн се2

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

С-кортеж представляет собой множество элементарных кортежей - это множество можно вычислить как декартово произведение компонент С-кортежа Для изображения С-кортежей используются прямые скобки Например, ЩХУ7\ = [А В С], означает, что ЛсХ, ВсУ, Сс2 и Я[ХЩ = АхВхС

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

С-система представляет собой множество элементарных кортежей Это множество равно объединению множеств элементарных кортежей, содержащихся в соответствующих С-кортежах Например, С-систему

ахщ =

в2 с2

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

<2\ХЩ = (Л,х£|хС,)и (А2хВгхС2)

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

В АК-объектах содержатся фиктивные компоненты Они бывают двух видов Одна из них - полная компонента - используется в С-кортежах и обозначается "*" Значением этой фиктивной компоненты является домен соответствующего атрибута Другую фиктивную компоненту "0" - пустое множество, которая используется в 1)-кортежах, рассмотрим позднее Здесь и далее в качестве примеров будем рассматривать АК-объекты, заданные в пространстве Б = Ху.¥х2, где Х= {а, Ъ, с, с/}, У- {/, g, И), 2= {а, Ъ, с) Тогда справедливы равенства

ЯАХЩ = [* {/, И) {а, Ь}] = [{а, Ь, с, <И} {/, к) Я Ь}], ОЛХЩ = [{Ь, * {а, Ь}] = [{Ъ, {/; к) {а, 6}]

Ясно, что любая совокупность однотипных АК-объектов является алгеброй множеств Операции и проверки включения или равенства между этим АК-объектами реализуются на основании теорем 1 - 6 Пусть заданы однотипные С-кортежи Р = [Р\ Р2 Р„] и <2 = [С?1 <2«] Теорема 1.Рглд= [Р|ПО, Р2п02 Р„ п £?„] Примеры {{Ь, {/, /7} {а, Ь}] п [ * [/, {а, с}] = {{Ъ, <*} {/} {а}], [{6, с1) {/, /7} {а,Ь}]п[* {а, с}] = [{6, 0 {а}] = 0 Теорема 2 Рс.0, ест и топько если Р,с Q¡ для всех /=1,2, , и Теорема 3 Р и <2 с [Р\^~>0\ Рг^йг Рп и причем равенство возможно лишь в двух случаях (1) РсО или ОсР,

(и) Р, = <2, для всех соответствующих пар компонент за исключением одной пары Заметим, что в алгебре кортежей в соответствии с Определением 4 во

Г Р Р Р

г, ^1 I 2 Гп

всех случаях справедливо равенство Р и С =

Теорема 4. Пересечение двух однотипных С-систем равно С-системе, содержащей все непустые пересечения каждого С-кортежа первой С-системы с каждым С-кортежем второй С-системы

Теорема 5. Объединение двух однотипных С-систем равно С-системе, содержащей все С-кортежи операндов

В некоторых случаях после вычисления объединения С-систем можно сократить общее число кортежей в полученной С-системе, если использовать условия (1) или (п) в Теореме 3

Чтобы выразить алгоритмы вычисления дополнений АК-объектов, необходимо еще одно определение

Определение 5 Для любой компоненты Р/ АК-объекта ее дополнение (Р}) определяется как дополнение относительно домена соответствующего ей атрибута

Теорема 6. Для произвольного С-кортежа Р = [Р\ Р^ Р„]

Р =

С-системы размерности пхп, у которых все компоненты, не принадлежащие главной диагонали, равны "*", будем называть диагональными

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

{а,с} * * Г= * * =]{й;С} {с}[

* * {с}

Такое представление диагональной С-системы образует новую структуру АК, которая называется О-кортежем

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

Дополнение С-кортежа можно прямо записывать как й-кортеж Например, если Т\ = [{¿, с?} * {а, Ь}], то Г, = ]{а, с} 0 {с}[ В £)-кортежах константа "0" - фиктивная компонента При преобразовании £>-кортежа с фиктивными компонентами в диагональную С-систему строки, соответствующие фиктивным компонентам, оказываются пустыми и поэтому могут быть удалены из этой С-системы Например,

7i = ]{a,c} 0 {c}[ =

{а,с}

0

{с}

{а,с)

И

F-

Термины "С-кортеж" и "¿»-кортеж" выбраны не случайно в простейшем случае С-кортеж соответствует конъюнкции, а D-кортеж - дизъюнкции одноместных предикатов с разными переменными Используя ¿»-кортежи, можно сформировать еще одну (пятую) структуру АК - ¿»-систему

Определение 7 D-система - структура, состоящая из множества однотипных ¿»-кортежей и равная пересечению множеств элементарных кортежей, содержащихся в этих ¿»-кортежах

Изображение ¿»-системы аналогично изображению С-системы, только вместо обычных прямых скобок используются перевернутые

Теорема 7 Дополнением С-систечы является D-система той Dice размерности, в которой каждая компонента равна дополнению соответствующей компоненты в исходной С-системе Например, дополнение С-системы \{a,b,d) {/,/1} {b}

FIXYZ] = v ' lJ 1 11 L {b,c} * {a,c}J

заданной в пространстве S, можно вычислить как D-систему

~X\{a,b,d} Y\{f,h) Z\{6}|" = 1{с} {g} {а,с) X\{b,c} Y\* Z\{a,c}[ \{a,d) 0 {b}

Нетрудно видеть, что соотношения между С-объектами (С-кортежи и С-системы) и D-объектами (D-кортежи и D-системы) соответствуют законам двойственности де Моргана В силу этого они названы альтернативными классами

Чтобы обеспечить полноту операций алгебры множеств для произвольной совокупности однотипных АК-объектов, разработаны алгоритмы преобразования ZJ-кортежей и ¿»-систем в эквивалентные им С-системы В частности, одним из методов преобразования D-системы в С-систему является следующий алгоритм Алгоритм преобразования D-системы в С-систему

1) преобразовать каждый D-кортеж ¿»-системы в С-систему,

2) используя теорему 4, вычислить пересечение всех полученных С-систем

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

G[XZ] =

G,[XYZ]=+Y(G[XZ]) =

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

Добавление фиктивного атрибута осуществляется только в том случае, если добавляемый атрибут отсутствует в схеме отношения АК-объекта При этом в С-кортежи и в С-системы в соответствующие столбцы добавляется фиктивные компоненты "*", а в D-кортежи и D-cистемы - фиктивные компоненты "0"

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

Если в С-кортеж или в С-систему вводится фиктивный атрибут, то эта процедура соответствует известному в исчислении предикатов правилу вывода, которое называется правилом обобщения Например, если АК-объект

{а,с} * _{a,c,d) {b,c} j

соответствует формуле F(x, z) исчисления предикатов, то, добавив в этот АК-объект фиктивный атрибут Y, получим АК-объект

{а,с] * *

{a,c,d} * {b,c}_

который соответствует формуле \/yF(,х, z), полученной из формулы F(x, z) по правилу обобщения Для С-кортежей и С-систем это соответствие очевидно, для D-кортежей и £>-систем это соответствие (с учетом того, что в них фиктивной компонентой является "0") устанавливается с помощью следующей теоремы

Теорема 8. Добавление нового фиктивного атрибута в D-кортеж или в D-систему соответствует правы чу обобщения

Элиминация атрибута осуществляется так из АК-объекта удаляется столбец, а из его схемы отношения - соответствующий атрибут Однако в отличие от предыдущей операции логический смысл этой операции зависит от того, к какому классу объектов она применяется Семантика операции -Atr в терминах математической логики устанавливается на основе теорем 9 и 10

Теорема 9. Пусть X ] - С-система, у которой отсутствуют С-кортежи с пустыми компонентами в атрибуте X Тогда для соответствующего этой С-системе предиката Р{ , х, ) формула -X(R) соответствует формуле 3х{Р)

Теорема 10. Пусть X ] - D-система, у которой отсутствуют D-кортежп с компонентами «*» в атрибуте X Тогда для

соответствующего этой D-системе предиката Р{ , х, ) формула -X(R) соответствует формуле \/х(Р)

В базах данных операции «+А/г» и «-Atr» применяются, в частности, при вычислении соединения и композиции двух разнотипных отношений, заданных АК-объектами В общем случае можно выполнять операции соединения и композиции отношений для любых пар АК-объектов, у которых различаются схемы отношений Пусть заданы две структуры R\[V) и R2{W\ При этом V и W являются множествами атрибутов и V ^ W Эти множества можно разложить на непересекающиеся подмножества X, Y, Z, используя следующие операции

Х= ИЛУ, Y— Wr\V, Z = WW Тогда получим V= YuZ и W = XuY С учетом этого данные отношения можно переписать так R\[YZ\ и R2[XY]

Операция соединения Ri[YZ] ® R2[XY\ отношений в реляционной алгебре выполняется с помощью попарного сравнения всех элементарных кортежей из разных отношений Если при сравнении этих кортежей окажется, что в проекции [F] они совпадают, то в этом случае из двух кортежей формируется кортеж со схемой отношения [XYZ], и этот кортеж становится одним из элементов соединения отношений Например, имеются два элементарных кортежа Т^е R\ и Т2<= R2, при этом

Г,[У2] = (с, d, e,f, g), T2[XY] = (a, b, c, d, e), где T2[X] = {a, b), r,[Z] = {f, g), h[Y\ = T2[Y] = (c, d, e)

В этом случае результатом композиции этих кортежей является элементарный кортеж r3[XyZ] = (а, Ь, с, d, e,f, g)

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

R,[YZ] © R2[XY] = +X(R0 n +Z(R2) = n VZ(R2) (1)

Операция композиции Rt[YZ]°R2[XY] отношений вычисляется после вычисления соединения отношений Для этого требуется из каждого элементарного кортежа, принадлежащего соединению отношений, изъять проекцию [У] Например, композицией двух приведенных выше кортежей Г, и Т2 является элементарный кортеж Tn[XZ] = (a, b,f, g)

В алгебре кортежей композиция отношений вычисляется по формуле R\[YZ] °R2[XY] = ~Y(+X(R,) n +Z(R2)) = -Y(R, Ф Л2), (2)

при условии, что Rt © R2 выражено в виде С-кортежа или С-системы

Использование формул (1) и (2) позволяет вычислить операции соединения и композиции АК-объектов без разложения их на элементарные кортежи, используя операции алгебры множеств с компонентами АК-объектов

Связь алгебры кортежей с законами математической логики Рассмотрим соответствия между структурами АК и формулами математической логики В исчислении предикатов С-кортежу в тривиальном случае (когда отдельные атрибуты не соотносятся с многоместными

отношениями) соответствует конъюнкция одноместных предикатов с разными переменными Например, логической формуле

Н = Р1(х)лР2(у)лР3(г) соответствует С-кортеж Р[ХУ2] = [Р1 Р2 Рз], где X, У и 2 - области определения переменных х, у иг, Р\ с X, Р2 с У, с 2

Отрицанию формулы Я (дизъюнкции одноместных предикатов) ~пН= -тР^х) V -тР2(у) V -2РзСг)_ соответствует £>-кортеж Р=]Р^ Р2 Ръ [

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

АК-объект, оказавшийся при проверке пустым, соответствует тождественно ложной формуле

АК-объект, равный некоторому частному универсуму, соответствует общезначимой формуле или тавтологии

Непустой АК-объект соответствует выполнимой формуле Методы квантификации в АК с помощью операций с атрибутами приведены выше

Логический вывод в АК основан на теореме 11

Теорема 11. Пусть даны АК-объекты -Рь , /•"„ и б Тогда б есть следствие Т7!, , Р„ тогда и точько тогда, когда П П /%,) с в

Домены атрибутов в АК могут быть любыми не обязательно равными друг другу множествами Это означает, структуры АК соответствуют формулам многосортного исчисления предикатов

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

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

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

одноместные предикаты, а к аксиомам исчисления предикатов добавляются некоторые «собственные» аксиомы

В 1996 г автором был предложен новый вариант математического моделирования силлогистики на основе ¿-структур Этот вариант оказался сравнительно простым и наглядным и обладает более широкими аналитическими возможностями по сравнению с предшествующими системами анализа Эти новые возможности (анализ коллизий, поиск и проверка корректности гипотез, поиск абдуктивных заключений), как оказалось, можно при определенных условиях применить и в более широких (выходящих за рамки силлогистики) системах анализа рассуждений К таким системам относятся системы типа «объекты - свойства», системы, заданные в виде соотношений между некоторыми множествами в семействе множеств В последнем случае имеется возможность выводить новые соотношения между множествами и решать задачи существования входящих в семейство множеств

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

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

(и) для любого элемента А соблюдается равенство А = А,

(ш) для любых двух элементов А и В, связанных отношением А < В,

верна контрапозиция В<А, (IV) для любого элемента А отношение А<А допустимо лишь для случая, когда А = 0 и А =1 Системы, у которых соблюдаются свойства (1) - (ш), но необязательно свойство (iv), называются ОС-структурами (сокращение слова quasl-сотр1етеп1 — квазидополнение) Подкласс <9С-структур, в которых всегда выполняется свойство (iv), выделен как их частный случай и назван логической структурой Эйлера или сокращенно Е-структурой В этом случае квазидополнение называется просто дополнением Оно соответствует дополнению алгебры множеств, но не дополнению в решетках

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

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

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

г25 > ^-чп ) и (3)

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

^ (Ъ]Ь ,Ь]П), (4)

где Ьц - базовые литералы (термины или их отрицания), содержащиеся в рассуждении, - неопределенные литералы, используемые для обозначения не предусмотренных изначально терминов в данном рассуждении (в естественном языке неопределенным литералам частично соответствует выражение «некоторые X») Символом обозначено отношение

частичного порядка, которое в ^-структурах изоморфно отношению "с"

Если литералы представить как множества, то формуле (3) соответствует выражение 1,0 с (Ь,\(Л Ьа п г\1т), а формуле (4) -(ХнП^дП Ши)*0

Рассуждением в данной системе является произвольная совокупность суждений вида (3) или (4), являющихся посылками рассуждения Для анализа рассуждений используется два правила вывода, которые являются свойствами ()С-структур

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

2) правило транзитивности (из суждений А->В и В—>С следует А-+С) Используя последовательно эти правила, получаем множество всех

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

В то же время этих правил недостаточно для того, чтобы получить некоторые заключения аристотелевой силлогистики - те самые, для получения которых в системе Я Лукасевича введены дополнительные «собственные» аксиомы В ^-структурах для получения таких заключений используется другой метод - с помощью вычисления верхних конусов литералов Верхний конус литерала Ь, (обозначается - это множество, содержащее Ь, и все литералы, являющиеся потомками Ь, Тогда заключение строится как частное суждение, в правой части которого содержится некоторое подмножество литералов из ¿f Такие заключения не являются формальными следствиями, но оказываются вполне обоснованными при условии, что литерал, для которого построен верхний конус, соответствует непустому множеству

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

Анализ рассуждений на основе ^-структур по своим аналитическим возможностям превосходит силлогистику Аристотеля Рассмотрим методы анализа совместимости рассуждений

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

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

Рассмотрим гипотезы По сути гипотеза - это новое знание, которое не является следствием принятых аксиом (или посылок) В то же время, чтобы гипотеза была корректной, она не должна противоречить принятым аксиомам Для ^-структур это означает, что при добавлении сформулированной гипотезы в конкретную структуру не происходит логических конфликтов в виде коллизий Корректность гипотезы можно проверить, если добавить ее в систему в качестве посылки Затем построить все следствия из этих посылок и убедиться, что в системе отсутствуют коллизии Однако эту процедуру можно упростить, если воспользоваться следующим соотношением Обозначим 1? и ЬА соответственно нижний и верхний конусы литерала Ь Введем операцию инверсии для множества литералов Инверсией (7пу(5)) произвольного множества 5 литералов является множество литералов такое, что каждый литерал 1,е 5 заменяется на литерал Д е Например, если 5 = {А, В, С), то 1т>(5!) = {А, В, С}

Тогда справедлива следующая теорема

Теорема 12. Новое суждение А->В является корректной гипотезой в корректной Е-структуре (7, если совместно соблюдаются два равенства (1) А^г>В&= 0, (и) Ачгл1т{В*) = 0 Рассмотрим еще одну новую для полисиллогистики задачу, которая возникает в ситуациях, когда известны посылки (или аксиомы), и суждение, которое на основании достоверных знаний или опыта считается следствием из данных посылок, но, на самом деле, не выводится из них Например, таким «неправильным» следствием является некоторый достоверный факт или

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

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

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

Рассмотрим некоторые аспекты моделирования с помощью АК технических систем Пусть задана система 5 с множеством возможных состояний У = £>> , Кроме того, в состав входит некоторое множество К узлов или подсистем V = {V1, У2, , V,,} В свою очередь, каждому узлу V, соответствует некоторое множество X, - {с|, с'г, , с'к } его

состояний, где к, — число состояний, в котором может находиться узел V,, а множества X, — произвольные множества При этом X, могут быть конечными или бесконечными множествами

Точной моделью системы 5 является соответствие между всеми возможными наборами состояний всех узлов и состояниями системы Каждому состоянию ^еУ системы соответствует некоторое множество элементарных кортежей из декартова произведения 0~Х\У.Х2* Математически это соотношение можно отобразить как соответствие 5 (5)

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

Ограничение С1 соответствие £>—>7 является однозначным (или функциональным) отображением Это означает, что ни одному элементарному кортежу из В не может соответствовать более одного элемента из У

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

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

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

1) Система, удовлетворяющая ограничениям С1 и С2, оказывается изоморфной некоторой модели многосортного исчисления предикатов

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

ScDxY-+{T,F} (6)

окажется изоморфным модели многосортного исчисления предикатов

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

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

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

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

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

вычислительную сложность до полиномиальной Известная в математической логике задача проверки выполнимости КНФ, которая часто используется при проверке корректности логического вывода и лежит в основе теории сложности вычислений, реализуется в АК как начальный этап алгоритма преобразования £>-систем в С-системы

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

является тождественно ложной формулой В этом случае, если известна вероятность каждой формулы то вероятность формулы /^у/ъу V/7,, вычисляется как сумма вероятностей входящих в нее подформул

В АК ортогональной является С-система, у которой пересечение каждой пары входящих в нее С-кортежей пусто В теории логико-вероятностного моделирования разработаны методы ортогонализации только для формул исчисления высказываний, что соответствует структурам АК, у которых домены всех атрибутов являются двухэлементными множествами В го же время в АК разработаны методы ортогонализации для АК-объектов, у которых домены атрибутов содержат произвольное число элементов Этот результат базируется на следующих двух доказанных автором теоремах Пусть <2ь бь > бш-ь 0,т ~ произвольные множества

Теорема 13 £>-кортеж вида ]б| 62 Qm \ От[ преобразуется в

эквивалентную ему ортогональную С-систему

О * * *

а в2 * *

а а б^ *

б, бг 0тЧ б„

Теорема 14 Если Р и б - ортогональные С-системы, то их пересечение либо пусто, либо состоит из одного С-кортежа, либо является ортогональной С-системой

Эти теоремы используются в следующем алгоритме преобразования произвольной й-системы в ортогональную С-сиапечу

Шаг 1 Каждый £>-кортеж, содержащийся в Д-системе, преобразовать по теореме 13 в ортогональную С-систему

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

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

В реляционных БД основными объектами управления являются файлы, организованные в виде таблиц С точки зрения АК эти таблицы состоят из

множества элементарных кортежей, содержащихся в данной таблице (отношении) Можно также представить такую таблицу как С-систему, в которой все компоненты являются одноэлементными множествами

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

Рассмотрим примеры Пусть в БД используется отношение в виде АК-объекта P[XYZ\ Требуется найти в отношении Р возможные значения атрибутов X и Y при заданном диапазоне значений D атрибута Z На языке SQL этот запрос выражается так

SELECT * FROM Р WHERE Z с D

На языке АК этот запрос выражается как С-кортеж Q\[XYZ\= [* * Z>] Ответ на запрос можно получить, вычислив P[XYZ] n Q\[XYZ\

Рассмотрим пример, где требуется соединение отношений Предположим, что в БД помимо отношения P[XYZ] имеется отношение R[YVW] и требуется ответить на вопрос, каковы значения атрибутов Хи V, если Z = а На языке SQL вопрос выражается так

SELECTX, V FROM Р, Я WHERE Z= a AND PY=RY В АК схема отношения запроса соответствует схеме отношения АК-объекта, полученного в результате соединения Р и R Тогда запрос выражается как С-кортеж Q2[XYZVW] = [* * {а}* *], а ответ на запрос будет получен в атрибутах^ и К после вычисления по формуле (P[XYZ\ Ф R[YVW]) п [* * {а}* *] Другой вариант этой формулы (P[XYZ] о [* * {а}]) Ф R[YVW] позволяет во многих случаях существенно уменьшить трудоемкость вычислений Эту же схему вычислений можно использовать в запросе типа

SELECT Z, V FROM Р, R WHERE Z = a AND W=b AND P Y=RY, в котором дополнительно задано фиксированное значение для атрибута W

Тогда запросом будет С-кортеж Q2[XYZVW] = [* * {а} * {Ь}], а ответ на запрос получим в результате следующих вычислений (.P[XYZ] п [* * {й}]) © (R[YVW] п [4= 1= {6}])

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

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

Предикаты по сути являются отношениями или элементами отношений Например, набор предикатов ЭС ~ isa(ab S\), isa (а2, Si), isa(a3, iS'j),

!sa(a4, S2), (7)

propyl, c¡, d¡), propyl, c2, d2), prop^z, cu di)

является представлением двух отношений бинарного isa и трехместного prop В структурах АК предикаты можно выразить как С-системы Так, модель (7) можно представить так

isa[XY\ ■■

{а{,а2,а3} {5,}

К) {52}

W} {с,} М) {5,} {с2} {d2}

(8)

ргор[У2У\'

{с,} ^

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

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

Иногда в качестве слотов используются правила - их можно выразить с помощью алгоритмов АК (см ниже)

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

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

Рассмотрим пример, используя совокупность предикатов (7) и их представление в АК (8) Пусть задано следующее правило вывода ЕСЛИ isa[XY\ Иprop[YZV\ ТО property[XZV¡

Если использовать терминологию АК, то в этом типичном для БЗ правиле предусматривается формирование нового отношения property Логическая связка «И» между предикатами в правилах соответствует соединению соответствующих отношений Чтобы согласовать результат этой операции со схемой отношения property, необходимо элиминировать атрибут У, что означает вычисление композиции отношений isa и prop Тогда, если на вход системы поступили факты, например, Х=а\ и V= di, то их можно выразить в виде запроса

g[XF]=[{a,} {d2}]

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

(гsa{XY\ ° prop[YZV\) гл [{а,} * {d2}\, где в запрос Q[XV| добавлен фиктивный атрибут Z Популярным примером правила, при реализации которого требуется композиция отношений, является следующее предложение «Если Х - отец Y и Y - родитель Z, то X — дед Z»

В последние годы по мере усложнения прикладных ЭС стало ясно, что для их разработки явно недостаточно средств, которые используются в «интеллектуальных» языках программирования {Пролог, Лисп и т д) Поэтому разработчики вынуждены переходить на программирование ЭС с

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

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

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

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

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

присутствовать в новом знании) - соответствует коллизии парадокса в ¿¿-структурах,

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

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

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

А выводимо из К, если и только если К с А i Отличительный признак гипотез

А является гипотезой, если неверно, что К с А Проверка корректности гипотез

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

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

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

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

Рассмотрим, как решаются эти задачи с помощью АК Основным структурообразующим понятием АК является С-кортеж Если известны вероятностные меры компонент С-кортежа, то мера самого С-кортежа вычисляется как произведение мер его компонент Если С-кортеж Я = [Л В С] задан в измеримых атрибутах, и меры его компонент равны соответственно /¿(А), /¿(5) и /х(С), то /Щ=М(А) ц{В) ц{С) Для вычисления мер АК-объектов, отличающихся от С-кортежей, необходима их ортогонализацш - преобразование в эквивалентную С-систему, в которой пересечение любой пары С-кортежей является пустым множеством Мера ортогональной С-системы в точности равна сумме мер содержащихся в ней С-кортежей На основе приведенных выше теорем 13 и 14 были разработаны методы и алгоритмы, с помощью которых можно преобразовать в ортогональную С-систему любой АК-объект Это дает возможность построить вероятностные модели не только для систем, изоморфных исчислению высказываний (это означает, что число возможных состояний у каждого атрибута равно двум), но и для систем, у которых число состояний атрибутов превышает два Это позволило существенно расширить область применения логико-вероятностных методов

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

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

А=>В= АчВ = }{0} {!}[ =

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

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

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

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

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

В качестве примера рассмотрим решение задачи Нильсона Имеются всего две логические переменные (атрибуты) ХА и Хц, каждая из них имеет два состояния 1 - для событий ^и5и0 - для событий А и В С учетом этого выразим-заданные формулы в структурах АК

А[ХАХВ] = [{1}+], я[ад] = [>{1}],

{0} ■»

.{1} {1}]

Здесь Л-кортеж ]{0} {1}[, соответствующий формуле Л з В, преобразован по теореме 13 в ортогональную С-систему

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

р(А) =рь

(1 -р(А))+р(А)р(В)=р2

Из этой системы следует что

р{В)=Р1±Р1^ Р\

'В статье Нильсона ответ получен как неравенство р2+ р\ -1 <р(В) < р2, в то время как в данном решении получен точный ответ В то же время из этого ответа следует, что значение вероятности р2 не может быть произвольным и должно удовлетворять неравенствур\ +р2> 1 (в противном случае р{В) принимает отрицательное значение) Это означает, что логическая связь событий А и В, выраженная с помощью соответствующих формул, инициирует определенные ограничения на величины их вероятностей

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

/

Список публикаций по теме диссертации

Книги

1 Кулик Б А Логические основы здравого смысла / Под ред Д А Поспелова СПб Политехника 1997 131 с

2 Кулик Б А Логика естественных рассуждений СПб Невский диалект 2001 128 с

Публикации в изданиях, рекомендованных ВАК РФ

1 Кулик Б А Система поиска слов в произвольном тексте И Программирование 1987 № 1 С 49-50

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

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

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

5 Кулик Б А Новые классы КНФ с полиномиально распознаваемым свойством выполнимости // Автоматика и телемеханика 1995 №2 С 111-124

6 Кулик Б А Представление логических систем в вероятностном пространстве на основе алгебры кортежей 1 Основы алгебры кортежей//Автоматика и телемеханика 1997 №1 С 126-136

7 Кулик Б А , Наумов M В Представление логических систем в вероятностном пространстве на основе алгебры кортежей 2 Измеримые логические системы //Автоматика и телемеханика 1997 №2 С 169-179

8 Кулик Б А Анализ надежности систем с многими состояниями на основе алгебры кортежей // Автоматика и телемеханика, 2003 №7 С 13-18

9 Кулик Б А Вероятностная логика на основе алгебры кортежей // Известия РАН Теория и системы управления 2007 №¡1 С 118-127

Статьи, изобретения, материалы конференций

1 Кулик Б А Быстродействующие ИПС на основе операций с логическими векторами // Управляющие системы и машины 1989 №4 С 14-19

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

3 Кулик Б А Основные принципы философии здравого смысла (познавательный аспект) // Новости искусственного интеллекта 1996 № 3 С 7-92

4 Кулик Б А Программа для моделирования и анализа естественных рассуждений // Компьютерные инструменты в образовании, 1998 №2, с 55-63

5 Кулик Б А А если заглянуть в третье тысячелетие9 // Новости РФФИ 1998 №2(5)

6 Кулик Б А Есть ли логика в современном образовании99'? // Новости РФФИ, 1998 № 7(10)

7 Кулик Б А С чем идет современная логика в XXI век9//Вестник РФФИ 2000 №3(21)

8 Кулик Б А Логика естественных рассуждений Учебная программа курса лекций для студентов СПбГУКИ по специальности 351400 «Прикладная информатика» // Учебно-методические материалы Выпуск первый СПб СПбГУКИ, 2005, с \ 10—114

9 Ас 1322292 СССР Устройство для адресации по содержанию блока памяти БИ № 25, 1987 (Авт Б А Кулик, Э В Рахов, В M Питерский Б H Лысков)

10 А с 1464164 СССР Устройство для адресации по содержанию блока памяти БИ № 9, 1989 (Авт ТП Корниец, ЬА Кулик, Э В Рахов)

11 А с 1485254 СССР Устройство для адресации по содержанию блока памяти БИ № 21, 1989 (Авт Б А Кулик, Э В Рахов, H H Востров ТП Корниец)

12 Патент 2028664 Российской Федерации Устройство для параллельной обработки данных БИ №4, 1995 (Авт Б А Кулик, Л Е Кулик, В Ф Федоров)

13 Кулик Б А Моделирование рассуждений на основе законов алгебры множеств / Труды Пятой нац конф по искусственному интеллекту Казань 1996 Т 1, с 58-61

14 Кулик Б А Интерпретируемые системы логического вывода / Международная конференция "Смирновские чтения" (тезисы докладов) M Институт философии РАН 1997 С 54-55

15 Кулик Б А Система логического вывода на логических графах / Современная логика проблемы теории, истории и применения в науке Материалы V Общероссийской научной конференции СПб 1998 С 169-171

16 Кулик Б А Алгебраические основы естественных рассуждений Е-струкгуры / Материалы второй международной конференции "Логико-лингвистическое управление динамическими объектами (DOLLC'99)" СПб 1999 С 29-40

17 Кулик Б А, Романов Л Н Алгебраический подход к моделированию и анализу естественных рассуждений на основе Е-структур / Интеллектуальное управление новые интеллектуальные технологии в задачах управления (1СГГ99) Труды Международной конференции Переславль-Залесский, 1999 М Физматлит 1999 С 50-54

18 Кулик Б А Логическая модель развивающегося знания на основе ^-структур /Современная логика проблемы теории, истории и применения в науке Материалы VI Общероссийской научной конференции СПб 2000 С 204-211

19 Кулик Б А Индуктивный вывод в ЛГ-структурах /Современная логика проблемы теории, истории и применения в науке Материалы VI Общероссийской научной конференции СПб 2000 С 477-480

20 Кулик Б А Вероятностное моделирование систем на основе алгебры кортежей /Тр>ды 1 междунар научной школы "Моделирование и анализ риска и качества в сложных системах -

2001" СПб ООО "НПО Омега" 2001 С 155-158

21 Кулик Б А О математических основаниях естественной логики /Материалы VII Общероссийской научной конференции "Современная логика проблемы теории, истории и применения в науке" СПбГУ 2002 С 67-70

22 Кулик Б А Обобщенный подход к моделированию и анализу потенциально опасных объектов на основе QC-структур и алгебры кортежей /Труды междунар научной школы "Моделирование и анализ безопасности и риска в сложных системах - 2003" СПб СПбГУ АП, 2003 С 159-165

23 Кулик Б А Методика моделирования и анализа рассуждений на основе iT-c-rpvicryp / Материалы межд научно-практической конф «Проблемы преподавания логики и дисциплин логического цикла» Киев ИПЦ «Киевский университет» 2004 С 54-55

24 Кулик Б А Модифицируемые рассуждения в рамках классической логики / Материалы VIII , Общероссийской научной конференции "Современная логика проблемы теории, истории и

применения в науке" СПбГУ 2004 С 379-382

25 Кулик Б А. Вероятностная логика на основе алгебры кортежей / Труды междунар научной школы "Моделирование и анализ безопасности и риса в сложных системах - 2005" СПбГУ АП 2005 С 406-412

?г5 Кулик Б А Следствия и гипотезы в естественных рассуждениях / Материалы IX Общероссийской научной конференции "Современная логика проблемы теории, истории и применения в науке" СПбГУ 2006 С 374-376

27 Кулик Б А Логико-вероятностные методы анализа на основе алгебры кортежей / Кибернетика и информатика Сборник научных трудов к 50-летию секции кибернетики Дома Ученых им М Горького РАН СПб Изд-во Политехи ун-та 2006 С 171-193

28 Кулик Б А Обобщенный подход к моделированию и анализу интеллектуальных систем на основе алгебры кортежей / Труды VI Международной конференции «Идентификация систем и .Задачи управления» SICPRO'07 М ИПУ РАН, 2007 С 679-715

29 Кулик Б А Логико-вероятностный анализ интеллектуальных систем на основе алгебры кортежей /Труды междунар научной школы "Моделирование и анализ безопасности и риска в сложных системах - 2007" СПб ГУАП, 2007 С 137-149

30 Кулик Б А Теория отношений как математическая основа логики / Труды международной научной конференции «Философия математики актуальные проблемы» М , Изд Савин С А , 2007 С 111-113

31 Kulik В Development of Aigonthmical Provision for the Calculation of Systems' Reliability and Safety on the Basis of the Tuple Algebra /Im Proceedings of the International Conference on Informatics and Control (ICI&C97) Samt Petersburg 1997 pp 1087-1093

Введение.

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

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

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

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

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

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

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

2.1.1 Введение.

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

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

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

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

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

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

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

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

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

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

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

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

3 (?С-структуры: от полисиллогистики к нечеткой логике.

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

3.2 Введение в ^С-структуры.

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

3.2.2 Вывод в <2С-структурах.

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

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

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

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

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

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

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

3.3.4 Сравнение силлогистики Аристотеля и ^-структур.

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

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

3.3.7 Zs-структуры и исчисление высказываний.

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

3.4 gC-структуры и нечеткие множества.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 показаны возможности алгебры кортежей при моделировании и анализе различных типов бинарных и многоместных отношений. Устанавливается, что операции с атрибутами позволяют сравнительно легко вычислять для отношений, представленных в структурах АК, операции соединения и композиции, которые часто используются как в информационных, так и в интеллектуальных системах.

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

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

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

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

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

Автором был определен и исследован новый частный случай у-множеств, имеющих наибольший (1) и наименьший (0) элементы - QC-структуры, которые являются у-множествами с одной операцией - квазидополнением. Для этой операции постулируются следующие свойства: i) для любого элемента у-множества А существует или может быть вычислен единственный элемент А, который называется квазидополнением А; ii) для любого элемента^ соблюдается равенство А =А; iii) для любых двух элементов А и В, связанных отношением А<В, верна контрапозиция В<А\ iv) для любого элемента А отношение А< А допустимо лишь для случая, когда А — О и А = 1.

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

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

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

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

L,o —» (La, ) и (1)

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

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

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

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

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

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

Если литералы представить как множества, то формуле (1) соответствует выражение ho с (Ьцп La п . глЬщ), а формуле (2) - (Lnc\ La n . nLm)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим некоторые аспекты моделирования с помощью АК технических систем. Пусть задана система S с множеством возможных состояний Y = {t\, tz, tr). Кроме того, в состав S входит некоторое множество V узлов или подсистем V = {V\, Vi, . , V„). В свою очередь каждому узлу F, соответствует некоторое множество X, = {с\, с'2. . , с'к } его состояний, где к,- — число состояний, в котором может находиться узел V,, а множества X, — произвольные множества. При этом X, могут быть конечными или бесконечными множествами.

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

S:D^Y. (3)

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

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

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

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

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

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

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

Sc: DxY^{T,F} окажется изоморфным модели многосортного исчисления предикатов, в которой отсутствуют ограничения на число состояний узлов и системы в целом.

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

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

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

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

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

Алгоритмы ортогонализации АК-объектов используются в логико-вероятностном моделировании (J1BM) [100]. В JIBM ортогональной называется дизъюнкция вида FivF2v.vF„ такая, что для любых i Ф j формула F,aFj является тождественно ложной формулой. В этом случае, если известна вероятность каждой формулы F„ то вероятность формулы F\s/F2V.\/Fn вычисляется как сумма вероятностей входящих в нее подформул.

В АК ортогональной является С-система, у которой пересечение каждой пары входящих в нее С-кортежей пусто. В теории логико-вероятностного моделирования разработаны методы ортогонализации только для формул исчисления высказываний, что соответствует структурам АК, у которых домены всех атрибутов являются двухэлементными множествами. В то же время в АК разработаны методы ортогонализации для АК-объектов, у которых домены атрибутов содержат произвольное число элементов, что соответствует формулам исчисления предикатов. Этот результат базируется на доказанных автором теоремах [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]. Основные задачи, решаемые с помощью

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23 оценки риска уникальных систем» и в учебном процессе Санкт-Петербургского

Государственного Университета Культуры и Искусств и Санкт-Петербургского государственного Технического Университета.

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

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

Заключение

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

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

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

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

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

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

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

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

279

1. Авторское свидетельство 1322292 СССР. Устройство для адресации по содержанию блока памяти. БИ № 25, 1987.(Авт.: Б.А. Кулик, Э.В. Рахов, В.М. Питерский, Б.Н. Лысков).

2. Авторское свидетельство 1464164 СССР. Устройство для адресации по содержанию блока памяти. БИ № 9, 1989.(Авт.: Т.П. Корниец, .Б.А. Кулик, Э.В. Рахов).

3. Авторское свидетельство 1485254 СССР. Устройство для адресации по содержанию блока памяти. БИ № 21, 1989.(Авт.: Б.А. Кулик, Э.В. Рахов, Н.Н. Востров, Т.П. Корниец).

4. Аристотель. Сочинения в 4-х т. Т.2 М., Мысль, 1978.

5. Арнольд В.И. Математическая дуэль вокруг Бурбаки // Вестник РАН. 2002. Т. 72, № 3, с. 245250.

6. Башмаков А.И., Башмаков И.А. Интеллектуальные информационные технологии: Учебн. пособие. М.: Изд-во МГТУ им. Н.Э. Баумана, 2005. 304 с.

7. Биркгоф Г., Барти Т. Современная прикладная алгебра. М.: Мир. 1976. 400 с.

8. Бурбаки Н. Очерки по истории математики. М.: Издательство иностранной литературы, 1963.

9. Бурбаки Н. Теория множеств. М.: Мир, 1965.

10. Васильев Н.А. Воображаемая логика. М.: Наука, 1989.

11. Вишняков В.А., Буланже Д.Ю., Герман О.В. Аппаратно-программные средства процессоров логического вывода. М.: Радио и связь, 1991.

12. Генцен Г. Исследование логических выводов. В кн.: Математическая теория логического вывода. М.: Наука, 1967, с. 9 - 74.

13. Гетманова А.Д. Учебник по логике. М.: "Владос", 1994.

14. Георгиев В. О. Модели представления знаний предметных областей диалоговых систем (обзор) // Известия РАН. Техн. кибернетика, 1993, № 5. С. 24-44

15. Гильберт Д., Аккреман В. Основы теоретической логики. М.: ИЛ. 1947.

16. Гладкий А. В. Введение в современную логику. М.: МЦНМО, 2001.

17. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. Киев: Наукова думка, 1989.

18. Гэри М., Джонсон Л. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

19. Данцин Е.А. Алгоритмика задачи выполнимости // Вопросы кибернетики. Проблемы сокращения перебора. М., 1987. С. 7-29.

20. Дейт К.Дж. Введение в системы баз данных. 6-е издание. Киев, М., СПб.: Издательский дом «Вильяме», 1999.

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

22. Евстигнеев В.А. Применение теории графов в программировании. М.: Наука, Гл. ред. физ.-мат. лит. 1985. 352 с.

23. Закревский А. Д. Представление знаний и логический вывод в пространстве многозначных признаков. В кн. Логика и компьютер. Вып. 2: Логические языки, содержащие рассуждения и методы поиска доказательств. М.: Наука, 1995. С. 3-16.

24. Закревский АД. Матричный аппарат логического вывода в конечных предикатах // Философские основы неклассической логики: Тр. научно-иссл. семинара по логике, М.: Ин-т философии АН СССР, 1990, с.70-80.

25. Зенкин А.А. Принцип разделения времени и анализ одного класса квазифинитных правдоподобных рассуждений (на примере теоремы Г. Кантора о несчетности) // Доклады РАН. Раздел "Математика". 1997. Т. 356, № 6. С. 733-735.

26. Индейцев А.И., Сергеев А.Г. Система интеллектуальной поддержки борьбы за живучесть надводного корабля // Методы и средства информационной поддержки борьбы за живучесть надводных кораблей. СПб., ИПМаш РАН. 1995. С. 15-35.

27. Искусственный интеллект. В 3-х книгах. Кн. 2. Модели и методы: Справочник/ Под ред. Д.А. Поспелова - М.: Радио и связь. 1990.

28. КарриХ.Б. Основания математической логики. М.: Мир, 1969.

29. Клини С. Математическая логика. М.: Мир. 1973. 480 с.

30. Колмогоров А. Н. Основные понятия теории вероятностей. — М.: Наука, 1974. — 120 с.

31. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — М.: Наука, 1972. —496 с.

32. Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. М.: Изд-во МГУ, 1982.

33. Кофман А. Введение в теорию нечетких множеств. М.: Радио и связь, 1982.

34. Кривоносое А. Т. Язык. Логика. Мышление. М. Моск. гос. лингв ун-т, 1996.

35. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир,1978. 432 с.

36. Кузичев А. С. Диаграммы Венна. — М.: Наука, 1968. — 252 с.

37. Кулик Б.А. А если заглянуть в третье тысячелетие? // Новости РФФИ, 1998. № 2(5).

38. Кулик Б.А. Алгебраические основы естественных рассуждений: Е-структуры // Материалы второй международной конференции "Логико-лингвистическое управление динамическими объектами (DOLLC'99)", Санкт-Петербург, 21 25 июня 1999 г., с. 29-40.

39. Кулик Б.А. Анализ надежности систем с многими состояниями на основе алгебры кортежей // Автоматика и телемеханика, 2003. № 7. С. 13-18.

40. Кулик Б.А. Быстродействующие ИПС на основе операций с логическими векторами // Управляющие системы и машины. 1989. № 4. С. 14-19.

41. Кулик Б.А. Вероятностная логика на основе алгебры кортежей // Известия РАН. Теория и системы управления. 2007. № 1. С. 118-127.

42. Кулик БА. Вероятностная логика на основе алгебры кортежей // Труды междунар. научной школы "Моделирование и анализ безопасности и риса в сложных системах 2005" (СПб. 28 июня - 1 июля 2005 г.). СПб., ГОУ ВПО "СПбГУАП". 2005. С. 406-412.

43. Кулик Б.А. Вероятностное моделирование систем на основе алгебры кортежей // Труды междунар. научной школы "Моделирование и анализ риска и качества в сложных системах -2001" (СПб. 18 22 июня 2001 г.) СПб, Издательство ООО "НПО Омега", 2001. С. 155-158.

44. Кулик Б А. Есть ли логика в современном образовании ? // Новости РФФИ, 1988. № 7(10)

45. Кулик Б.А. Индуктивный вывод в Е-структурах // Современная логика: проблемы теории, истории и применения в науке. Материалы VI Общероссийской научной конференции. Санкт-Петербург, 22-24 июня 2000 г. С. 477 - 480.

46. Кулик Б А. Интерпретируемые системы логического вывода // Международная конференция "Смирновские чтения" (тезисы докладов). М.: Институт философии РАН. 1997. С. 54-55.

47. Кулик Б.А. Логика естественных рассуждений. СПб. Невский диалект. 2001. 128 с.

48. Кулик Б.А. Логика естественных рассуждений. Учебная программа курса лекций для студентов СПбГУКИ по специальности 351400 «Прикладная информатика» // Учебно-методические материалы. Выпуск первый. СПб.: Изд-во СПбГУКИ, 2005, с. 110-114.

49. Кулик Б.А. Логико-вероятностные методы анализа на основе алгебры кортежей // Кибернетика и информатика. Сборник научных трудов к 50-летию секции кибернетики Дома Ученых им М. Горького РАН. СПб.: Изд-во Полтехн. ун-та. 2006. С. 171-193.

50. Кулик Б.А. Логическая модель развивающегося знания на основе Е-структур // Современная логика: проблемы теории, истории и применения в науке. Материалы VI Общероссийской научной конференции. Санкт-Петербург, 22 - 24 июня 2000 г. С. 204 -211.

51. Кулик Б.А. Логические основы здравого смысла / под ред. Д.А. Поспелова. СПб. Политехника. 1997. 131 с.

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

53. Кулик Б.А. Методика моделирования и анализа рассуждений на основе Е-структур // Мат. междунар. научно-практической конф. «Проблемы преподавания логики и дисциплин логического цикла». 13-14 мая 2004 г. Киев. ИПЦ «Киевский университет». С. 54-55.

54. Кулик Б.А. Моделирование рассуждений на основе законов алгебры множеств // Труды Пятой национальной конференции по искусственному интеллекту, Казань, 7-11 октября 1996 г. Т. 1, с. 58-61.

55. Кулик Б.А. Модифицируемые рассуждения в рамках классической логики // Материалы VIII Общероссийской научной конференции "Современная логика: проблемы теории, истории и применения в науке". 24 26 июня 2004 г. СПб. Издательство СпбГУ, 2004. С. 379-382.

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

57. Кулик Б.А. О математических основаниях естественной логики // Материалы VII Общероссийской научной конференции "Современная логика: проблемы теории, истории и применения в науке". 20 22 июня 2002 г. СПб. Издательство СпбГУ, 2002. С. 67-70.

58. Кулик Б.А. Обобщенный подход к моделированию и анализу интеллектуальных систем на основе алгебры кортежей. // Труды VI Международной конференции «Идентификация систем и задачи управления» SICPRO'07 (Москва, 29 января 1 февраля 2007 г.). С. 679-715.

59. Кулик Б.А. Основные принципы философии здравого смысла (познавательный аспект) // Новости искусственного интеллекта. 1996. № 3. С. 7-92.

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

61. Кулик Б.А. Представление логических систем в вероятностном пространстве на основе алгебры кортежей. 1. Основы алгебры кортежей //Автоматика и телемеханика. 1997. № 1. С. 126-136.

62. Кулик Б.А. Программа для моделирования и анализа естественных рассуждений// Компьютерные инструменты в образовании, 1998. № 2, с. 55 -63.

63. Кулик Б.А. С чем идет современная логика в XXI век? // Вестник РФФИ, № 3(21), 2000.

64. Кулик Б.А. Система логического вывода на логических графах // Современная логика: проблемы теории, истории и применения в науке. Материалы V Общероссийской научной конференции. Санкт-Петербург, 18-20 июня 1998 г.С. 169 -171.

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

66. Кулик Б.А. Система поиска слов в произвольном тексте // Программирование. 1987. № 1. С. 49-50.

67. Кулик Б.А. Следствия и гипотезы в естественных рассуждениях// Материалы IX Общероссийской научной конференции "Современная логика: проблемы теории, истории и применения в науке". 22 24 июня 2006 г. СПб. Издательство СпбГУ, 2006. С. 374-376.

68. Кулик Б.А., Наумов М. В. Представление логических систем в вероятностном пространстве на основе алгебры кортежей. 2. Измеримые логические системы //Автоматика и телемеханика. 1997. № 2. С. 169-179.

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

70. Курант Р., Роббинс Г. Что такое математика. Элементарный очерк идей и методов. M-JI.: ОГИЗ, 1947.

71. Курош А.Г. Общая алгебра (лекции 1969 1970 года). М.: Наука, Гл. ред. физ.-мат. лит. 1970. 160 с.

72. Кэрролл Л. Логическая игра-М.: Наука, 1991.

73. Кэрролл. Л. История с узелками. М.: Мир. 2000.

74. Левин Л.А. Универсальные задачи перебора // Проблемы передачи информации. 1973. Вып.З. С.115-116.

75. Лейбниц Г.В. Сочинения в четырех томах. Т.З М.: Мысль. С.632-658.

76. Лекции лауреатов премии Тьюринга. М.: Мир, 1993.

77. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И. Тышкевич Р.И. М.: Наука, Гл. ред. физ.-мат. лит. 1990. 384 с.

78. ЛипскийВ. Комбинаторика для программистов. М.: "Мир", 1988. 213 с.

79. Логика и компьютер. Вып. 4. Карпенко А.С. Многозначные логики. -М.: Наука, 1997.

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

81. Лукасевич Я. Аристотелевская силлогистика с точки зрения современной формальной логики. М. 1959.

82. Мальцев А.И. Алгебраические системы. М.: Наука. 1970.

83. Марков А.А. Теория алгорифмов. М.-Л.: Из-во АН СССР, 1954.

84. Маслов С.Ю. Теория дедуктивных систем и ее применения. М.: Радио и связь. 1986.

85. Математическая энциклопедия. В 5-ти томах. М.: Советская энциклопедия. 1977-1985 гг.

86. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971.

87. Мендельсон Э. Введение в математическую логику. М.: Наука. 1984.

88. Непейвода Н.Н. Прикладная логика. Учебное пособие. Ижевск:. Издательство Удмуртского университета, 1997. 385 с.

89. Новиков П. С. Элементы математической логики. М.: Наука. 1973.

90. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер. 2002. 304 с.

91. Общая алгебра. Т.1/ О.В. Мельников, В.Н. Ремесленников, В.А. Романьков и др. Под общ. ред. JI.A. Скорнякова. М:. Наука, Гл. ред. физ.-мат. лит. 1990. 592 с.

92. Патент 2028664 Российской Федерации. Устройство для параллельной обработки данных. БИ№ 4, 1995. (Авт.: Б.А. Кулик, Л.Е. Кулик, В.Ф. Федоров).

93. Плоткин Б.И. Универсальная алгебра, алгебраическая логика и базы данных. М.: Наука, Гл. ред. физ.-мат. лит. 1991. 468 с.

94. Поспелов Д. А. Моделирование рассуждений. Опыт анализа мыслительных актов. — М.: Радио и связь, 1989. — 184 с.

95. Представление и использование знаний: Пер. с япон. /Под ред. X. Уэно, М. Исидаука. М.: Мир, 1989. 220 с.

96. Рейнгольд Э, Нивергелълът Ю, Део Н. Комбинаторные алгоритмы. Теория и практика. М.: "Мир", 1980.476 с.

97. Рид К. Гильберт. М.: Наука, 1977.

98. Рябинин И.А. Надежность и безопасность структурно-сложных систем. СПб.: Политехника, 2000.

99. Рябинин И.А. Черкесов Г.Н. Логико-вероятностные методы исследования надежности структурно-сложных систем. М:. "Радио и связь", 1981. 264 с.

100. Салж В. Н. Решетки с единственными дополнениями. М.: Наука, 1984. — 128 с.

101. Сикорский Р. Булевы алгебры. М.: Мир, 1969.

102. Скорняков J7.A. Элементы теории структур. М.: Наука, Гл. ред. физ.-мат. лит. 1982. 160 с.

103. Смалъян Р. Теория формальных систем. М.: Наука. 1981.

104. Смаллиан Р. М. Принцесса или тигр? М.: Мир, 1986.

105. Смирнов В. А. Логические методы анализа научного знания. М.: Наука, 1987.

106. Смолин Д. В. Введение в искусственный интеллект. М.: ФИЗМАТ ЛИТ, 2004.

107. Соложенцев ЕД Сценарное логико-вероятностное управление риском в бизнесе и технике. СПб.: Издательский дом "Бизнес-пресса". 2004. 432 с.

108. Стокмейер Л. Классификация вычислительной сложности проблем // Кибернетический сборник, новая серия. Вып. 26. 1989. С.20-83.

109. Столл P.P. Множества. Логика. Аксиоматические теории. М.: "Просвещение", 1968.

110. Стяжкин Н. И. Формирование математической логики. М.: Наука, 1967.

111. ИЗ. ТакеутиГ. Теория доказательств. М.: Мир, 1978,412 с.

112. Турчин В. Ф. Метаалторитмический язык // Кибернетика. 1968. № 4. С. 43-53.

113. Ульман Д.Д, УидомД. Введение в системы баз данных. М:. Издательство «Лори», 2000.

114. ХалмошП. Теория меры. М.: ИЛ, 1953.

115. Цаленко М.Ш. Семантические и математические модели баз данных. М.: ВИНИТИЮ сер. информатикаю 1985. (Итоги науки и техники).

116. Чень Ч, Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука. 1983, —360 с.

117. Чери С., Готлоб Г., Танка Л. Логическое программирование и базы данных. М.: Мир, 1992.352 с.

118. Яблонский С.В. Введение в дискретную математику. М.: Наука. Главная редакция физико-математической литературы. 1979.

119. Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. М.: Наука, 1966.

120. Яновская С.А. Математическая логика и основания математики- В кн. Математика в СССР за сорок лет. Т.1. Физматгиз.1959, С.13-120.

121. Codd E.F. A relational model of data for large shared data banks. Comm. ACM, 1970, v. 13, N 6, p. 377-387.

122. Codd E.F. Relational completeness of data base sublanguages. Data Base Systems: Proc of Courant Computer Science Symposia 6, New York City, May 24-25. 1971. Prentice Hill, 1972, p. 33-64.

123. Codd. E.F. Normalized Data Base Structure: A Brief Tutorial Proc. 1971 ACM SIGFIDET Workshop on Data Description, Access and Control. P. 1-17.

124. Colmerauer A. Metamorphosis grammar. Natural language communication with computers. // Lect. Notes in Сотр. Sci. vol. 63 (1976).

125. Davis М., Putnam Н. A computing procedure for quantification theory. J. ACM, 1960, 1, p. 201 -215.

126. Fagin R. Normal Forms and Relational Database Operations. Proc. 1971 ACM SIGMOD Intern. Conf. On Management of Data. P. 153-160.

127. Galil Z. On enumeration procedures for theorem proving and for integer programming. -Automata, languages and programming (Third Intern. Collq.) Edinburgh, Univ. Edinburgh, 1976. PP.355-381.

128. Karp R.M. Reducibility among computational problems. Complexity of computer computations, Plenum press, New York, 1972. PP. 85-104. Русский перевод: Р.М.Карп. Сводимость комбинаторных проблем // Кибернетический сборник, новая серия, вып. 12. С.16-38].

129. Krom M.R. The decision problem for a class of first-order formulas in which all disjunctions are binary.— Z. math. Logic Grundl. Math., 1967, 13, p. 15-20.

130. Kulik B. Reliability Analysis of the Systems with Many States on the Basis of the Algebra of Tuples // Automation and Remote Control, 2003, Vol. 64, No. 7, pp. 1029-1034.

131. Kulik B.A. A Logic Programming System Based on Cortege Algebra. Journal of Computer and Systems Sciences International, 1995, Vol.33, No.2, pp. 159-170.

132. Kulik B.A. New Classes of Conjunctive Normal Forms with a Polynomially Recognizable Property of Satisfiability. Automation and Remote Control, 1995, Vol.56, No.2 Pt2, pp.245-255.

133. Kulik B.A. N-Tuple Algebra-Based Probabilistic Logic Systems Analysis and Operations Research. 2007. Vol. 46, No. 1, pp. 111 - 120.

134. Kulik B.A. Representation of Logical Systems in a Probabilistic Space in Terms of Cortege Algebra. 1 Elements of cortege algebra.//Automation and Remote Control, 1997, Vol.58, No.l Pt2, pp. 102-114.

135. Kulik B.A., Naumov M. V. Representation of Logical Systems in a Probabilistic Space in Terms of Cortege Algebra. 2.Measurable logical systems. // Automation and Remote Control, 1997, Vol.58, No.2 Pt2, pp.290-298.

136. McCarthy J. A basis for a mathematical theory of computation. Proc. Western Joint Сотр. Conf., Los Angeles, May 1961. PP. 225-238.

137. Newell A., Shaw J.S., Simon H.A. Empirical explorations of the logic theory machine: a case study in heuristics. Report P-951. Rand Corporations. 1957, March.

138. NilssonN. J. Probabilistic Logic // Artificial Intelligence, 28 ,1986, pp. 71-87.

139. Rabin M.O. Degree of difficulty of computing a function and a partial ordering of recursive sets.

140. Technical Report 2. Hedrew University. Jerusalem. 1960.