Отношения

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

Отношение существует между двумя объектами. Обозначим эти объекты строчными буквами, например, а и b, а само отно­шение — буквой R. Тогда мы можем записать, что между а и b существует отношение R:

а R b. (4.2.1)

Например, R может выражать отношение “больше чем”. В этом случае формула (4.2.1) означает, что “а больше, чем b”. Мы также можем ввести другие отношения, например “равно”, “предшествует”, “старше чем”.

Классификация отношений

Отношения можно разбить на: рефлексивные, симметричные и транзитивные.

Рефлексивные отношения. Говорят, что отношение рефлексивное, если оно устанавливается между одним и тем же объектом. Например,

a R a. (4.2.2)

Лишь немногие отношения являются рефлексивными. Так, отношение “равно” — рефлексивное, а отношение “старше чем” — нерефлексивное.

Симметричные отношения. Отношение считается симметричным, если оно применимо к элементам а и b при их рас­смотрении как в данном порядке, так и в обратном:

a R b & b R а. (4.2.3)

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

Многие отношения являются несимметричными (асимметрич­ными). Простым примером может служить отношение “стар­ше чем”.

Транзитивные отношения. Представим транзитив­ное отношение в символической форме:

a R b & b R c a R c. (4.2.4)

Отсюда следует, что отношение R является транзитивным, если оно, существуя между а и b и одновременно между b и с, сущест­вует между а и с. Так, если Катя старше Гали, а Галя стар­ше Изабеллы, то Катя старше Изабеллы.

На первый взгляд может показаться, что все отношения должны быть транзитивными. Однако это не так и примером тому может слу­жить отношение “не равно”. Подставьте в таком отношении вместо а - 6, вместо b 5, а вместо с – 6 и вы увидите, что отноше­ние “не равно” не является транзитивным (оно нетранзитивное), иначе вам придется признать, что 6 не равно 6.

Графы

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

Рис 4.1. Граф

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

Граф состоит из ряда вершин и ребер. Он должен содержать, по крайней мере, одну вершину. Ребро является отрезком прямой, вершина—точкой. Для каждого ребра также должна существо­вать вершина, которая его завершает. Пример графа показан на рис. 4.1.

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

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

Направление

Выше уже обсуждались симмет­ричные отношения, такие, как “ра­вен”, “следующий”, “родной брат”. Эти отношения не опреде­ляют направления; они устанавливаются между элементами без указания на то, какой из них задается первым. Симметричные отношения легко представить с помощью рассмотренного только что графа. В данном случае ребро отображает симметричное от­ношение, а вершины — объекты, к которым это отношение приме­няется.

Асимметрия

О

Рис. 4.2. Орграф

тношение называется асимметричным, если между а и b оно существует, а между b и а - нет. В качестве примера можно при­вести отношения “больше чем”, “отец”, “дядя”. Направление определяет, какой объект служит под­лежащим, а какой дополнением по от­ношению к глаголу, выражающему отношение. Здесь важно определить объект, который устанавливается пер­вым. Так, мы говорим, что Максим — отец Валеры , но обратное утвержде­ние неверно: Валера не отец Максима. Ребро графа не показывает, какой из объектов упоминается первым.

Орграф

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

Типы отношений, изображаемых с помощью графа

Н

а рис. 3.4 показаны в форме графа три типа отноше­ний (рефлексивное, симметричное и транзитивное).

Рис. 3.4. Рефлексивное (1), симметричное (2) транзи­тивное (3) отношения

Для рефлексивного отношения стрелка начинается и заканчи­вается в вершине а, поскольку отношение устанавливается между элементом и им самим. В симметричном отношении первая стрелка начинается в а и заканчивается в b, а вторая начинается в b и заканчивается в а, так как отношение устанавливается в двух направлениях. Для транзитивного отношения первая стрелка направлена от а к b, вторая - от b к с, а третья, опре­деляющая транзитивность, - от а к с.