«ПРЕДСТАВЛЕНИЕ И ОБРАБОТКА ЗНАНИЙ В ГРАФОДИНАМИЧЕСКИХ АССОЦИАТИВНЫХ МАШИНАХ Под редакцией В.В. Голенкова Минск 2001 Учреждение образования Белорусский государственный университет информатики и радиоэлектроники ...»

В.В. Голенков, О.Е. Елисеева, В.П. Ивашенко, В.М. Казан

Н.А. Гулякина, Н.В. Беззубенок, Т.Л. Лемешева, Р.Е. Сердюков

И.Б. Фоминых

ПРЕДСТАВЛЕНИЕ И ОБРАБОТКА

ЗНАНИЙ В

ГРАФОДИНАМИЧЕСКИХ

АССОЦИАТИВНЫХ

МАШИНАХ

Под редакцией В.В. Голенкова Минск 2001 Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники»

ПРЕДСТАВЛЕНИЕ И ОБРАБОТКА

ЗНАНИЙ В

ГРАФОДИНАМИЧЕСКИХ

АССОЦИАТИВНЫХ

МАШИНАХ

Под редакцией В.В. Голенкова Минск УДК 007.2 (075.8) Коллектив авторов:

В.В. Голенков, О.Е. Елисеева, В.П. Ивашенко, В.М. Казан Н.А. Гулякина, Н.В. Беззубенок, Т.Л. Лемешева, Р.Е. Сердюков И.Б. Фоминых Представление и обработка знаний в графодинамических ассоциативных машинах / В.В.Голенков, О.Е.Елисеева, В.П.Ивашенко и др.: Под ред. В.В.Голенкова. – Мн.: БГУИР, 2001. – 412 с.

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

В книгу вошли результаты проектов, финансируемых Белорусским Республиканским Фондом фундаментальных исследований в рамках совместной белорусско-российской программы фундаментальных исследований «БРФФИ-РФФИ 2000»: «Разработка принципов и методов создания интегрированных динамических экспертных систем» (№ 00-7036), «Анализ и моделирование псевдооптических нейронных сетей» (№ 00-7029).

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

Табл. 17. Ил. 270. Библиогр.: 693 назв.

Рецензенты:

доктор технических наук А.С.Гринберг доктор технических наук Б.М.Лобанов доктор технических наук Н.А.Ярмош Издано при поддержке СП International Business Alliance Рекомендовано к печати Советом БГУИР (протокол № 2 от 25.10.2001) ISBN 985-444-312- © Коллектив авторов, Belarusian state university of informatics and radioelectronics

KNOWLEDGE REPRESENTATION AND PROCESSING

IN GRAPH-DYNAMIC ASSOCIATIVE COMPUTERS

Knowledge Representation and Processing in Graph-Dynamic Associative Computers. V.V. Golenkov, O.E. Eliseeva, V.P. Ivashenko and others. Edited by V.V. Golenkov. - Minsk, BSUIR, 2001. – 412 с.

ISBN 985-444-312- Graph-dynamic associative models for representation and processing of knowledge in artificial intelligence systems are represented. The base of this model is, firstly, a description of different types of knowledge represented by homogeneous semantic networks having a base set-theoretic interpretation and, secondly, interpretation of knowledge processing as a graph-dynamic process, i.e. a process of semantic networks configuration modification.

The results of the projects financed by the Belarusian Republic Fund of Fundamental Researches realized in a framework of a joint program of fundamental researches “BRFFR – RFFR – 2000”: “ Development of principles and methods for construction of integrated dynamic expert systems”(No. 00-7036), “ Analysis and simulation of pseudo-optical neuron networks” (No. 00 – 7029) are included.

The book is intended for skillful specialists as well as for postgraduates and students taking an interest in artificial intelligence.

Dr.Sc. A.S. Grinberg,; Dr.Sc. B.M. Lobanov; Dr.Sc. N.A. Jarmosh.

Issued under sponsorship of JV International Business Alliance.

Содержание Предисловие

Введение

1. Графодинамическая парадигма обработки информации

1.1. Концепция графодинамических моделей

1.1.1. Понятие формальной модели обработки информации

1.1.2. Классификация формальных моделей обработки информации

1.1.3. Интеграция и интерпретация формальных моделей обработки информации............. 1.1.4. Семиотические модели обработки информации

1.1.5. Графодинамические ассоциативные модели обработки знаний и известные виды моделей представления знаний

1.2. Графовые языки

1.2.1. Понятие реляционной структуры как уточнение понятия предметной области и понятия информационной конструкции

1.2.2. Линейные тексты

1.2.3. Нелинейные тексты

1.2.4. Денотационная семантика текстов

