Графическое задание детерминированных функций
Пусть 
. Выше мы показали, что с помощью векторной записи данную функцию можно свести к функции 
, где 
. Рассмотрим бесконечную фигуру (рисунок 1):
|
Рисунок 1
Называть её будем деревом, и построена она следующим образом. Возьмём произвольную вершину 
, которую назовём корнем дерева. Из неё проведём N рёбер, которые образуют первый ярус. Из концов каждого из рёбер также проведём N рёбер, которые образуют второй ярус и т. д. Рёбра каждого пучка нумеруются слева направо числами 0, 1,…, N-1 или их значениями в k-ичной системе счисления.
В дальнейшем на рисунках номера рёбер будут опускаться. Далее, каждому ребру в построенном дереве произвольным образом припишем одно из чисел множества {0, 1,…, k-1}. В результате получим так называемое нагруженное дерево.
Рассмотрим следующее нагруженное дерево (рисунок 2):
Рисунок 2
Начиная движение с корня дерева, пойдём по рёбрам. Так, например, последовательности (0, 0, 1, 1…), где числа 0, 0, 1, 1, … – номера рёбер, соответственно, 1-го,2-го,3-го,4-го и т. д. ярусов соответствует выделенный маршрут и последовательность (0, 1, 1, 1…).
Теорема 1Функция из 
будет детерминированной тогда и только тогда, когда она может быть заданна с помощью нагруженного дерева.
Доказательство. Покажем, что любое нагруженное дерево задает некоторую детерминированную функцию. Действительно, пусть 
– произвольная последовательность чисел, где 
, I = 1, 2,…. Будем считать, что 
– номер ребра 1-го яруса, 
– номер ребра 2-го яруса и т. д. Данной последовательности в нагруженном дереве соответствует единственный маршрут, ведущий из корня дерева. Числа, приписанные выделенным ребрам образуют выходную последовательность 
. Покажем, что построенная функция из 
является детерминированной. Пусть 
и 
– две входные последовательности такие, что 
.
Ясно, что маршруты в нагруженном дереве, соответствующие данным последовательностям на первых t ярусах совпадают. А это значит, что 
, т. е. функция детерминированная. Обратное утверждение очевидно. Теорема доказана.
Рассмотрим следующие примеры:
Пример 4 
. Ясно, что 
и число ребер, выходящих из вершин равно 
. Построим дерево соответствующее данной функции (рисунок 3):
. . . . . . . . . .
|
Рисунок 3
Например, входной последовательности {0, 1, 1, …} будет соответствовать входная последовательность {1, 0, 0, …}.
Пример 5 
, которая задаётся следующим образом.
, где x(t)·y(t) – конъюнкция.
Для данной функции k=n=2 и число ребер, выходящих из вершин равно N = 
= 4. Ребру с номером D = (0,0) соответствует значение (0,0) = 0
1 = (0,1) 0·1 = 0
2 = (1,0) 1·0 = 0
3 = (1,1) 1·1 = 1.
Следовательно, данной функции соответствует следующее нагруженное дерево (рисунок 4):
Рисунок 4
Пример 6 
, k = n = 1, N = 
= 1.
Дерево, соответствующее данной функции строится следующим образом. Процесс приписывания ребрам чисел начинается с 1-го яруса
0 = (0,0) 0+0=0
1 = (0,1) 0+1=1
2 = (1,0) 1+0=1
3 = (1,1) 1+1=0
При этом, если появляется перенос в следующий разряд, то конец соответствующего ребра кончается кружочком. Это позволяет выполнить вычисление в следующем ярусе (рисунок 5):
Рисунок 5