авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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

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

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

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

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

ЛОГИЧЕСКИЙ АНАЛИЗ СИСТЕМ НА ОСНОВЕ

АЛГЕБРАИЧЕСКОГО ПОДХОДА

Специальность 05.13.01 – Системный анализ, управление и обработка

информации (по прикладной математике и процессам управления)

АВТОРЕФЕРАТ

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

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

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

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

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

Доктор физико-математических наук, профессор (Санкт-Петербургский Братчиков Игорь Леонидович государственный университет);

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

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

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

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

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

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

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

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

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

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

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

2. При моделировании и анализе модифицируемых рассуждений (т.е.

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) «объекты – свойства»;

2) системы подмножеств, заданные некоторыми соотношениями между некоторыми подмножествами;

3) системы рассуждений типа полисиллогистики;

4) системы нечетких множеств.

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

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

проверки правильности следствия;

формулировки и проверки гипотез;

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

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

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

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

1. При проектировании и разработке программно-математического обеспечения для моделирования и логического анализа систем.

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

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

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

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

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

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

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

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

2) системы подмножеств, заданные некоторыми соотношениями между некоторыми подмножествами;

3) системы рассуждений типа полисиллогистики;

4) системы нечетких множеств.

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

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

формулировки и проверки гипотез;

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

5) Теоретическое обоснование и алгоритмы решения задач логико вероятностного анализа систем на основе алгебры кортежей;

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

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

Реализация результатов. Результаты исследований нашли свое применение в работах по выполнению Программы фундаментальных исследований Отделения энергетики, машиностроения, механики и процессов управления РАН «Динамика и устойчивость многокомпонентных машиностроительных систем с учетом техногенной безопасности» (2003– 2006 гг.), по гранту РФФИ № 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 столетия работами Ж.-Д. Жергонна, А. де Моргана, Дж. Буля, Дж. Венна, Л. Кэрролла и др. В конце XIX и первой четверти XX столетий появляются работы, которые дали толчок развитию математической логики (Г. Кантор, Дж. Пеано, Б. Рассел и др.) и логико-вероятностному анализу (П.С. Порецкий, С.Г. Бернштейн и др.). Были сформулированы парадоксы теории множеств (в частности, парадокс Рассела), в результате чего у многих математиков и логиков возникли сомнения в корректности понятия «множество». Эти события инициировали поиск оснований математики и логики в рамках теории формальных систем (ТФС). Тем самым было определено направление дальнейшего развития методов логического анализа. Это направление в дальнейшем реализовалось как декларативный подход в рамках искусственного интеллекта и стимулировало интенсивное развитие неклассических логик, основной особенностью которых является несоответствие законам булевой алгебры и алгебры множеств.

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

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

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

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

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

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

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





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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, если задан элементарный кортеж T[XYZ] = (a, b, c), то подразумевается, что aX, bY и cZ.

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

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

Например, R[XYZ] = [A B C], означает, что AX, BY, CZ и R[XYZ] = ABC.

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

C-система представляет собой множество элементарных кортежей. Это множество равно объединению множеств элементарных кортежей, содержащихся в соответствующих C-кортежах. Например, C-систему A B C Q[XYZ] = 1 1 A2 B2 C можно представить как множество элементарных кортежей, вычисляемое по формуле Q[XYZ] = (A1B1C1) (A2B2C2).

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

В АК-объектах содержатся фиктивные компоненты. Они бывают двух видов. Одна из них – полная компонента – используется в C-кортежах и обозначается “”. Значением этой фиктивной компоненты является домен соответствующего атрибута. Другую фиктивную компоненту “” – пустое множество, которая используется в D-кортежах, рассмотрим позднее. Здесь и далее в качестве примеров будем рассматривать АК-объекты, заданные в пространстве S = XYZ, где X = {a, b, c, d}, Y = {f, g, h}, Z = {a, b, c}. Тогда справедливы равенства:

Q1[XYZ] = [ {f, h} {a, b}] = [{a, b, c, d} {f, h} {a, b}];

