Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Пусть /(а)=^. Из определения следует, что у детерминированной функции значение ч{т) лг-го (лг = 1,2,...)
члена последовательности ^ полностью определяется значениями первых т членов
а(1), а(2), ..съ(т)
последовательности а, т. е.
'у{яг)==/1П(а(1), а(2), ..а{т)).
Поскольку
/м(а(1), а(2), ..а(т)) =
= /m(ai(l), ап{1), ai(2), ..ап{т)),
то ясно, что /т ~ функция из Pk, зависящая от пт переменных.
Таким образом, детерминированная функция J(X) определяется последовательностью функций А-значной логики
/ {/lj /г) ? * -1 /т, ? • Л,
где
/г — /2(^1, ?2),
/т Х2, * • ч Хт) t
Xi = (х,(1), х2(1), .. ч *«(!)).
Х2 = (ха(2), хг(2), .. ч Яя(2)),
Хт = (х:(т), х2(т), , ..хп(т))
Детерминированная функция /(х х„) может
быть проинтерпретирована следующим образом. Пусть мы имеем некоторый «дискретный преобразователь» (рис. 1), Б котором существует п входов XI, Xzi .. м х„ и один выход /. На входы в моменты времени ? — 1, 2, ... ..т, ... подаются (входлые) последовательности
0Ц =•(011(1), «1(2), ..аДт), ..Л,
а2 — (а2(1), «2(2), а2(т), ..Л,
И в эти же моменты I на выходе возникает (выходная) последовательность 'у ~ {ч(1), 4(2), . -^{т),.. причем 7 = /(а.1, аг, .ая). Очевидно» что в дискретном преобразователе значение 'у(те) зависит только от значений входных последовательностей в моменты времени 2 — 1, 2, ..т и не завысит от значений в будущие моменты х1—
времени. Поэтому преобразова- хг~г
ние / есть детерминированная д. _1
функция.
Заметим, что константы из рис, 1
Рд> * (п = 0) интерпретируются дискретным преобразователем без
входов («генератором»). Заметим также, что поступающие на входы преобразователя последовательности, т. е. («!» я2, ?.ач), можно рассматривать как последовательность наборов
{(а,(1), «г (1), а»(1))’, (а, (2), а* (2), ..а„ (2)),...).
Здесь введенное нами тождество выполнено естественным образом.
Из того, что детерминированная функция {(хи .. хп) полностью определена последовательностью функций /с-значной логики, вытекает следующий факт.
Теорема 1. Мощность множества всех детерминированных функций, зависящих от переменных хи хг, -... ..хп, равна С.
В заключение приведем ряд иллюстраций.
Пример 2. а) Функция }ф(хи ..х„), где Ф(^1,... ..хп) ^ Рк, определена следующим образом;
и[хц ..хп)~ {Ф(^(1), ..., зг„(1)),
0(^(2), ..., хп(2)), ..., Ф(х1(т),'..Хп(т)), ...).
Значение функции /Ф определяется путем вычисления значений функции Ф по значениям соответствующих членов входных последовательностей. Отсюда /ф е Рд В частности, если взять Ф(^1, хг) — Хх&-хг (к — 2), то
/<е(-гн я2)~
— {ас,(1)&а:2(1), ^(2)& .т2(2), ..., а;1(/?г)&хг{тп), ...).
Здесь Еыходная последовательность — почленная конъюнкция входных последовательностей.
Обозначим через &*к множество всех функции /ф, где Ф е= РК.
б) Функция г ~ х + у, представляющая сложение двух &-значных последовательностей, определяется путем использования обычного алгоритма сложения двух чисел столбиком в /с-ычном счислении, но только с бесконечным числом разрядов:
... х (3), а: (2), х (1)
+ ...у(3),у(2>.у(1)
... а(З), г (2), г(1)
Ясно, что г(гп) определяется по первым т членам слагаемых. Поэтому я + I/ е Рд к.
в) Функция хг определяется через алгоритм умножения чисел в к-ичиой системе счисления, но с бесконечным числом разрядов
х(Щ, х (2),- я(1)
,т(3), аг(2), х(\)
X
+
.т(3) х{\), а; (2) лг (1), #(!} а;(1) х(2) х(2), хИ) х{2) а; (1) х (3)
2(3), 2(2), 2(1)
Здесь г(т) полностью определяется по первым т членам входной последовательности. Поэтому х* рд к.
Нетрудно привести примеры функций ИЗ Рс.к, которые не являются детерминированными. Так, функция }(х) из примера 1 этого параграфа не является детерминированной.
Итак, на первом этапе мы получили подкласс Рп к класса Рс,к' Однако класс Ряя является также обширным — его мощность есть с.
§ 2. Задание детерминированных функций при помощи деревьев. Вес дерева
Для детерминированных функций можно предложить более наглядный способ задания, чем для произвольных функции из Рс,ь- Он основан на аппарате деревьев*).
*) Строгое определение дерева приводится в части III,
ГЛ. 3. 0,-Д. ФУНКЦИИ С ОПЕРАЦИЯМИ
п
Пусть А, п — целые числа и N =• к*. Рассмотрим бесконечную фигуру, изображенную на рис. 2. Она состоит из вершин и ориентированных ребер. Будем называть эту фигуру деревом. Вершина ?0 называется корнем дерева, из нее исходит пучок из N ребер, образующих 1-й
Рис. 2.
ярус. Каждое из ребер 1-го яруса ведет в вершину, из которой в свою очередь исходит пучок из N ребер, образующих 2-й ярус, и т. д. Вершины, являющиеся концами ребер нг-го яруса, причисляются также к т-му ярусу (вершина считается вершиной 0-го яруса). Ребра каждого пучка нумеруются слева направо числами О, 1, ... .. N — 1 (см. рис. 2) или их записями в А-ичной системе счисления:
(О, .«.,0,0);(0, 0,1);(А — 1, А — 1,..А — 1).
п п п
В дальнейшем на рисунках номера ребер будут опускаться. Будем называть ветвью дерева связное *) подмножество ребер, содержащее в каждом ярусе ровно по одному ребру. Очевидно, что каждой ветви дерева можно сопоставить последовательность
