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 входят следующие элементы:
• первичные (терминальные) элементы;
• знаки атрибутов, которые следует отличать от самих атрибутов;
• вторичные (производные) элементы, являющиеся знаками множеств, состоящих только из первичных элементов универсума, – такие множества будем называть простыми;
• вторичные элементы, являющиеся знаками кортежей, состоящих только из первичных элементов универсума, – такие кортежи будем называть простыми;
• вторичные элементы, являющиеся знаками множеств, в состав которых входит хотя бы один вторичный элемент (знак множества или знак кортежа), – такие множества будем называть метамножествами;
• вторичные элементы, являющиеся знаками кортежей, в состав которых входит хотя бы один вторичный элемент, – такие кортежи будем называть метакортежами.
О п р е д е л е н и е 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 знаков связок реляционной структуры разбивается на два подмножества:
где S – множество знаков неупорядоченных связок реляционной структуры G, которым в рамках этой конструкции приписывается атрибут c o n n S e t _ ;
T – множество знаков упорядоченных связок (кортежей) реляционной структуры G, которым в рамках этой структуры приписывается атрибут c o n n T u p l e _.
Вторичные элементы, знаки которых принадлежат множеству S R, будем называть множествами реляционной структуры G.
Множество реляционной структуры – это множество, которое целиком, как математическая структура, входит в состав (является фрагментом) этой реляционной структуры. Это означает, что в состав указанной реляционной структуры входят знак указанного множества, все элементы этого множества, все пары отношения принадлежности, связывающие знак множества с его элементами.
Кортеж реляционной структуры – это кортеж, который целиком, как математическая структура, входит в состав (является фрагментом) этой реляционной структуры вместе со всеми его элементами, со знаками всех используемых им атрибутов и со всеми соответствующими ему парами отношения принадлежности.
Атрибут реляционной структуры – это атрибут, используемый по крайней мере одним кортежем, входящим в состав указанной реляционной структуры.
Первичный элемент реляционной структуры – это такой элемент, который не является ни знаком множества, целиком входящего в состав указанной реляционной структуры, ни знаком кортежа, целиком входящего в состав этой структуры, ни знаком атрибута такого кортежа. Знаки множеств, знаки кортежей и знаки атрибутов могут быть первичными элементами реляционной структуры, но в этом случае соответствующие множества и кортежи как математические структуры не считаются фрагментами указанной реляционной структуры. Даже если в число первичных элементов реляционной структуры входит знак некоторого множества, а также все элементы этого множества, то считается, что пары отношения принадлежности, связывающего знак указанного множества с его элементами, в состав указанной реляционной структуры не входят.
Отношение реляционной структуры – это специально выделенное (чаще всего бесконечное) множество реляционной структуры.
Следует подчеркнуть, что пары отношения принадлежности, связывающие знаки атрибутов реляционной структуры и вторичные элементы реляционной структуры с элементами обозначаемых ими множеств или кортежей, входят в состав реляционной структуры, хотя формально ее элементами не являются.
О п р е д е л е н и е 1. 2. 1. 4. Пусть r – одно из отношений некоторой реляционной структуры и пусть элементами этого отношения являются вторичные элементы указанной реляционной структуры.
Тогда множество m будем называть областью определения отношения r в том и только в том случае, если выполняются следующие условия:
1) каждый элемент кортежа, принадлежащего отношению r, является элементом множества m ;
2) каждый элемент множества, принадлежащего отношению r, является элементом множества m ;
3) каждый элемент множества m является либо элементом некоторого кортежа, принадлежащего отношению r, либо элементом некоторого множества, принадлежащего отношению r.
В область определения отношения могут входить не только первичные элементы и элементы неопределенного типа, но и вторичные элементы реляционной структуры, если среди кортежей или множеств, принадлежащих отношению r, имеются метакортежи или метамножества.
О п р е д е л е н и е 1. 2. 1. 5. Множество l будем называть проекцией отношения r по атрибуту a в том и только в том случае, если:
1) каждый элемент с атрибутом a кортежа, принадлежащего отношению r, является элементом множества l ;
Отношения реляционной структуры бывают классическими (простыми) и неклассическими.
Классическое отношение r представляет собой подмножество декартова произведения P P. P, где P – множество первичных элементов, т.е. r P P. P.
Если количество сомножителей равно 1, т.е. r P, то классическое отношение называется унарным. Если количество сомножителей равно 2, т.е. r P P, то классическое отношение называется бинарным. Если количество сомножителей равно 3, т.е. r P P P, то классическое отношение называется тернарным и т.д.
Следовательно, классическое отношение – это либо некоторое множество первичных элементов ( r P ), либо некоторое множество простых (т.е. состоящих из первичных элементов) кортежей, состоящих при этом из одинакового количества элементов, которым ставятся в соответствие одинаковые наборы атрибутов (натуральные числа от 1 до n, где n – количество элементов кортежа).
Неклассические отношения реляционной структуры отличаются от классических следующим:
элементами неклассического отношения могут быть элементы реляционной структуры разного типа (в частности, неклассическому отношению могут одновременно принадлежать как первичные элементы, так и знаки кортежей с разным количеством элементов, знаки множеств с разным количеством элементов, в том числе знаки отношений, а также знаки атрибутов);
• элементами неклассического отношения могут быть не только знаки простых кортежей, элементами которых являются первичные элементы реляционной структуры, но и знаки метакортежей, среди элементов которых имеется хотя бы один вторичный элемент реляционной структуры. Кроме того, элементами неклассических отношений могут быть знаки как простых множеств, так и метамножеств;
элементами неклассического отношения могут быть не только знаки кортежей, в которых каждому элементу соответствует свой атрибут, но и знаки кортежей, в которых некоторые элементы имеют одинаковые атрибуты, не имеют атрибутов или имеют несколько атрибутов;
элементами неклассического отношения могут быть не только знаки классических кортежей, но и знаки кортежей, для которых набор атрибутов представляет собой произвольный набор натуральных чисел, а также знаки кортежей, в которых в качестве атрибутов используются не только натуральные числа.
Отношения, в область определения которых могут входить знаки отношений, а элементами могут быть знаки метакортежей и метамножеств, будем называть метаотношениями.
Реляционные структуры могут быть самыми разными в зависимости от того, какие отношения входят в их состав и как эти отношения связаны друг с другом. Важными характеристиками здесь являются арность, симметричность, однозначность и область определения отношений (так, например, одно отношение реляционной структуры может полностью или частично входить в область определения другого отношения).
Переход от классических реляционных структур к неклассическим (сложноструктурированным) реляционным структурам – это переход к иерархическим, многоуровневым структурам, в которых имеют место связи не только между первичными элементами, но и между связями, а также между целыми конструкциями. Это обстоятельство является очень важным при представлении знаний в интеллектуальных системах, ибо в них часто приходится иметь дело со сложноструктурированными, иерархическими предметными областями.
Особо отметим то, что знак кортежа, представляющего некоторую реляционную структуру, может входить в число вторичных элементов другой реляционной структуры, которую будем называть реляционной метаконструкцией. Более того, в число отношений реляционной метаконструкции может входить отношение «быть знаком реляционной структуры» (т.е. быть знаком кортежа, представляющего реляционную структуру). Таким образом, наша трактовка реляционной структуры позволяет, не выходя за рамки реляционной структуры, описывать сами реляционные структуры и связи между ними.
Примерами реляционных метаконструкций являются структуры, описывающие всевозможные морфизмы между реляционными структурами. Каждый такой морфизм – это соответствие между множествами элементов двух реляционных структур, удовлетворяющее тем или иным свойствам. Важнейшими примерами морфизмов являются гомоморфизмы и изоморфизмы.
О п р е д е л е н и е 1. 2. 1. 6. Пусть G 1 – реляционная структура, представляющая собой кортеж, множество элементов которого в соответствии с их атрибутами разбивается на семейство подмножеств ( P 1, A 1, K 1, R 1, D 1 ), а G 2 – реляционная структура, представляющая собой кортеж, множество элементов которого разбивается на семейство подмножеств ( P 2, A 2, K 2, R 2, D 2 ) (см. определение 1.2.1.3). Соответствие между множеством элементов реляционной структуры G 1 и множеством элементов реляционной структуры G 2 будем называть гомоморфизмом в том и только в том случае, если оно удовлетворяет следующим условиям:
Здесь x *, a *, k *, r *, d * есть образы элементов x, a, k, r, d в рамках рассматриваемого соответствия.
О п р е д е л е н и е 1. 2. 1. 7. Реляционная структура G 1 гомоморфна реляционной структуре G 2 в том и только в том случае, если существует гомоморфизм между ними.
О п р е д е л е н и е 1. 2. 1. 8. Соответствие между множеством элементов реляционной структуры G 1 и множеством элементов реляционной структуры G 2 будем называть изоморфизмом в том и только в том случае, если оно является гомоморфизмом между G 1 и G 2, а также гомоморфизмом между G 2 и G 1.
О п р е д е л е н и е 1. 2. 1. 9. Реляционные структуры G 1 и G 2 изоморфны в том и только в том случае, если существует изоморфизм между ними.
Наряду с понятием реляционной структуры введем понятие нестационарной реляционной структуры, т.е. реляционной структуры, изменяющейся во времени. В этом смысле обычные реляционные структуры можно назвать стационарными. Для нестационарных реляционных структур вводится понятие ситуативного отношения, т.е. отношения, которое в разных состояниях нестационарной реляционной структуры состоит из разных элементов (разных кортежей, разных множеств или разных первичных элементов).
Важнейшим приемом описания нестационарной реляционной структуры является ее представление в виде обычной (стационарной) реляционной метаконструкции, описывающей соотношение во времени между различными состояниями нестационарной реляционной структуры, каждое из которых описывается конкретной стационарной реляционной структурой. Состояние нестационарной реляционной структуры будем также называть ситуациями этой структуры. Таким образом, описание нестационарных реляционных структур также приводит к сложноструктурированным иерархическим реляционным структурам.
Важно подчеркнуть, что при создании сложных интеллектуальных систем обычно приходится иметь дело именно с неклассическими сложноструктурированными иерархическими реляционными структурами самого разного вида, и в частности с реляционными метаконструкциями.
1.2.2. Линейные тексты К л ю ч е в ы е п о н я т и я : линейный текст, символьная конструкция.
Перейдем к рассмотрению информационных конструкций, которые представляют собой реляционные структуры, описывающие структуру информационных объектов, т.е. объектов, которые сами являются описаниями каких-либо предметных областей. Никаких ограничений на структуру информационных объектов не накладывается и, соответственно этому, не накладывается никаких ограничений и на структуру информационных конструкций. Единственное, что в информационных конструкциях невозможно, – это то, чтобы их первичными элементами были предметы описываемой предметной области.
Первичными элементами информационных конструкций могут быть не сами предметы описываемой предметной области, а их знаки. Первичными элементами информационных конструкций могут быть также символы, из которых строятся знаки предметов описываемой предметной области.
В данном пункте рассматривается один из видов информационных конструкций – линейные тексты (символьные информационные конструкции), называемые также символьными конструкциями, линейными информационными конструкциями, цепочечными информационными конструкциями, цепочками символов, строками символов, которые являются традиционным видом информационных конструкций.
О п р е д е л е н и е 1. 2. 2. 1. Пусть G s – информационная конструкция, задаваемая кортежем, множество элементов которого в соответствии с их атрибутами разбивается на семейство подмноP s, A s, K s, R s, D s ) (см. определение 1.2.1.3). Информационную конструкцию жеств G s будем называть символьной конструкцией в том и только в том случае, если выполняются следующие условия:
< K s >, где R p есть семейство унарных отношений, заданных на множестве P s ;
Первичные элементы символьной конструкции (т.е. элементы множества P s ) будем называть символами. Каждый бинарный асимметричный кортеж, принадлежащий множеству K s, есть связь непосредственного соседства символов в строке. При этом атрибут “ 1 _ ” указывает на предшествующий символ, а атрибут “ 2 _ ” указывает на последующий символ. Унарные отношения, входящие в состав R p, будем называть типами символов, а все семейство унарных отношений R p будем называть алфавитом символов.
На множестве символьных конструкций задается целый ряд отношений – отношение равенства, отношение включения, отношение конкатенации.
Символьные конструкции равны, если 1) они изоморфны, 2) у них совпадают алфавиты символов, 3) типы символов в рамках указанного изоморфизма соответствуют сами себе. Очевидно, что множество всевозможных символьных конструкций может быть разбито на классы равных символьных конструкций.
Символьная конструкция, определяемая семейством множеств ( P s, A s, K s, R s, D s ), связная, если симметризация и транзитивное замыкание отношения < K s >приводят к декартову произведению P s P s.
Символьная конструкция, определяемая семейством множеств ( P s, A s, K s, R s, D s ), является результатом конкатенации связных символьных конструкций, определяемых семейством множеств ( P s i, A s i, K s i, R s i, D s i ) и семейством множеств i – самый правый символ первой символьной конструкции;
j – самый левый символ второй символьной конструкции.
Утверждение 1. 2. 2.1. Любую реляционную структуру можно представить в виде эквивалентного линейного текста.
Существует большое число способов (языков) представления (кодирования) произвольных реляционных структур в виде символьных конструкций. Определим один из таких языков, который условно назовем L r s. Этот язык является прообразом формального языка SCBs, который подробно рассмотрен ниже в разделе 2.
О п р е д е л е н и е 1. 2. 2. 2. Будем утверждать, что реляционная структура, задаваемая семейством множеств ( P, A, K, R, D ), и символьная конструкция, принадлежащая языку L r s и определяемая семейством множеств ( P s, A s, K s, R s, D s ), эквивалентны тогда, и только тогда, когда существует взаимно однозначное соответствие между множеством P A K R D (множеством всех элементов исходной реляционной структуры) и некоторым множеством S, каждый элемент которого представляет собой множество равных символьных конструкций, входящих в состав конструкции ( P s, A s, K s, R s, D s ) и являющихся идентификаторами (именами) соответствующих элементов исходной (представляемой) реляционной структуры. При этом должны выполняться следующие условия:
r *, y * S, r * и y * – идентификаторы элементов y и r ;
ствуют элементы реляционной структуры y r, r R, для которых r * и y * являются идентификаторами;
3) если связка k, k K является неупорядоченной и состоит из элементов y 1, y 2. y n, т.е. y 1, y 2. y n k, то в символьной конструкции присутствует строка вида 4) если в символьной конструкции присутствует строка вида k * k *, y 1 *, y 2 *. y n * S, то в реляционной структуре существует неупорядоченная связка k, k K, состоящая из элементов y 1, y 2. y n, y 1, y 2. y n k, для которых y 1 *, y 2 *. y n * являются идентификаторами, k * является идентификатором элемента k ;
Рассмотренные символьные конструкции противопоставляются графовым структурам, к числу которых будем относить все информационные конструкции, не являющиеся символьными. При определении графовых структур не уточняется, что из себя представляют первичные элементы этих структур, как конкретно выглядят связки графовых структур. Уточнение всего этого приводит к самым различным вариантам представления и изображения графовой структуры. Так, например, можно говорить о матричных представлениях (матрицы смежности, матрицы инцидентности), о списковых, о графических (топологических) представлениях.
1.2.3. Нелинейные тексты К л ю ч е в ы е п о н я т и я : бинарная информационная конструкция, отношение принадлежности, однородная информационная конструкция.
Если рассматривать информационные конструкции, являющиеся реляционными структурами общего вида, как способ представления информации в памяти систем обработки информации, то следует отметить недостаточный конструктивизм такого представления, ибо трудно построить соответствие между элементами реляционной структуры общего вида и элементами абстрактной или реальной памяти, в которой эта структура может храниться и преобразовываться. Для того чтобы иметь такое соответствие, нужно ограничить (а в идеале – зафиксировать) набор атрибутов и отношений информационной конструкции, не нарушая при этом семантической мощности. Перейдем к частным видам информационных конструкций, удовлетворяющим данному требованию.
О п р е д е л е н и е 1. 2. 3. 1. Информационную конструкцию G g, описывающую реляционную структуру G и представляющую собой кортеж, множество элементов которого в соответствии с их атрибутами разбивается на семейство подмножеств ( P g, A g, K g, R g, D g ), будем называть бинарной информационной конструкцией, если выполняются следующие условия:
1) элементы множества P g взаимно однозначно соответствуют элементам описываемой реляционной структуры G. Каждый элемент множества P g, т.е. каждый первичный элемент структуры G g, считается семантически эквивалентным соответствующему элементу описываемой реляционной структуры G ;
3) связки реляционной структуры G g представляют собой бинарные кортежи, имеющие вид множество K g может входить несколько раз (такие кортежи называются кратными). От множества K g можно перейти ко множеству K g *, K g * P g ( P g K g * D g ), оставив для каждой группы кратных кортежей по одному представителю;
R i, где R t – множество знаков унарных отношений (для каждого r R t имеет место r ( P g D g ) ), R i – множество знаков бинарных отношений (для каждого r R i имеет место r K g ). Унарные отношения будем также называть метками первичных и неопределенных элементов бинарной информационной конструкции.
Если элемент описываемой реляционной структуры есть ее первичный элемент, представляющий собой некий предмет соответствующей предметной области, то семантическим эквивалентом этого элемента в бинарной информационной конструкции является знак указанного предмета. Если элемент описываемой реляционной структуры есть знак множества или кортежа (атрибуты и отношения считаются частными видами множеств), то семантическим эквивалентом этого элемента в бинарной информационной конструкции является знак семантически эквивалентного множества или кортежа, т.е. множества или кортежа, состоящего из тех, и только тех элементов бинарной информационной конструкции, которые семантически эквивалентны элементам указанного выше множества или кортежа, входящего в состав описываемой реляционной структуры.
У т в е р ж д е н и е 1. 2. 3. 1. Каждую реляционную структуру можно представить в виде эквивалентной бинарной информационной конструкции.
Доказательство этого утверждения сводится к построению алгоритма, обеспечивающего для произвольной реляционной структуры построение эквивалентной бинарной информационной конструкции, а также к построению обратного алгоритма, обеспечивающего для произвольной бинарной информационной конструкции построение эквивалентной реляционной структуры общего вида.
Дадим определение эквивалентности реляционных структур общего вида и бинарных информационных конструкций, на основании которого указанные алгоритмы легко могут быть получены.
О п р е д е л е н и е 1. 2. 3. 2. Пусть G – реляционная структура, представляющая собой кортеж, определяемый семейством множеств ( P, A, K, R, D ), а G g – бинарная информационная конструкция, представляющая собой кортеж, определяемый семейством множеств ( P g, A g, K g, R g, D g ), удовлетворяющих следующим условиям:
2) A g = < 1 _, >(по определению бинарной конструкции);
где p – отношение принадлежности элемента множеству;
Будем говорить, что реляционная структура G и бинарная информационная конструкция G g эквивалентны тогда и только тогда, когда существуют взаимно однозначные соответствия между P и ( R t r R g ), между D и P d ( P d P g ) и при этом выполняются следующие условия:
1) если x r, r R, то x * r *, r * R t r и наоборот. Здесь x *, r * – образы объектов x, r в рамках указанных соответствий;
2) если в рамках реляционной структуры имеет место x k, k K, где k – вторичный элереляционной структуры, являющийся множеством, то k * P k, x * P g, 3) если в рамках реляционной структуры имеет место k K, a A, k = (. a : x. ), Здесь x *, a *, k * – образы объектов x, a, k в рамках указанных соответствий.
Элементы множества P g будем называть узлами бинарной информационной конструкции, а элементы множества K g – дугами бинарной информационной конструкции. Элементы множества P v – знаки первичных элементов исходной реляционной структуры, элементы множества P d – знаки элементов неопределенного типа исходной реляционной структуры, элементы множества P k – знаки связок (упорядоченных или неупорядоченных) исходной реляционной структуры. Подчеркнем, что здесь имеется в виду не связка бинарной конструкции, а связка эквивалентной реляционной структуры общего вида, которая сама в бинарную конструкцию не входит, а входит знак (имя) этой связки.
Как было отмечено, отношение p трактуется как отношение принадлежности элемента множеству.
Каждое из остальных отношений, входящих в семейство R i, есть отношение принадлежности элемента кортежу под определенным атрибутом (каждому такому отношению соответствует свой атрибут принадлежности). Итак, переход от реляционной структуры общего вида к эквивалентной бинарной конструкции суть:
1) замена первичных элементов и элементов неопределенного типа на их знаки;
2) сведение произвольного набора атрибутов к двум атрибутам;
3) сведение вторичных элементов произвольного вида к бинарным кортежам;
4) сведение произвольного набора отношений к унарным и бинарным отношениям.
В процессе такого перехода атрибуты исходной реляционной структуры «превращаются» в соответствующие отношения принадлежности, вторичные элементы – в первичные, отношения исходной реляционной структуры – в унарные отношения, элементы неопределенного типа – в первичные.
Нетрудно заметить, что рассмотренный переход от реляционных структур общего вида к эквивалентным бинарным конструкциям есть своего рода декомпозиция реляционных структур, в результате чего неявно заданное в реляционной структуре общего вида отношение принадлежности, скрытое внутри вторичных элементов реляционной структуры (знаков множеств и знаков кортежей), приобретает в рамках бинарной конструкции явное очертание. Более того, отношение принадлежности со всеми его модификациями может интерпретироваться как топологическое присоединение (того или иного вида) одного элемента бинарной конструкции к другому. Это обстоятельство является очень важным, так как позволяет говорить не только об алгебраических и теоретико-множественных свойствах бинарных конструкций, но и об их топологических свойствах. Кроме того, простая топологическая интерпретация бинарных конструкций, в частности простая возможность их графического изображения, позволяет говорить о переработке бинарных конструкций более конструктивно, чем о переработке реляционных структур общего вида.
Так, например, первичным элементам бинарной информационной конструкции можно поставить в соответствие элементы памяти, в которой эта конструкция хранится и перерабатывается. Тогда набор унарных отношений, которым принадлежит первичный элемент (т.е. набор его меток), есть не что иное, как текущее состояние соответствующего ему элемента памяти. А набор дуг (пар) принадлежности, которыми первичный элемент связан с другими элементами, есть не что иное, как система связей, которыми соответствующий элемент памяти связан с другими элементами памяти в текущий момент времени. При этом в процессе переработки бинарной информационной конструкции в самом общем случае может происходить как изменение состояния элементов памяти, так и изменение связей между ними.
Переход от реляционных структур общего вида к эквивалентным бинарным информационным конструкциям можно считать одним из способов упрощения (канонизации) реляционных структур. Дальнейший анализ бинарных информационных конструкций на предмет их упрощения приводит к понятию однородных информационных конструкций – реляционных структур, не имеющих меток и имеющих единственное отношение (бинарное асимметричное отношение принадлежности).
О п р е д е л е н и е 1. 2. 3. 3. Информационную конструкцию G g, описывающую реляционную структуру G и представляющую собой кортеж, множество элементов которого в соответствии с их атрибутами разбивается на семейство подмножеств ( P g, A g, K g, R g, D g ), будем называть однородной информационной конструкцией, если выполняются следующие условия:
1) элементы множества P g взаимно однозначно соответствуют элементам описываемой реляционной структуры G. Каждый элемент множества P g, т.е. каждый первичный элемент конструкции G g, считается семантически эквивалентным соответствующему элементу описываемой реляционной структуры G ;
3) связки реляционной структуры G g представляют собой либо простые бинарные кортежи принадk Pk, q Pg, ( Pg = Pv P k P d ), либо бинарные метакортежи принадлежности, имеющие вид ( 1 _ : k, 2 _ : c ), где k P k, c K g. При этом кортеж c может быть как простым кортежем, так и метакортежем. Связки однородной конструкции будем называть дугами этой конструкции (соответственно простыми дугами и метадугами);
4) R g = < K g >. Семейство отношений реляционной структуры G g включает в себя единственное отношение – отношение принадлежности, представляющее собой множество знаков всех бинарных асимметричных кортежей принадлежности.
У т в е р ж д е н и е 1. 2. 3. 2. Каждую бинарную информационную конструкцию можно представить в виде эквивалентной однородной информационной конструкции.
Иными словами, любую бинарную информационную конструкцию можно свести к реляционной структуре с единственным отношением – бинарным асимметричным отношением принадлежности.
Это утверждение легко доказывается на основании следующего определения эквивалентности бинарной информационной конструкции и однородной информационной конструкции.
О п р е д е л е н и е 1. 2. 3. 4. Пусть G g – бинарная информационная конструкция, представляющая собой кортеж, определяемый семейством множеств ( P g, A g, K g, R g, D g ), удовлетворяющих условиям:
Здесь p – отношение принадлежности элемента множеству, обозначаемому некоторым узлом в рамках исходной бинарной информационной конструкции;
а G q – однородная информационная конструкция, представляющая собой кортеж, определяемый семейством множеств ( P q, A q, K q, R q, D q ), удовлетворяющих условиям:
Здесь P q v – множество предметных узлов однородной конструкции, P q k – множество знаков множеств и знаков кортежей;
Будем говорить, что бинарная информационная конструкция G g и однородная информационная конструкция G q эквивалентны тогда и только тогда, когда существуют взаимно однозначные соотРаздел 1. 0B0BГрафодинамическая парадигма обработки информации рот. Здесь k *, x *, y * – образы объектов k, x, y в рамках указанных выше соответствий;
Итак, в результате перехода от бинарной информационной конструкции произвольного вида к однородной информационной конструкции каждое унарное отношение исходной бинарной информационной конструкции «превращается» в первичный элемент, являющийся знаком соответствующего множества первичных элементов, а каждое бинарное отношение r исходной бинарной информационной конструкции, относящееся к классу R i a, «превращается» в первичный элемент, являющийся знаком соответствующего множества пар (дуг) принадлежности, каждая из которых связывает знак некоторого кортежа исходной реляционной структуры общего вида с некоторым элементом указанного кортежа, имеющим в рамках этого кортежа атрибут, соответствующий отношению r.
Следует подчеркнуть то, что все вторичные элементы (дуги) однородной информационной конструкции имеют одинаковую и четкую теоретико-множественную интерпретацию. Каждая такая дуга связывает знак некоторого множества (из которого дуга выходит) с одним из элементов этого множества.
Если от однородной информационной конструкции осуществить точно такой же переход, какой мы осуществляли от произвольной реляционной структуры к эквивалентной бинарной информационной конструкции, то получится информационная конструкция, которую назовем предельной. В предельной информационной конструкции дуги (пары) принадлежности (как простые дуги, так и метадуги) будут сведены к кортежам инцидентности, каждый из которых связывает знак дуги принадлежности либо со знаком некоторого множества, либо с первичным элементом, принадлежащим этому множеству. Соответственно этому отношение принадлежности однородной информационной конструкции (не являющееся простым отношением) сводится к двум (простым) бинарным отношениям инцидентности. Одно из этих отношений связывает знаки дуг принадлежности со знаками множеств (т.е. с элементами, из которых эти дуги выходят). А каждая пара инцидентности, принадлежащая другому из этих отношений, связывает знак дуги принадлежности с первичным элементом предельной информационной конструкции, в который эта дуга входит, т.е. с элементом множества, обозначаемого первичным элементом, из которого указанная дуга выходит.
В основе дальнейшего рассмотрения графодинамических моделей обработки информации используются однородные информационные конструкции в силу того, что они имеют очень простую базовую семантическую интерпретацию, носящую теоретико-множественный характер и непосредственно не зависящую от описываемой предметной области.
О перспективности рассмотренных в данном пункте бинарных и однородных информационных конструкций свидетельствует большой интерес к бинарным представлениям (бинарным моделям) баз данных [80; 539;
401] Рассматривая соотношение произвольной описываемой реляционной структурой с некоторой эквивалентной символьной информационной конструкцией (см. определение 1.2.2.2), а также с эквивалентной бинарной информационной конструкцией (см. определение 1.2.3.2) и с эквивалентной однородной информационной конструкцией (см. определение 1.2.3.4), мы фактически определяем денотационную семантику произвольных информационных конструкций, относящихся 1) к одному из возможных символьных фактографических языков, 2) к графовому фактографическому языку бинарных информационных конструкций и 3) к графовому фактографическому языку однородных информационных конструкций.
Особенность перечисленных языков заключается в том, что, во-первых, все они являются фактографическими языками и, во-вторых, все они обеспечивают представление фактографической (экстенсиональной) информации о реляционных структурах любого вида. Графовый фактографический язык бинарных информационных конструкций и графовый фактографический язык однородных информационных конструкций относятся к классу графовых семантических языков, которые будут рассмотрены в пункте1.2.6.
1.2.4. Денотационная семантика текстов К л ю ч е в ы е п о н я т и я : денотационная семантика информационной конструкции, знак, Базовая семантическая информационная конструкция, семантическая сеть.
Каждый информационный объект является моделью (описанием) некоторой предметной области и, следовательно, имеет определенные связи с описываемой предметной областью. Внутренняя структура информационного объекта определяется соответствующей информационной конструкцией. Внутренняя структура предметной области определяется соответствующей реляционной структурой. Совокупность связей информационной конструкции с реляционной структурой, определяющей структуру описываемой предметной области, будем называть денотационной семантикой информационной конструкции.
Ключевым понятием денотационной семантики информационных конструкций является понятие знака.
Знак – это минимальный семантически значимый фрагмент информационной конструкции. Знак может быть представлен либо элементом информационной конструкции, либо фрагментом информационной конструкции, состоящим из нескольких элементов. Знак в рамках информационной конструкции представляет (заменяет, изображает) нечто из описываемой предметной области. Этим нечто может быть либо конкретный предмет (объект) описываемой предметной области, либо конкретная связь, имеющая место в описываемой предметной области (это может быть связь между объектами, другими связями, понятиями, фрагментами предметной области), либо конкретный фрагмент описываемой предметной области, либо конкретное понятие этой предметной области. То, что обозначается знаком, называется его денотатом или денотационной семантикой этого знака. Множество знаков, входящих в состав информационной конструкции, однозначно соответствует множеству своих денотатов, т.е. каждому знаку не может соответствовать несколько денотатов. При этом указанное соответствие между множеством знаков, входящих в информационную конструкцию, и множеством их денотатов не обязано быть взаимно однозначным. Таким образом, разные знаки могут иметь один и тот же денотат, т.е.
обозначать одно и то же. Такие знаки будем называть синонимичными.
Рассмотрение денотационной семантики информационных конструкций различного вида основано на понятии базовой семантической информационной конструкции.
О п р е д е л е н и е 1. 2. 4. 1. Базовая семантическая информационная конструкция – это такая информационная конструкция, которая изоморфна некоторому фрагменту реляционной структуры, определяющей структуру описываемой предметной области. Все элементы базовой семантической информационной конструкции являются знаками, семантически эквивалентными соответствующим элементам указанного представляемого (кодируемого) фрагмента реляционной структуры.
Информационная конструкция называется семантической информационной конструкцией или семантической сетью, если морфизм между этой конструкцией и семантически эквивалентной ей базовой семантической информационной конструкцией является взаимно однозначным соответствием между множествами элементов указанных конструкций:
1) каждый первичный элемент базовой семантической конструкции является знаком, обозначающим некоторый конкретный предмет описываемой предметной области и взаимно однозначно соответствующим этому предмету;
2) каждый знак связки базовой семантической конструкции обозначает некоторую конкретную связь, имеющую место в описываемой предметной области, и взаимно однозначно соответствует этой связи;
3) каждый знак атрибута базовой семантической конструкции взаимно однозначно соответствует некоторому относительному понятию (множеству однотипных ролей, выполняемых в рамках определенных связей соответствующими компонентами этих связей);
4) каждый знак отношения базовой семантической конструкции взаимно однозначно обозначает некоторое понятие описываемой предметной области (некоторое множество знаков аналогичных в том или ином смысле предметов или связей).
Конкретная связь, имеющая место в описываемой предметной области, не обязательно должна быть простой, т.е. не обязательно должна быть связью между предметами описываемой предметной обласРаздел 1. 0B0BГрафодинамическая парадигма обработки информации ти. В число связей описываемой предметной области входят также некоторые фрагменты этой предметной области, состоящие из некоторого количества предметов, некоторого количества связей. К числу связей относятся также и ролевые структуры (фреймы).
Построение базовой семантической информационной конструкции, соответствующей описываемой предметной области, является важнейшим этапом формального описания предметной области, а также важнейшим этапом формирования базы знаний.
В качестве примера рассмотрим базовую семантическую информационную конструкцию, соответствующую геометрии Евклида. Первичными элементами этой конструкции являются знаки конкретных геометрических точек, конкретных прямых, конкретных плоскостей. Вторичными элементами этой конструкции являются знаки конкретных отрезков, треугольников, окружностей и т.д. Каждая такая геометрическая фигура трактуется как множество точек, удовлетворяющее определенным требованиям. Вторичными элементами рассматриваемой информационной конструкции являются также знаки связей инцидентности, конгруэнтности; связей сравнения по длине, по площади, по объему; связей, каждая из которых связывает тройку точек, одна из которых лежит между двумя другими, и т.д. Отношениям рассматриваемой информационной конструкции соответствуют такие абсолютные понятия, как «быть геометрической точкой», «быть прямой», «быть отрезком», «быть треугольником», «быть инцидентными геометрическими фигурами», «быть конгруэнтными геометрическими фигурами» и т.д. Атрибутами рассматриваемой информационной конструкции являются такие относительные понятия, как «быть более длинной линией», «быть менее длинной линией», «быть точкой, лежащей между» и т.д.
Таким образом, построить базовую семантическую информационную конструкцию описываемой предметной области – это, прежде всего, сформировать понятийный аппарат указанной предметной области, что требует глубокого анализа этой предметной области.
В основе нашего рассмотрения денотационной семантики информационных конструкций лежит следующее свойство базовой семантической информационной конструкции.
У т в е р ж д е н и е 1. 2. 4. 1. Любую фактографическую информацию (любые экстенсиональные знания) о любой предметной области можно представить в виде фрагмента базовой семантической информационной конструкции.
Если от базовой семантической информационной конструкции перейти к эквивалентным информационным конструкциям частного вида, то получатся различные виды семантических конструкций – семантическая бинарная конструкция, семантическая однородная конструкция. Введенные семантические конструкции различного вида можно считать различными вариантами уточнения понятия семантической сети.
Если рассматривать множество информационных конструкций, эквивалентных некоторой базовой семантической информационной конструкции, то последнюю можно считать формальным уточнением денотационной семантики указанных конструкций.
Важнейшим свойством семантических конструкций различного вида является их ассоциативность, т.е.
наличие достаточно простой процедуры, позволяющей для любых объектов или связей описываемой предметной области выделить их окрестность по отношению принадлежности. Другими словами, ассоциативность семантических конструкций – это наличие простых процедур, с помощью которых легко находятся ответы на следующие вопросы:
• какими связями связан данный предмет с другими предметами;
• в каких связях заданный предмет выполняет заданную роль;
• какие предметы и под какими атрибутами участвуют в заданой связи;
• каким классам принадлежит заданный предмет или заданная связь;
• какими связями связано между собой некоторое число заданных предметов и (или) связей.
Такая ассоциативность семантических конструкций становится возможной благодаря тому, что каждый знак (знак какого-либо предмета, какой-либо связи, какого-либо понятия) в каждую семантическую конструкцию входит однократно.
Итак, семантическая конструкция есть такая информационная конструкция (общего или частного вида), в которой:
1) в качестве знаков используются элементы этой конструкции, а не более сложные ее фрагменты, состоящие из нескольких элементов;
2) отсутствует синонимия знаков, т.е. разные знаки не могут иметь совпадающие денотаты.
Очевидно, далеко не каждая информационная конструкция является семантической конструкцией.
Классическим примером несемантических информационных конструкций являются символьные конструкции (см. пункт 1.2.2.). Во-первых, знаки в символьной конструкции представлены идентификаторами – фрагментами символьной конструкции, состоящими в общем случае из нескольких символов. Это обусловлено тем, что алфавит символов в символьных конструкциях конечен и обычно состоит из небольшого числа унарных отношений, заданных на первичных элементах символьных конструкций, тогда как количество предметов, связей, понятий, обозначаемых знаками информационных конструкций, является, в общем случае, неограниченным. Во-вторых, в символьных конструкциях при описании нетривиальных предметных областей принципиально невозможно избежать синонимии знаков, т.е. многократного вхождения в символьную конструкцию знаков, обозначающих одно и то же.
Обычно синонимичные знаки в символьных конструкциях представляются равными (совпадающими, одинаковыми) строками символов. Неравные строки символов также могут быть синонимичными знаками. В символьных конструкциях встречаются омонимичные идентификаторы, т.е. идентификаторы, которые являются равными (совпадающими) строками символов, но имеют разную денотационную семантику.
В основе дальнейшего рассмотрения графодинамических моделей обработки информации будем использовать однородные информационные конструкции. Благодаря их однородности существенно сокращается номенклатура механизмов обработки этих конструкций на низших уровнях.
Первым семантическим свойством однородных информационных конструкций является то, что они имеют простую базовую семантическую интерпретацию, носящую теоретико-множественный характер и непосредственно не зависящую от описываемой предметной области. Каждый первичный элемент однородной информационной конструкции является либо знаком некоторого предмета описываемой предметной области (первичные элементы будем называть знаками предметов или предметными узлами), либо знаком некоторого множества, состоящего из первичных и (или) вторичных элементов однородной информационной конструкции. Таким образом, все первичные элементы (узлы) однородной информационной конструкции являются знаками двух типов: знаками предметов или знаками множеств. Причем элементами указанных множеств могут быть только первичные и вторичные элементы однородной информационной конструкции. Каждый вторичный элемент (дуга) однородной информационной конструкции является позитивным высказыванием о принадлежности некоторого первичного или вторичного элемента однородной информационной конструкции некоторому множеству, обозначаемому узлом, из которого указанная дуга выходит (т.е. тем узлом, который является первым компонентом этой дуги).
Вторым семантическим свойством однородных информационных конструкций является то, что они всегда представляют собой семантические информационные конструкции, причем даже тогда, когда они являются информационными метаконструкциями, описывающими структуру несемантических информационных конструкций. Так, например, переходя от символьной информационной конструкции к ее эквивалентному представлению в виде однородной информационной конструкции, эта символьная информационная конструкция «превращается» в семантическую сеть, которая описывает синтаксис указанной символьной конструкции и которую можно легко нарастить семантической сетью, аналогичным образом устроенной и описывающей семантику этой символьной конструкции.
Итак, однородные информационные конструкции всегда являются семантическими информационными конструкциями. При этом по семантическим признакам выделяется два класса однородных информационных конструкций:
1) однородные информационные конструкции, описывающие структуру (синтаксис) информационных конструкций, не являющихся семантическими. Денотатами (описываемыми предметными областяРаздел 1. 0B0BГрафодинамическая парадигма обработки информации ми) таких однородных метаконструкций являются реляционные структуры, определяющие внутреннюю структуру несемантических информационных конструкций;
2) однородные информационные конструкции, описывающие структуру семантических информационных конструкций, которые, в свою очередь, описывают произвольные предметные области. Денотатами таких однородных информационных конструкций можно считать как указанную семантическую информационную конструкцию, так и предметную область, описываемую этой семантической информационной конструкцией.
Исследуя семантические свойства информационных конструкций, можно говорить о фактографических и логических высказываниях (фактографических и логических информационных конструкциях). Фактографические высказывания непосредственно представляют структуру описываемой предметной области, т.е. представляют конкретные факты, имеющие место в описываемой предметной области. В отличие от этого логические высказывания представляют информацию о свойствах и законах описываемой предметной области. Благодаря этому появляется возможность компактного описания бесконечных предметных областей с помощью информационных конструкций, состоящих из конечного числа элементов.
Отличительными особенностями логических высказываний по сравнению с фактографическими являются:
1) появление логических переменных наряду со знаками конкретных предметов и связей предметной области (указанные знаки иногда называют логическими константами). Семантически каждая логическая переменная является знаком произвольного элемента из некоторого множества, которое может содержать как логические константы, так и логические переменные. Указанное множество элементов называют областью возможных значений соответствующей переменной;
2) появление простых (атомарных) высказываний и сложных (конъюнктивных, дизъюнктивных, импликативных) высказываний;
3) появление позитивных, негативных и нечетких высказываний;
4) появление кванторных высказываний, т.е. высказываний, свободные переменные которых связываются кванторами (кванторами существования, кванторами всеобщности и т.д.);
5) появление формальных теорий для стационарных и нестационарных предметных областей. Формальная теория – это конъюнктивное высказывание, изначально считающееся истинным. Соответственно этому позитивность, негативность и нечеткость компонентов (логических множителей) формальных теорий определяет истинные, ложные и неопределенные высказывания в рамках данной формальной теории.
Основным принципом представления информации о законах какой-либо предметной области (интенсиональных знаний о предметной области) является формальное рассмотрение законов не самой описываемой предметной области, а универсального фактографического высказывания, которое включает в себя всю фактографическую информацию описываемой предметной области. Таким образом, логические высказывания по своей сути являются информационными метаконструкциями, т.е. конструкциями, описывающими другие информационные конструкции.
Для расcмотренных выше информационных конструкций фактографического типа выделим следующие классы:
1) базовые семантические информационные конструкции;
2) семантические конструкции различного вида, не являющиеся базовыми (в первую очередь, однородные информационные конструкции);
3) символьные конструкции.
Совершенно аналогичные классы можно выделить и для информационных конструкций логического типа. Для этого в перечисленные фактографические высказывания необходимо дополнительно ввести средства представления логических переменных, логических связок, кванторов, высказываний, формальных теорий.
1.2.5. Классификация языков К л ю ч е в ы е п о н я т и я : символьный язык, графовый язык, семантический язык, сложноструктурированная предметная область, фактографический язык, логический язык, нестационарная предметная область, семантическая мощность языка.
С формальной точки зрения каждый конкретный язык представляет собой некоторое множество (являющееся бесконечным для практически интересных языков) информационных конструкций, которые имеют общие синтаксические свойства (т.е. общие принципы своего внутреннего устройства), а также общие денотационно-семантические свойства (т.е. общие принципы своего соотношения с описываемыми предметными областями). Общие синтаксические свойства информационных конструкций, принадлежащих языку, будем называть синтаксисом этого языка, а общие денотационно-семантические свойства информационных конструкций, принадлежащих языку, – денотационной семантикой этого языка. Синтаксис языка чаще всего задается как конструктивное определение множества так называемых синтаксически правильных (правильно построенных) конструкций соответствующего языка. Множество синтаксически правильных конструкций языка – это условное расширение множества конструкций, принадлежащих данному языку. Конструктивное определение множества синтаксически правильных конструкций языка задается следующими множествами:
1) множеством элементарных (атомарных, примитивных) конструкций;
2) множеством синтаксических правил, указывающих, как из имеющихся синтаксически правильных конструкций можно построить также синтаксически правильную конструкцию.
Денотационная семантика языка чаще всего формально задается как метод (в частности, алгоритм) перевода произвольной конструкции описываемого языка (языка-объекта) на некий другой язык, денотационная семантика которого считается известной и является достаточно простой. Языками с наиболее простой денотационной семантикой являются языки, конструкции которых представляют собой семантические конструкции.
С прагматической точки зрения каждому языку можно поставить в соответствие присущий только этому языку метод представления информации, являющейся описанием некоторого класса областей, т.е. метод построения информационных конструкций. Каждый такой метод ограничивает (уточняет) вид (внутреннее строение) информационных конструкций и соотношение информационных конструкций с описываемыми предметными областями.
Классификация языков осуществляется в соответствии с тем, какими синтаксическими и семантическими особенностями обладают информационные конструкции, принадлежащие этим языкам.
Первый признак классификации языков – линейность языковых конструкций. По этому признаку языки делятся на символьные (линейные) и графовые (нелинейные, сетевые). Символьные языки – это языки, которым принадлежат только символьные конструкции. Все остальные языки будем называть графовыми.
Во множестве графовых языков, в свою очередь, можно выделить следующие подклассы: языки информационных конструкций общего вида, языки бинарных информационных конструкций, языки однородных информационных конструкций, языки предельных информационных конструкций. Из сказанного ранее (см. пункт 1.2.3.) следует, что от каждого графового языка, принадлежащего одному из перечисленных классов, достаточно легко перейти к эквивалентному графовому языку, который принадлежит любому другому из перечисленных классов графовых языков.
Важнейшим свойством символьных языков является то, что для каждого такого языка при конечном фиксированном для всех конструкций языка алфавите символов (разным языкам могут соответствовать разные алфавиты) обеспечивается возможность формирования неограниченного количества знаков, соответствующих неограниченному количеству денотатов.
Предложенный нами язык однородных информационных конструкций также обеспечивает открытый характер при одинаковом для всех языковых конструкций наборе отношений, задающих эти конструкции.
По второму признаку классификации языки делятся на семантические и несемантические. Семантические языки – это языки, которым принадлежат только семантические конструкции. Все остальные языки считаются несемантическими.
Символьная информационная конструкция может быть семантической сетью, если описываемая предметная область имеет линейную структуру и если связи между символами в символьной информационной конструкции ставятся в соответствие связям между предметами в описываемой предметной области. Но далеко не каждая фактографическая конструкция может быть одновременно и семантической информационной конструкцией, и символьной информационной конструкцией. В частности, не существует символьного семантического языка, обеспечивающего эквивалентное представление произвольных информационных конструкций общего вида.
Третий признак классификации языков – степень сложности структур описываемых предметных областей. По этому признаку выделяют языки, ориентированные на описание сложноструктурированных предметных областей. В сложноструктурированных предметных областях отсутствуют ограничения на вид связей. В этих предметных областях связи могут быть между предметами, связями, фрагментами предметной области, относительными понятиями, абсолютными понятиями.
Пятый признак классификации языков – наличие фактора времени. По этому признаку языки делятся на языки описания стационарных предметных областей и языки описания нестационарных предметных областей, т.е. предметных областей, состояние которых меняется во времени. Нестационарная предметная область формально трактуется как множество упорядоченных во времени стационарных предметных областей, называемых состояниями (ситуациями). Каждому состоянию нестационарной предметной области ставится в соответствие информационная конструкция, описывающая это состояние. В целом описание нестационарной предметной области есть метаописание системы информационных конструкций, каждая из которых описывает одно из состояний нестационарной предметной области. Следовательно, язык описания нестационарных предметных областей должен включать в себя язык описания стационарных предметных областей. Описание нестационарной предметной области можно также трактовать как метаописание некоторой нестационарной информационной конструкции.
При этом за основу такого метаописания можно брать не только систему состояний нестационарной информационной конструкции, но и систему взаимодействующих переходных процессов, осуществляющих переход от одного состояния к другому. Важнейшим классом языков описания нестационарных предметных областей являются языки процедурного программирования, описывающие преобразование информационных конструкций.
Шестой признак классификации языков – наличие метаязыковых средств, достаточных для полного самоописания языка. По этому признаку языки делятся на стратифицированные, у которых указанные средства отсутствуют, и нестратифицированные, которые являются собственными метаязыками и которые, следовательно, не имеют четкой грани между языком-объектом и метаязыком, а также между информационной конструкцией-объектом и метаконструкцией.
Седьмой признак классификации языков – семантическая мощность. Семантическая мощность языка – это все то, что может быть описано с помощью конструкций этого языка. Языки с неограниченной семантической мощностью, т.е. языки, в которых имеется потенциальная возможность представления любой информации, будем называть универсальными. Согласно рассматриваемому признаку классификации, языки делятся на универсальные и специализированные. В свою очередь, специализированные языки могут сравниваться по своей семантической мощности, т.е. по многообразию описываемых предметных областей, а также по многообразию свойств, описываемых в этих областях. Универсальные языки можно рассматривать как результат интеграции всевозможных специализированных языков, поэтому при создании универсального языка принципиально важной является разработка методов интеграции специализированных языков в рамках создаваемого универсального языка. В основе такой интеграции, в частности, может лежать выделение языка-ядра, общего для всех интегрируемых языков. Универсальные языки по определению должны быть языками, ориентированными на описание сложноструктурированных предметных областей, логическими языками, языками описания нестационарных предметных областей, нестратифицированными языками.
Подчеркнем, что языки представления знаний для интеллектуальных систем нового поколения должны быть универсальными, а также открытыми языками, т.е. языками, позволяющими достаточно легко интегрировать самые различные специализированные языки.
Важнейшим классом специализированных языков являются языки программирования, включающие в себя языковые средства представления самих программ и языковые средства представления информационных конструкций (данных), которые перерабатываются в процессе реализации этих программ.
Каждая программа есть описание некоторого метода решения произвольной задачи из определенного класса задач. Существуют два принципиально разных класса методов решения задач – процедурные и непроцедурные методы. Процедурный метод решения произвольной задачи из определенного класса задач – это явная декомпозиция всего процесса решения задачи на иерархическую систему более простых и, в конечном счете, элементарных процессов. Таким образом, описание процедурного метода решения некоторого класса задач (такое описание будем называть процедурной программой) есть не что иное, как описание некоторого класса нестационарных информационных конструкций. Следовательно, языки процедурного программирования следует отнести к классу языков описания нестационарных предметных областей (см. пятый признак классификации языков). В отличие от этого непроцедурный метод решения произвольной задачи из определенного класса задач явно не рассматривает сам процесс решения задачи, а представляет собой информационную конструкцию, которая, будучи соединена с исходными данными задачи из указанного класса, предоставляет решателю (абстрактной машине) дополнительную информацию, достаточную для решения произвольной задачи соответствующего класса. При этом способ использования решателем этой дополнительной информации может быть самый различный.
Важным классом специализированных языков для интеллектуальных систем являются языки спецификаций программ. Язык спецификаций программ – это метаязык, обеспечивающий описание программ, и в частности описание денотационной семантики программ, т.е. формальное определение класса задач, решаемых с помощью каждой программы. Наличие описаний спецификаций программ, имеющихся в памяти интеллектуальной системы, дает возможность интеллектуальной системе найти для появившейся у нее задачи программу, обеспечивающую решение этой задачи, если, конечно, такая программа имеется.
1.2.6. Семантические сети и семантические графовые языки Ключевые п о н я т и я : графовый язык, графовый семантический язык представления знаний.
Семантические языки, т.е. языки, которым принадлежат только семантические информационные конструкции, являются основным объектом исследований в данной работе. Все семантические языки с нетривиальной семантической мощностью являются графовыми языками.
Можно говорить о целом семействе семантических графовых языков, называемых также языками семантических сетей. В частности, в соответствии с типологией семантических информационных конструкций, рассмотренных выше, можно выделить следующие семантические языки: язык базовых семантических информационных конструкций, язык бинарных информационных конструкций, язык однородных информационных конструкций.
Примерами графовых семантических языков (как специализированных, так и языков, претендующих на универсальность) также являются:
способ организации семантических сетей, используемый В.Н.Вагиным для поддержки параллельноВ а г и н В. Н. 1 9 8 9 к н – Д е д у к И О ;
способы организации семантических сетей, рассмотренные в работе [445] (С к р э г г П. 1 9 8 3 с т С е м а н С к М П );
К достоинствам семантических графовых языков представления знаний, по сравнению с другими способами представления знаний, относятся:
• компактность, обусловленная тем, что в отличие от символьного текста в семантической сети знак каждого объекта или понятия описываемой предметной области присутствует только в одном экземпляре и состоит из одного элемента;
• ассоциативность, заключающаяся в существовании простых процедур поиска элементов семантической сети, связанных заданным образом с заданными элементами;
• наличие простой возможности введения метаинформации в семантическую сеть путем простого наращивания исходной семантической сети метасетью без какого-либо изменения исходной семантической сети;
• возможность рассмотрения описываемых предметных областей одновременно на неограниченном числе уровней детализации;
• приспособленность к поддержке структур любого вида, и в частности к поддержке сложноструктурированных знаний;
• приспособленность к интеграции самых различных специализированных языков и самых различных моделей представления знаний;
• приспособленность к представлению различного рода лингвистических знаний (о синтаксисе, о семантике, о прагматике естественных языков), что делает эффективным использование семантических графовых языков для создания естественно-языковых интерфейсных подсистем в интеллектуальных системах;
• приспособленность к параллельной асинхронной переработке знаний, что делает эффективным использование семантических графовых языков для создания интеллектуальных систем, поддерживающих сложноструктурированные знания и сложные логические операции.
Подробнее о достоинствах семантических графовых языков см. в работах [127; 125; 444; 80] В данной работе мы будем рассматривать графовый семантический язык представления знаний, ориентированный на описание сложноструктурированных предметных областей, обеспечивающий представление логических высказываний самого различного вида и обладающий высокой степенью открытости. Кроме того, мы будем рассматривать различные графовые языки параллельного асинхронного программирования, легко интегрируемые в состав указанного выше графового семантического языка представления знаний. Напомним при этом, что программы, представляющие собой описания различных методов решения различных классов задач, составляют важнейшую часть баз знаний интеллектуальных систем.
Предлагаемый в данной работе графовый семантический язык представления знаний, обладающий указанными выше свойствами, назван языком SCL (Semantic Code Logic) – см. раздел 5. В качестве базового языка представления знаний (языка-ядра), на основе которого осуществляется интеграция всевозможных специализированных языков в состав языка SCL, предлагается язык SC (Semantic Code) – см. раздел 4.
Резюме к подразделу 1. В подразделе 1.2 графовые языки рассматриваются в сравнении с символьными языками и в контексте общей типологии языков. Кроме того, формально рассмотрены синтаксические и семантические свойства информационных конструкций, принадлежащих графовым языкам.
В целях формального уточнения понятия предметной области и понятия информационного объекта введено понятие реляционной структуры как обобщение классического понятия алгебраической модели. Рассмотрены наиболее интересные виды информационных конструкций: бинарные, однородные, символьные информационные конструкции.
В целях формального уточнения денотационной семантики информационных конструкций введено понятие базовой семантической информационной конструкции. Денотационная семантика информационной конструкции определяется как ее соотношение с эквивалентной базовой семантической информационной конструкцией. Информационные конструкции произвольной структуры, имеющие наиболее простой вид соотношения с эквивалентными им базовыми семантическими информационными конструкциями, определены как семантические конструкции.
Графовые языки в настоящее время не являются практически используемыми языками, несмотря на их преимущества по сравнению с символьными языками. В данной работе мы пытаемся это устранить.
При этом нас будут интересовать не просто графовые языки, а графовые семантические языки, ибо языки именно этого класса дают достаточно «прозрачную» возможность реализации моделей параллельной асинхронной переработки знаний путем их сведения к более простым и в конечном счете к непосредственно реализуемым моделям.
Для того чтобы оценить практическую значимость идеи создания и реализации графовых языков, сделаем небольшой экскурс в становление теории графов как области математики. Особенность теории графов заключается в том, что исследуемые ею математические объекты были хорошо известны и до нее. Это конечные алгебраические модели частного вида. Но на эти алгебраические модели теория графов взглянула, условно говоря, «топологическим» взглядом. И сразу оказался обнаженным для этих структур целый ряд аспектов, имеющих, как скоро выяснилось, большое практическое значение. Конечно, графы как картинки, иллюстрирующие ту или иную задачу, использовались задолго до появления теории графов. Практика показала плодотворность теоретико-графового взгляда на большое количество задач, и не только при постановке задач, но и при рассмотрении процесса их решения. Но все это в настоящее время сдерживается определенной сложностью погружения теоретико-графового взгляда на решаемую задачу в современные технологии программирования, которые в конечном счете скрывают, камуфлируют то, что теоретико-графовый взгляд пытается обнажить. С появлением графовых языков представления знаний и графовых языков программирования это противоречие снимается.
Наиболее острая потребность в графовых языках ощущается в CAD-CAM-задачах, в задачах структурного распознавания, в задачах, связанных с обработкой иерархической сложноструктурированной информации.
В заключение сделаем несколько общих примечаний о графовых структурах.
П р и м е ч а н и е 1. Графовый способ представления дискретной информации обладает универсализмом в том смысле, что любое представление дискретной информации можно рассматривать как графовую структуру. Следовательно, есть все основания считать понятие графовой структуры и понятие текста (в общем виде) тождественными понятиями. Действительно, когда мы говорим о графе, мы всегда подразумеваем некую предметную область, которую этот граф описывает, будь то схема улиц города, сеть железных дорог, принципиальная электрическая схема, структура молекулы какого-либо органического соединения или система состояний конечного автомата. А текст всегда можно рассматривать как граф, вершины и связи которого являются элементами текста (разумеется, элементы текста физически могут быть представлены самым различным образом). Так, например, текст, записанный на ленте машины Тьюринга, есть не что иное, как орграф с помеченными вершинами. Вершины этого орграфа есть ячейки ленты, в которые записывается тот или иной символ, а его дуги физически реализуются смежностью (соседством) ячеек ленты и связывают каждую ячейку ленты с непосредственно следующей за ней ячейкой.
Графовая трактовка текста встречается в целом ряде работ по формальным системам. Текстовая трактовка графовой структуры также встречается в ряде работ. Так, например, А.А.Зыков рассматривает графовую структуру как «средство описания тех или иных взаимосвязей между математическими Итак, графовая структура можно рассматривать как объект или процесс, являющийся дискретной моделью некоторого другого объекта или процесса. Под дискретностью модели здесь понимается не фиРаздел 1. 0B0BГрафодинамическая парадигма обработки информации зическое свойство объектов, являющихся дискретными моделями, а тот факт, что для восприятия информации, содержащейся в дискретной модели, достаточно изучить ее строение только до определенного уровня. Так, например, изменение написания какого-либо символа в рукописном тексте, не переходящее грани возможного его написания, не изменяет содержащейся в тексте информации, т.е. не является существенным для текста.
П р и м е ч а н и е 2. Одну и ту же информацию можно представлять различными видами графов. Отсюда следуют два вывода:
• необходимо разрабатывать стандарты;
• среди этих стандартов нужно выявлять наиболее удобные способы графового представления информации.
П р и м е ч а н и е 3. До сих пор в основном мы пользовались такими языками, которые являются способами представления дискретной информации в виде линейных (цепочечных) графовых структур. Сюда относятся все естественные языки, подавляющее большинство искусственных языков. Не исключением является и способ представления информации в памяти современных ЭВМ.
разработке языков представления дискретной информации представляет значительные удобства.
Нелинейная графовая структура является естественной и удобной формой описания любой сложной системы (стационарной, нестационарной, абстрактной), в которой удается выделить некоторое множество элементов системы и некоторый набор отношений, заданных на этом множестве элементов. Эффективность нелинейного способа описания систем может быть проиллюстрирована следующими примерами.
Формализация описания систем, исследуемых органической химией, привела к графовой форме описания молекулы органических соединений.
Описание электронной системы оказалось удобнее всего строить в виде принципиальной электрической схемы, которая представляет собой не что иное, как граф.
П р и м е ч а н и е 5. Среди способов (языков) нелинейного представления дискретной информации наиболее удобным для переработки является представление в виде семантических сетей. Об этом свидетельствует интенсивное развитие теории семантических сетей, которая сформировалась в рамках исследований по системам искусственного интеллекта, системам автоматического перевода с одного естественного языка на другой и которая рассматривается сейчас как формальный аппарат исследования сложных процессов обработки информации (распознавания образов, планирования целенаправленных действий, обнаружения закономерностей и т.д.).
П р и м е ч а н и е 6. В рамках способа представления информации при помощи семантических сетей, в свою очередь, также возможен полиморфизм. Это требует разработки стандартных способов представления семантических сетей, т.е. специальных языков семантических сетей. Одним из таких языков является рассматриваемый ниже язык SC (Semantic Code).
Рассмотрение интеллектуальных систем на семантическом уровне является наиболее перспективным подходом к формальному уточнению понятия интеллектуальной системы. Такой подход развивается в работах Рассмотрение семантического уровня информационно-логической организации интеллектуальных систем позволяет в большой степени абстрагироваться от несущественных деталей технической реализации этих систем и, таким образом, позволяет сконцентрировать внимание на принципиальных особенностях их организации.
Попов Э.В.1976кн-АлгорОИР ; Хант Э.1978кн-ИскусИ ; Гладун В.П.1977кнЭ в р и с П в С С ). Суть проблемы представления знаний заключается не в том, чтобы суметь представить знания (представить их можно, например, и на естественном языке), а в том, чтобы представить эти знания в памяти так, чтобы ими можно было достаточно удобно пользоваться. Следовательно, проблему представления и организации знаний нельзя решать в отрыве от логики системы и от организации ее памяти. Так, например, представление знаний существенным образом зависит от способа организации доступа к памяти. Хорошо организованные знания должны быть записаны в память так, чтобы достаточно просто можно было найти требуемую в текущий момент информацию (требуемый фрагмент знаний).
Связь теоретико-графовых методов с семантическими сетями обусловлена тем, что теоретикографовая трактовка задачи всегда неявно подразумевает формализацию перерабатываемых данных не просто в виде некоторой графовой структуры, а в виде такой графовой структуры, которая обладает вполне определенными семантическими свойствами, а именно – является семантической сетью, хотя явно о семантических сетях в теории графов речь не идет. Этим обстоятельством обусловлены естественность, наглядность и удобство теоретико-графовой трактовки задачи, в чем легко убедиться, сравнив содержательную запись какого-либо теоретико-графового алгоритма с записью программы, обеспечивающей его реализацию на современных ЭВМ.
Кроме традиционных приложений в органической химии, в электротехнике теоретико-графовые методы в настоящее время широко используются в социологии, экономике, теории вероятностей, генетике, математической лингвистике, проектировании дискретных устройств и т.д. Об эффективности теоретико-графовых методов говорят также результаты, полученные при разработке структурного подхода к распознаванию образов, который позволяет сократить сложность процедуры распознавания по сравнению с другими подходами и обеспечивает распознавание в тех случаях, когда другие подходы оказываются неприемлемыми [512] «возможность приложения теории графов к столь различным областям заложена, в сущности, уже в самом понятии графа, сочетающего в себе теоретико-множественные, комбинаторные и топологические аспекты».
1.3. Абстрактные графодинамические ассоциативные машины К л ю ч е в ы е п о н я т и я : абстрактная машина обработки информации; графодинамическая параллельная асинхронная абстрактная ассоциативная машина.
Цель данного подраздела – рассмотреть графодинамические параллельные асинхронные абстрактные машины с общих позиций, как подкласс абстрактных машин обработки информации, и показать, что этот подкласс абстрактных машин является наиболее перспективным для проектирования интеллектуальных систем нового поколения, а следовательно, и для проектирования компьютеров нового поколения, ориентированных на поддержку интеллектуальных систем.
1.3.1. Абстрактные машины обработки информации и соответствующие им операции, элементарные процессы и микропрограммы К л ю ч е в ы е п о н я т и я : абстрактная машина обработки информации, память, операция.
Как было отмечено выше, каждому языку можно поставить в соответствие его синтаксис, отражающий свойства внутреннего строения конструкций этого языка, и денотационную семантику, отражающую общие свойства соотношения между конструкциями языка и описываемой ими предметной областью.