Q2[XYZ] = [{b, d} {a, b}] = [{b, d} {f, g, h} {a, b}].

Ясно, что любая совокупность однотипных АК-объектов является алгеброй множеств. Операции и проверки включения или равенства между этим АК-объектами реализуются на основании теорем 1 – 6. Пусть заданы однотипные C-кортежи P = [P1 P2 … Pn] и Q = [Q1 Q2 … Qn].

Теорема 1. P Q = [P1Q1 P2Q2 … Pn Qn].

Примеры: [{b, d} {f, h} {a, b}] [ {f, g} {a, c}] = [{b, d} {f} {a}];

[{b, d} {f, h} {a, b}] [ {g} {a, c}] = [{b, d} {a}] =.

Теорема 2. PQ, если и только если Pi Qi для всех i = 1, 2, …, n.

Теорема 3. P Q [P1Q1 P2Q2 … Pn Qn], причем равенство возможно лишь в двух случаях:

P Q или Q P;

(i) (ii) Pi = Qi для всех соответствующих пар компонент за исключением одной пары.

Заметим, что в алгебре кортежей в соответствии с Определением 4 во P P2... Pn всех случаях справедливо равенство P Q = 1.

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

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

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

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

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

Теорема 6. Для произвольного C-кортежа P = [P1 P2 … Pn] P1...

P2...

P=.

............

... Pn C-системы размерности nn, у которых все компоненты, не принадлежащие главной диагонали, равны “”, будем называть диагональными.

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

Например, {a, c} T= {g} = ]{a, c} {g} {c}[.

{c} Такое представление диагональной C-системы образует новую структуру АК, которая называется D-кортежем.

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

Дополнение C-кортежа можно прямо записывать как D-кортеж.

Например, если T1 = [{b, d} {a, b}], то T1 = ]{a, c} {c}[. В D-кортежах константа “” – фиктивная компонента. При преобразовании D-кортежа с C-систему строки, фиктивными компонентами в диагональную соответствующие фиктивным компонентам, оказываются пустыми и поэтому могут быть удалены из этой C-системы. Например, {a, c} {a, c} T1 = ]{a, c} {c}[ = =.

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

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

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

Теорема 7. Дополнением C-системы является D-система той же размерности, в которой каждая компонента равна дополнению соответствующей компоненты в исходной C-системе.

Например, дополнение C-системы {a, b, d } { f, h} {b} F[XYZ] =, {a, c} {b, c} * заданной в пространстве S, можно вычислить как D-систему X \ {a, b, d } Y \ { f, h} Z \ {b} {c} {g} {a, c} F= =.

Z \ {a, c} {a, d } {b} X \ {b, c} Y \ Нетрудно видеть, что соотношения между C-объектами (C-кортежи и C-системы) и D-объектами (D-кортежи и D-системы) соответствуют законам двойственности де Моргана. В силу этого они названы альтернативными классами.

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

Алгоритм преобразования D-системы в C-систему:

1) преобразовать каждый D-кортеж D-системы в C-систему;

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

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

Рассмотрим операции с атрибутами (см. Определение 1).

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

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

Добавление фиктивного атрибута осуществляется только в том случае, если добавляемый атрибут отсутствует в схеме отношения АК-объекта. При этом в C-кортежи и в C-системы в соответствующие столбцы добавляется фиктивные компоненты “”, а в D-кортежи и D-системы – фиктивные компоненты “”.

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

Если в C-кортеж или в C-систему вводится фиктивный атрибут, то эта процедура соответствует известному в исчислении предикатов правилу вывода, которое называется правилом обобщения. Например, если АК-объект {a, c} G[XZ] = {a, c, d } {b, c} соответствует формуле F(x, z) исчисления предикатов, то, добавив в этот АК-объект фиктивный атрибут Y, получим АК-объект {a, c} G1[XYZ] = +Y(G[XZ]) =, {a, c, d } {b, c} который соответствует формуле yF(x, z), полученной из формулы F(x, z) по правилу обобщения. Для C-кортежей и C-систем это соответствие очевидно, для D-кортежей и D-систем это соответствие (с учетом того, что в них фиктивной компонентой является “”) устанавливается с помощью следующей теоремы.

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

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