1.2.5. Классификация языков

1.2.6. Семантические сети и семантические графовые языки

1.3. Абстрактные графодинамические ассоциативные машины

1.3.1. Абстрактные машины обработки информации и соответствующие им операции, элементарные процессы и микропрограммы

1.3.2. Классификация абстрактных машин обработки информации

1.3.3. Графодинамические параллельные асинхронные абстрактные машины как наиболее перспективный класс абстрактных машин для проектирования сложных интеллектуальных систем

Выводы к разделу 1

2. Теоретико-множественные принципы представления фактографических знаний в памяти графодинамических ассоциативных машин

2.1. Базовые понятия, лежащие в основе языка SCB

2.2. Основные положения языка SCB (Semantic Code Basic)

2.3. Ядро языка SCBg (Semantic Code Basic graphical) – графической модификации языка SCB. 2.4. Средства обеспечения наглядности языка SCBg

2.5. Ядро языка SCBs (Semantic Code Basic string) – линейной модификации языка SCB............. 2.6. Формирование идентификаторов в языке SCB

2.7. Приведение текстов языка SCBs к лаконичному виду

2.8. Формальное описание синтаксиса языка SCBs

Выводы к разделу 2

3. Представление основных математических структур на языке SCB

3.1. Типология множеств и их представление в языке SCB. Основные множества языка SCB и соответствующие им ключевые узлы

3.2. Понятие кортежа. Атрибуты элементов кортежа. Представление кортежей в языке SCB.

Типология кортежей

3.2.1. Понятие кортежа и атрибута

3.2.2. Примеры кортежей и их представление в языках SCBg и SCBs

3.2.3. Типология кортежей

3.3. Понятие отношения. Представление отношений в языке SCB. Типология отношений.

Классические и неклассические отношения

3.3.1. Обобщение традиционной трактовки отношений

3.3.2. Типология отношений на основе базовой типологии множеств

3.3.3. Типология отношений на основе типологии кортежей, входящих в состав отношения, а также анализа соотношения между кортежами

3.3.4. Типология отношений на основе понятия проекции и понятия области определения 3.3.5. Типология отношений на основе понятия функциональной зависимости

3.3.6. Представление и типология классических отношений

3.3.7. Отношения предельного вида

3.3.8. Типология бинарных отношений и метаотношения над ними

3.3.9. Множество соответствий как метаотношение, заданное на множестве бинарных ориентированных отношений

3.3.10. Типология тернарных отношений и метаотношения над ними

3.3.11. Отношения над множествами

3.3.12. Отношения над кортежами

3.3.13. Отношения над отношениями

3.3.14. Числовые отношения

3.4. Представление реляционных структур в языке SCB. Типология реляционных структур.

Классические и неклассические реляционные структуры

3.4.1. Представление реляционных структур в языке SCB

3.4.2. Типология реляционных структур

3.4.3. Отношения над реляционными структурами. Реляционные метаструктуры................ 3.4.4. Графовые структуры и отношения над ними

Выводы к разделу 3

4. Ядро открытого семейства графовых языков представления знаний, построенных на теоретико-множественной основе

4.1. Основные понятия, лежащие в основе логических языков

4.2. Язык SC (Semantic Code), являющийся основой построения различных логических языков и языков представления знаний

4.3. Язык SCg (Semantic Code graphical) – графическая модификация языка SC

4.4. Язык SCs (Semantic Code string) – линейная модификация языка SC

4.5. Ключевые узлы графового языка SC

4.6. Понятие sc-подъязыка. Семейство графовых языков, построенных на базе языка SC........... 4.7. Понятие абстрактной sc-машины

4.8. Понятие формальной sc-модели

Выводы к разделу 4

5. Представление логических формул и формальных теорий в памяти графодинамических ассоциативных машин

5.1. Принципы построения графового логического языка SCL (Semantic Code Logic) на теоретико-множественной основе

5.2. Запись логических формул с использованием стилизованного естественного языка............. 5.3. Язык SCLs (Semantic Code Logic string) – формальный линейный логический язык классического типа, использующий язык SCs для записи атомарных логических формул

5.4. Язык SCLg (Semantic Code Logic graphical) – графический вариант изображения текстов языка SCL

5.5. Примеры записи логических формул на предложенных логических языках

5.6. Формальная метатеория и её представление на языке SCL

Выводы к разделу 5

6.1. Представление знаний, связанных с понятием измерения

6.2. Описание динамических систем

6.3. Описание целей в графодинамических ассоциативных машинах

6.4. Гипертекстовые семантические сети

6.5. Принципы представления нейросетевых моделей

