С.В. Яблонский - Введение в дискретную математику, страница 14

О п р е д е л е н и е. Число т классов эквивалентности, на которое разбивается множество всех поддеревьев данного дерева, нааывается весом дерева и соответственно весом детерминированной функции *). ° ) Данное определение может быть распростраиеио в иа константы.

Последовательность (у(1), у(2), ..., у(т), ...,) иаображается вырожденным деревом, состоип(им иа одной ветви у(1) у(2) у(ж) о.1 о~о...а~о... В ием можно рассматривать поддеревья и определить аквиаалеитность поддеревьев. В4 ч. т. Фтнкцпональнык систкмы с опаглцпямн Иначе говоря, вес — это максимальное число попарно неэквивалентных поддеревьев. При этом не исключается случай, когда вес г бесконечен.

Обратимся к примеру 3. В дереве для функции ~б,(л„лД (рис. 3), как мы 'виделн, все поддеревья эквивалентны, поэтому г 1. В дереве для функции з х + р (рис. 4) каждое поддерево эквивалентно либо поддереву с корнем $„ либо поддереву с корнем $ь поэтому г 2. В дереве для функции з л' (рис.

5) поддеревья с корнями $„ $о $„ ... (лежащие на левой ветви) попарно неэквивалентны, так как в силу справедливости соотношения (О... О а (М + 1), ...)з = (О... О п (8 + 1), ...) з з; поддерево с корнем $< в первых ( ярусах заполнено нулями, а в (~+ 1)-м ярусе имеет ребро, которому приписано значение 1.

Здесь г Для занумерованных деревьев можно ввести нумерацию вершин. Сначала перенумеруем классы эквивалентности числами О, 1, ... так, чтобы класс, в который по- Рис. б падает исходное дерево, имел номер О. Таким образом, нумерация содержит большой произвол. Далее, взяв произвольную вершину $, определим класс, в который попадает дерево с корнем $. Пусть х — номер этого класса. Тогда вершине $ присваивается номер к. Мы получаем дерево, у которого занумерованы также и вершины, причем корень имеет номер О. На рпс.

6 приведены нумера- гл. а о.-д. етнкцнн с опкгацпями цин вершин для двух основных примеров — функций ~б,(х„х,) и з х+ р. Если в рассматриваемом дереве сохранить только нумерацию вершин, то легко видеть, что нумерация ребер не восстанавливается однозначным образом. Тем не менее, нумерация вершин весьма полезна при исследовании исходного дерева.

В ряде случаев нумерацию вершин можно осуществлять параллельно с нумерацией ребер. Так, з примере для з х + р номер вершины О появляется в случае отсутствия переноса, а 1 — при наличии переноса е). Рассмотрим теперь дерево с занумерованными ребрами и вершинами. Возьмем произвольную ветвь, она проходит через вершины ~., ~о . ", Ь, ..., Ь, ... Пусть зтим вершинам приписаны соответственно номера О, к„ ..., кь ..., кь ... Допустим, что х~ к~ (~чь!) и для всех пар (в, 1) (ать~), для которых к~ кь индекс ) является наименьшим.

Произведем усечение данной ветви, сохранив ее начальный отрезок до вершины $е Производя зту операцию усечения для каждой ветви, мы получим усеченное дерево. Для случая функции конечного веса г на каждой ветви происходит повторение номеров вершин и номер /, л г л л з л Рис. 7 определяющий усечение, удовлетворяет неравенству ) < г.

Позтому для таких функций усеченное дерево будет конечным. «) Вспомним, что з примере Д б) при наличии перекоса з следующий разряд конец соответствующего ребра мы помечали кружочком, 88 Ч. Ь ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ На рис. 7 приведены усеченные деревья для функций ~д(хо хэ) и г= х+ у. Эти усеченные деревья непосредственно получаются иг деревьев, приведенных на рис. 6. Легко видеть, что усеченное дерево с эанумерованными ребрами и вершинами позволяет полностью восстановить псходвое аанумерованное дерево. 5 3. Ограниченно-детерминированные функции и способы вх вадании О и р е д е л е н и е.