Теорема 9. Пусть R[…X…] – C-система, у которой отсутствуют C-кортежи с пустыми компонентами в атрибуте X. Тогда для соответствующего этой C-системе предиката P(…, x, …) формула –X(R) соответствует формуле x(P).

Теорема 10. Пусть R[…X…] – D-система, у которой отсутствуют D-кортежи с компонентами «» в атрибуте X. Тогда для соответствующего этой D-системе предиката P(…, x, …) формула –X(R) соответствует формуле x(P).

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

X = W\V;

Y = WV;

Z = V\W.

Тогда получим: V = YZ и W = XY. С учетом этого данные отношения можно переписать так: R1[YZ] и R2[XY].

Операция соединения R1[YZ] R2[XY] отношений в реляционной алгебре выполняется с помощью попарного сравнения всех элементарных кортежей из разных отношений. Если при сравнении этих кортежей окажется, что в проекции [Y] они совпадают, то в этом случае из двух кортежей формируется кортеж со схемой отношения [XYZ], и этот кортеж становится одним из элементов соединения отношений. Например, имеются два элементарных кортежа T1 R1 и T2 R2, при этом T1[YZ] = (c, d, e, f, g);

T2[XY] = (a, b, c, d, e), где T2[X] = (a, b);

T1[Z] = (f, g);

T1[Y] = T2[Y] = (c, d, e).

В этом случае результатом композиции этих кортежей является элементарный кортеж T3[XYZ] = (a, b, c, d, e, f, g).

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

R1[YZ] R2[XY] = +X(R1) +Z(R2) = x(R1) z(R2). (1) Операция композиции R1[YZ] R2[XY] отношений вычисляется после вычисления соединения отношений. Для этого требуется из каждого элементарного кортежа, принадлежащего соединению отношений, изъять проекцию [Y]. Например, композицией двух приведенных выше кортежей T и T2 является элементарный кортеж T4[XZ] = (a, b, f, g).

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

R1[YZ] R2[XY] = –Y(+X(R1) +Z(R2)) = –Y(R1 R2), (2) при условии, что R1 R2 выражено в виде C-кортежа или C-системы.

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

Связь алгебры кортежей с законами математической логики.

Рассмотрим соответствия между структурами АК и формулами предикатов C-кортежу в тривиальном математической логики. В исчислении случае (когда отдельные атрибуты не соотносятся с многоместными отношениями) соответствует конъюнкция одноместных предикатов с разными переменными. Например, логической формуле H = P1(x) P2(y) P3(z) соответствует C-кортеж P[XYZ] = [P1 P2 P3], где X, Y и Z – области определения переменных x, y и z;

P1 X;

P2 Y;

P3 Z.

Отрицанию формулы H (дизъюнкции одноместных предикатов) H = P1(x) P2(y) P3(z) соответствует D-кортеж P = ] P1 P2 P3 [.

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

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

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

Непустой АК-объект соответствует выполнимой формуле.

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

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

Теорема 11. Пусть даны АК-объекты F1,..., Fn и G. Тогда G есть следствие F1,..., Fn тогда и только тогда, когда (F1... Fn) G.

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

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

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

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

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

системы, заданные в виде соотношений между некоторыми множествами в семействе множеств.

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

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

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

для любого элемента A соблюдается равенство A = A;

(ii) для любых двух элементов A и B, связанных отношением A B, (iii) верна контрапозиция B A ;

(iv) для любого элемента A отношение A A допустимо лишь для случая, когда A = 0 и A = 1.

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

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

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

1) общие суждения типа Li0 (Li1, Li2,..., Lin) и (3) 2) частные (или экзистенциальные) суждения типа wj (Lj1, Lj2,..., Ljm), (4) где Lst – базовые литералы (термины или их отрицания), содержащиеся в рассуждении, wr – неопределенные литералы, используемые для обозначения не предусмотренных изначально терминов в данном рассуждении (в естественном языке неопределенным литералам частично соответствует выражение «некоторые X»). Символом “” обозначено отношение частичного порядка, которое в E-структурах изоморфно отношению “”.

