Глава 1. Образующие

1.1. Образующие и их свойства

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

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

Множество всех образующих состоит из непересекающихся классов образующих где общий индекс, индекс класса образующих,

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

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

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

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

Величина арности представляет собой сумму входной арности и выходной арности :

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

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

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

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

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

Мы будем пользоваться графическим формализмом, таким, как на рис. 1.1.1, для того, чтобы дать интуитивное представление о свойствах образующих. На этом рисунке входная арность равна 2, соответствующие показатели связей — и и выходная арность — 3, соответствующие показатели связей — так что общая арность равна 5.

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

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

Определение 1.1.1. Будем считать, что множество отображений образует множество преобразований подобия, если:

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

(ii) Любое отображает в себя при любом индексе класса образующих а;

(iii) множество не влияет на связи (но может влиять на показатели связей).

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

Рис. 1.1.1.

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

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

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

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

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

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

С помощью такого отображения можно заменять образующие элементы множества образующими множества не нарушая комбинаторную структуру.