6.5.1. Краткое описание полной прямолинейной модели псевдооптической нейронной сети и методов расчета её поведения

графодинамических машин

Выводы к разделу 6

7. Навигационно-поисковая графодинамическая ассоциативная машина

7.1. Операции навигационно-поисковой графодинамической ассоциативной машины.................. 7.1.1. Информационные конструкции, описывающие состояние навигационнопоисковой графодинамической ассоциативной машины

7.1.2. Семейство операций поиска теоретико-графовой окрестности указываемого scэлемента

7.1.3. Семейство операций поиска в рамках указываемой формальной теории всех истинных высказываний, релевантных указываемой высказывательной форме (заданному образцу)

7.1.4. Семейство операций поиска семантических окрестностей указываемого sc-элемента

7.1.5. Семейство операций поиска семантической связи между (двумя или более) sc-элементами

7.1.6. Семейство навигационно-поисковых операций в гипертекстовой семантической сети

7.2. Пример работы навигационно-поисковой графодинамической ассоциативной машины........ Выводы к разделу 7

8. Графодинамические ассоциативные машины вывода

8.1. Семейство легко интегрируемых абстрактных графодинамических ассоциативных машин вывода

8.1.1. Информационные конструкции, описывающие состояние абстрактной графодинамической ассоциативной машины вывода

8.1.2. Операции абстрактной графодинамической ассоциативной машины вывода............. 8.2. Решение задач в графодинамических ассоциативных машинах вывода

Выводы к разделу 8

Заключение

Литература

CONTENTS

Annotation

Introduction

1. Information Processing. Graph-Dynamic paradigm

1.1. Conception of graph-dynamic models

1.1.1. Concept of information processing formal model

1.1.2. Classification of information processing formal models

1.1.3. Information processing formal models integration and interpretation

1.1.4. Semiotic models of information processing

1.1.5. Graph-dynamic knowledge processing formal models and admitted model types of knowledge representation

1.2. Graph languages

1.2.1. Concept of a relational structure as the concept specification of the subject and information structure

1.2.2. Linear texts

1.2.3. Nonlinear texts

1.2.4. Denotative text semantics

1.2.5. Language classification

1.2.6. Semantic networks and semantic graphic languages

1.3.

Abstract

graph-dynamic associative computers

1.3.1. Information processing abstract computers and corresponding operations, elementary processes and microprograms

1.3.2. Classification of information processing abstract computers

1.3.3. Graph-dynamic parallel asynchronous abstract computers as the most perspective class of abstract computers for designing complex intelligent systems

Chapter 1 conclusions

2. Set-Theoretical principles of factual knowledge representation in memory of graph-dynamic associative computers

2.1. SCB language (Semantic Code Basic). Basic statements

2.2. SCB language (Semantic Code Basic). Basic concepts

2.3. SCBg kernel (Semantic Code Basic graphical) – SCB graphical modification

2.4. SCB visual methods features

2.5. SCBs kernel (Semantic Basic Code string) – SCB linear modification

2.6. Identifier compilation in SCB

2.7. SCB texts reduction to laconic form

2.8. SCB Syntax. Formal description

Summary to Chapter 2

3. SCB description of basic mathematical structures

3.1. Set typology and their representation in SCB. SCB basic sets and their corresponding key nodes

3.2. Cortege concept. Attributes of cortege elements. Cortege representation in SCB. Cortege typology

3.2.1. Cortege and attribute concept

3.2.2. Cortege samples and their description in SCBg and SCBs

3.2.3. Cortege typology

3.3. Concept of relation. Relation representation in SCB. Relation typology. Classical and non classical relations

3.3.1. Traditional relation generalization. Resume

3.3.2. Relation typology based on set base typology

3.3.3. Relation typology based on typology of corteges belonging to a relation

3.3.4. Relation typology based on projection concept

3.3.5. Relation typology based on functional dependence concept

3.3.6. Description and typology of classical relations

3.3.7. Boundary relations

3.3.8. Binary relations typology and metarelations

3.3.9. Set of correspondences as a metarelation assigned on sets of binary oriented relations..... 3.3.10. Ternary relations typology and metarelations

3.3.11. Relations on sets

3.3.12. Relations on corteges

3.3.13. Relations on relations

3.3.14. Numeric relations

3.4. Representation of relational structures in SCB. Relational structures typology. Classical and nonclassical relational structures

3.4.1. Description of relational structures in SCB

3.4.2. Typology of relational structures

3.4.3. Relations on relational structures. Relational metastructures

3.4.4. Graphic structures and relations on them

Chapter 3. Conclusions

4. Kernel of the open set of knowledge representation graph languages created on set-theory base........... 4.1. Basic concepts of logic languages