Если литералы представить как множества, то формуле (3) соответствует выражение Li0 (Li1 Li2... Lin), а формуле (4) – (Li1 Li2... Lin).

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

1) правило контрапозиции (если AB, то B A);

2) правило транзитивности (из суждений AB и BC следует AC).

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

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

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

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

В математической логике сформулирован только один критерий противоречивости: когда из посылок выводится некоторое следствие и его отрицание. В то же время и в повседневных, и в неформализованных научных рассуждениях одним из бесспорных критериев парадоксальности системы является вывод контрарных следствий (например, из посылок следует, что «всем A присуще B» и «всем A не присуще B»). Тем не менее, формально эти два суждения не являются отрицаниями друг друга (отрицанием формулы x(A(x)B(x)) в исчислении предикатов является формула x(A(x)B(x)) – «некоторым A не присуще B», но не формула x(A(x)B(x)), которая соответствует суждению «всем A не присуще B»).

Чтобы устранить это несоответствие между формальной логикой и естественными рассуждениями, в систему анализа на основе E-структур вводится понятие коллизия. Определены два типа формальных коллизий:

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

Рассмотрим гипотезы. По сути гипотеза – это новое знание, которое не является следствием принятых аксиом (или посылок). В то же время, чтобы гипотеза была корректной, она не должна противоречить принятым аксиомам. Для E-структур это означает, что при добавлении сформулированной гипотезы в конкретную структуру не происходит логических конфликтов в виде коллизий. Корректность гипотезы можно проверить, если добавить ее в систему в качестве посылки. Затем построить все следствия из этих посылок и убедиться, что в системе отсутствуют коллизии. Однако эту процедуру можно упростить, если воспользоваться следующим соотношением. Обозначим L и L соответственно нижний и верхний конусы литерала L. Введем операцию инверсии для множества литералов. Инверсией (Inv(S)) произвольного множества S литералов является множество литералов такое, что каждый литерал LiS заменяется на литерал Li Inv(S). Например, если S = {A, B, C}, то Inv(S) = { A, B, C }.

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

Теорема 12. Новое суждение AB является корректной гипотезой в корректной E-структуре G, если совместно соблюдаются два равенства:

AB = ;

(i) (ii) AInv(B) =.

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

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

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

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

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

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

Рассмотрим некоторые аспекты моделирования с помощью АК технических систем. Пусть задана система S с множеством возможных состояний Y = {t1, t2,..., tr}. Кроме того, в состав S входит некоторое множество V узлов или подсистем V = {V1, V2,..., Vn}. В свою очередь, i каждому узлу Vi соответствует некоторое множество Xi = { c1i, c2,..., cki } его i состояний, где ki — число состояний, в котором может находиться узел Vi, а множества Xi — произвольные множества. При этом Xi могут быть конечными или бесконечными множествами.

Точной моделью системы S является соответствие между всеми возможными наборами состояний всех узлов и состояниями системы.

Каждому состоянию tjY системы соответствует некоторое множество элементарных кортежей из декартова произведения D = X1X2... Xn.

Математически это соотношение можно отобразить как соответствие:

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

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

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

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

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

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

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

множество допустимых (true) и множество недопустимых (false) состояний, определяемых в соответствии с конструктивными или технологическими особенностями моделируемой системы. При этом соответствие Sc: DY{T, F} (6) окажется изоморфным модели многосортного исчисления предикатов.

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

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

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

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

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

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

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

Пусть Q1, Q2,..., Qm-1, Qm – произвольные множества.

