С.В. Яблонский - Введение в дискретную математику (1060464), страница 13
Текст из файла (страница 13)
В частности, если взять Ф (х„х,) х~ й х, (й 2), то (,б (х„х,)- - (х,(1)йх,(1), х,(2)йх,(2), ..., х,(т)йх,(т), ). Здесь выходная последовательность — почленная коньюнкция входных последовательностей. 78 Ч 1 ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ Обозначим через У'» множество всех функций ~е, где Ф ы Р„. б) Функция з х+ у, представляющая сложение двУх Й-значных последовательностей, определяется путем использования обычного алгоритма сложения двух чисел столбиком в й-ичном счислении, но только с бесконечны»1 чнслом разрядов: ... х (3), х (2), х (1) " р (3) р (2) р (1) ... г (3), г (2), г (1) Ясно, что з(1г.) определяется по первым л» членам слагаемых. Поэтому х + р 1и Р, „. в) Функция х' определяется через алгоритм умнон1ения чисел в й-ичной свстеме счисления, но с бесконечным числом разрядов ...
х(3), х(2), х(1) ... х(3), х(2), х(1) ... х(3) х(1), х(2) х(1), х(1) х(1) ... х(2) х(2), х(1) х(2) ... х(1) х(3) ... з(3), г (2), г(1) Здесь г(т) полностью определяется по первым л» членам входной последовательности, Поэтому х' 1и Рв ь Нетрудно привести примеры функций из Р1,», которые не являются детерминированными. Так, функция 1(х) из примера 1 этого параграфа не является детерминированной. Итак, на первом этапе мы получили подкласс Р,, класса Ро». Однако класс Р„„являетсн также обширным — его мощность есть и й 2.
Задание детерминированнык функций при помощи деревьев. Вес дерева Для детерминированных функций можно предложить более наглядный способ задания, чем для произвольные функций из Р, ». Оп основан на аппарате деревьев е). ') Строгое определение дерева врвводвтся в части Ш. гл. з. о.-д.
отнкции с операциями 79 Пусть й, л — целые числа и Ф й". Рассмотрим бесконечную фигуру, изображенную на рис. 2. Ова состоит из вершин и ориентированных ребер. Будем называть ету фвгуру деревом. Вершина $, иазывается корнем дерева, из иее исходит пучок из гг' ребер, образующих 1-й 7 час тарос Ркс. 2. ярус. Каждое из ребер 1-го яруса ведет в вершину, из которой в свою очередь исходит пучок из 1«' ребер, образующих 2-й ярус, и т. д. Вершины, являющиеся концами ребер лс-го яруса, причисляются также к т-му ярусу (вершина $, считается вершиной 0-го яруса). Ребра каждого пучка нумеруются слева направо числами О, 1, ...
..., гт' — 1 (см. рис. 2) или их записями в й-ичной системе счвслеиия: (О, ..., О, О); (О, ..., О, 1); ...; (Ус — 1, Рс — 1,..., й — 1). В дальнейшем иа рисунках номера ребер будут опускаться. Будем называть ветвью дерева связвое *) подмноже'ство ребер, содержащее в каждом ярусе ровно по одному ребру. Очевидно, что каждой ветви дерева можно сопоставить последовательность а = (а(1), а(2), ..., а(ш), ...), где гп — номер яруса, а а(т) — номер ребра, входящего в зту ветвь, если идти по ней, начиная от корня. Так, например, ветви, помеченной иа рис.
2 штриховой ли- «) Упорядоченное мвожсство ребер, е котором конец предыду- щего ребра является началом последующего. ч. ь ФункциОнАльные снсте11ы с ОпеРАцпямн ~(Х) - (~,(Х,), ~,(ХО Х,), ..., ~ (Х„ Х„ ..., Х )', ), при помощи ~(Х) ка1кдому ребру дерева припишем число из Е,. Для этого возьмем произвольное ребро из т-го яруса (т — 1, 2, ...) и рассмотрим путь, ведущий из корня к этому ребру — оя может быть также определен как отрезок произвольной ветви, проходящей через данное ребро.
Очевидно, что путь определен однозначным образом н моя<ет быть охарактернаован некоторым кортежем а(1), а(2), ..., а(т) номеров ребер пути, отсчптываемых от корня. Исходному ребру припишем т-11 член выходной последовательности — число т(т), где "((т)=)„,(а(1), ..., а(т)). Полученное дерево будем называть занумерованным деревом (точнее, деревом с ванумврованнььии ребразш). Пример 3.
а) Для функции ),й (х„х,) имеем:й =и 2,)т' 4 и т(т) ~ (Х„ Хь ..., Х ) 1„(Х„) х,(т)бах,(т). Следовательно, т(т) зависят только от последнего члена кортежа, ведущего к данному ребру, т. е. от номера ребра. Ребру с номером 0 = (О, 0) соответствует значение 0 бс 0 = О, «ОА1 О, «13:0 О, «161 1. «1=(0, 1) « 2 (1 0) « 3 (1, 1) На рис. 3 представлено соответствующее занумерованное дерево. нпей, соответствует последовательность (О, 1, Ж вЂ” 1, ...). Очевидно, что а ен Еьн Справедливо и обратное утверждение: каждой последовательности а из Ес в соответствует некоторая ветвь дерева.
Таким образом, мы имеем взаимно однозначное соответствие между ветвями дерева и элементами множества Еон. В силу этого мы можем пользоваться деревом для геометрического задания множества Е,,н. Пусть ДХ) является функцией из Р (М = й") и Х (х„..., х.). Используя соотношение гл. з. о.-д. егнкцни с опвглцпями а б) Для функции х к+р имеем й= 2, я 2 и Ж 4. Очевидно, что ~л(т)+ р(т) (шоб2) прн отсутствии переноса, х(т) ( л(т)+ р(лз)+ $ (шоб 2) при наличии переноса. Отсюда нетрудно усмотреть аакон.получения занумерованного дерева (рис. 4). Процесс приписывания ребрам Р .З чисел начинается с 1-го яруса. Затем переходят ко 2-му ярусу и т. д.
При этом, если появляется перенос в следующий разряд, то конец соответствующего ребра помечается кружочком. Это позволяет выполнить вычисления в следующем ярусе. в) Для функции з х' имеем к 2, ~ ° х и М *2. Здесь явное выражение для г(ж) в виде функции 1 (к(1), ..., к(т)) значительно сложнее, чем в предыдущих случаях, и удобнее вычнслять г(ш), пользуясь алго- 32 ч. г. Фтнкциональныи систвмы с опвегцпями ритмом возведения в квадрат.
Из него видно, что г(1) = х(1), г(2)= О, г(3) = х(2)+ х(1) х(2) (шоб 2), г(4)=х(1)х(З)+х(1)х(2) (шоб2) и т. д. Соответственно получаем начальный фрагмент занумерованного дерева (рис. 5). 4'р Рвс. 5 Итак, мы видим, что по детерминированной функции можно получить занумерованное дерево.
Обратное утверждение, вообще говоря, неверно: занумерованное дерево может определять несколько детерминированных функций. Параметры Ж и й' (где М вЂ” число ребер, исходящих из каждой вершины, а Й' — максимум чисел, приписанных ребрам) могут допускать несколько решений уравнения У й" при й > й'. (Всегда существует решение й У и и 1, т.
е. определяется детерминированная функция от одного переменного.) Однако, если по детерминированной функции Дхь ..., х„) построить занумерованное дерево, то по этому занумерованному дереву с параметрами Й и и определится единственная детерминированная функция, а именно )(хь ..., х„). Таким образом, занумерованными деревьями можно пользоваться в качестве аппарата для изучения детерминированных функций.
Возьмем занумероваяиое дерево для некоторой детерминированной функции 1(Х) ((хо ..., х„). Пусть $— произвольная его вершина и-го яруса. В нее из корня $~ ведет путь а(1), ..., а(т) гл.э. О..д.Функции с опеРлциями (прк $ $, путь является пустым). Совокупность всех ветвей, исходящих иэ $, порождает некоторое дерево с порвем $, которое будем нааывать специальным поддеревом исходного дерева. Это поддерево определяется множеством всех последовательностей иа Ес» с фиксированным началом и(1), ..., а(вь). Так как исходное дерево занумеровано, то поддерево является также аанумерованным. Если в поддереве ввести нумерацию ярусов, начиная с 1-го, то еьту будет соответствовать детерминированная функция )'(Х). Ее моя<по аналитически определить следующим образом: пусть У(Х) - (1,(Х,), (,(Х„Х,), ...), р(Х) у((Х,), ~1(Х„Х,), „.).
Тогда 1д,(Хы ..., Х1) /~ен(а(1), ..., а(пь), Х„,, „Хт) (1 1, 2, ...). Определение. Два поддерева с корнями $, и $, исходного дерева называются эквивалентными, если у" (Х) = 12» (Х). Очевидно, что при естественном наложении двух эквивалентных поддеревьев их нумерации совпадают. Так, в дереве на рис. 3 все поддеревья эквивалентны, а в дереве ка рис. 4 поддеревья с корнями $, и $» вквивалентны, а с корнями $, и $, — не эквивалентны. Соотношение эквивалентности поаволяет в исходном дереве множество всех поддеревьев раэбить на классы эквивалентности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