4.2. SC language (Semantic Code) as a base for creating various logical languages and knowledge representation languages

4.3. SCg language (Semantic Code graphical) – SC graphical modification

4.4. SCs language ( Semantic Code string) – SC linear modification

4.5. Key nodes of SC graph language

4.6. SC-sub language concept. Set of graph languages created on SC basis

4.7. Concept of abstract sc-computer

4.8. Concept of formal sc-model

Chapter 4 conclusions

5. Description of logical formulas and formal theories in memory of graph-dynamic associative computers

5.1. Principles of SCL graph logical language (Semantic Code Logic) construction on set-theory basis

5.2. Logical formulas recording using conventionalized natural language

5.3. SCLs language (Semantic Code Logic string) – a formal linear logical language of a classical type using SCs for recording atomic logical formulas

5.4. SCLg language – graphical variant for reproducing SCL texts

5.5. Samples of recording of logical expressions in conventionalized natural language

5.6. Formal meta theory and its description in SCL

Chapter 5 conclusions

6. Knowledge typology and knowledge representation languages in graph-dynamic associative computers

6.1. Knowledge representation related to a measure concept

6.2. Dynamic systems description

6.3. Description of aims in graph-dynamical associative computers

6.4. Hypertext semantic networks

6.5. Principles of description of neuronet models

6.5.1. Brief description of a total rectilinear model of pseudo-optical neuronet and of methods of calculation of its behaviour

6.5.2. Principles of description of pseudo-optical neuronets in graph-dynamical computers memory

Conclusions to Chapter 6

7. Navigation and search graph-dynamical associative computer

7.1. Navigation and search graph-dynamical associative computer operation

7.1.1. Informational constructions describing a status of navigation and search graphdynamical associative computer

7.1.2. Search operations set of theoretical graphical area of the specified sc-element

7.1.3. Search operations set in a specified formal theory boundaries of all true expressions relevant to the specified expressive form (given specimen)

7.1.4. Search operations set of semantic areas of the specified sc-element

7.1.5. Search operations set of the semantic connection between two or more specified scelements

7.1.6. Navigation and search operations set in hypertext semantic network

7.2. A sample of a navigation and search graph-dynamical associative computer operation

Conclusions to Chapter 7

8. Graph-dynamical associative logical computers

8.1. A set of easily integrated abstract graph-dynamical associative logical computers

8.1.1. Information constructions describing a status of an abstract graph-dynamical associative logical computer

8.1.2. Abstract graph-dynamical associative logical computer operations

8.2. Task solution by abstract graph-dynamical associative logical computers

Conclusions to Chapter 8

Conclusion

References

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

Особенностью предлагаемых моделей является:

• ассоциативность;

• легкая интегрируемость;

• возможность обработки знаний не только простой, но и сложной структуры;

• единство языка и метаязыка;

• ориентация на параллельную асинхронную обработку знаний.

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

• «Математические основы искусственного интеллекта»;

• «Модели представления знаний, базы данных и СУБД»;

• «Нейросетевые модели и нейрокомпьютеры»;

• «Логические основы интеллектуальных систем»;

• «Технология и инструментальные средства проектирования интеллектуальных систем».

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

• «Параллельная графовая вычислительная система, ориентированная на решение задач искусственного интеллекта». Проект финансировался Министерством Промышленности Республики Беларусь и выполнялся под руководством В.В.Голенкова рядом организаций – Научноисследовательским институтом электронных вычислительных машин (НИИЭВМ), Институтом технической кибернетики Национальной Академии Наук Беларуси, Белорусским государственным университетом информатики и радиоэлектроники. Со стороны НИИЭВМ большой вклад в выполнение этого проекта внесли В.М.Казан и Л.М.Романовская.

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

• «Разработать инструментальные средства построения интеллектуальных систем на основе графового языка логического программирования, ориентированного на распределенную переработку интегрированных баз данных и знаний». Проект финансировался Фондом Информатизации РБ.

• «Разработка принципов и методов создания интегрированных динамических экспертных систем».

Проект финансируется Белорусским республиканским фондом фундаментальных исследований в рамках совместной белорусско-российской программы фундаментальных исследований “БРФФИРФФИ 2000”, № 00-7036. Руководителем этого проекта с российской стороны является доктор технических наук И.Б.Фоминых (Российский НИИ информационных технологий и автоматизации проектирования).

• «Анализ и моделирование псевдооптических нейронных сетей». Проект финансируется Белорусским республиканским фондом фундаментальных исследований в рамках совместной белорусскороссийской программы фундаментальных исследований “БРФФИ-РФФИ 2000”, № 00-7029. Руководителем этого проекта с российской стороны является доктор технических наук О.П.Кузнецов (Институт проблем управления Российской Академии Наук), предоставленные которым материалы были использованы в 6-м разделе данной книги.

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

