Граф вычисления сложной функции
Сложная функция задается с помощью суперпозиции некоторого набора "простых". Простые функции принадлежат исходно задаваемому конечному множеству F. Формально они выделены только принадлежностью к множеству F - никаких обязательных иных отличий этих функций от всех прочих в общем случае не предполагается.
В этом разделе мы изучим способы задания сложных функций, то есть формулы и соответствующие им графы. Свойства самих функций нас сейчас не интересуют (будем рассматривать ноты, а не слушать музыку).
Теория выражений, определяющих сложные функции, является простейшим разделом математической логики, в которой сами эти выражения называются термами [3.4].
Термы - это правильно построенные выражения в некотором формальном языке. Чтобы задать такой язык, необходимо определить его алфавит. Он состоит из трех множеств символов:
- C - множество символов, обозначающих константы;
- V - множество символов, обозначающих переменные;
- F - множество функциональных символов, , где
- множество символов для обозначения функций k переменных.
Вводя различные множества символов, мы постоянно обращаемся к их интерпретации ("... символы, обозначающие..."). Строго говоря, это не нужно - можно (а с чисто формальной точки зрения - и должно) описать все правила действия с символами, не прибегая к их интерпретации, однако ее использование позволяет сократить изложение формальных правил за счет обращения к имеющемуся содержательному опыту.
Термы определяются индуктивно:
- любой символ из есть терм;
- если - термы и
, то
- терм.
Множество термов T представляет собой объединение:
где
Удобно разбить T на непересекающиеся множества - слои
Для оперирования с термами очень полезны две теоремы [3.4].
Эта теорема является точной формулировкой эквивалентности используемой бесскобочной и обычной записи.
Пусть u и v - выражения, то есть последовательности символов алфавита. Скажем, что u входит в v, если существуют такие выражения p и q (возможно, пустые), что v совпадает с puq.
Теорема 2 (о вхождении терма в терм). Пусть
Доказываются эти теоремы элементарной индукцией по длине термов [3.4]. В доказательстве теоремы 2 выделяется лемма, представляющая и самостоятельный интерес.
Лемма 1. Каждое вхождение любого символа в терм ? начинает вхождение некоторого терма в ?.
Определим отношение между термами
- ;
- если t совпадает с ,и- термы, то;
- если и
, то
.
Согласно теореме 2,
Для каждого терма t определим множество входящих в него термов
Свяжем с термом t ориентированный граф
Для произвольного графа G будем обозначать v(G) множество вершин, а e(G) - множество ребер G.
Возьмем для примера выражение для сложной функции
 | (3) |
 | (3') |
Рис. 3.1.
Граф
Для того, чтобы терм однозначно восстанавливался по графу, необходимы еще два дополнения.
- Сопоставим каждой вершине метку p(?) - символ алфавита. Если вершина принадлежит нулевому слою
, то ей соответствует терм, совпадающий с символом из
. Этот символ и сопоставляется вершине в качестве метки.
Если вершина принадлежит(i>0), то меткой служит функциональный символ: вершине ? сопоставляется, если ? имеет вид
, где, а- термы. - Каждому ребру , приходящему в вершину ?, сопоставим метку P(?', ?) - конечное множество натуральных чисел (номеров): пусть терм ? имеет вид
, где, а- термы, тогда ребру (?', ?) сопоставляется множество тех i (), для которых ?' совпадает с
. На практике в большинстве случаев эта метка состоит из одного номера, но возможны и другие варианты - так же, как функции вида f(x,x). Для графических иллюстраций удобно ребра (?', ?), имеющие в своей метке P(?', ?) больше одного номера, рисовать как пучок ребер, идущих от вершины ?' к вершине ? - по одному такому ребру для каждого номера из P(?', ?); этот номер и будет меткой соответствующего ребра из пучка.
Граф
Итак, для всякого терма t построен ориентированный граф
А) если для данного
при фиксированном ? образует разбиение множества номеров {1,...,k}, то есть
при
На этом завершается изложение основных формальных конструкций. Прежде, чем переходить к интерпретации, сформулируем теорему об эквивалентности графического и формульного представления термов.
Пусть G - конечный ориентированный граф, не имеющий ориентированных циклов, и в G существует и единственна такая вершина
Теорема 3. Существует и единственен терм t, для которого
Доказательство проводится в два этапа. Сначала в G устанавливается послойная структура: строится разбиение множества вершин G:
Доказательство основного утверждения теоремы проводится индукцией по числу слоев k.
Интерпретация сопоставляет терму сложную функцию. Она строится так. Задается некоторое множество D - область интерпретации. Каждой константе с, входящей в интерпретируемый терм t, сопоставляется элемент из D (
Если
Заметим, что заданная интерпретация терма t одновременно определяет интерпретацию каждого терма, входящего в t.
Представим процесс вычисления сложной функции
Пусть задана интерпретация терма t и определены значения всех переменных, входящих в t. Тогда для любого терма ?, входящего в t, также задана интерпретация и определены значения всех функций
Для каждой вершины ?, принадлежащей ненулевому слою, можно выписать уравнение функционирования, связывающее значения вершин. Пусть
образует разбиение множества {1,2,...,k}.
Уравнение функционирования для вершины ?, принадлежащей ненулевому слою, имеет вид
 | (4) |
В силу уравнения функционирования (4), если для входящих в ? ребер
С каждой вершиной графа ?, принадлежащей ненулевому слою, ассоциируется автомат, вычисляющий функцию