Детерминированная функция ((хо ..., х„) называется ограниченно-детерминированной (о.-д.) функцией, если она имеет конечный вес. Класс всех о.-д. функций, принадлежащих Р,,„обозначим черев Р.з.ье). Нримеры 3, а) и 3, б) предыдущего параграфа дают примеры о.-д. функций, а пример 3, в) показывает, что (бр (2,Е) (1Я (де) (дт) Рис. 8 класс Р„„— класс всех о.-д. функций является собственным подклассом класса Р,, ь — класса детерминированных функций.

Для любой о.-д. функции соответствующее ей полное (бесконечное) аанумерованное дерево можно всегда свести к конечному дереву с аанумерованными ребрами и вершинами. Если в этом усеченном дереве проиввести отождествление вершин с одинаковыми номерами, то получим так называемую диаграмму Мура ее).

На рис. 8 ° ) Класс Р,з, ь, а частности, содержит все периодические последоаательности из Есь. е') диаграммы Мура можно использовать и дли представлении просто детерминироэанаыл функций. В этом случае диаграмма будет содержать, вообще юеори, бесконечное число нержин, ГЛ. 3. 'О.-Д. ФНИКЦПИ С ОПЕРАЦИЯМИ 87 приведена диаграмма Мура для функции з х+ у. В ней нулем отмечена начальная вершина и для удобства ребрам приписаны пары чисел (а, (), первое из которых обоаначает номер ребра, а второе — число, соответствующее этому ребру.

гг,ц 9;Ю где рве. Э Таким образом, о.-д. функции можно задавать не только при помощи бесконечных аанумерованных деревьев, но н диаграммами Мура. В общем случае, когда ) имеет вес г, диаграмма Мура имеет г вершин, причем одна из них выделена в качестве начальной; нз каждой вершины исходит У й" ребер; ребрам приписаны пары (О, "('), (1, "("), ..., (У вЂ” т, "(Он). В последующем диаграммы, удовлетворяющие данным свойствам, мы будем также называть диаграммами Мура. Диаграммы Мура позволяют строить о.-д.

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

8. Таким образом, не каждая диаграмма Мура с г вершинами изображает о.-д. функцию веса г. Однако диаграммы Мура позволяют оценить число о.-д. функций, зависящих от и переменных х„..., х„и имеющих вес г. Теорема 2. Число р (й, и, г) о.-д. функций из рьз, зависящих от и переменных хн ..., х„и имеющих еес г, не превосходит (гЮ~'ь". Доказательство. Возьмем диаграмму Мура для о.-д, функции веса г. В ней из каждой вершины исходит Й й" ребер, причем а-е ребро соединено с одной иэ г 33 ч.

1. Функционлльные системы с ОпеРАциями вершин и ему приписана пара (а, 1), где 0 < 1 ~ й — 1. Таким образом, число р(й, и, г) не превосходит числа диаграмм Мура вышеуказанного вида. Данные диаграммы могут быть получены следующим образом. Возьмем г вершин, занумерованных числами О, ... ..., г — 1 (Π— выделенная вершина), из каждой из которых исходит по Л»= й" ребер, зануыерованных числа-, ми О, ..., »т' — 1. Ыы имеем г»т' ребер. Каждое ребро может быть соединено с любой из г вершин и ему может быть приписано любое из й чисел.

Поэтому р(1.", и, г) ~(гй)' = (гй)" Теорема доказана. ПУсть 1(Х)=1(ло ..., Я„) — о.-д. фУнкциЯ. Рассмотрим ее диаграмму Мура. 11редположим, что в момент 1 — 1 ыы находились в вершине л(т) х (» — 1), тогда при поступлении в момент времени 8 числа а(1) мы ф переместимся в диаграмме по ребру 13~ а(»), выходящему из вершины х(» — 1) (см. рпс. 10), при этом пои»т О лучим выходное значение ((Г) и перейдем в вершину х(»). Таким образом, величины (а(»), х(» — 1)) однозначно определяют величины (1(1), х(») ).

Введенные ранее величины а и ( будем называть соответственно входной и выходной величинами, а х— состолниел». Пусть переменные Х, ч, Я таковы, что: Х описывает значение входной величины а, »',) описывает значение состояния х и Я описывает значение выходной величины "~.

На основании приведенных выше рассуждений мы приходим к следующим уравнениям*): Я(») д» (Х(»), 9(1-1)), »3(г) У(Х(1), Яс — Ц)', где ч»(0) О. Данные уравнения называются канониче- скими рравиениял»и. Нетрудно перейти от векторной за- *] Для констант пз Р я,» аналогичные построения дают уравпення, е которых отсутствует переменная Х. гл.з. о.-д.отпкции с опзглцпями 89 писи канонических уравнений к скалярной.

Пусть ) 1ой«г(. Тогда з(С) = Р'(хг(С), ..., х»(С), % (С вЂ” 1), ..., %(С вЂ” 1)), тг(С) = 6, (хг (С), ..., х»(С), 1', (С вЂ” 1), ..., дс (С вЂ” 1)), д, (С) = бс (х, (С), ...,, „(С), р, (С вЂ” 1), ..., д, (С вЂ” 1)), й,(0) -.„-д, (О) -О. Здесь Р', 6„..., 61 — функции из Р„определенные на множестве Ю', являющемся подмножеством из Еа х ... х Еа, »+! а именно: переменные х„..., х. пробегают значения пз Ем а вектор (д„..., д ) принимает г значений (например, двоичные записи чисел О, 1, ..., г — 1). Очевидно, что множество ю является цилиндром ' (или цилиндрическим) ко х„..., х *). Р Доопределив функции Р', 6о ..., % иа всей области ах...ха, у Фу» Ст, 6„ ..., 6 пз Р, и канонические уравнения примут более удобнуго для иас форму (так как здесь мы можем использовать развитый ранее аппарат формул): г (с) Г (х, (с), ..., х (с), о, (с — 1 ), ..., о~(с — 1 ) ), Ь (С) ба(х,(С), ..., х»(С), Ь (С вЂ” 1), ..., т (С вЂ” 1) ), () д~(С)=6~(х~(С), ..., х»(С), д~(С вЂ” 1), ..., 6~(С вЂ” 1)), д,(0) ...