Начиная с 1996 года кафедра интеллектуальных информационных технологий БГУИР активно сотрудничает с компанией JV International Business Alliance. Благодаря этому сотрудничеству, кафедра за короткий срок в современных непростых условиях достигла необходимого уровня. Формы сотрудничестПредисловие ва были направлены не только на повышение уровня подготовки молодых специалистов, в том числе путем подключения студентов (начиная со 2-го курса) к серьезным проектам, но и на совместную разработку перспективных конкурентоспособных наукоемких программных продуктов. Данная книга является этому подтверждением.

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

Авторы книги выражают искреннюю признательность всем участникам проектов, результаты которых вошли в книгу, преподавателям и аспирантам кафедры интеллектуальных информационных технологий БГУИР, а также студентам специальности «Искусственный интеллект», принимающим активное участие в выполнении проектов и их внедрении в учебный процесс. Следует особо отметить таких студентов, как А.Рукин, С.Хованский, А.Слиборский, С.Шкред, М.Рафалович, Д.Рожанский.

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

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

В книге для более наглядного и понятного восприятия текста принят ряд соглашений.

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

Второстепенные примечания в тексте выделяются мелким шрифтом.

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

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

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

Приводимые в тексте библиографические ссылки, помимо порядкового номера в списке литературы, содержат также (в круглых скобках) краткие идентификаторы этих ссылок, в которых указывается фамилия автора, год издания и аббревиатура названия статьи или книги. Например, ссылка (П о с п е л о в Д. А. 1 9 8 6 к н - С и т у а У ) означает, что речь идет о книге, автор которой Поспелов Д.А., издана книга в 1986 году и ее наименование «Ситуационное управление: Теория и практика».

Кроме того, в тексте используются различные шрифты для всевозможных разделителей (таких как точка, запятая, двоеточие, скобки и т.п.). Различие способов отображения разделителей продиктовано тем фактом, что описываемые формальные языки также содержат разделители, которые должны отличаться от тех, которые используются в обычном естественно-языковом тексте. В частности, используется три вида кавычек: "прямые" симметричные кавычки "... " – для выделения всевозможных иносказаний; асимметричные жирные кавычки “... ” – для явного выделения (если это требуется в данном контексте) фрагментов формального текста описываемых языков; угловые кавычки «... » – для выделения всевозможных наименований или цитат.

Введение Расширение областей применения методов и средств искусственного интеллекта приводит к следующему:

• существенно увеличиваются размеры перерабатываемых баз знаний;

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

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

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

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

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

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

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

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

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

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

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

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

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

В данной книге, а также в работе [411] (П р о г р В А М - 2 0 0 1 к н ) описываются результаты исследований, которые посвящены созданию легко расширяемого семейства согласованных друг с другом моделей параллельной переработки информации, в состав которого включаются:

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

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

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

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

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

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

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

• использование принципа языка-ядра (базового языка) при создании указанного выше семейства графовых языков;

• ориентация на открытые языки;

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

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

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

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

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

• фактографический язык SCB (Semantic Code Basic);

• язык SC (Semantic Code), являющийся расширением языка SCB и основой для построения различных логических языков и языков программирования;

• язык SCL (Semantic Code Logic), являющийся одним из возможных (но не единственно возможным) логических языков, построенных на основе языка SC;

• язык описания целей (заданий) в графодинамических ассоциативных машинах;

• язык SCP (Semantic Code Programming), являющийся языком программирования, ориентированным на переработку знаний, представленных в виде текстов языка SC и его подъязыков;

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

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

• эффективной поддержке сложноструктурированных знаний;

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

поддержке параллельной переработки знаний.

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

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

интеллектуальные обучающие и тренажерные системы [236] (И н т е л О С и В У О - 2 0 0 1 к н );

интеллектуальные систем автоматизации деятельности организаций, интеллектуальные виртуальные органиации [236] (И н т е л О С и В У О - 2 0 0 1 к н ), интеллектуальные системы управления корпоративными знаниями;

интеллектуальные геоинформационные системы;

интеллектуальные системы поддержки принятия решений в условиях дефицита времени;

интеллектуальные системы управления сложными объектами;

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

интеллектуальные системы защиты информационных ресурсов открытых корпоративных систем.

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

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

1.1. Концепция графодинамических моделей Ключевые понятия: графодинамические параллельные асинхронные модели;

формальная модель обработки информации; интеграция; интерпретация.

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

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

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

Основными особенностями рассматриваемых в данной книге моделей являются:

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

