Глава 2. Формализм образов

2.1. Принцип атомизма

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

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

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

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

(I) равномерное движение по окружности на плоскости;

(II) вычислительные модули для выполнения

арифметических операций; (2.1.1)

(III) тригонометрические функции;

(IV) правила подстановки;

(V) атомы — узлы решетки.

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

Всякая образующая описывается с помощью признаков. В случае (I) из (2.1.1) в качестве признаков могут выбираться координаты центра окружности, радиус, угловая скорость и фазовый угол. В случае (II) образующая может иметь вид «прибавить 5», «перемножить » или «величина, обратная X», так что в качестве признаков можно выбирать некую метку, характеризующую тип операции и задающую в случае необходимости константы, например число 5 в первом варианте образующей.

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

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

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

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

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

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

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

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

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

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

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

Подмножества

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

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

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

образующей Число связей обозначается соответственно как входная арность и как выходная арность; см. Примечания А.

Рис. 2.1.1

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

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

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