Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
Рис. 6
Таким образом, о.-д. функции можно задавать не только при помощи бесконечных аанумерованных деревьев, но и диаграммами Мура. В общем случае, когда / имеет вес г, диаграмма Мура имеет г вершин, причем одна из них выделена в качестве начальной; из каждой вершины исходит N =• кп ребер; ребрам приписаны пары (0, 7'), (1, 7"), ..(ТУ—1, 7('Л°). В последующем диаграммы, удовлетворяющие данным свойствам, мы будем также называть диаграммами Мура. Диаграммы Мура позволяют строить о.-д. функции любого веса г. При такого рода построениях нужно иметь в виду, что хотя по формально заданной диаграмме Мура о.-д. функция восстанавливается Однозначно, однако если по этой о.-д. функции построить диаграмму Мура вышеуказанным способом, то она может не совпасть с исходной. Так, например, диаграмма, представленная на рис. 9, как нетрудно убедиться, задает функцию а =* х + у и отлична от диаграммы, приведенной на рис. 8.
Таким образом, не каждая диаграмма Мура с г вершинами изображает о.-д. функцию веса г. Однако диаграммы Мура позволяют оценить число о.-д. функций, зависящих от п переменных хи ..., хя и имеющих вес г. $ Теорема 2. Число р (к, л, г) о.-д. функций из зависящих от п переменных хи и имеющих
вес г, не превосходит (гк)ткП.
Доказательство. Возьмем диаграмму Мура для о.-д. функции веса г. В ней из каждой вершины исходит Лг *= кп ребер, причем а-е ребро соединено с одной из г
88 ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
вершин и ему приписана пара (а, ?у)» ГДО 0 < у < к — 1. Таким образом, число р(к, п, г) не превосходит числа диаграмм Мура вышеуказанного вида. Данные диаграммы могут быть получены следующим образом.
Возьмем г вершин, занумерованных числами 0, ...
..., г — 1 (0 — выделенная вершина), из каждой из которых исходит по N = кп ребер, занумерованных числами 0, ..N — 1.. Мы имеем гЛт ребер. Каждое ребро может быть соединено с любой из г вершин и ему может быть приписано любое из к чисел. Поэтому
р(к, п1г)<(гА-)гЛ’ = (г*)гА"
Теорема доказана.
Пусть ..., хп)— о.-д. функция. Рассмот-
рим ее диаграмму Мура. Предположим, что в момент ? — 1 мы находились ' в вершине у. {I — 1), тогда при поступлении в момент времени ? числа а(?) мы переместимся в диаграмме по ребру а (/), выходящему из вершины у (? — 4) (см. рис. 10), при этом получим выходное значение у{?) и перейдем в вершину к(1). Таким образом, величины (а (?), х (? — 1)) однозначно определяют величины (у(г)> х(1)).
Введенные ранее величины а и у будем называть соответственно входной и выходной величинами, ах — состоянием.
Пусть переменные А', (?, 2 таковы, что: А7 описывает значение входной величины а, () описывает значение состояния к ш 2 описывает значение выходной величины у.
На основании приведенных выше рассуждений мы приходим к следующим уравнениям *):
где е(0)-0. Данные уравнения называются каноническими уравнениями. Нетрудно перейти от векторной за-
*) Для констант из Роя, ь аналогичные построения дают уравнения, в которых отсутствует переменная X.
ГЛ. 3. О.-Д. ФУНКЦИИ С ОПЕРАЦИЯМИ 89
лиси канонических уравнений к скалярной. Пусть I = ==]^г[. Тогда
*(0 = Р' К (0, *? *, я„(0т (г — 1), ..., & (? — 1)),
?1 (0 = (Х1 (О, • - ?, ха (г), 0 — 1), ?. -, 41 {г — 1)),
Чі (0 = СІ (яГі (0, ..., Хп (І). Яі (* — 1)> • • > Яі (* — і)), <7і(0) = ... «а (0) = 0.
Здесь і7', — функции из определенные на
множестве являющемся подмножеством ИЗ Кц X ...ХІТі
?г+?
а именно: переменные хп пробегают значения из
Ек, а вектор {ц\, д:) принимает г значений (напри-
мер, двоичные записи чисел 0, 1, ..г—1). Очевпдпо, что множество & является цилиндром (или цилиндрическим) ПО X1, ,,,,ЖЛ*)1
Доопределив функции і7", Ои ..., на всей области Екх ? •.ХЕН, мы получим соответственно функции
ї 14~ ^
7^, из Рй, и канонические уравнения примут
более удобную для нас форму (так как здесь мы можем использовать развитый ранее аппарат формул):
z{t) = F(xl(t), хп{1), дЛ(? - 1), .$,{* - !))',
4і{1) Сі(?і(ї), ..хп{1), — 1), ..4і{Ь 1)),
(*)
Я1{1)=01{хі{1), хп(?), я,{1-і), Яі{і~і)),
?1(0) = ...«д,<0) = 0.
Для ограниченно-детерминированных функций, описанных в примерах 3, а) и 3, б), канонические уравнения
*) Множество & а Ек X ... х ^называется цилиндрическим
п+1
по первым координатам х\, ..хп тогда и только тогда, когда любые два набора (?', ..., ?#п, т|,) и (?", чА Чр ли-
бо одновременно принадлежат либо одновременно не принадлежат
Очевидно, что область определения с? функций Р', ,..,
является цилиндрическим множеством ПО ЯГ], , . Хп.
SO ч. I. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
имеют, соответственно, следующий вид: я (f) = (f) &л:2 (f);
z(t) = x{t)-\- y{t)+ g(t — 1) (mod 2),
q(t) = x{t)y{t)\/ x{t)q{t~ i)Vy(t)q{t~ 1),
g(0)-0.
Пример 4. Пусть о.-д. функция f(x) задана диаграммой Мура, приведенной на рис. 11. Для нее функции и & приведены в табл. 1.
о
Закодировав состояния 0, 1, № (в,1)
W,Q) ^ (Г, О)
8
Рис. 11
Таблица 1
X Q 9
0 0 0 1
0 1 0 1
0 2 1 2
1 0 0 2
1 1 1 1
1 2 0 2
наборами (0, 0), (0, 1) и (1, 0), мы получим функции F\ Glt G2 (см. табл. 2).