• ассоциативность, т.е. использование ассоциативного метода доступа к требуемым фрагментам перерабатываемой информации;

• параллелизм;

• асинхронность;

• возможность обработки информации с помощью операций высокого уровня.

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

1) линейный характер перерабатываемых информационных конструкций, линейный характер связи между элементами памяти и структурно фиксированный характер изменения состояния памяти;

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

3) последовательный характер переработки;

4) синхронный, т.е. основанный на централизованном управлении, характер организации обработки информации;

5) низкий уровень операций обработки информации.

Подробнее о перечисленных свойствах классических моделей обработки информации см. в работе [129] Известными примерами графодинамических моделей обработки информации, в частности, являются алгоритмы Колмогорова [259] (К о л м о г о р о в А. Н.. 1 9 5 8 с т - к О п р е д А ), вегетативная машина Борщева [64] (Б о р щ е в В. Б. 1 9 8 9 с т - В е г е т М ), всевозможные графовые грамматики [379; 376; 377; 378] 1.1.1. Понятие формальной модели обработки информации К л ю ч е в ы е п о н я т и я : формальная модель обработки информации, первичные элементы, синтаксические правила, начальная информационная конструкция, операции формальной модели, формальная модель, язык, абстрактная машина.

Приведем классическое определение формальной модели.

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

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

P – множество синтаксических правил формальной модели, которые определяют множество синтаксически правильных (правильно построенных) информационных конструкций (конструктивных объектов), перерабатываемых в рамках данной формальной модели;

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

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

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

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

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

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

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

О п р е д е л е н и е 1. 1. 1. 2. Формальная модель F задается тройкой где L – язык формальной модели F с присущими ему синтаксисом и семантикой;

S – начальная информационная конструкция формальной модели F, которая должна принадлежать языку L ;

C – абстрактная машина обработки информации, определяющая операции (правила преобразования) конструкций языка L. Множество операций абстрактной машины C в точности соответствует множеству операций формальной модели, которое в определении 1.1.1.1 обозначено символом W.

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

Приведенное определение формальной модели обработки информации условно разбивает модель обработки информации на модель представления информации и модель преобразования информации (модель манипулирования информационными конструкциями).

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

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

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

Рассматриваемая нами трактовка формальной модели дает возможность четко выделить три этапа разработки конкретных формальных моделей:

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

• разработка абстрактной машины (машины реализации хранимых программ или машины переработки знаний);

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

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

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

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

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

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

Если начальная информационная конструкция формальной модели включает в себя фактографические (экстенсиональные) знания, относящиеся к некоторой предметной области, и знания о свойствах и законах этой предметной области (интенсиональные знания) [242] (К а н д р а ш и н а Е. Ю.. 1 9 8 9 к н П р е д с З о В и П ), а операциями формальной модели являются операции переработки знаний, то соответствующую формальную модель будем называть формальной моделью переработки знаний. Такие операции могут поддерживать самые различные стратегии решения задач (стратегии рассуждений) – классические и неклассические, дедуктивные и индуктивные, четкие и нечеткие, строгие и правдоподобные. Частным видом формальных моделей переработки знаний являются формальные модели логического вывода.

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

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

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

Если перерабатываемые информационные конструкции являются цепочками (строками) символов, т.е.

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

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

Третьим признаком классификации формальных моделей является характер возможных преобразований перерабатываемых информационных конструкций – возможность изменения связей между элементами этих конструкций. По этому признаку формальные модели делятся на формальные модели переработки структурно фиксированных информационных конструкций и формальные модели переработки структурно перестраиваемых информационных конструкций.

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

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

К л ю ч е в ы е п о н я т и я : интеграция, интерпретация.

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

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

Интеграция формальных моделей в общем случае предполагает:

перекодировку начальных информационных конструкций интегрируемых моделей;

• соединение перекодированных начальных информационных конструкций;

• преобразование каждой операции интегрируемой модели в эквивалентную операцию интегрированной формальной модели.

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

Интерпретация произвольной формальной модели сводится:

к выбору некоторого языка программирования;

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

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

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

1.1.4. Семиотические модели обработки информации К л ю ч е в ы е п о н я т и я : семиотическая модель, метаоперация, метаязык, семиотическая абстрактная машина.

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

Такие модели называются семиотическими моделями или семиотическими системами [392] Семиотические модели носят открытый, гибкий, легко перестраиваемый, модифицируемый, самоизменяемый, адаптируемый, эволюционируемый, немонотонный, динамический характер.

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

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

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

