Логический анализ систем на основе алгебраического подхода тема диссертации и автореферата по ВАК РФ 05.13.01, доктор физико-математических наук Кулик, Борис Александрович

• Кулик, Борис Александрович
• доктор физико-математических наук
• 2007

Оглавление диссертации доктор физико-математических наук Кулик, Борис Александрович

Введение.

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

Список литературы диссертационного исследования доктор физико-математических наук Кулик, Борис Александрович, 2007 год

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.