Теорема 13. D-кортеж вида ]Q1 Q2... Qm-1 Qm[ преобразуется в Q1... Q Q... 1 эквивалентную ему ортогональную C-систему:.

...

Q1 Q2... Qm Q1 Q2... Qm 1 Qm Теорема 14. Если P и Q – ортогональные C-системы, то их пересечение либо пусто, либо состоит из одного C-кортежа, либо является ортогональной C-системой.

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

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

Шаг 2. Найти пересечение всех C-систем, полученных на шаге 1.

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

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

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

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

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

SELECT * FROM P WHERE Z D.

На языке АК этот запрос выражается как C-кортеж Q1[XYZ]= [ D].

Ответ на запрос можно получить, вычислив P[XYZ] Q1[XYZ].

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

SELECT X, V FROM P, R WHERE Z = a AND P.Y = R.Y.

В АК схема отношения запроса соответствует схеме отношения АК-объекта, полученного в результате соединения P и R. Тогда запрос выражается как C-кортеж Q2[XYZVW] = [ {a} ], а ответ на запрос будет получен в атрибутах X и V после вычисления по формуле:

(P[XYZ] R[YVW]) [ {a} ].

Другой вариант этой формулы:

(P[XYZ] [ {a}]) R[YVW] позволяет во многих случаях существенно уменьшить трудоемкость вычислений. Эту же схему вычислений можно использовать в запросе типа SELECT X, V FROM P, R WHERE Z = a AND W = b AND P.Y = R.Y, в котором дополнительно задано фиксированное значение для атрибута W.

Тогда запросом будет C-кортеж Q2[XYZVW] = [ {a} {b}], а ответ на запрос получим в результате следующих вычислений:

(P[XYZ] [ {a}]) (R[YVW] [ {b}]).

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

Далее рассматривается представление в АК экспертных систем (ЭС).

Базы знаний ЭС содержат модели и правила. Известно четыре типа моделей:

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

Рассмотрим другие модели.

Предикаты по сути являются отношениями или элементами отношений.

Например, набор предикатов ЭС isa(a1, S1);

isa(a2, S1);

isa(a3, S1);

isa(a4, S2);

(7) prop(S1, c1, d1);

prop(S1, c2, d2);

prop(S2, c1, d3).

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

{S1} {c1 } {d 1 } {a1, a 2, a3 } {S1 } ;

prop[YZV] = {S1} {c 2 } {d 2 }.

isa[XY] = (8) {a 4 } {S 2 } {S 2 } {c1 } {d 3 } Семантической сетью является ориентированный граф, в узлах которого содержатся имена объектов, а дуги помечены именами отношений.

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

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

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

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

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

Рассмотрим пример, используя совокупность предикатов (7) и их представление в АК (8). Пусть задано следующее правило вывода:

ЕСЛИ isa[XY] И prop[YZV] ТО property[XZV].

Если использовать терминологию АК, то в этом типичном для БЗ правиле предусматривается формирование нового отношения property. Логическая связка «И» между предикатами в правилах соответствует соединению соответствующих отношений. Чтобы согласовать результат этой операции со схемой отношения property, необходимо элиминировать атрибут Y, что означает вычисление композиции отношений isa и prop. Тогда, если на вход системы поступили факты, например, X = a1 и V = d2, то их можно выразить в виде запроса Q[XV] = [{a1} {d2}].

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

(isa[XY] prop[YZV]) [{a1} {d2}], где в запрос Q[XV] добавлен фиктивный атрибут Z. Популярным примером правила, при реализации которого требуется композиция отношений, является следующее предложение: «Если X – отец Y и Y – родитель Z, то X – дед Z».

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

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

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

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

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

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

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

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

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

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

A выводимо из K, если и только если K A.

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

A является гипотезой, если неверно, что K A.

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

A является корректной гипотезой, если K A не содержит коллизий.

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

Пусть A – предполагаемое следствие из K, которое не удовлетворяет условию K A. Тогда B является допустимым абдуктивным заключением, если соблюдаются два условия: (KB) A и KB не содержит коллизий.

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

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

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

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

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

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

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

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

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

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

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

В качестве примера рассмотрим решение задачи Нильсона. Имеются всего две логические переменные (атрибуты) XA и XB, каждая из них имеет два состояния: 1 – для событий A и B и 0 – для событий A и B. С учетом этого выразим заданные формулы в структурах АК:

A[XA XB] = [{1} ];

B[XA XB] = [ {1}];

{0} A B = A B = ]{0} {1}[ = {1} {1} Здесь D-кортеж ]{0} {1}[, соответствующий формуле A B, преобразован по теореме 13 в ортогональную C-систему.

Пусть переменными будут вероятности p(A) и p(B), которые соответствуют состоянию 1. Тогда состоянию 0 соответствуют вероятности 1–p(A) и 1–p(B). С учетом этого получим следующую систему из двух уравнений:

p(A) = p1;

(1 – p(A)) + p(A) p(B) = p2.

Из этой системы следует что p p2 p(B) = 1.

p В статье Нильсона ответ получен как неравенство p2+ p1 –1 p(B) p2, в то время как в данном решении получен точный ответ. В то же время из этого ответа следует, что значение вероятности p2 не может быть произвольным и должно удовлетворять неравенству p1 + p2 1 (в противном случае p(B) принимает отрицательное значение). Это означает, что логическая связь событий A и B, выраженная с помощью соответствующих формул, инициирует определенные ограничения на величины их вероятностей.

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

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

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

Машинная реализация АК-объектов позволяет использовать три уровня параллелизма: на уровне компонент;

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ РАБОТЫ В диссертационной работе проведены теоретические исследования, направленные на увеличение эффективности и результативности логического анализа систем. В результате этих исследований получены следующие результаты.

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

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

1) «объекты – свойства»;