W F – метаоперации (метаправила) модификации семейства формальных моделей, определяющих текущее состояние семиотической модели. Эти метаоперации обеспечивают: 1) перевод пассивных формальных моделей в активное состояние; 2) перевод активных формальных моделей в пассивное состояние; 3) ликвидацию формальных моделей; 4) синтез новых или модификацию имеющихся формальных моделей.

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

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

Одним из вариантов реализации семиотической модели M = ( F S, W F ) является построение формальной метамодели F = ( L, S, C ), обеспечивающей интерпретацию семиотической модели M. Построение формальной метамодели F включает в себя:

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

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

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

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

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

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

Недостатки, обычно приписываемые сетевым моделям [120] (Г е о р г и е в В. О. 1 9 9 3 с т М о д е л П З ), относятся не столько к самим моделям, сколько к сложностям их реализации на традиционных (фон-Неймановских) компьютерах. Если же вести речь о специальных графодинамических компьютерах, ориентированных на реализацию графодинамических моделей, то преимущество моделей такого класса становится очевидным, ибо их выразительные возможности намного превышают возможности других моделей. Тем более, что графодинамические модели представления и переработки знаний не являются альтернативой фреймовым, логическим и продукционным моделям, поскольку вполне могут существовать графодинамические фреймовые модели (в рамках которых фреймы представляются в виде графовых конструкций), графодинамические логические модели (в рамках которых логические высказывания представляются в виде графовых конструкций, а логический вывод рассматривается как манипуляция такими конструкциями), графодинамические продукционные модели (в рамках которых перерабатываемая продукциями информация и сами продукции представляются в виде графовых конструкций). Более того, в рамках графодинамической парадигмы легко представить себе комплексные модели, сочетающие в себе и фреймовые, и логические, и продукционные аспекты, т.е.

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

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

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

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

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

Графодинамическая парадигма является также единственно возможной основой для развитых форм ассоциативного доступа к хранимой в памяти информации [269] (К о х о н е н Т. 1 9 8 0 к н - А с с о ц П ).Как известно, без развитых форм ассоциативного доступа к требуемым фрагментам перерабатываемой сложноструктурированной информации, имеющим произвольный размер, произвольную конфигурацию и произвольную "привязку" к остальной части хранимой информации, невозможна реализация наиболее перспективных моделей параллельной переработки сложноструктурированной информации – Резюме к подразделу 1. Завершая данный подраздел, отметим следующее.

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

• графодинамические модели легко поддерживают развитые формы ассоциативного доступа;

графодинамические модели легко поддерживают параллельную реализацию операций;

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

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

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

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

2. Преимущество графовых средств представления информации по сравнению с символьными средствами и преимущество графодинамических моделей обработки информации отмечается в целом ряде работ. "Всякий раз, когда с задачей удается связать граф, обсуждение резко упрощается и большие фрагменты словесного описания заменяются манипуляциями с картинками" [317] 3. В основе графодинамических моделей обработки информации лежит понятие графового языка, подробно рассматриваемое в подразделе 1.2, и понятие графодинамической абстрактной машины, подробно рассматриваемое в подразделе 1.3.

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

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

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

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

1.2. Графовые языки К л ю ч е в ы е п о н я т и я : графовый язык, графовая структура, реляционная структура.

В данном подразделе рассматриваются основные понятия, связанные с нетрадиционным классом языков – классом графовых языков, текстами которых являются графовые структуры.

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

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

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

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

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

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

Для уточнения понятий сложноструктурированной предметной области и сложноструктурированной информационной структуры вводится понятие реляционной структуры. Это понятие является обобщением классического понятия алгебраической модели [316] (М а л ь ц е в А. И. 1 9 7 0 к н - А л г е б С ), а также таких понятий, как клубная система [65] (Б о р щ е в В. Б. 1 9 8 3 с т - С х е м ы Н К С ), гиперсеть [385] Реляционные структуры позволяют работать со структурами существенно более сложного вида, чем алгебраические модели, – иерархическими, многоуровневыми структурами.

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

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

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

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

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

Следует четко отличать понятие самого множества (как математической конструкции) от понятия знака множества. Знак одного множества может быть элементом другого множества. Кроме того, знак множества может быть одним из элементов того множества, которое он сам обозначает.

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

Атрибут a _ кортежа t задается знаком атрибута a _, перечнем его элементов, каждый из которых является парой отношения принадлежности, связывающего знак кортежа t с его элементами, имеющими атрибут a _, семейством пар отношения принадлежности, связывающих знак атрибута a _ с каждым его элементом.

Элементами кортежей могут быть объекты любой природы. В общем случае кортежу принадлежит несколько элементов. Элемент, принадлежащий одному кортежу, может принадлежать другому кортежу.