2) системы подмножеств, заданные некоторыми соотношениями между некоторыми подмножествами;

3) системы рассуждений типа полисиллогистики;

4) системы нечетких множеств.

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

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

формулировки и проверки гипотез;

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

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

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

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

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

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

Политехника. 1997. 131 с.

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

Публикации в изданиях, рекомендованных ВАК РФ 1. Кулик Б.А. Система поиска слов в произвольном тексте // Программирование.1987. № 1. C.

49-50.

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

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

Техн. кибернетика. 1993. № 3. С. 226–239.

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

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

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

126–136.

7. Кулик Б. А., Наумов М. В. Представление логических систем в вероятностном пространстве на основе алгебры кортежей. 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. Кулик Б.А. А если заглянуть в третье тысячелетие? // Новости РФФИ. 1998. № 2(5).

6. Кулик Б.А. Есть ли логика в современном образовании99? // Новости РФФИ, 1998. № 7(10) 7. Кулик Б.А. С чем идет современная логика в XXI век? // Вестник РФФИ. 2000. № 3(21).

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

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

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

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

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

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

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

15. Кулик Б.А. Система логического вывода на логических графах / Современная логика:

проблемы теории, истории и применения в науке. Материалы V Общероссийской научной конференции. СПб.: 1998. С. 169 –171.

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

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

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

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

2000. С. 477–480.

20. Кулик Б.А. Вероятностное моделирование систем на основе алгебры кортежей /Труды междунар. научной школы "Моделирование и анализ риска и качества в сложных системах 2001". СПб. ООО "НПО Омега". 2001. С. 155–158.

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

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

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

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

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

2005. С. 406–412.

26. Кулик Б.А. Следствия и гипотезы в естественных рассуждениях / Материалы 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 B. Development of Algorithmical Provision for the Calculation of Systems’ Reliability and Safety on the Basis of the Tuple Algebra /Iin Proceedings of the International Conference on Informatics and Control (ICI&C’97). Saint Petersburg. 1997. pp 1087–1093.

Подписано в печать 12.03.2008. Тираж 100 экз.

199178, СПб, Большой пр. В.О., 61, ИПМаш РАН заказ №

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.