Элементы кортежа могут входить в его состав многократно. Знак одного кортежа может быть элементом другого кортежа. Более того, знак кортежа может быть одним из элементов того кортежа, который он сам обозначает.

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

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

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

Кортеж, имеющий элементы c 1, c 2,..., c n, атрибутами которых в рамках данного кортежа соответственно являются a 1 _, a 2 _,..., a n _, в символьной записи будем представлять следующим образом: ( a 1 _ : c 1, a 2 _ : c 2,..., a n _ : c n ). При этом кортежи классического вида, атрибутами которых являются номера их компонентов, т.е. кортежи ( 1 _ : c 1, 2 _ : c 2,..., n _ : c n ), будем представлять также и общепринятым образом: ( c 1, c 2,..., c n ).

У т в е р ж д е н и е 1. 2. 1. 1. Любой кортеж можно представить в виде классического кортежа, т.е.

кортежа, атрибутами которого являются номера его элементов.

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

Кортежи друг от друга могут отличаться:

1) набором атрибутов (классические кортежи, неклассические кортежи с числовыми атрибутами, неклассические кортежи с нечисловыми атрибутами);

2) количеством элементов (унарные, бинарные, тернарные кортежи и т.д.);

3) наличием или отсутствием элементов, имеющих одинаковые атрибуты;

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

5) наличием или отсутствием элементов кортежа, являющихся одновременно атрибутами этого же кортежа;

6) тем, является ли знак кортежа элементом обозначаемого им кортежа.

A, определяется рекурсивно на основе следующих утверждений:

1) P H. Элементы множества P будем называть первичными (терминальными) элементами универсума H. Само множество P будем называть базовым множеством универсума H ;

2) A H ; A P =. Множество A формально трактуется как множество знаков атрибутов;

3) если h i есть подмножество универсума H ( h i H ), то знак этого подмножества также является элементом универсума H ;

4) если h i есть произвольный элемент универсума H ( h i H ), а a i _ есть произвольный элемент множества A ( a i _ A ), то знак одноэлементного (унарного) кортежа ( a i _ : h i ) также является элементом универсума H ;

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

6) никаких других элементов множество H не содержит.

Таким образом, в состав универсума H входят следующие элементы:

• первичные (терминальные) элементы;

• знаки атрибутов, которые следует отличать от самих атрибутов;

• вторичные (производные) элементы, являющиеся знаками множеств, состоящих только из первичных элементов универсума, – такие множества будем называть простыми;

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

• вторичные элементы, являющиеся знаками множеств, в состав которых входит хотя бы один вторичный элемент (знак множества или знак кортежа), – такие множества будем называть метамножествами;

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

Завершая рассмотрение понятия универсума, отметим то, что это понятие можно считать обобщением известного понятия шкалы множеств [77] (Б у р б а к и Н. 1 9 6 5 к н - Т е о р и М ).

О п р е д е л е н и е 1. 2. 1. 2. Пусть h i, h j – произвольные элементы универсума. Будем говорить, что h j принадлежит h i в том, и только в том случае, если либо h j есть элемент множества, знаком которого является h i, либо h j есть элемент кортежа, знаком которого является h i.

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

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

1) если h j принадлежит вторичному элементу h i, то h j подчинен элементу h i ;

2) если h j подчинен элементу h i, а h k подчинен элементу h j, то h k подчинен элементу Теперь перейдем к определению понятия реляционной структуры.

О п р е д е л е н и е 1. 2. 1. 3. Реляционная структура G задается кортежем:

где P – множество первичных элементов реляционной структуры G (которые в рамках этой структуры отмечаются атрибутом p r i m a r y E l _ );

A – множество знаков атрибутов реляционной структуры G (которые в рамках этой структуры отмечаются атрибутом a t t r _ );

K – множество знаков связок реляционной структуры G (которые в рамках этой структуры отмечаются атрибутом c o n n _ );

R – множество знаков отношений реляционной структуры G (которые в рамках этой структуры отмечаются атрибутом r e l _ ). Знаки связок и знаки отношений реляционной структуры будем называть вторичными элементами этой структуры;

D – множество элементов неопределенного типа реляционной структуры G (которые в рамках этой структуры не имеют атрибутов).

При этом должны выполняться следующие условия:

• множества P, A, K, R, D попарно не пересекаются;

вторичные элементы реляционной структуры G представляют собой знаки множеств или кортежей и являются вторичными элементами универсума H, построенного на множестве P с атриR ) H. Это условие назовем свойством иерархичности реляционных структур, которое заключается в том, что элементами вторичных элементов реляционной структуры являются элементы (в том числе и вторичные элементы) этой же реляционной структуры;

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

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

Множество K знаков связок реляционной структуры разбивается на два подмножества: