Московский государственный университет Московский государственный университет
имени М. В. Ломоносова

Факультет вычислительной математики и кибернетики










В. Б. Алексеев, С. А. Ложкин




ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ,
СХЕМ И АВТОМАТОВ







Учебное пособие по курсам
``Введение в дискретную математику''
и ``Основы кибернетики''





















Москва 2000

УДК   519.95

ББК 22.176

А 47

Алексеев В.Б., Ложкин С.А. ``Элементы теории графов, схем и автоматов'' (учебное пособие для студентов) - М.: Издательский отдел ф-та ВМиК МГУ (лицензия ЛР N 040777 от 23.07.1996), 2000 г. - 58 с.

В программу курсов ``Введение в дискретную математику'' (1 курс) и ``Основы кибернетики'' (3-4 курс), которые являются обязательными для студентов, обучающихся по специальности 01.02 - прикладная математика, входят различные вопросы теории графов, схем и автоматов. В основных учебных пособиях по данным курсам некоторые из этих вопросов отсутствуют. Методическая разработка призвана восполнить указанный пробел. В ее первой части рассматриваются некоторые свойства деревьев и планарных графов. Во второй части разработки описываются различные типы схем и устанавливаются связи между ними, изучается сложность реализации этими схемами некоторых функций. В третьей части рассматриваются автоматы и их реализация схемами, а также эксперименты с автоматами.

Рецензенты: Лупанов О.Б., чл.-корр.РАН, профессор Сапоженко А.А., д.ф.-м.н., профессор

Печатается по решению Ученого Совета факультета вычислительной математики и кибернетики МГУ им.М.В.Ломоносова.

ISBN   5-89407-087-2
                                                    ©Издательский отдел
факультета вычислительной
математики и кибернетики
МГУ им.М.В.Ломоносова,2000

ОГЛАВЛЕНИЕ


Введение

4

Часть 1. Графы

6
x1 Основные понятия теории графов 6
x2 Деревья 12
x3 Планарные графы 16

Часть 2. Схемы

22
x4 Формулы и схемы из функциональных элементов. Задача
синтеза и простейшие способы ее решения 22
x5 Реализация некоторых "управляющих" систем функций
алгебры логики в классе СФЭ 28
x6 Реализация некоторых "арифметических" систем ФАЛ
в классе СФЭ 35
x7 Метод Шеннона для синтеза СФЭ. Верхняя и нижняя
оценки функции Шеннона и сложности некоторых ФАЛ 40

Часть 3. Автоматы

48
x8 Автоматные функции. Их реализация схемами из
функциональных элементов и элементов задержки 48
x9 Эксперименты с автоматами. Теорема Мура 54
ВВЕДЕНИЕ

При изучении дискретных систем, в частности, систем преобразования информации, требуется строить математические модели, описывающие структуру или функционирование таких систем. В учебном пособии рассматриваются некоторые из таких моделей.

Одним из наиболее важных понятий, относящихся к структуре дискретных систем, является понятие графа. Это понятие, описывающее структуру связей между отдельными частями системы, в силу своей общности используется во многих математических моделях.

Графы очень часто используются в приложениях, поскольку они возникают как модель при изучении многих объектов. Например, структура молекулы является графом, в котором вершинами служат атомы, а ребрами - валентные связи. Блок-схема алгоритма представляет собой орграф, в котором вершинами являются отдельные операторы, а дуги указывают переходы между ними. Другие примеры графов: узлы и соединения в электрической цепи, схема дорог, множество предприятий с указанием двухсторонних связей между ними, группа людей с указанием их психологической совместимости, структура управления с указанием объектов и их подчиненности друг другу и т.д.

Тематика исследований, связанных с графами, очень широка. Это и исследование структуры и свойств графов, изучение специальных классов графов, построение быстрых алгоритмов для решения различных задач на графах и т. д. Здесь мы рассмотрим только некоторые простые вопросы, относящиеся к свойствам произвольных графов, а также рассмотрим два важных класса графов - деревья и планарные графы, - и изучим их свойства.

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

При изучении схем решаются две основные задачи: задача анализа и задача синтеза. Задача анализа состоит в нахождении функционирования данной схемы, а задача синтеза - в построении схемы, имеющей (реализующей) заданное функционирование. Каждая из этих задач может рассматриваться либо как индивидуальная задача, и тогда ее решением является конкретное функционирование (схема), либо как массовая задача, и тогда ее решением должен быть алгоритм нахождения функционирования (схемы). Задача синтеза имеет, как правило, множество решений, из которых выбирают решение, оптимальное по какому-либо критерию. Чаще всего в качестве такого критерия выступает сложность схемы, понимаемая как сумма сложностей составляющих ее элементов.

В §§ 4-7 мы мы рассмотрим, как решается задача синтеза для схем из функциональных элементов - для преобразователей без памяти, реализующих некоторые системы булевых функций. В §§ 8-9 рассматриваются автоматы-преобразователи с памятью, работающие по тактам в дискретном времени. Кроме задач анализа и синтеза автоматов, которые рассматриваются в §8, изучаются также эксперименты с автоматами (§ 9), что тесно связано с тестированием вычислительных устройств.

Часть 1. Графы


xx 1. Основные понятия теории графов


Определение. Графом G (в широком понимании) называется любая пара (V,E), где V = {v1, v2, ... } - множество элементов любой природы, а E = {e1, e2, ... } - семейство пар элементов из V, причем допускаются пары вида (vi, vi) и одинаковые пары. Если пары в V рассматриваются как неупорядоченные, то граф называется неориентированным, если как упорядоченные, то граф называется ориентированным (орграфом).

Элементы множества V называются вершинами графа, а пары из E - его ребрами; в орграфе они называются ориентированными ребрами или дугами.

Говорят, что ребро e = (u,v) в неориентированном графе соединяет вершины u и v, а в ориентированном графе дуга e = (u,v) идет из вершины u в вершину v.

Графы можно условно изображать следующим образом. Вершины будем изображать точками, а каждое ребро (дугу) (vi, vj) О E - линией, соединяющей точки, соответствующие vi и vj. Если (vi, vj) - дуга, то на этой линии будем указывать стрелку от vi к vj.

На рис. 1.1 приведены неориентированный и ориентированный графы G = (V,E), где V = {1,2,3,4 }, E = {e1, e2, e3, e4, e5, e6, e7 } и e1 = (1,2), e2 = (2,3), e3 = (3,4), e4 = (4,2), e5 = (1,4), e6 = (4,2), e7 = (1,1).


Picture Omitted
Рис. 1.1.

Пара вида (vi, vi) называется петлей в вершине vi. Если пара (vi, vj) встречается в E более одного раза, то говорят, что (vi, vj) - кратное ребро. В графах на рис. 1.1 (4,2) - кратное ребро, e7 - петля.

Замечание. Часто в литературе под графом понимается граф без петель и кратных ребер. В этом случае граф с кратными ребрами называют мультиграфом, граф с кратными ребрами и петлями - псевдографом.

Графы очень часто используются в приложениях, поскольку они возникают как модель при изучении многих объектов. Например, структура молекулы является графом, в котором вершинами являются атомы, а ребрами - валентные связи. Блок-схема алгоритма представляет собой орграф, в котором вершинами являются отдельные операторы, а дуги указывают переходы между ними. Другие примеры графов: элементы и соединения в электрической цепи, схема перекрестков и дорог, множество предприятий с указанием двухсторонних связей между ними, группа людей с указанием их психологической совместимости, структура управления с указанием объектов и их подчиненности друг другу и т. д.

Определение. Говорят, что вершины vi и vj смежны в графе G = (V,E), если в E входит пара (vi, vj) или (vj, vi). Говорят, что ребро (дуга) (vi, vj) инцидентно вершинам vi и vj.

Определение. Степенью вершины в неориентированном графе называется число ребер, инцидентных данной вершине, при этом петли учитываются дважды. Вершины степени 0 называют изолированными.

Например, в неориентированном графе на рис. 1.1 степень вершины 3 равна 2, степени остальных вершин равны 4.

Теорема 1.1. Пусть в графе G p вершин и q ребер. Пусть deg vi - степень вершины vi. Тогда
p
е
i = 1 
deg vi = 2q.

Доказательство. Когда мы считаем степень одной вершины, мы считаем все ребра, выходящие из нее. Вычисляя сумму всех степеней, мы получаем, что каждое ребро считается дважды, так как оно инцидентно двум вершинам (петли по определению степени также посчитаются дважды). Поэтому общая сумма будет равна удвоенному числу ребер.

В ориентированном графе можно определить степень так же, как в неориентированном графе, если не учитывать ориентацию. Кроме этого, для ориентированных графов вводится следующее определение.

Определение. Полустепенью исхода d-(v) (полустепенью захода d+(v)) вершины v в ориентированном графе называется число дуг, выходящих из данной вершины (соответственно входящих в данную вершину).

Легко видеть, что в любом ориентированном графе выполняется равенство
p
е
i = 1 
deg-(vi) = p
е
i = 1 
deg+(vi),
поскольку в обеих частях равенства каждая дуга учитывается ровно 1 раз.

Для человека удобно геометрическое представление графа, такое, например, как на рис 1.1. В компьютере используют другие, ``более дискретные'', способы представления графов. Один из наиболее распространенных способов - представление графа матрицей смежности.

Определение. Пусть граф G имеет p вершин и пусть его вершины занумерованы числами 1, 2, ... , p. Матрица с p строками и p столбцами называется матрицей смежности графа G, если для любых 1 Ј i Ј p и 1 Ј j Ј p   a[i, j] равно числу ребер (дуг), идущих из вершины i в вершину j.

Например, графы, изображенные на рис. 1.1, представляются следующими матрицами смежности.


ж
з
з
з
з
з
з
и
1
1
0
1
1
0
1
2
0
1
0
1
1
2
1
0
ц
ч
ч
ч
ч
ч
ч
ш
                        ж
з
з
з
з
з
з
и
1
1
0
1
0
0
1
0
0
0
0
1
0
2
0
0
ц
ч
ч
ч
ч
ч
ч
ш

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

Однако, если в графе мало ребер, то представление графа матрицей смежности может быть не очень хорошим. Например, если в графе 50 вершин, то матрица будет иметь 2500 элементов, хотя в графе может оказаться лишь несколько сотен ребер. В таких случаях используют списки смежностей. Для каждой вершины образуется список, в который заносят все вершины, в которые из данной вершины идут ребра (дуги). Например, графы, изображенные на рис. 1.1, представляются следующими списками смежностей


1:
1,
2,
4;
2:
1,
3,
4,
4;
3:
2,
4;
4:
1,
2,
2,
3.
                               
1:
1,
2,
4;
2:
3;
3:
4;
4:
2,
2.

При представлении графов списками смежностей и при динамическом изменении графов необходимо использовать алгоритмы работы со списками, что хорошо реализуется в ряде алгоритмических языков.

При изучении структуры графов некоторые графы можно не различать.

Определение. Пусть G1 = (V1,E1) и G2 = (V2,E2) - два графа. Тогда G1 и G2 называются изоморфными, если существуют взаимно однозначные отображения f1: V1 ® V2, f2: E1 ® E2 такие, что для любого ребра (дуги) (u,v) О E выполняется f2 (u,v) = (f1(u),f1(v)). Другими словами, соответствующие ребра должны соединять соответствующие вершины.

Для графов без петель и кратных ребер это определение эквивалентно следующему более простому определению.

Определение (для графов без петель и кратных ребер). Графы G1 = (V1,E1) и G2 = (V2,E2) называются изоморфными, если существует взаимно однозначное отображение f: V1 ® V2 такое, что (u,v) О E1Ы (f(u),f(v)) О E2.

Рассмотрим теперь некоторые понятия, связанные с внутренней структурой графа.

Определение. Граф G1 = (V1,E1) называется подграфом графа G = (V,E), если V1 Н V и E1 Н E.

Определение. Путем в графе (орграфе) G = (V,E) называется последовательность вершин и ребер (дуг) вида


v0, (v0, v1), v1, ... , vn-1, (vn-1, vn), vn,

где все vi О E и все (vi, vi+1) О E. Длина пути - это число ребер (дуг) в нем. Говорят, что этот путь идет из v0 в vn.

Цепь - это путь без повторяющихся ребер (дуг), простая цепь - путь без повторяющихся вершин.

Лемма 1.1. Из любого пути, идущего из v0 в vn, где v0 vn, можно выделить подпуть из v0 в vn, являющийся простой цепью.

Доказательство. Пусть данный путь - не простая цепь. Тогда в нем повторяется некоторая вершина v, то есть он имеет вид: P1 = v0C1vC2vC3vn. Тогда он содержит подпуть P2 = v0C1vC3vn. Если в P2 повторяется некоторая вершина, то аналогично удалим еще кусок и т. д. Процесс должен закончиться, т. к. P1 - конечный путь.

Определение. Путь называется замкнутым, если vn = v0. Путь называется циклом, если vn = v0 и ребра (дуги) не повторяются. Путь называется простым циклом, если vn = v0 и больше нет повторений вершин.

Далее под графом будут пониматься только конечные неориентированные графы.

Определение. Граф G = (V,E) называется связным, если для любых двух вершин vi, vj О V в G существует путь из vi в vj.

Отношение ``существует путь из вершины v в вершину w в графе G'' является отношением эквивалентности на множестве вершин. Поэтому, если граф G не связный, то его вершины можно разбить на несколько подмножеств так, что вершины в одном и том же множестве можно соединить путем, а вершины из разных множеств нельзя соединить путем. Каждое такое множество вершин вместе с ребрами графа G, соединяющими эти вершины, называется связной компонентой графа G. Так, например, граф на рис. 1.2 имеет 3 связных компоненты.


Picture Omitted
Рис. 1.2.

Докажем теперь несколько вспомогательных утверждений о связности и циклах, которые потребуются нам в дальнейшем.

Лемма 1.2. Если граф G = (V,E) связный и a О V, b О V, a b, и (a,b) П E, то при добавлении к графу G ребра (a,b) в полученном графе будет простой цикл.

Доказательство. Так как G - связный граф, то в нем есть путь из a в b. Тогда по лемме 1.1 в G есть простая цепь C из a в b. Поэтому в полученном графе есть цикл C, (b,a), a.

Лемма 1.3. Если граф G = (V,E) связный и ребро (a,b) содержится в некотором цикле в графе G, то при выбрасывании из графа G ребра (a,b) снова получится связный граф.

Доказательство. Это утверждение следует из того, что при выбрасывании из графа G ребра (a,b) вершины a и b все равно остаются в одной связной компоненте, поскольку из a в b можно пройти по оставшейся части цикла.

Лемма 1.4. Пусть в графе G = (V,E) p вершин и q ребер. Тогда в G не менее p-q связных компонент. Если при этом в G нет циклов, то G состоит ровно из p-q связных компонент.

Доказательство. Пусть к некоторому графу H, содержащему вершины u, v, добавляется ребро (u,v). Тогда если u, v лежат в разных связных компонентах графа H, то число связных компонент уменьшится на 1. Если u, v лежат в одной связной компоненте графа H, то число связных компонент не изменится. В любом случае число связных компонент уменьшается не более чем на 1. Значит при добавлении q ребeр число связных компонент уменьшается не более чем на q. Так как граф G получается из графа G1 = (V,Ж) добавлением q ребeр, то в G не менее p-q связных компонент. Пусть теперь в G нет циклов, и пусть в процессе получения G из G1 добавляется ребро (u,v). Если бы u, v лежали уже в одной связной компоненте, то в G, согласно лемме 1.2, возникал бы цикл. Следовательно, u, v лежат в разных связных компонентах и при добавлении ребра (u,v) число связных компонент уменьшается ровно на 1. Тогда G состоит ровно из p-q связных компонент.

Следствие. Если q Ј p-2, то любой граф с p вершинами и q ребрами не связен.

Доказательство. По лемме 1.4 число связных компонент не менее p-q і 2.

Если граф G с p вершинами задан матрицей смежности A, то быстрое нахождение связных компонент можно осуществить следующим образом. Рассмотрим матрицу I1 порядка p, в которой на диагонали стоят 1, I1(i,j) = 1, если a(i,j) > 0 и I1(i,j) = 0, если a(i,j) = 0. Тогда равенство I1(i,j) = 1 равносильно тому, что из вершины с номером i в вершину с номером j существует путь длины не более 1. Определим теперь матрицу Ik порядка p, в которой Ik(i,j) = 1 тогда и только тогда, когда из вершины с номером i в вершину с номером j существует путь длины не более k. Легко понять, что все матрицы Ik при k і p-1 совпадают и элемент с номером (i,j) в них равен 1 тогда и только тогда, когда из вершины с номером i в вершину с номером j существует хотя бы один путь. Обозначим такую матрицу IҐ. Рассмотрим операцию умножения матриц, которая отличается от обычного умножения только тем, что вместо сложения используется дизъюнкция. Тогда легко видеть, что Ik+1 = Ik·I1.

Утверждение. Пусть p-1 Ј 2m. Тогда матрицу IҐ можно получить из матрицы I1, используя не более 2p3m операций конъюнкции и дизъюнкции.

Доказательство. Будем последовательно вычислять матрицы I2, I4, I8, ..., I2m, возводя предыдущую матрицу в квадрат. Возведение матрицы в квадрат (по обычному правилу: ``строчка на столбец'') требует не более 2p3 операций конъюнкции и дизъюнкции. Доказываемое утверждение следует из того, что I2m = IҐ, поскольку p-1 Ј 2m.


xx 2. Деревья


Определение. Граф G = (V,E) называется деревом, если он связный и не содержит циклов. Вершины степени 1 в дереве называют его листьями.

Определение. Подграф G1 = (V1,E1) графа G = (V,E) называется остовным деревом, если G1 - дерево и V1 = V.

Теорема 2.1. Любой (конечный) связный граф G = (V,E) содержит хотя бы одно остовное дерево G1 = (V,E1).

Доказательство. Если в G нет циклов, то положим G1 = G. Если в G есть циклы, то удалим из G какое-нибудь ребро, входящее в цикл. Получится некоторый подграф Gў . По лемме 1.3 Gў - связный граф. Если в Gў нет циклов, то положим G1 = Gў, иначе продолжим этот процесс. Процесс должен завершиться, так как E - конечное множество.

Теорема 2.2. Пусть в дереве G имеется p вершин и q ребер. Тогда q = p-1.

Доказательство. Так как G - связный граф и G не содержит циклов, то p-q = 1 по лемме 1.4. Отсюда q = p-1.

Понятие дерева можно определить различными способами, что вытекает из следующей теоремы.

Теорема 2.3. Пусть G = (V,E) - неориентированный граф без петель и кратных ребер, |V| = p, |E| = q. Тогда следующие 5 условий эквивалентны:

1) G - дерево;

2) G - без циклов и q = p-1;

3) G - связный и q = p-1;

4) G - связный, но при удалении любого ребра становится несвязным;

5) G - без циклов, но при добавлении любого нового ребра на тех же вершинах появляется цикл.

Доказательство. Докажем следущие переходы 1)Ю 2)Ю3)Ю 4)Ю 5)Ю 1), откуда будет следовать, что из любого условия вытекает любое другое.

Переход 1)Ю 2) следует из теоремы 2.2. Пусть теперь выполняется 2). Тогда по лемме 1.4 в G число связных компонент равно p-q = 1, то есть G - связный граф. Отсюда следует переход 2)Ю 3). Переход 3)Ю 4) вытекает из следствия к лемме 1.4. Пусть выполняется 4). Тогда если бы в G был цикл, то при удалении любого ребра из этого цикла G остался бы связным, согласно лемме 1.3. Это противоречило бы 4). Значит G не имеет циклов. Вторая часть условия 5) вытекает, согласно лемме 1.2, из того, что G связный. Таким образом, получаем, что 4)Ю 5). Пусть выполняется 5). Если при этом G - не связный граф и вершины u, v лежат в разных связных компонентах графа G, то добавление к G ребра (u,v), очевидно, не порождает циклов, что противоречит 5). Отсюда следует, что G - связный граф, то есть 5)Ю 1). Теорема доказана.

Условия 4) и 5) показывают, что множество всех деревьев - это множество всех минимальных связных графов и, в то же время, множество всех максимальных графов без циклов.

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

Определение. 1) Граф, имеющий одну вершину v, которая выделена, и не имеющий ребер, является корневым деревом с корнем v.

2) Пусть D1, D2, ... , Dm, где m і 1 - корневые деревья с корнями v1, v2, ... , vm. Пусть Di = (Vi, Ei) и ViЗVj = Ж при i j. Пусть v П V1ИV2И... ИVm. Тогда граф D = (V,E), где V = V1ИV2И... ИVmИ{v}, E = E1ИE2И... ИEmИ{(v,v1),... ,(v,vm)} и выделена вершина v, является корневым деревом с корнем v (см. рис. 2.1). При этом D1, D2, ... , Dm называются поддеревьями корневого дерева D.


Picture Omitted

Рис. 2.1.

3) Только такие графы называются корневыми деревьями, которые могут быть построены по 1) и 2).

Например, файловая структура в компьютере является корневым деревом. При этом корню соответствует сам компьютер, вершинам второго яруса соответствуют диски A, B, C, D и т. д., вершинам третьего яруса соответствуют директории, вершинам следующих ярусов соответствуют поддиректории и файлы.

Определение. Упорядоченное корневое дерево - это корневое дерево D, в котором задан порядок его поддеревьев D1, D2,... , Dm (можно считать, что числами 1,2,... , m занумерованы ребра, выходящие из корня дерева D) и каждое Di - само есть упорядоченное корневое дерево.

Теорема 2.4. Число упорядоченных корневых деревьев с q ребрами не превосходит 4q.

Доказательство. Рассмотрим важный для приложений способ обхода упорядоченного корневого дерева, который называют ``поиском в глубину''. Этот обход описывается рекурсивно следующим образом. 1) Начать из корня дерева D; 2) пока есть поддеревья, перейти по ребру в корень очередного поддерева, рекурсивно обойти это поддерево ``в глубину'', вернуться в корень исходного дерева. В результате обход ``в глубину'' проходит по каждому ребру дерева D ровно 2 раза: один раз при переходе в очередное поддерево, второй раз при возвращении из этого поддерева. В соответствии с обходом ``в глубину'' будем строить последовательность из 0 и 1, записывая на каждом шаге 0 или 1, причем 0 будем записывать, если происходит переход в очередное поддерево, а 1, если мы возвращаемся из поддерева. Получим последовательность из 0 и 1 длины 2q, которую назовем кодом дерева D. По этому коду однозначно восстанавливается дерево D, поскольку каждый очередной разряд однозначно указывает, начинать ли строить новое очередное поддерево или возвращаться на ярус ближе к корню. Таким образом, упорядоченных корневых деревьев с q ребрами не больше, чем последовательностей из 0 и 1 длины 2q, а их число равно 22q = 4q.

Изоморфизм корневых деревьев определяется так же, как изоморфизм обычных графов, но дополнительно требуется, чтобы корню одного дерева сопоставлялся при изоморфизме корень другого дерева. Для упорядоченных корневых деревьев дополнительно требуется, чтобы при изоморфизме сохранялась упорядоченность.

Следствие. Число неизоморфных корневых деревьев с q ребрами и число неизоморфных обычных деревьев с q ребрами не превосходит 4q.

Доказательство. Выделяя в неизоморфных деревьях по одной точке, мы получим неизоморфные корневые деревья. Упорядочивая поддеревья в неизоморфных корневых деревьях, мы получим различные упорядоченные корневые деревья. Поэтому число неизоморфных деревьев с q ребрами не превосходит числа неизоморфных корневых деревьев с q ребрами, которое, в свою очередь, не превосходит числа различных упорядоченных корневых деревьев с q ребрами. Отсюда и из теоремы 2.4 получаем доказываемое следствие.

Отметим, что корневые деревья часто рассматривают как ориентированные.

Определение. Ориентированным деревом называется корневое дерево, все ребра которого ориентированы к корню.

В ориентированных деревьях нет ориентированных циклов. Но это не единственные графы, обладающие этим свойством.

Определение. Ориентированным ациклическим графом называется любой ориентированный граф, в котором нет ориентированных циклов.

Определение. Вершина ориентированного графа называется истоком (стоком), если в нее не входит ни одна дуга, то есть d+(v) = 0, (соответственно, из нее не выходит ни одной дуги, то есть d-(v) = 0.

Утверждение 1.1. В любом (конечном) ориентированном ациклическом графе есть хотя бы один исток и хотя бы один сток.

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

Определение. Глубиной вершины v в ориентированном ациклическом графе называется максимальная длина ориентированного пути из всех истоков в вершину v.

Это определение корректно в силу утверждения 1.1. При этом глубина каждой вершины в ориентированном ациклическом графе не превосходит p-1, где p - число вершин в графе.

Утверждение 1.2. Пусть (u,v) - дуга в ориентированном ациклическом графе. Тогда глубина вершины v больше, чем глубина вершины u.

Доказательство следует из того, что если из некоторого истока в вершину u существует ориентированный путь длины k, то из того же истока в вершину v существует ориентированный путь длины k+1.


xx 3. Планарные графы


Пусть задан неориентированный граф G = (V,E). Пусть каждой вершине vi из V сопоставлена точка ai в некотором евклидовом пространстве, причем ai aj при i j. Пусть каждому ребру e = (vi, vj) из E сопоставлена непрерывная кривая L, соединяющая точки ai и aj и не проходящая через другие точки ak. Тогда если все кривые, сопоставленные ребрам графа, не имеют общих точек, кроме концевых, то это множество точек и кривых называется геометрической реализацией графа G.

Теорема 3.1. Каждый конечный граф G можно реализовать в трехмерном евклидовом пространстве (без пересечения ребер).

Доказательство. Возьмем в пространстве любую прямую l и разместим на ней все вершины графа G. Пусть в G имеется q ребер. Проведем q полуплоскостей через l так, чтобы прямая l была их общим ребром (типа тетрадки). После этого каждое ребро графа G можно изобразить линией в своей полуплоскости и они, очевидно, не будут пересекаться.

Определение. Граф называется планарным, если существует его планарная реализация, то есть геометрическая реализация на плоскости (без пересечения ребер).

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

Теорема 3.2 (формула Эйлера.) Для любой планарной реализации связного планарного графа G = (V,E) с p вершинами, q ребрами и r гранями выполняется равенство: p-q+r = 2.

Доказательство. При фиксированном p индукцией по q. Так как G - связный граф, то q і p-1 по следствию из леммы 1.4.

а) Базис индукции: q = p-1. Так как G - связный и q = p-1, то по теореме 2.3 G - дерево, то есть в G нет циклов. Тогда r = 1. Отсюда p-q+r = p-(p-1)+1 = 2.

б) Пусть для p-1 Ј q < q0 теорема справедлива. Докажем, что для q = q0 она тоже справедлива. Пусть G - связный граф с p вершинами и q0 ребрами и пусть в его планарной реализации r граней. Так как q0 > p-1, то G - не дерево. Следовательно, в G есть цикл. Пусть ребро e входит в цикл. Тогда к нему с двух сторон примыкают разные грани. Удалим ребро e из G. Тогда две грани сольются в одну, а полученный граф G1 по лемме 1.3 останется связным. При этом получится планарная реализация графа G1 с p вершинами, q0-1 ребрами и r-1 гранями. Так как q0-1 < q0, то, по предположению индукции, для G1 справедлива формула Эйлера, то есть p-(q0-1)+(r-1) = 2, откуда p-q0+r = 2. Что и требовалось доказать.

Следствие 1. Формула Эйлера справедлива и для геометрической реализации связных графов на сфере.

Доказательство. Пусть связный граф G с р вершинами и q ребрами реализован на сфере S так, что число граней равно r. Пусть точка A на сфере не лежит на линиях этой геометрической реализации. Пусть P - некоторая плоскость. Поставим сферу S на P так, чтобы точка A была самой удаленной от плоскости. Спроектируем S на P центральным проектированием с центром в A. Тогда на плоскости P мы получим геометрическую реализацию связного графа с р вершинами и q ребрами, причем число граней будет равно r (грань на сфере, содержащая A, отображается во внешнюю грань на плоскости). По теореме 3.2 получаем p-q+r = 2.

Следствие 2. Для любого выпуклого многогранника справедливо равенство p-q+r = 2, где p - число вершин, q - число ребер, r - число граней.

Доказательство. Пусть выпуклый многогранник M имеет р вершин, q ребер и r граней. Пусть O - внутренняя точка многогранника М. Рассмотрим сферу S с центром в O настолько большого радиуса, чтобы M целиком лежал внутри S. Рассмотрим центральное проектирование с центром в точке O, и спроектируем вершины и ребра M на S. Тогда на S мы получим геометрическую реализацию некоторого связного графа с р вершинами, q ребрами и r гранями. Отсюда p-q+r = 2.

Формула Эйлера позволяет доказать непланарность некоторых графов.

Определение. Графом K5 называется граф с 5 вершинами, в котором каждая пара вершин соединена ребром (см. рис. 3.1).

Теорема 3.3. Граф K5 не планарен.

Доказательство. Допустим, что для графа K5 существует планарная реализация. Так как граф K5 связен, то для этой планарной реализации справедлива формула Эйлера p-q+r = 2. Поскольку в графе K5 имеем p = 5 и q = 10, то число всех граней должно равняться r = 2-p+q = 7. Пусть грани занумерованы 1, 2, ..., r и пусть при обходе i-ой грани по периметру (по ее краю) проходится qi ребер. Так как при этом каждое ребро проходится дважды (оно является стороной для двух граней), то еi = 1r qi = 2q = 20. Но в каждой грани не менее 3 сторон. Поэтому qi і 3 для всех i. Отсюда еi = 1r qi і 3r = 21. Получаем 20 і 21 - противоречие. Значит для графа K5 не существует планарной реализации.


Picture Omitted

Рис. 3.1.

Определение. Графом K3,3 называется граф с 6 вершинами a1, a2, a3, b1, b2, b3, в котором каждая вершина ai соединена ребром с каждой вершиной bj и нет других ребер (см. рис. 3.1).

С графом K3,3 связана следующая известная задача о трех домах и трех колодцах. Есть 3 дома и 3 колодца, но хозяева домов в большой вражде. Можно ли так проложить дорожки от каждого дома к каждому колодцу, чтобы они нигде не пересекались?

Ответ на этот вопрос дает следующая теорема.

Теорема 3.4. Граф K3,3 не планарен.

Доказательство. Допустим, что для графа K3,3 существует планарная реализация. Так как граф K3,3 связен, то для этой планарной реализации справедлива формула Эйлера p-q+r = 2. Поскольку в графе K3,3 имеем p = 6 и q = 9, то число всех граней должно равняться r = 2-p+q = 5. Так же, как в доказательстве предыдущей теоремы, получаем, что еi = 1r qi = 2q = 18, где qi - число сторон в i-ой грани. Но в графе K3,3 нет циклов длины 3. Поэтому в каждой грани не менее 4 сторон. Следовательно, qi і 4 для всех i. Отсюда еi = 1rqi і 4r = 20. Получаем 18 і 20 - противоречие. Значит для графа K3,3 не существует планарной реализации.

Граница любой грани является путем в графе, так, например, границей внутренней грани на рис. 3.2 является путь (указаны только вершины): 1,2,4,5,4,6,4,2,3,1. Пусть длина границы i-ой грани (число ребер) равна qi (для грани на рис. 3.2 q = 9).


Picture Omitted
Рис. 3.2.

Лемма 3.1. Для любой геометрической реализации на плоскости связного планарного графа с q ребрами выполняется равенство:
r
е
i = 1 
qi = 2q,
где суммирование ведется по всем граням (включая внешнюю грань).

Доказательство. Равенство следует из того, что у каждого ребра две стороны и при суммировании qi каждое ребро учитывается дважды: либо оно входит в границы двух соседних граней, либо оно дважды учитывается в одной грани.

Теорема 3.5. Если в связном планарном графе G = (V,E) с p вершинами и q ребрами нет циклов длины меньше k (k і 3), то q Ј [k/(k-2)](p-2).

Доказательство. Так как по условию qi і k для всех k, то из леммы 3.1 получаем 2q і kr и r Ј [2q/k]. Из формулы Эйлера r = 2-p+q. Отсюда 2-p+q Ј [2q/k]. Далее (k-2)q Ј k(p-2) и q Ј [k/(k-2)](p-2).

Следствие 1. Для любого связного планарного графа G = (V,E) без петель и кратных ребер с p вершинами и q ребрами справедливо неравенство: q Ј 3(p-2).

Указание. В теореме 3.5 можно взять k = 3.

Следствие 2. Для любого планарного графа G = (V,E) без петель и кратных ребер с p вершинами, q ребрами и m связными компонентами справедливо неравенство: q Ј 3(p-2m).

Доказательство. Пусть в i-ой связной компоненте (i = 1,2,... ,m) pi вершин и qi ребер. Тогда в ней по следствию 1 qi Ј 3(pi-2). Суммируя все эти неравенства, получаем q Ј 3(p-2m).

Следствие 3. В любом планарном графа G = (V,E) без петель и кратных ребер есть вершина степени не более 5.

Доказательство. Пусть G - планарный граф с p вершинами и q ребрами. Тогда q Ј 3(p-2) < 3p. Пусть dmin - минимальная степень вершин в G. Тогда с учетом теоремы 1.1 получаем
6p > 2q = p
е
i = 1 
deg vi і pdmin.
Отсюда dmin < 6, то есть dmin Ј 5.

Если ребро графа изображено в виде линии, то можно на ней поставить точку и считать ее новой вершиной степени 2. Формально эта операция определяется следующим образом.

Определение. Пусть G - любой граф и (a,b) - его ребро. Операцией подразделения ребра (a,b) называется удаление из графа G ребра (a,b), добавление новой вершины c и добавление двух новых ребер (a,c) и (c,b).

Определение. Граф G1 называется подразделением графа G, если G1 может быть получен из G несколькими подразделениями ребер.

Определение. Графы G1 и G2 называются гомеоморфными, если существуют их подразделения, которые изоморфны.

Существует следующий критерий планарности.

Теорема 3.6 (Понтрягина-Куратовского). Для того, чтобы граф G был планарным, необходимо и достаточно, чтобы он не содержал ни одного подграфа, гомеоморфного графам K5 или K3,3.

Доказательство. 1) Необходимость. Пусть G - планарный. Допустим, что он содержит подграф G1, гомеоморфный графу K5 или K3,3. Рассмотрим планарную реализацию графа G. Удалив лишние вершины и ребра, мы получим планарную реализацию подграфа G1. Но G1 геометрически - это граф K5 или K3,3 с точками на ребрах. Если проигнорировать эти точки, то мы получим планарную реализацию графа K5 или K3,3. Но это невозможно по теоремам 3.3 и 3.4.

2) Достаточность доказывается тяжело, и здесь мы это доказательство опустим. Доказательство можно найти, например, в [2].

Подмножество вершин графа называется независимым, если никакие вершины из этого подмножества не смежны (не соединены ребром). Во многих приложениях рассматриваются разбиения вершин на независимые подмножества. Такие разбиения удобно описывать следующим образом.

Определение. Пусть K = {C1, C2, ... , Cm} - произвольное множество элементов, называемых цветами. Отображение C: V ® {C1,C2, ... , Cm}, где V - множество вершин графа G, называется раскраской (вершинной) графа G. Раскраска называется правильной, если для любого ребра (v1, v2) О E выполняется C(v1) C(v2).

Teорема 3.7. Вершины любого планарного графа можно правильно раскрасить в не более чем 5 цветов.

Доказательство (индукцией по числу вершин p).

1) Базис индукции: p = 1 - очевидно.

2) Пусть для p < p0 утверждение справедливо и пусть G = (V,E) - планарный граф с |V| = p0. По следствию 3 из теоремы 3.5 в G есть вершина v степени не более 5. Рассмотрим укладку на плоскости графа G без пересечения ребер. Удалим из G вершину v и все инцидентные ей ребра. Получим планарный граф G1 с числом вершин p0-1. По предположению индукции его вершины можно правильно раскрасить в 5 цветов C1, C2, C3, C4, C5. Пусть в G вершина v смежна с v1, v2, ... , vk, (где k Ј 5). Рассмотрим 2 варианта:

а) Среди цветов вершин v1, v2, ... , vk в G нет цвета Ci (1 Ј i Ј 5). Тогда вершине v припишем цвет Ci и получим правильную раскраску графа G в 5 цветов.

б) Степень вершины v равна 5 и среди вершин v1, v2, ... ,v5 в G1 есть все 5 цветов. Без ограничения общности будем считать, что в укладке графа G ребра (v, v1), (v, v2), (v, v3), (v, v4), (v, v5) выходят из v в порядке по часовой стрелке и что C(vi) = Ci, i = 1,... ,5. Пусть V1 - множество всех вершин в G1, до которых можно дойти из v1 по ребрам графа G1, используя только вершины цветов C1 и C3. Возможны 2 варианта:

б1) v3 П V1. Тогда в V1 поменяем цвета C1 ® C3, C3 ®C1. Так как вершины из V1 не смежны с другими вершинами цветов C1 и C3, то останется правильная раскраска и среди v1, v2,... , v5 не будет цвета C1. Тогда вершине v припишем цвет C1.

б2) v3 О V1. Это значит, что в G1 есть цепь из v1 в v3, все вершины которой имеют цвета C1 и C3. Эта цепь вместе с ребрами (v3,v) и (v, v1) образует цикл в G, причем вершины v2 и v4 лежат по разные стороны от этого цикла. Это значит, что из v2 нельзя пройти в v4 в графе G1 только по вершинам цветов C2 и C4. Пусть V2 - множество всех вершин в G1, до которых можно дойти из v2 по ребрам графа G1, используя только вершины цветов C2 и C4. Тогда v4 П V2 и далее поступаем как в б1).

В любом случае вершины графа G можно правильно раскрасить в не более чем 5 цветов, и теорема доказана.

Часть 2. Схемы


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

При изучении схем решаются две основные задачи: задача анализа и задача синтеза. Задача анализа состоит в нахождении функционирования данной схемы, а задача синтеза - в построении схемы, имеющей (реализующей) заданное функционирование. Каждая из этих задач может рассматриваться либо как индивидуальная задача, и тогда ее решением является конкретное функционирование (схема), либо как массовая задача, и тогда ее решением должен быть алгоритм нахождения функционирования (схемы). Задача синтеза имеет, как правило, множество решений, из которых выбирают решение, оптимальное по какому-либо критерию. Чаще всего в качестве такого критерия выступает сложность схемы, понимаемая как сумма сложностей составляющих ее элементов.

В § 4-8 мы рассмотрим, как решается задача синтеза для некоторых конкретных видов схем.


xx 4. Формулы и схемы из функциональных элементов. Задача синтеза и простейшие способы ее решения


В [8, с. 14-20] дано индуктивное определение формулы и реализуемой ею функции алгебры логики (ФАЛ). С содержательной точки зрения формула представляет собой слово, построенное из символов ``базисных'' ФАЛ, символов булевых переменных (БП) и разделителей, которое задает последовательность выполнения операций суперпозиции. Напомним это определение и рассмотрим способ представления формул с помощью деревьев.

Пусть X - счетный упорядоченный алфавит БП, и пусть у нас имеется счетный алфавит функциональных символов (ФС) для обозначения ФАЛ от этих БП. Две ФАЛ считаются, как обычно [8], равными, если они имеют одни и те же существенные БП и задают одинаковые отображения области значений этих БП, т. е. единичного куба Bn, где B = {0,1}, а n - число БП, во множество B. Функция, существенно зависящая от всех своих БП, называется существенной.

Пусть, далее, Б = {j1,j2,...,jb} - система ``исходных'' ФАЛ или, иначе, базис, где ФАЛ ji, i = 1,...,b, зависит от ki, ki і 1, БП и является существенной ФАЛ, если ki і  2. Предполагается, что система базисных ФАЛ полна в алгебре логики, и допускается, в общем случае, наличие в ней ``лишних'' ФАЛ, после удаления которых оставшаяся система по-прежнему является полной (см. [8]). Предполагается также, что все ФС ji, i = 1,...,b, различны, хотя, возможно, некоторым из них соответствуют равные ФАЛ.

Сопоставим каждому ФС ji, i = 1,...,b, функциональный элемент (ФЭ) Ei, имеющий ki входов, причем входу с номером j соответствует j-я БП xj ФАЛ ji, и один выход, на котором эта ФАЛ реализуется (см. рис. 4.1.а). Упрощенный вариант изображения ФЭ Ei в виде вершины графа с пометкой ji, в которую входят ki упорядоченных, т. е. пронумерованных числами 1,..,ki, дуг, показан на рис. 4.1.б. При этом предполагается, что дуга с номером j, 1 Ј j Ј ki, соответствует j-му входу ФЭ Ei. В дальнейшем мы, как правило, не будем делать существенных различий между ФС ji и ФЭ Ei. Чаще всего мы будем иметь дело с базисом Б0 = {&,Ъ,Ш}, где базисными являются ФАЛ x1·x2, x1Ъx2 и [`x]1.


Picture Omitted
Дадим индуктивное определение формулы над Б и реализуемой ею ФАЛ (это определение в отличие от [8] неявно предполагает наличие в Б ФАЛ, тождественно равной БП).

Любая БП xj из X считается формулой глубины 0 над Б, которая реализует ФАЛ, равную xj. Если для всех j, j = 1,...,ki, определена формула Fj глубины qj над базисом Б, которая реализует ФАЛ fj от БП из X, то запись вида
F = ji(F1,...,Fki)
(4.1)
является формулой глубины q+1 над Б, где
q = max
{q1,...,qki},
(4.2)
которая реализует ФАЛ f от БП из X такую, что f = ji(f1,...,fki). Так, запись вида

(x1·x2)
 
·(x1Ъx2)
(4.3)
является формулой глубины 3 над базисом Б0, которая реализует ФАЛ x1Еx2. Все записи, полученные в результате указанного индуктивного построения, и только они, считаются формулами над Б.

Важным частным случаем формул над базисом Б0 являются (см., например, [8]) дизъюнктивные нормальные формы (ДНФ). Напомним, что любую ФАЛ f(x1,...,xn) можно представить ее совершенной ДНФ:
f(x1,...,xn) =
Ъ
s = (s1,...,sn) О Nf 
x1s1·...·xnsn,
(4.4)
где, как обычно, x0 = [`x] и x1 = x, а Nf - множество тех наборов s, s О Bn, для которых f(s) = 1.

Индукцией по глубине каждой формуле глубины q над Б можно сопоставить упорядоченное корневое дерево глубины q, все ребра которого ориентированы к корню, каждому листу сопоставлена БП из X, а каждой внутренней вершине - ФС из Б. Так, формуле xj соответствует ``тривиальное'' дерево с единственной вершиной, являющейся корнем и листом одновременно, которой сопоставлена БП xj (см. рис. 4.2.а). Формуле F вида (4.1) соответствует дерево D с корнем v, показанное на рис. 4.2.б, где Dj, j = 1,...,ki, - дерево с корнем vj, которое соответствует формуле Fj. Граф, который получается из дерева D, соответствующего формуле F, в результате ``склеивания'' листьев с одинаковыми пометками, называется квазидеревом, соответствующим формуле F. На рис. 4.3.а показано дерево, а на рис. 4.3.б - квазидерево, которые соответствуют формуле (4.3). Заметим, что формула по сопоставленному ей дереву или квазидереву восстанавливается однозначно.


Picture Omitted

Picture Omitted
Рассмотрим теперь более общую по сравнению с формулами модель - модель схем из функциональных элементов (СФЭ), в которой последовательность операций суперпозиции базисных ФАЛ задается с помощью ориентированного ациклического графа, обобщающего квазидерево, и где возможно многократное использование промежуточных результатов.

Пусть X и Z - счетные упорядоченные попарно не пересекающиеся алфавиты БП, причем БП из X (Z) считаются входными (соответственно, выходными) БП. Пусть по-прежнему Б, Б={ji}i = 1b, - полный базис, где ФАЛ ji, i = 1,...,b, зависит от ki, ki і  1, БП и является существенной ФАЛ, если ki і  2.

По аналогии с упорядоченными деревьями ориентированнный граф G называется упорядоченным, если дуги, входящие в каждую его вершину v, упорядочены, т. е. пронумерованы числами 1,2,...,d+(v).

Определение. Схемой из функциональных элементов над базисом Б называется ориентированный ациклический упорядоченный граф S, вершины которого помечены следующим образом:

1) каждый исток S помечен некоторой БП из X, причем различные истоки помечены различными БП;

2) каждая отличная от истока вершина v схемы S помечена ФС ji, где ki = d+(v);

3) некоторые вершины S помечены выходными БП из Z так, что одной и той же вершине может быть сопоставлено несколько БП из Z, но разным вершинам не может быть сопоставлена одна и та же БП. При этом входные (выходные) БП, которые приписаны каким-либо вершинам S, считаются входными (соответственно, выходными) БП S, а те вершины, которым они сопоставлены, - входами (соответственно, выходами) СФЭ S.

Заметим, что квазидерево, соответствующее формуле над базисом Б, становится СФЭ над Б, если его корню приписать выходную БП. В связи с этим формулы над Б будем считать частным случаем СФЭ над Б. На рис 4.4.а показан пример СФЭ над базисом Б0 с входными БП x1, x2 и выходными БП z1, z2, которая получена из квазидерева, приведенного на рис. 4.3.б, а на рис. 4.4.б дано ее более ``наглядное'' изображение в виде сети (см. [6, с. 227-229]), построенной из соответствующих ФЭ.


Picture Omitted
Определим теперь функционирование СФЭ S над базисом Б с входными БП x1,x2,...,xn и выходными БП z1,...,zm1. Сначала индукцией по q, q = 0,1,..., определим для каждой вершины v глубины q в схеме S реализуемую в ней формулу Fv = Fv (x1,...,xn) глубины q над базисом Б. Если q = 0, т. е. v - вход S, положим Fv = xj, где xj - входная БП, сопоставленная вершине v. Пусть теперь v - вершина глубины q, q і 1, схемы S, которая имеет пометку ji и в которую входит ki дуг, причем дуга с номером j, 1 Ј j Ј ki, исходит из вершины vj глубины qj, где уже реализована формула Fj = Fvj глубины qj, а для чисел q,q1,...,qki выполнено (4.2). Тогда в вершине v реализуется формула F = Fv вида (4.1), которая имеет глубину q+1.

При этом считается, что в вершине v СФЭ S реализуется ФАЛ f(x1,...,xn), если ФАЛ f реализуется формулой Fv, и что СФЭ S реализует систему ФАЛ F, F =  (f1,...,fm), или реализует систему булевых уравнений: z1 = f1,..., zm = fm, если fj, j = 1,...,m, - ФАЛ, реализованная в той выходной вершине СФЭ S, которой приписана БП zj. Так, СФЭ на рис. 4.4 реализует систему ФАЛ (x1·x2, x1Еx2) или систему уравнений: z1 = x1·x2, z2 = x1Еx2. Схемы, реализующие одинаковые системы ФАЛ, называются эквивалентными. Заметим, что изменение нумерации дуг, входящих в такую вершину v СФЭ S, которой сопоставлен ФЭ ei c симметрической ФАЛ ji, не изменяет ФАЛ, реализуемую в вершине v, а значит, не влияет на функционирование S. В связи с этим в подобных случаях номера дуг, входящих в вершину v, могут не указываться.

Две СФЭ Sў и Sўў считаются изоморфными, если они изоморфны как помеченные графы, т. е. если существуют такие взаимнооднозначные отображения множества вершин Sў на множество вершин Sўў и множества дуг Sў на множество дуг Sўў, которые сохраняют отношение инцидентности вершин и дуг, а также все пометки. Из определения вытекает, что в соответствующих друг другу вершинах изоморфных СФЭ реализуются одинаковые формулы, а значит, и одинаковые ФАЛ. Следовательно, две изоморфные СФЭ эквивалентны.

Пусть СФЭ Sў получается из СФЭ S в результате удаления вершины v и переноса начальной вершины всех дуг S, исходящих из v, а также всех выходных БП, приписанных v, в отличную от нее вершину w, глубина которой в S не больше, чем глубина v. Тогда СФЭ Sў считается результатом применения к СФЭ S операции удаления вершины v, а вершина w называется преемником вершины v. Тот факт, что СФЭ Sў получается из CФЭ S в результате (многократной) операции удаления вершин из СФЭ S, будем записывать в виде неравенства Sў < S. Схема S называется тупиковой, если она не эквивалентна ни одной СФЭ Sў такой, что Sў < S.

Вершина СФЭ называется висячей, если из нее не выходит ни одна дуга и она не является выходом схемы. Две вершины СФЭ считаются эквивалентными, если в них реализуются равные ФАЛ. Применяя к СФЭ S операцию удаления одной из двух эквивалентных вершин, преемником которой является другая вершина, мы получим СФЭ Sў, которая, очевидно, эквивалентна S.

Схема называется приведенной (строго приведенной), если в ней нет висячих (соответственно висячих и эквивалентных) вершин. Заметим, что тупиковая СФЭ является строго приведенной, и что из любой СФЭ можно получить эквивалентную ей приведенную (строго приведенную) СФЭ с помощью операции удаления висячих (соответственно висячих и эквивалентных) вершин.

Рассмотрим теперь задачу синтеза на примере СФЭ. Число ФЭ в СФЭ называется ее сложностью. Сложность СФЭ S обозначается через L(S). Для системы ФАЛ F через LБ(F) обозначим минимальную сложность тех СФЭ S над базисом Б, которые реализуют F. Величина LБ(F) называется сложностью системы ФАЛ F над базисом Б. При этом СФЭ S, которая реализует F, и для которой L(S) = LБ(F), считается минимальной СФЭ над базисом Б. Заметим, что СФЭ, показанная на рис. 4.4, является минимальной СФЭ над базисом Б0, и что сложность системы ФАЛ F = (x1·x2, x1Еx2) над базисом Б0 равна 4.

Введем, далее, функцию LБ(n) натурального аргумента n, которая определяется следующим образом:
LБ(n) =
max
f(x1,...,xn) 
LБ(f)
и называется функцией Шеннона для класса СФЭ над базисом Б. Функция Шеннона характеризует сложность самой ``сложной'' ФАЛ от БП x1,...,xn в классе СФЭ над базисом Б.

Вместо сложности L(S) СФЭ S можно рассмотреть ее глубину D(S), а затем аналогичным образом определить глубину DБ(F) для системы ФАЛ F в базисе Б и ввести функцию Шеннона DБ(n). Можно рассмотреть ``взвешенную'' сложность (глубину) СФЭ, когда при подсчете сложности (соответственно глубины) каждый ФЭ учитывается со своим коэффициентом, и т. п. Можно рассматривать подобные функционалы сложности для подклассов класса СФЭ (класса формул, класса ДНФ и т. д.). В дальнейшем мы, как правило, будем рассматривать оптимальную по сложности реализацию ФАЛ в классе СФЭ над базисом Б0. В связи с этим индекс Б = Б0 будем опускать.

Для решения задачи синтеза СФЭ можно использовать переборный алгоритм, который просматривает все схемы сложности 1,2,3,... до тех пор, пока не найдет схему, реализующую заданную систему ФАЛ. Следует отметить, что трудоемкость этого метода синтеза очень быстро растет с ростом числа переменных n, и что при n і  5 он становится практически неприменимым.

С другой стороны, всегда можно использовать метод синтеза, основанный на моделировании совершенной ДНФ. Следующее утверждение непосредственно вытекает из (4.4).

Лемма 4.1. Для любой ФАЛ f(x1,...,xn) существует СФЭ, реализующая f со сложностью не более, чем n·2n+1.

Следствие. L(n) Ј n·2n+1.

Замечание. Во многих случаях после построения СФЭ по лемме 4.1. целесообразно использовать операцию удаления эквивалентных вершин для перехода к соответствующей строго приведенной СФЭ.


xx 5. Реализация некоторых ``управляющих'' систем функций алгебры логики в классе СФЭ


Рассмотрим примеры решения задачи индивидуального синтеза СФЭ - синтеза СФЭ для систем ФАЛ, которые часто встречаются в практике проектирования дискретных управляющих систем и для которых хотелось бы иметь более простые схемы, чем схемы, построенные по лемме 4.1.

Для множества A и любого натурального n через (A)n или просто An обозначается, как обычно, n-я декартова степень множества A, т. е. множество наборов (слов, систем) длины n с элементами из A. Для набора b, b О An, через b[i], где 1 Ј  i Ј  n, обозначается его i-й элемент, т. е. b = (b[1],...,b[n]). Если a О Bn, то число еi = 1na[i]·2n-i, т. е. число, двоичная запись которого совпадает с a, называется номером a и обозначается через |a|.

Пусть P2(n), n = 1,2,..., - множество всех ФАЛ от БП x1,x2,...,xn, а P2m(n) - его m-я декартова степень, m = 1,2,..., т. е. множество систем из m ФАЛ от БП x1,x2,...,xn. Определим некоторые ``управляющие'' системы ФАЛ и рассмотрим реализующие их СФЭ. При этом мы часто будем давать одно и то же название как самой системе ФАЛ, так и СФЭ, которая ее реализует, добавляя к нему в случае необходимости слово ``функциональный'', если речь идет о системе ФАЛ, и слово ``схемный'', если речь идет о схеме.

Система ФАЛ Qn из P2(n) такая, что при всех i, i = 1,2,...,2n, справедливо равенство:
Qn[i] = x1s1·...·xnsn,
(5.1)
где s = (s1,...,sn) О Bn и |s| = i-1, называется (функциональным) дешифратором порядка n. Это связано с тем, что на любом наборе a, a О Bn, значений БП x1,...,xn ровно одна из ФАЛ системы Qn - ФАЛ с номером |a|+1 - обращается в 1.

Функция mn от (входных) БП x1,...,xn,y0,y1,...,y2n-1 такая, что при всех a, a О Bn, и b, b О B2n, имеет место равенство:
mn(a,b) = b[i],
где (i-1) = |a|, называется (функциональным) мультиплексором порядка n. Если рассматривать БП x1,...,xn как ``адресные'' БП, а БП y0,y1,...,y2n-1 - как ``информационные'' БП, то значение мультиплексора mn равно значению той его информационной БП, номер которой поступил на адресные БП mn. Легко убедиться в том, что для ФАЛ mn справедливо представление:
mn(x1,...,xn,y0,...,y2n-1) = 2n
Ъ
i = 1 
Qn[i]·yi-1.
(5.2)

Под (функциональным) шифратором порядка n понимается любая система из n ФАЛ от входных БП x0,x1,...,x2n-1 такая, что каждому входному набору a, в котором равна 1 только одна БП xj, 0 Ј  j Ј  2n-1, она сопоставляет выходной набор b, b О Bn, для которого |b| = j. Тем самым, шифратор вырабатывает ``адрес'' той входной БП, которая равна 1, если другие входные БП принимают при этом нулевые значения.

Будем называть схемным дешифратором, мультиплексором или шифратором любую СФЭ, которая реализует соответствующую систему ФАЛ.

Обозначим через Qn систему длины 22n из всех различных ФАЛ множества P2(n), в которой столбец значений ФАЛ Qn[i], 1 Ј  i Ј  22n, рассматриваемый как двоичный набор длины 2n, имеет номер (i-1). Систему Qn будем называть универсальной системой ФАЛ порядка n, а любую СФЭ, которая ее реализует, - универсальным многополюсником порядка n.

Отметим, что дешифратор, мультиплексор и шифратор часто используются в качестве составных частей схем записи и чтения информации по заданному адресу.

Рассмотрим теперь вопросы, касающиеся сложности описанных схем.

При построении ``сложных'' СФЭ из более простых мы будем опираться на понятие подсхемы и принцип эквивалентной замены (см. [9]). СФЭ Sў называется подсхемой СФЭ S, если множество ее вершин (дуг) является подмножеством множества вершин (соответственно дуг) S, а все те вершины Sў, из которых в S выходит хотя бы одна дуга, не принадлежащая Sў, или которые являются выходами S, являются выходами Sў. При этом предполагается, что все дуги в Sў имеют те же номера, что и в S, а все вершины Sў имеют те же ФС, что и в S. Принцип эквивалентной замены для СФЭ вытекает из определения их функционирования и состоит в том, что если подсхему Sў СФЭ S заменить эквивалентной ей СФЭ Sўў, то полученная в результате СФЭ [^(S)] будет эквивалентна СФЭ S. В связи с этим подсхемы, которые не имеют общих внутренних вершин, можно рассматривать как (многовыходные) макроэлементы.

Лемма 5.1. Для любого натурального n существует схемный дешифратор порядка n, имеющий сложность не более, чем n·2n+1, и глубину не более, чем2 ]logn[+1.

Доказательство. Для построения искомого дешифратора достаточно каждую ФАЛ системы Qn реализовать по ее совершенной ДНФ (5.1) на основе d-ярусного дерева из n ФЭ &, где d = ]logn[ (см. рис. 5.1).


Picture Omitted
Следствие. L(Qn) Ј n·2n+1.

Следующее утверждение доказывается, по существу, применением к построенному в лемме 5.1 схемному дешифратору операции удаления эквивалентных вершин (см. § 4).


Теорема 5.1. Сложность минимального схемного дешифратора порядка n равна
2n+O(n·2n/2).

Доказательство. Поскольку любой дешифратор порядка n при n і 2 реализует систему из 2n ФАЛ, отличных от БП, то в нем должно быть по крайней мере 2n вершин, отличных от входов. Следовательно, сложность любого дешифратора порядка n, n і 2, в классе СФЭ не меньше, чем 2n.

Разобьем набор входных БП x = (x1,...,xn) на поднаборы xў = (x1,...,xk) и xўў =  (xk+1,...,xn), где k - некоторый параметр и 1 Ј  k Ј  (n-1). Пусть Qў и Qўў - функциональные дешифраторы порядка k и (n-k) от БП xў и xўў, а Sў и Sўў - соответствующие им схемные дешифраторы, которые построены по лемме 5.1. Легко видеть, что любую ФАЛ Qn[i], 1 Ј i Ј 2n, можно представить в виде
Qn[i] = Qў[j]·Qўў[l],
(5.3)
где i = 2n-k(j-1)+l и 1 Ј j Ј 2k, 1 Ј l Ј 2n-k. Дешифратор S порядка n от БП x содержит дешифраторы Sў,Sўў в качестве подсхем и реализует каждую ФАЛ Qn[i], 1 Ј i Ј 2n, с помощью одного ФЭ &, входы которого присоединены к выходам Sў и Sўў (см. рис. 5.2) в соответствии с (5.3). Из построения S следует, что
L(S) = 2n+L(Sў)+L(Sўў) Ј 2n+n+k·2k+1+(n-k)2n-k+1,
и поэтому при k = [n/2] получим:
L(S) Ј 2n+O(n·2n/2).
Теорема доказана.


Следствие 1. Построенный дешифратор порядка n имеет глубину не больше, чем ]logn[+2.

Следствие 2. Если в качестве дешифраторов Sў и Sўў взять дешифраторы, уже построенные по теореме 5.1, то полученный дешифратор порядка n будет иметь сложность
2n+2[n/2]+2]n/2[+O(n·2n/4) Ј 2n+ 3Ц2
2
2n/2+O(n·2n/4)
и поэтому

2n Ј L(Qn) = 2n+ 3Ц2
2
2n/2+O(n·2n/4).


Picture Omitted
Лемма 5.2. Для любого натурального n существует схемный мультиплексор порядка n, который имеет сложность не более, чем 3·2n+O(n·2n/2).

Доказательство. Построим схемный мультиплексор S в соответствии с (5.2) на основе дешифратора Sўў порядка n, который является его подсхемой. Для этого каждый выход Sўў и соответствующий ему информационный вход S присоединим к входам ФЭ &, а затем продизъюнктируем выходы всех таких ФЭ &. Если дешифратор Sўў взять из теоремы 5.1, то полученный таким образом мультиплексор S будет искомым.

Лемма доказана.


Следствие. Построенный мультиплексор порядка n имеет глубину не больше, чем n+]logn[+3.


Теорема 5.2. Существует схемный мультиплексор порядка n, имеющий сложность
2n+1+O(2n/2).

Доказательство. Разобьем набор x = (x1,...,xn) адресных БП мультиплексора mn на поднаборы xў и xўўтак же, как это было сделано при доказательстве теоремы 5.1, а набор y = (y0,...,y2n-1) его информационных БП - на поднаборы y(1),..., y(2k) длины 2n-k каждый, где y(j)[l] = yi-1 при i = 2n-k(j-1)+l и всех j,l таких, что 1 Ј j Ј 2k, 1 Ј l Ј 2n-k. При этом из (5.2), (5.3) следует, что:
mn(x,y) = 2k
Ъ
j = 1 
Qў[j] ж
и
2n-k
Ъ
l = 1 
Qўў[l]·y(j)[l] ц
ш
,
и поэтому
mn(x,y) = mk(xў,mn-k(xўў,y(1)),...,mn-k(xўў,y(2k))).
(5.4)

Рассмотрим мультиплексор S, который реализует mn по формуле (5.4). Для каждого j, j = 1,...,2k, S содержит в качестве подсхемы мультиплексор Sjўў порядка (n-k) от БП xўў,y(j), причем выходы этих мультиплексоров подаются в соответствии с (5.4) на информационные входы мультиплексора Sў порядка k с адресными БП xў (см. рис. 5.3). Если мультиплексоры Sў и Sjўў, j = 1,...,2k, построить в соответствии с леммой 5.2, а затем перейти от СФЭ S к эквивалентной ей строго приведенной СФЭ [^(S)] (см. § 4), то при k = [n/2] мы получим искомый мультиплексор. Действительно, из доказательства леммы 5.2 следует, что все мультиплексоры Sjўў, j = 1,...,2k, имеют общий дешифратор Sўў порядка (n-k), и поэтому
L( ^
S
 
) Ј L(Sў)+2n+1+L(Sўў) Ј 2n+1+O(2n/2)
в силу теоремы 5.1.

Теорема доказана.

Следствие. L(mn) Ј 2n+1+O(2n/2)


Наряду с дешифратором Qn и мультиплексором mn порядка n иногда рассматривают также полудешифратор [^Q]n порядка n с входными БП x1,...,xn и полумультиплексор [^(m)]n порядка n с входными БП x1,...,xn,y0,...,y2n-1-1, такие, что
^
m
 

n 
= 2n-1-1
Ъ
j = 0 
yj Qn[j+2n-1+1],   ^
Q
 

n 
[i] = Qn[2n-1+i],
где i = 1,...,2n-1. Заметим, что при x1 = 0 имеют место равенства:
^
m
 

n 
= 0,   ^
Q
 

n 
[i] = 0.
Аналогично доказанным выше утверждениям устанавливаются оценки:
L( ^
Q
 

n 
) = 2n-1+O(2n/2),

L( ^
m
 

n 
) Ј 2n+O(2n/2).


Picture Omitted
Перейдем теперь к построению шифраторов. Определим систему ФАЛ Dn длины n от БП x = (x0,x1,...,x2n-1) так, что
Dn[i] =
Ъ
s = (s1,...,si-1,1,si+1,...,sn) 
x|s|
(5.5)
для всех i, i = 1,...,n. Заметим, что Dn[i] = 1 тогда и только тогда, когда среди БП xj, j = 0,1,...,2n-1, номер которых имеет единицу в i-м разряде своей двоичной записи, есть хотя бы одна БП, раная единице. Это означает, что система ФАЛ Dn является (функциональным) шифратором порядка n. Если для каждого i, i = 1,...,n, ФАЛ Dn[i] реализовать формулой (5.5), то мы получим схемный шифратор сложности n(2n-1-1), так как в каждую дизъюнкцию (5.5) входит ровно половина БП набора x. Следовательно, доказано утверждение:

Лемма 5.3. Для любого натурального n существует схемный шифратор порядка n, который имеет сложность не более, чем n·2n-1.

Более ``экономный'' схемный шифратор может быть построен с помощью рекурсивного разбиения множества входных БП пополам.


Теорема 5.3. Существует схемный шифратор порядка n, сложность которого не больше, чем 2n+1.

Доказательство. Разобьем набор БП x = (x0,...,x2n-1) на поднаборы xў = (x0,...,x2n-1-1) и xўў = (x2n-1,...,x2n-1). Пусть Dў и Dўў - функциональные шифраторы порядка (n-1) от БП xў и xўў, а Sў и Sўў - соответствующие им схемные шифраторы. Из (5.5) следует, что
Dn[1] = x2n-1Ъ...Ъx2n-1 = x2n-1Ъ (n-1)
Ъ
j = 1 
Dўў[j]
(5.6)
и
Dn[i+1] = Dў[i]ЪDўў[i]
(5.7)
для всех i, i = 1,...,(n-1). Следовательно, из шифраторов Sў и Sўў, а также (2n-2) ФЭ Ъ на основе (5.6)-(5.7) можно построить шифратор S порядка n, для которого:
L(S) Ј L(Sў)+L(Sўў)+(2n-2)
(5.8)

Используя неравенство (5.8) рекурсивно и полагая, что L(D1) Ј  1, так как D1 состоит из БП x1, получим:
L(S) Ј 2(n-1)+4(n-2)+...+3·2n-3+2·2n-2+2n-1 =

= 2n-1 ж
з
и
1+ 1
2
·2+...+ 1
2n-1
(n-1) ц
ч
ш
\leqslant2n-1 ж
з
и
Ґ
е
t = 1 
t
2t-1
ц
ч
ш
=

= 2n-1 Ґ
е
s = 1 
Ґ
е
t = s 
1
2t-1
= 2n+1

Теорема доказана.

Следствие. L(Dn) Ј 2n+1.


Теорема 5.4. Минимальный универсальный многополюсник порядка n имеет сложность 22n-n.

Доказательство. Нижняя оценка следует из того, что универсальный многополюсник порядка n реализует систему из 22n-n ФАЛ, отличных от БП (см. доказательство теоремы 5.1). Для получения верхней оценки построим универсальный многополюсник S по совершенным ДНФ всех реализуемых ФАЛ (см. лемму 4.1), а затем перейдем от него к эквивалентной строго приведенной СФЭ Sў (см. § 4). Заметим, что число вершин СФЭ Sў, отличных от входов, не больше, чем число различных ФАЛ от БП x1,...,xn, отличных от этих БП. Следовательно,
L(Sў) Ј 22n-n.

Теорема доказана.


xx 6. Реализация некоторых ``арифметических'' систем ФАЛ в классе СФЭ


Рассмотрим теперь некоторые ``арифметические'' системы ФАЛ и построим реализующие их СФЭ.

Системы Sn, Mn и Wn, состоящие из (n+1), 2n и n ФАЛ от БП x =  (x1,...,xn), y =  (y1,...,yn) соответственно, такие, что
|Sn(x,y)| = |x|+|y||Mn(x,y)| = |x|·|y|,
и, если |x| і |y|, то
|Wn(x,y)| = |x|-|y|,
называются (функциональным) сумматором, умножителем и вычитателем порядка n соответственно.

Система Cn, состоящая из (n+1) ФАЛ от БП x = (x1,...,x2n), такая, что значение |Cn(x)| равно числу единиц в наборе x, называется (функциональным) счетчиком порядка n.

В [8] приведен сумматор порядка n, имеющий сложность 9n-5. Мы построим такой же сумматор несколько иначе.


Теорема 6.1. Существует схемный сумматор порядка n, имеющий сложость 9n-5.

Доказательство. Для n = 1 сумматор S1 показан на рис. 4.4. На рис. 6.1.а показана СФЭ Sў сложности 9, которая реализует систему ФАЛ Sў от БП x, y и qў такую, что
|Sў(x,y,qў)| = x+y+qў,
т. е. реализует сложение трех одноразрядных чисел. Действительно, на выходе z2 СФЭ Sў реализуется ФАЛ xЕyЕqў, а на выходе z1 единица появляется только тогда, когда либо x = y = 1, либо xЕy = qў = 1, т. е. на выходе z1 в СФЭ Sў реализуется ФАЛ
xyЪ(xЕy)qў = xyЪxqўЪyqў = h(x,y,qў).
Схемный сумматор Sn порядка n с входными БП x1,...,xn,y1,...,yn и выходными БП z0,z1,...,zn можно построить из сумматора Sn-1 порядка (n-1) с входными БП x2,...,xn,y2,...,yn и выходными БП z1ў,z2,...,zn, а также одной СФЭ Sў так, как это показано на рис. 6.2. Заметим, что переход от сумматора Sn-1 к сумматору Sn моделирует сложение n-разрядных чисел в два этапа: на первом этапе складываются числа, образуемые (n-1) младшими разрядами, а на втором этапе складываются старшие разряды и перенос, возникший на первом этапе. Очевидно, что
L(Sn) = 9n-5.

Теорема доказана.

Следствие. L(Sn) Ј 9n-5.

Замечание. Если схему Sў на рис. 6.2 заменить на схему Sўў, показанную на рис. 6.1.б, мы получим (схемный) квазисумматор порядка n, n і 2, который имеет сложность 9n-9 и правильно складывает n-разрядные двоичные числа, каждое из которых не превосходит 2n-1.


Picture Omitted

Picture Omitted
Теорема 6.2. Существует схемный вычитатель порядка n, имеющий сложность не больше, чем 11n-5.

Доказательство. Заметим, что
|
x
 
| = 2n-1-|x|,
где x = (x1,...,xn), [`x] = ([`x]1,...,[`x]n), и поэтому
Wn(x,y) = |x|-|y| = 2n-1-(2n-1-|x|+|y|) =
S
 

n 
(
x
 
,y)
Следовательно, схемный вычитатель порядка n может быть получен из схемного сумматора порядка n в результате инвертирования входов его первого слагаемого, а также всех его выходов, и имеет сложность не больше, чем 11n-5.

Теорема доказана.

Замечание. Из построенного вычитателя в результате ``поднятия'' отрицаний, присоединенных к выходам z2 схемы Sў или S1 в соответствии с равенствами
z2 =
u
 
&w, 
z
 

2 
= uЪ
w
 
,
где u и w - выходы ФЭ & и Ъ СФЭ S1 (см. рис. 4.4.б), можно получить вычитатель сложности не больше, чем 10n-4.


Теорема 6.3. Существует схемный счетчик порядка n, который имеет сложность не более, чем 9·2n.

Доказательство. Счетчик Sn порядка n с входными БП x1,...,x2n и выходными БП z1,...,zn+1 можно построить из счетчика Sn-1 порядка (n-1) с входными БП x1,..,x2n-1 и выходными БП z1ў,...,znў, такого же счетчика Sn-1 с входными БП x2n-1+1,...,x2n и выходными БП z1ўў,...,znўў, а также квазисумматора (см. замечание к теореме 6.1) [^(S)] порядка n с входными БП z1ў,...,znў,z1ўў,...,znўў и выходными БП z1,...,zn+1 (см. рис. 6.3), поскольку на выходах счетчиков Sn-1 числа, большие, чем 2n-1, не позволяются.

В силу замечания к теореме 6.1 квазисумматор [^(S)] можно построить со сложностью не больше, чем 9n-9, и поэтому
L(S) Ј 2L(Sў)+(9n-9)
(6.1)

Используя неравенство (6.1) рекурсивно и полагая, что L(S1) = 4, так как C1[1] =  x1·x2,C1[2] =  x1Еx2, то есть C1 =  S1, получим
L(Sn) Ј 9(n-1)+18(n-2)+...+9·2n-2+4·2n-1
Следовательно (см. выкладки в конце доказательства теоремы 5.3),
L(Sn) Ј 9·2n

Теорема доказана.

Следствие. L(Cn) Ј 9·2n.


Picture Omitted
Замечание. В общем случае счетчик, то есть схема с n выходами, на которых появляется двоичная запись числа единиц в наборе значений входных переменных, может иметь N, 2n-1 Ј  N <  2n, входов. Такой счетчик можно построить из ``стандартных'' счетчиков, порядки которых соответствуют номерам единичных компонент набора a, a О Bn, такого, что |a| = N, и не более чем (n-1)-го сумматора порядка n. Каждый из стандартных счетчиков вычисляет число единиц в своей части набора из N переменных, а сумматоры складывают числа, появившиеся на выходах счетчиков. Сложность построенной схемы не превосходит, очевидно, 9(N+n2).


Рассмотрим теперь сложность умножителя Mn для умножения двух неотрицательных n-разрядных двоичных чисел X = |(x1,x2,...,xn)| и Y = |(y1,y2,...,yn)|. Так как X < 2n и Y < 2n, то XY < 22n и для представления результата требуется не более 2n выходов. Обозначим через LM(n) наименьшее возможное число элементов в умножителе Mn. Очевидно, что LM(1) = 1, так как умножение 1-разрядных чисел осуществляет элемент конъюнкция.

Утверждение. Существует СФЭ для умножения n-разрядного числа X на 1-разрядное число y с числом элементов n.

Действительно, если X = |(x1,x2,...,xn)| и Xy = Z = |(z1,z2,...,zn)|, то zi=xiy для всех i = 1,2,... ,n.

При умножении двух n-разрядных чисел X и Y ``в столбик'' надо n раз умножить X на 1-разрядное число (всего n2 конъюнкций) и затем n-1 раз сложить числа длиной не более 2n. Такой алгоритм (схема) имеет сложность по порядку n2. Следующая теорема показывает, что алгоритм умножения ``в столбик'' не оптимален по порядку.

Теорема 6.4 (Карацуба А. А. [4]). Существует такая константа c, что для всех n LM(n) Ј c nlog23.

Докажем сначала несколько вспомогательных лемм.

Лемма 6.1. Существует константа c1 такая, что LM(n+1) Ј LM(n)+c1n для всех n.

Доказательство. Пусть требуется перемножить два (n+1)-разрядных числа X1 = |(x0,x1,...,xn)| и Y1 = |(y0,y1,...,yn)|. Тогда обозначим |(x1,x2,...,xn)| = X и |(y1,y2,...,yn)| = Y. При этом X1 = x02n+X, Y1 = y02n+Y и
X1Y1 = x0y022n+(x0Y+y0X)2n+XY.
Поэтому для вычисления X1Y1 достаточно использовать умножитель Mn для вычисления XY, 2n элементов для вычисления x0Y и y0X, 1 элемент для вычисления x0y0 и 3 сумматора порядка не более 2n+2, так как X1Y1 < 22n+2. Отметим, что числа x0y0 и x0Y+y0X надо подавать на сумматоры со сдвигом, одновременно подавая на младшие разряды 0. При этом 0 можно предварительно получить подсхемой с 2 элементами, реализующей x0[`x]0 = 0.Так как сложность каждого сумматора можно сделать не более 9(2n+2), а сложность Mn равной LM(n), то сложность полученной схемы будет не больше чем LM(n)+c1n для некоторой константы c1. Лемма доказана.

Лемма 6.2 (основная). Существует константа c2 такая, что LM(2n) Ј 3LM(n)+c2n, для всех n.

Доказательство. Пусть нужно перемножить два 2n-разрядных числа X и Y. Разобьем их на части, содержащие по n разрядов. Тогда получим X = X12n+X2, Y = Y12n+Y2. Отсюда
XY = X1Y122n+(X1Y2+X2Y1)2n+X2Y2 =

= X1Y122n+[(X1+X2)(Y1+Y2)-X1Y1-X2Y2]2n+X2Y2.
Так как X1Y2+X2Y1 і 0, то при вычитании в квадратной скобке не возникает отрицательных чисел. Таким образом, схему для умножения XY можно построить, используя 2 оптимальных умножителя Mn с числом элементов LM(n) в каждом для вычисления X1Y1 и X2Y2, умножитель Mn+1 с числом элементов LM(n+1) для вычисления (X1+X2)(Y1+Y2), 4 сумматора порядка не более 4n (так как XY < 24n) и 2 вычитателя порядка 2n+2. В некоторых сумматорах опять на младшие разряды надо подавать 0, который реализуем подсхемой с 2 элементами: 0 = x[`x], где x - любая входная переменная. Для построенной схемы M2n с учетом леммы 6.1 получим для некоторых констант c и c2:
L(M2n) Ј 2LM(n)+LM(n+1)+cn Ј 3LM(n)+c1n+cn = 3LM(n)+c2n
.

Лемма 6.3. Существует такая константа c3, что для любого натурального k выполняется LM(2k) Ј c33k.

Доказательство. Положим f(k) = [(LM(2k))/(3k)]. Тогда из предыдущей леммы имеем
LM(2k)
3k
\leqslant LM(2k-1)
3k-1
+ c2
3
( 2
3
)k-1
и
f(k) Ј f(k-1)+ c2
3
( 2
3
)k-1 Ј f(k-2)+ c2
3
( 2
3
)k-2+ c2
3
( 2
3
)k-1 Ј

Ј ... Ј f(1)+ c2
3
[ 2
3
+ ( 2
3
)2+...+( 2
3
)k-1] Ј c3
для некоторой константы c3, поскольку сумма в квадратных скобках не превосходит сумму 2 бесконечно убывающей геометрической прогрессии с первым членом [2/3] и знаменателем [2/3]. Таким образом [(LM(2k))/(3k)] Ј c3 и LM(2k) Ј c33k.

Доказательство теоремы Карацубы. Пусть n - любое натуральное число и n > 1. Тогда существует натуральное k такое, что 2k-1 < n Ј 2k. Для умножения n-разрядных чисел будем использовать схему M2k с числом элементов LM(2k), подавая на старшие 2k-n входных разрядов обоих сомножителей 0, предварительно реализованный подсхемой из 2 элементов. Тогда имеем
LM(n) Ј LM(2k)+2 Ј c33k+2 = 3c33k-1+2 =

= 3c32(k-1)log23+2 < 3c3nlog23+2 Ј cnlog23
для некоторой константы c.

В заключение отметим, что существует алгоритм Шенхаге и Штрассена для умножения двух n-разрядных чисел, дающий оценку LM(n) Ј cnlognloglogn, где c - некоторая константа и логарифмы можно считать двоичными.


xx 7. Метод Шеннона для синтеза СФЭ. Верхние и нижние оценки функции Шеннона и сложности некоторых ФАЛ


В § 4 был рассмотрен простейший метод синтеза СФЭ для произвольной ФАЛ f(x1,...,xn), основанный на моделировании ее совершенной ДНФ. Если при этом воспользоваться замечанием к лемме 4.1 и все конъюнкции вида x1s1·...·xnsn реализовать с помощью одного схемного дешифратора, то в силу теоремы 5.1 можно построить СФЭ Sf, которая реализует ФАЛ f(x1,..,xn) и для которой
L(Sf) Ј 2n+1+O(n·2n/2).
Рассмотрим еще более ``экономный'' метод синтеза СФЭ - метод Шеннона.


Теорема 7.1. Для любой ФАЛ f(x1,...,xn) можно построить СФЭ Sf, которая реализует f и для которой
L(Sf) Ј 2n
n
+O ж
з
и
2nlogn
n2
ц
ч
ш
.

Доказательство. Разобьем набор БП x = (x1,...,xn) на поднаборы xў = (x1,...,xk) и xўў = (xk+1,...,xn), где k, 1 Ј k Ј n, - некоторый параметр. Для любого набора sў = (s1,...,sk) из Bk положим:
fsў(xўў) = f(sў,xўў).
Тогда для ФАЛ f будет справедливо представление:
f(xў,xўў) =
Ъ
sў = (s1,...,sk) О Bk 
x1s1·...·xksk·fsў(xўў) = mk(xў,f[0\tilde](xўў),...,f[1\tilde](xўў))
(7.1)
Построим СФЭ Sf из универсального многополюсника Sўў порядка (n-k) от БП xўў и мультиплексора Sў порядка k с адресными БП xў, на информационные входы которого подаются выходы Sўў в соответствии с (7.1) (см. рис. 7.1).

Если мультиплексор Sў построить по лемме 5.2, а универсальный многополюсник Sўў - по теореме 5.4, то
L(Sў) Ј 3·2k+O(k·2k/2), L(Sўў) Ј 22n-k.
Следовательно, полагая
k = ]n-log(n-2logn)[,
получим
L(Sf) Ј 2n
n-2logn
+O(n·2n/2)+ 2n
n2
= 6· 2n
n
+O ж
з
и
2nlogn
n2
ц
ч
ш
.
Теорема доказана.


Picture Omitted
Следствие. L(n) Ј 6·[(2n)/n]+O([(2nlogn)/(n2)]).

Рассмотрим теперь вопрос о нижних оценках функции Шеннона L(n) и сложности некоторых конкретных ФАЛ.

Пусть g(L,n) - число всех тех попарно неизоморфных неприводимых СФЭ с входными БП x1,...,xn и выходной БП z1, сложность которых не больше, чем L.


Лемма 7.1. При любых натуральных L,n справедливо неравенство
g(L,n) Ј (L+n)2L+4.

Доказательство. Пусть S - неприводимая СФЭ с входными БП x1,...,xn и выходной БП z1, для которой L(S) Ј L. Для задания СФЭ S достаточно:

1) выбрать целые неотрицательные числа L1,L2,L3 так, чтобы L1+L2+L3 Ј L, - это можно сделать не более, чем (L+1)4 способами;

2) взять L1 ФЭ &, L2 ФЭ Ъ и L3 ФЭ Ш, а затем каждый вход каждого из них ``присоединить'' к выходу некоторого другого ФЭ или к одному из входов S - это можно сделать не более, чем (L+n)2L способами;

3) поместить единственный сток СФЭ S к выходной БП z1.

Следовательно,
g(L,n) Ј (L+1)4·(L+n)2L Ј (L+n)2L+4.
Лемма доказана.


Лемма 7.2. При любых натуральных L,n справедливо неравенство:
g(L,n) Ј (32(L+n))L+1.

Доказательство. Пусть S - неприводимая СФЭ с входными БП x1,...,xn и выходной БП z1, для которой L(S) = Lў Ј L. Сопоставим СФЭ S ориентированное корневое упорядоченое помеченное дерево D, получающееся из графа S в результате ``снятия'' входных БП с истоков S, ``отсоединения'' от каждой вершины v графа S, такой, что d+(v) > 1, каких-либо (d+(v)-1) исходящих из нее дуг и объявления начальных вершин этих дуг новыми вершинами-листьями D (см. рис. 7.2). Заметим, что пометки внутренних вершин дерева Dтипами ФЭ базиса Б0 сохраняются, и что в каждую такую вершину D с пометкой ФС Ш входит одна дуга, а с пометкой & или Ъ - две дуги.

Заметим также, что для получения СФЭ S из дерева D достаточно каждый лист D присоединить либо к одной из входных вершин СФЭ S, помеченных БП x1,x2,...,xn, либо к одной из внутренних вершин самого дерева D.

Из построения дерева D следует, что число внутренних вершин (т. е. вершин, отличных от листьев) в нем равно Lў, а число ребер не больше, чем 2Lў, и поэтому число листьев в Dў не больше, чем Lў+1 (см. § 2). Следовательно, число различных СФЭ S, связанных с одним и тем же деревом D, не больше, чем (Lў+n)Lў+1, а из § 2 вытекает, что число различных деревьев D рассматриваемого вида не больше, чем
42Lў·2Lў = 25Lў.
Следовательно,
g(L,n) Ј L
е
Lў = 1 
32Lў(Lў+n)Lў+1 Ј (32(L+n))L+1.
Лемма доказана.


Picture Omitted
Доказательство двух следующих утверждений основано на т.н. ``мощностном'' принципе получения нижних оценок функции Шеннона.


Теорема 7.2. Для любого натурального n справедливо неравенство
L(n) і 2n-1
n
(1-o(1)).

Доказательство. Из определения функции Шеннона L(n) и величины g(L,n) следует, что
g(L(n),n) і 22n.
Логарифмируя это неравенство и применяя лемму 7.1, получим:
(2L(n)+4)·log(L(n)+n) і 2n,
откуда в силу теоремы 7.1 вытекает, что
(2L(n)+4)·(n+o(1)) і 2n.
Следовательно,
L(n) і 2n-1
n
(1-o(1))
Лемма доказана.


Теорема 7.3. Для любого натурального n справедливо неравенство:
L(n) і 2n
n
ж
з
и
1+ logn-6-o(1)
n
ц
ч
ш
.

Доказательство. Рассмотрим множество [^P]2(n), состоящее из тех ФАЛ f, f О P2(n), для которых
L(f) Ј ^
L
 
(n) = Lў(n)-n,
(7.2)
где
Lў(n) = 2n
n
ж
з
и
1+ logn-6
n
ц
ч
ш
.
(7.3)
Из (7.2), определения величины g(L,n) и леммы 7.1 следует, что
| ^
P
 

2 
(n)| Ј g( ^
L
 
(n),n) Ј (32Lў(n))Lў(n).
(7.4)
Логарифмируя (7.4) и используя (7.3), получим:
log| ^
P
 

2 
(n)| Ј Lў(n)(n-logn+5+o(1)) Ј

Ј 2n ж
з
и
1+ logn-6
n
ц
ч
ш
ж
з
и
1- logn-5-o(1)
n
ц
ч
ш
\leqslant

Ј 2n ж
з
и
1- 1-o(1)
n
ц
ч
ш
.
Следовательно,
2n-log| ^
P
 

2 
(n)|®Ґ  и  
| ^
P
 

2 
(n)|

22n
® 0
при n®Ґ, а значит, множество P2(n)\[^P]2(n) не пусто при достаточно больших n, и поэтому найдется такая ФАЛ f, f О P2(n), для которой
L(f) > ^
L
 
(n) = 2n
n
ж
з
и
1+ logn-6-o(1)
n
ц
ч
ш
.
(7.5)
Теорема доказана.

Следствие. Неравенство (7.5) выполняется для почти всех ФАЛ f из P2(n).

Рассмотрим теперь некоторые методы получения нижних оценок сложности конкретных ФАЛ. Соображения, связанные с тем, что сложность СФЭ S, которая реализует систему из m различных ФАЛ, отличных от БП, не может быть меньше, чем m, мы уже использовали в теоремах 5.1, 5.3. В случае дешифратора, а также в некоторых подобных случаях эту тривиальную оценку можно несколько уточнить.

Лемма 7.3. Сложность схемного дешифратора порядка n, n і  2, не меньше, чем 2n+Ц2·2n/2-n-1.

Доказательство. Пусть S - строго приведенный схемный дешифратор порядка n, n і  2, с входными БП x1,...,xn. Из строгой приведенности S следует, что каждый его выходной ФЭ является либо ФЭ &, либо ФЭ Ш. Действительно, если бы на выходе ФЭ Ъ СФЭ S реализовалась конъюнкция K = x1s1·...·xnsn, то хотя бы на одном из его входов также реализовалась бы конъюнкция K, и в СФЭ S оказалось бы две различных эквивалентных вершины (см. § 4). По этой же причине на входы всех двухвходовых ФЭ СФЭ S подаются различные ФАЛ. Заметим также, что выход ФЭ Eў, который одновременно является выходом S, не может поступать на вход другого ФЭ Eўў, выход которого также является выходом S, т.к. при этом ФЭ Eў и Eўў должны быть ФЭ & или Ш, на выходах которых реализуются разные конъюнкции из Qn, что невозможно. Пусть a - число вершин СФЭ S, отличных от ее выходов. Из указанных особенностей СФЭ S следует, что
2n Ј a(a-1)
2
+a Ј a(a+1)
2
,
и поэтому
a і Ц2·2n/2-1
Таким образом,
L(S) і 2n+a-n і 2n+Ц2·2n/2-n-1.
Лемма доказана.

Следствие. В силу следствия 2 из теоремы 5.1
2n+Ц2·2n/2-n-1 Ј L(Qn) Ј 2n+ 3
2
Ц2·2n/2+O(n·2n/4).

Лемма 7.4. Если СФЭ S реализует существенную ФАЛ f(x1,...,xn), то L(S) і  n-1, а если, кроме того, ФАЛ f немонотонна, то L(S) і  n.

Доказательство. Перейдем от СФЭ S, содержащей Lўў ФЭ & и Ъ, к дереву D так, как это было сделано при доказательстве теоремы 7.1. Заметим, что число БП f не больше, чем число листьев дерева D, которое, в свою очередь, не больше, чем Lўў+1. Следовательно,
L(S) і Lўў і n-1.
Если же в СФЭ S есть хотя бы один ФЭ Ш (в том случае, когда ФАЛ f немонотонна, ФЭ Ш в СФЭ S обязательно найдется), то
L(S) і Lўў+1 і n.
Лемма доказана.

Применяя лемму 7.3 к ФАЛ f =  [`x]1Ъ...Ъ[`x]n, получим, что L(f) і n. С другой стороны, ФАЛ f можно реализовать формулой [`(x1·...·xn)], и поэтому L(f) Ј  n. Следовательно, формула [`(x1·...·xn)] является минимальной (в классе СФЭ), и L(f) = n.

Будем говорить, что подмножество U множества БП ФАЛ f забивает БП x, x П U, ФАЛ f, если подстановки некоторых констант вместо БП U из ФАЛ f можно получить ФАЛ, не зависящую существенно от x. Множество переменных X ФАЛ f будем называть незабиваемым, если любая переменная x из X не забивается множеством X\{x}. Легко видеть, что при любой подстановке констант вместо некоторых переменных незабиваемого множества X ФАЛ f оставшиеся переменные из X образуют незабиваемое множество переменных для ФАЛ, получающейся в результате этой подстановки. Очевидно также, что все переменные незабиваемого множества X ФАЛ f являются существенными переменными f, если |X| і  2.


Теорема 7.4. Если у ФАЛ f есть незабиваемое подмножество из n переменных, то
L(f) і 2(n-1).

Доказательство. При n = 1 оценка теоремы, очевидно, верна. Предположив, что эта оценка верна для любой ФАЛ f и любого n Ј  (l-1), где l і  2, докажем ее справедливость для произвольной ФАЛ h, которая имеет незабиваемое подмножество, составленное из существенных переменных x1,...,xl ФАЛ h. Пусть S - минимальная СФЭ, реализующая ФАЛ h со сложностью L(h). Рассмотрим вершину v СФЭ S, в которую ведет дуга из входной вершины x1, и которой приписана ФАЛ j базиса Б0. Пусть s = 0, если j = u1·u2, и s = 1 в остальных случаях. Вершина v не может быть выходом S, так как иначе при x1 = s на выходе S появлялась бы константа и переменная x1 забивала бы, тем самым, переменные x2,...,xl ФАЛ h. Следовательно, найдется вершина w СФЭ S, в которую ведет дуга из вершины v. Пусть Sў - СФЭ, получающаяся из СФЭ S в результате подстановки константы3 s вместо переменной x1. Схема Sў реализует некоторую ФАЛ fў с незабиваемым множеством из переменных x2,...,xl и не содержит вершин v, w, то есть имеет сложность не более, чем L(S)-2. В силу индуктивного предположения L(fў) і  2(l-2), и поэтому
L(h) = L(S) і L(Sў)+2 і L(fў)+2 і 2(l-1).
Теорема доказана.

Следствие. L(mn) = 2·2n+O(2n/2).

Действительно, требуемая верхняя оценка для L(mn) вытекает из теоремы 5.2 (см. следствие), а так как БП y0,...,y2n-1 образуют незабиваемое множество БП mn, то теорема 7.3 дает необходимую нижнюю оценку.

Рассмотрим, в заключение, вопрос о сложности реализации симметрических ФАЛ.

Функция f(x1,...,xn) называется симметрической, если ее значение не меняется при любой перестановке аргументов. Значение симметрической ФАЛ однозначно определяется числом единиц в наборе значений ее переменных, так как два набора с одинаковым числом единиц всегда можно получить друг из друга некоторой перестановкой аргументов. Заметим, что любая отличная от константы симметрическая ФАЛ f(x1,...,xn) является существенной ФАЛ, и поэтому L(f) і  n-1 согласно лемме 7.3.


Теорема 7.5. Любую симметрическую ФАЛ от n переменных можно реализовать со сложностью 9n+O([n/logn]).

Доказательство. Пусть f(x1,...,xn) - симметрическая ФАЛ, k = ]log2(n+1)[, а ФАЛ g(y1,...,yk) на наборе [(a)\tilde] =  (a1,...,ak), где |[(a)\tilde]| Ј  n, равна значению ФАЛ f на наборах с |[(a)\tilde]| единицами и принимает произвольные значения на остальных наборах. Пусть Sў - счетчик с входными переменными x1,...,xn (см. замечание к теореме 6.3) сложности не более, чем 9(n+k2), а Sўў - СФЭ, реализующая ФАЛ g и имеющая сложность не более, чем 6(1+o(1))[(2k)/k] (см. теорему 7.1). Схема Sf, которая получается присоединением выходов СФЭ Sў к входам СФЭ Sўў, реализует, очевидно, ФАЛ f, и
L(Sf) = L(Sў)+L(Sўў) Ј 9n+O ж
з
и
2k
k
ц
ч
ш
= 9n+O ж
з
и
n
logn
ц
ч
ш
.
Теорема доказана.


Часть 3. Автоматы


xx 8. Автоматные функции. Их реализация схемами из функциональных элементов и элементов задержки


В данном параграфе рассматриваются некоторые вопросы, связанные с автоматами и осуществляемыми ими отображениями. Подробное изложение теории автоматов можно найти в (?) . В (?) рассматриваются автоматные отображенияия и операции над ними. Здесь мы рассмотрим связь между автоматными отображениями и схемами из функциональных элементов и элементов задержки.

Определение. Инициальным автоматом называется любая шестерка (A,B,Q,G,F,q0), где A, B, Q - произвольные множества, G - функция, отображающая пары из декартова произведения A×Q в Q, F - функция, отображающая пары из A×Q в B, и q0 О Q. Множества A, B, Q называются, соответственно, входным алфавитом, выходным алфавитом и алфавитом (множеством) состояний. Функция G называется функцией переходов, функция F - функцией выхода, q0 называется начальным состоянием.

Определим функционирование автомата. Будем рассматривать параметр t, принимающий значения 0,1,2,... , который можно интерпретировать как дискретное время. Будем считать, что на вход автомата может поступить любая последовательность a(1), a(2), a(3),... (конечная или бесконечная), где a(t) О A для всех t. Введем переменные q(t), t = 0,1,... и z(t), t = 1,2,..., которые будем называть состоянием автомата в момент t и выходным значением в момент t. Пусть x(t) - значение входа в момент t. Тогда определим z(t) и q(t) равенствами
м
п
п
н
п
п
о
z(t)
=
F(x(t), q(t-1))
q(t)
=
G(x(t), q(t-1))
q(0)
=
q0
(8.1)
Эти равенства называются каноническими уравнениями автомата. Легко видеть, что из канонических уравнений по x(1) и q(0) = q0 однозначно определяются z(1) и q(1). Затем по q(1) и x(2) однозначно определяются z(2) и q(2) и т.д. В результате по входной последовательности x(1), x(2),... ,x(n) однозначно определяется выходная последовательность z(1), z(2),... ,z(n), то есть автомат осуществляет отображение последовательностей любой длины (конечной или бесконечной) с элементами из A в последовательности той же длины с элементами из B.

Определение. Пусть A и B - два множества. Отображение последовательностей с элементами из A в последовательности с элементами из B называется автоматной функцией, если существует инициальный автомат, осуществляющий это отображение.

Пример. Пусть A = B = Q = {0,1} и автомат описывается следующими каноническими уравнениями
м
п
п
н
п
п
о
z(t)
=
q(t-1)
q(t)
=
x(t)
q(0)
=
0.
(8.2)
Легко видеть, что входная последовательность a(1), a(2), a(3),... отображается таким автоматом в последовательность 0, a(1), a(2),... . Этот автомат называется единичной задержкой.

Автоматы удобно задавать геометрически с помощью ориентированных графов. При этом каждому состоянию из множества Q сопоставляется вершина орграфа, и каждой паре (a,q), где a О A, q О Q сопоставляется дуга, идущая из вершины, соответствующей q, в вершину, соответствующую G(a,q). Этой дуге приписывается пометка (a,F(a,q)). Вершина, соответствующая начальному состоянию q0, помечается (мы будем помечать ее звездочкой). Описанный граф с пометками называется диаграммой Мура заданного автомата. Например, на рис. 8.1 представлена диаграмма Мура для задержки.


Picture Omitted
Рис. 8.1

Легко видеть, что диаграмма Мура однозначно задает автомат. По дугам и пометкам на дугах однозначно определяются функции переходов и выхода.

Рассмотрим теперь класс схем, с помощью которых можно реализовать автоматные функции.

Определение. Пусть задан базис Б={E1,... , Es, R}, где E1,... , Es - функциональные элементы (см. параграф 4), а R - элемент единичной задержки, имеющий один вход и один выход. Схемой из функциональных элементов и элементов задержки (СФЭЗ) в базисе Б называется граф, который удовлетворяет пунктам 1)-3) определения СФЭ (см. стр. ?) и в котором любой ориентированный цикл проходит хотя бы через одну вершину, соответствующую элементу задержки.

Будем считать, что все переменные СФЭЗ принимают значения из множества {0,1} и могут менять их в моменты времени t = 1,2,.... При этом функционирование элемента R описывается уравнениями (8.2), а функционирование ФЭ Ei, имеющего ki входов, по-прежнему описывается ФАЛ ji(u1,... , uki), i = 1,... , s. Для описания функционирования СФЭЗ с r элементами задержки R поступим следующим образом.

Пусть i-я задержка Ri, i = 1,... , r, приписана вершине vi, в которую идет дуга из вершины wi. Для всех i = 1,... , r удалим из СФЭЗ дуги (wi, vi). По определению СФЭЗ в полученном после этого графе не будет ориентированных циклов и он, тем самым, будет представлять собой СФЭ. Входами этой СФЭ будут все входы исходной схемы, а также все вершины vi, i = 1,... , r (заметим, что все они различны и отличны от входов исходной схемы). Выходами полученной СФЭ объявим все выходы исходной схемы и вершины wi, i = 1,... , r. Пусть в исходной схеме выходам приписаны переменные z1,... , zm, входам - переменные x1,... , xn. Вершинам vi припишем переменные qў1,... , qўr, а вершинам wi - переменные q1,... , qr. В соответствии с определением функционирования СФЭ, для некоторых ФАЛ fi, gj справедливо:
м
п
н
п
о
zi
=
fi(x1,... , xn, qў1,... ,qўr), i = 1,... , m
qj
=
gj(x1,... , xn, qў1,... ,qўr), j = 1,... , r.
(8.3)
Естественно считать, что равенства (8.3) выполняются в каждый момент времени t = 1,2,3,... , то есть
м
п
н
п
о
zi(t)
=
fi(x1(t),... , xn(t), qў1(t),... ,qўr(t)), i = 1,... , m
qj(t)
=
gj(x1(t),... , xn(t), qў1(t),... ,qўr(t)), j = 1,... ,r.
(8.4)
Так как, в соответствии с каноническими уравнениями (8.2), выход элемента задержки в момент t совпадает с его входом в момент t-1, то естественно считать, что в исходной схеме qўi(t) = qi(t-1) при t = 1,2,... для всех i = 1,... , r, где qi(0) = 0. Тогда равенства (8.4) принимают вид (где i = 1,... , m и j = 1,... , r):
м
п
н
п
о
zi(t)
=
fi(x1(t),... , xn(t), q1(t-1),... ,qr(t-1)),
qj(t)
=
gj(x1(t),... , xn(t), q1(t-1),... ,qr(t-1)),
qj(0)
=
0.
(8.5)
Полученные равенства определяют функционирование СФЭЗ и называются ее каноническими уравнениями.

Пример. СФЭ Sў на рис. 4.4б является ячейкой сумматора и реализует ФАЛ z1 = xyЪxqўЪyqў, z2 = xЕyЕqў. Тогда схема на рис. 8.2 будет иметь канонические уравнения
м
п
н
п
о
z(t)
=
x(t)Еy(t)Еq(t-1)
q(t)
=
x(t)& y(t) Ъx(t)& q(t-1) Ъy(t)& q(t-1)
q(0)
=
0.
Если на входы x и y этой СФЭЗ подавать два двоичных числа по одному разряду в каждый момент времени, начиная с младших разрядов, то на выходе схемы будет выдаваться сумма этих чисел, начиная с младших разрядов. Эта схема называется последовательным сумматором.


Picture Omitted

Рис. 8.2

Пусть E2n - множество всех наборов длины n с элементами 0 и 1. Если задана последовательность наборов из E2n в качестве значений входных переменных xi(t), i = 1,... , n, t = 1,2,... , то согласно (8.5) по ним однозначно определяется последовательность наборов длины m z1(t),... , zm(t) для t = 1,2,... . Таким образом, схема осуществляет преобразование последовательностей с элементами из E2n в последовательности с элементами из E2m.

Определение. Пусть автоматная функция j отображает последовательности в конечном алфавите A в последовательности в конечном алфавите B. Пусть СФЭЗ S осуществляет преобразование y последовательностей с элементами из E2n в последовательности с элементами из E2m. Будем говорить, что S моделирует j, если существуют отображения (кодирования) K1: A®E2n и K2: B® E2m, сопоставляющие разным элементам разные элементы и обладающие свойством: для любой последовательности T = a(1)a(2)... a(t) в алфавите A, если j(P) = R = b(1)b(2)...b(t), то y(K1(P)) = K2(T), где
K1(P) = K1(a(1))K1(a(2))...K1(a(t)),

K2(T) = K2(b(1))K2(b(2))... K2(b(t)).

Теорема 8.1. 1) Отображение, осуществляемое любой СФЭЗ, является автоматной функцией. 2) Для любой автоматной функции существует моделирующая ее СФЭЗ в базисе из функциональных элементов дизъюнкции, конъюнкции, отрицания и элемента задержки.

Доказательство. 1) Пусть отображение y, осуществляемое схемой S, задается каноническими уравнениями (8.5). Введем переменные X = (x1,... , xn), Q = (q1,... , qr), Z = (z1,... , zm), принимающие значения, соответственно в E2n, E2r, E2m. Положим q0 = (0,... ,0). Тогда (8.5) можно переписать в виде
м
п
п
н
п
п
о
Z(t)
=
F(X(t), Q(t-1))
Q(t)
=
G(X(t), Q(t-1))
Q(0)
=
q0,
где функции F, G не зависят явно от t. Отсюда видно, что отображение, осуществляемое схемой, совпадает с отображением, задаваемым автоматом (E2n, E2m, E2r, G, F, q0), то есть является автоматной функцией.

2) Пусть автоматная функция дана автоматом D = (A,B,Q,G,F,q0). Выберем n, m, r так, что 2n і |A|, 2m і |B|, 2r і |Q|. Рассмотрим произвольные отображения (кодирования) K1: A® E2n, K2: B® E2m, K3: Q® E2r, при которых разные элементы отображаются в разные элементы. Дополнительно потребуем, чтобы K3(q0) = (0,... ,0). Рассмотрим отображения Gў: E2n×E2r®E2r и Fў: E2n×E2r® E2m такие, что для любых a О A и q О Q выполняется
м
п
н
п
о
Gў(K1(a), K3(q))
=
K3(G(a,q))
Fў(K1(a), K3(q))
=
K2(F(a,q)).
(8.6)
Равенства (8.1) определяют отображения Gў и Fў только для пар [(a)\tilde] О E2n, [(b)\tilde] О E2r таких, что a является кодом некоторой буквы из A, а b является кодом некоторой буквы из B. Для остальных пар отображения Gў и Fў доопределим произвольно. Пусть [0\tilde] = (0,... ,0). Рассмотрим автомат H = (E2n, E2m, E2r, Gў, Fў, [0\tilde]) с каноническими уравнениями
м
п
п
п
н
п
п
п
о
Z(t)
=
Fў(X(t), Q(t-1))
Q(t)
=
Gў(X(t), Q(t-1))
Q(0)
=
~
0
 
(8.7)

Из (8.6) вытекает, что если автомат D преобразует последовательность P в алфавите A в последовательность T в алфавите B, то H преобразует код K1(P) последовательности P в код K2(T) последовательности T. Таким образом, достаточно показать, что автоматную функцию, задаваемую равенствами (8.7), можно реализовать схемой. Так как значением переменной X являются наборы длины n из E2n, то ее можно рассматривать как набор переменных (x1,... , xn), принимающих значения из E2. Аналогично для переменных Q и Z. Тогда (8.7) можно переписать в виде (8.4) для некоторых ФАЛ fi, gj. По теореме 4.2 можно построить СФЭ в базисе {дизъюнкция, конъюнкция, отрицание} с n+r входами и m+r выходами, реализующую семейство функций
м
п
н
п
о
zi
=
fi(x1,... , xn, qў1,... ,qўr), i = 1,... , m
qj
=
gj(x1,... , xn, qў1,... ,qўr), j = 1,... , r.
Пусть в этой СФЭ входная переменная qўj приписана вершине vj, а выходная переменная qj - вершине wj. Добавим дугу (wj, vj) и сопоставим вершине vj элемент задержки. Проделав это для всех пар qj, qўj (j = 1,... , r) получим СФЭЗ, функционирование которой описывается каноническими уравнениями (8.5). Эта схема является искомой. Теорема доказана.

Пример (ячейка памяти). Пусть требуется построить СФЭЗ для автомата с двумя входами, в котором выход в момент времени t всегда совпадает с состоянием в момент t-1, а состояние остается неизменным, если x2 = 0 (ячейка закрыта для записи), и состояние становится равным x1, если x2 = 0 (ячейка открыта для записи). Канонические уравнения такого автомата имеют вид
м
п
п
н
п
п
о
z(t)
=
q(t-1)
q(t)
=
x1(t)x2(t)Ъq(t-1) _
x
 

2 
(t)
q(0)
=
0.
На рис. 8.3 приведена СФЭЗ, реализующая ячейку памяти.


Picture Omitted

Рис. 8.3

Для получения памяти из 2n ячеек с записью одного бита по адресу достаточно взять 2n ячеек памяти, их входы x2 присоединить к различным выходам дешифратора порядка n, а все входы x1 присоединить к единому входу, на который поступает записываемый бит. Чтобы дополнительно обеспечить считывание по адресу достаточно выходы всех ячеек подать на различные информационные входы мультиплексора порядка n.


xx 9. Эксперименты с автоматами. Теорема Мура


Будем теперь рассматривать автоматы, в которых не выделено начальное состояние, то есть автомат задается пятеркой (A,B,Q,G,F).

Через A* будем обозначать множество всех конечных слов в алфавите A. Расширим функции F и G, определив F([`a],qi) и G([`a],qi) для любого состояния qi О Q и любого слова [`a] = (a(1),a(2),...,a(m)) О A*. Пусть автомат (A,B,Q,G,F) находится в состоянии qi О Q и на вход подается слово [`a] = (a(1),a(2),...,a(m)). Тогда на выходе будет последовательно выдаваться некоторое слово [`b] = (b(1),b(2),...,b(m)) и после подачи всего слова [`a] автомат окажется в некотором состоянии qk. Расширим функции F и G, положив F([`a],qi) = [`b], G([`a],qi) = qk.

Определение. Два состояния qi и qj автомата (A,B,Q,G,F) называются отличимыми, если существует входное слово [`a] О A* такое, что F([`a],qi) F([`a],qj). При этом слово [`a] называют экспериментом, отличающим qi и qj, а длину l([`a]) - длиной этого эксперимента.

Теорема 9.1 (Мур). Если в автомате (A,B,Q,G,F) состояния qi и qj отличимы и |Q| = r, то существует эксперимент [`a], отличающий qi и qj, длины l([`a]) Ј r-1.

Лемма 9.1. Пусть в автомате (A,B,Q,G,F) есть 2 состояния qu и qv, отличимые экспериментом длины p и не отличимые более коротким экспериментом, тогда для любого k, где 1 Ј k Ј p, существуют 2 состояния, отличимые экспериментом длины k и не отличимые более коротким экспериментом.

Доказательство. Пусть состояния qu,qv отличимы экспериментом [`a] длины p и не отличимы экспериментом меньшей длины. Пусть F([`a], qu) = [`b], F([`a],qv) = [`c]. Тогда, [`b] [`c], причем [`b] и [`c] различаются только последней буквой. Разобьем все слова [`a], [`b], [`c] на 2 подслова [`a] = [`a]1[`a]2, [`b] = [`b]1[`b]2, [`c] = [`c]1[`c]2, где l([`a]2) = l([`b]2) = l([`c]2) = k. Пусть G([`a]1,qu) = qў, G([`a]1,qv) = qўў. Тогда F([`a]2,qў) = [`b]2, f([`a]2,qўў) = [`c]2. Так как [`b]2 и [`c]2 различаются последней буквой, то qў и qўў отличимы экспериментом длины l([`a]2) = k. Допустим, что qў и qўў отличимы экспериментом [`a]3 длины l([`a]3) < k. Тогда F([`a]3,qў) = [`b]3, F([`a]3,qўў) = [`c]3 и [`b]3 [`c]3. Но тогда F([`a]1[`a]3,qu) = [`b]1[`b]3, F([`a]1[`a]3,qv) = [`c]1[`c]3 и [`b]1[`b]3 [`c]1[`c]3. Следовательно, qu и qv отличимы экспериментом [`a]1[`a]3 длины l([`a]1[`a]3) = l([`a]1)+l([`a]3) < (p-k)+k = p. Это противоречит условию. Значит (от противного) qў и qўў не отличимы экспериментом длины меньшей, чем k. Лемма доказана.

Доказательство теоремы Мура. Пусть состояния qi и qj отличимы экспериментом длины p и не отличимы более коротким экспериментом. Рассмотрим в данном автомате следующее отношение Rm на множестве состояний Q (m=0,1,...,p): состояния qi и qj не отличимы экспериментом длины m (считаем, что любые 2 состояния не отличимы экспериментом длины 0). Если для любого слова [`a] О A* длины m F([`a],qi) = F([`a],qj) и F([`a],qj) = F([`a],qk), то F([`a],qi) = F([`a],qk), поэтому Rm - это отношение эквивалентности для каждого m = 0,1,2,... , p. Относительно Rm Q разбивается на классы эквивалентности Q1(m), Q2(m),..., Qs(m)(m), так что любые два состояния из одного класса не отличимы экспериментом длины m, а любые два состояния из разных классов отличимы экспериментом длины m. При этом s(0) = 1 и Q = Q1(0). Посмотрим как меняются эти классы при переходе от m к m+1. Если 2 состояния отличимы экспериментом длины m, то они отличимы и экспериментом длины m+1, поэтому эксперименты из разных классов остаются в разных классах. По лемме 9.1 для любого m = 0,1,...,p-1 существуют 2 состояния, отличимые экспериментом длины m+1 и не отличимые экспериментом длины m. Следовательно, хотя бы один из классов эквивалентности относительно Rm распадается не менее чем на 2 класса эквивалентности относительно Rm+1. Отсюда 1 = s(0) < s(1) < s(2) < ... < s(p-1) < s(p) Ј r. Так как все s(i) - натуральные числа, то p Ј r-1. Теорема доказана.

Пример автомата на рис. 9.1 показывает, что оценку r-1 в теореме Мура в общем случае улучшить нельзя. Здесь, независимо от входного символа a G(a,qi) = 0, для i = 2,3,... ,r и G(a,q1) = 1.


Picture Omitted

Рис. 9.1

Для того, чтобы отличить состояния qr-1 и qr надо перевести хотя бы одно из них в q1 (входным словом длины r-2) и затем подать еще один входной символ. Следовательно, минимальная длина эксперимента, отличающего qr-1 и qr, равна r-1.

Определение. Пусть 2 автомата (A,B,Q1,G1,F1) и (A,B,Q2,G2,F2) имеют одинаковые входной и выходной алфавиты. Пусть qi О Q1 и qj О Q2. Будем говорить, что эксперимент [`a] О A* отличает состояния qi и qj, если F1([`a],qi) F2([`a],qj).

Теорема 9.2. Пусть даны 2 автомата (A,B,Q1,G1,F1), (A,B,Q2,G2,F2). Пусть |Q1| = r, |Q2| = m и qi О Q1, qj О Q2. Тогда, если qi и qj отличимы, то существует отличающий их эксперимент [`a] длины l([`a]) Ј r+m-1.

Доказательство. Можно считать, что Q1 ЗQ2 = Ж. Рассмотрим автомат (A,B,Q,G,F), в котором Q = Q1 ИQ2 и диаграмма которого получается объединением диаграмм исходных автоматов. Тогда |Q| = r+m и по предыдущей теореме qi, qj отличимы экспериментом [`a] длины l([`a]) Ј r+m-1. Теорема доказана.

Следующий пример (рис. 9.2) показывает, что оценка r+m-1 в общем случае неулучшаема. Здесь предполагается m і r и опять выходной символ зависит только от текущего состояния и не зависит от входного символа.


Picture Omitted

Рис. 9.2

Легко видеть, что если не использовать состояние qўm второго автомата, то нельзя отличить состояния q1 и qў1. Поэтому сначала надо перевести второй автомат словом [`(a1)] из qў1 в qўm. При этом l([`(a1)]) і m-1 и первый автомат под действием [`a] перейдет из q1 в qr. Чтобы далее получить различные выходные последовательности, надо перевести первый автомат из qr в q1 и подать еще один символ. Всего для того, чтобы отличить q1 от qў1, потребуется входное слово длины (m-1)+(r-1)+1 = m+r-1.

Определение. Автомат, в котором все состояния попарно отличимы, называется приведенным автоматом.

Неотличимые состояния в автомате образуют классы эквивалентности.

Определение. Число классов неотличимых состояний называется весом автомата.

Если склеить все неотличимые между собой состояния, то диаграмма корректно перейдет в диаграмму приведенного автомата, который реализует то же автоматное отображение входных слов в выходные, что и исходный автомат.

Рассмотрим следующую задачу. Дан автомат с известной диаграммой, но неизвестно его начальное состояние. Всегда ли существует эксперимент [`a], позволяющий определить это начальное состояние? Последнее равносильно тому, что F([`a],qi) F([`a],qj) для любых состояний qi qj.

Теорема 9.3. Существует приведенный автомат, в котором нельзя определить начальное состояние.

Доказательство. Рассмотрим автомат на рис. 9.3. Здесь первое число в скобках обозначает входной символ, а второе - выходной символ.


Picture Omitted

Рис. 9.3

Он приведенный, так как q2 отличается от q1 и q3 экспериментом 1, а q1 отличается от q3 экспериментом 0. С другой стороны, нет единого эксперимента, отличающего все состояния, так как любой эксперимент, начинающийся с 0, не отличает q1 и q2, а любой эксперимент, начинающийся с 1, не отличает q1 и q3. Теорема доказана.

Литература

[]
Алексеев В. Б., Ложкин С. А. Элементы теории графов и схем. - М.: Изд-во МГУ, 1991. - 40 с.

[]
Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. - М.: Наука, 1977. - 368 с.

[]
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. - М.: Наука, 1990. - 384 с.

[]
Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // ДАН СССР - 1962. - Т. 145. - N 2. - C. 293-294.

[]
Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. - М.: Наука, 1985. - 320 с.

[]
Лупанов О. Б. Асимптотические оценки сложности управляющих систем. - М.: Изд-во МГУ, 1984. - 137 с.

[]
Потемкин И. С. Функциональные узлы цифровой автоматики. - М.: Энергоатомиздат, 1988. - 320 с.

[]
Яблонский С. В. Введение в дискретную математику. - 2-е изд. - М.: Наука, 1986. - 384 с.

[]
Яблонский С. В. Эквивалентные преобразования управляющих систем. - М.: Изд-во МГУ, 1986. - 40 с.


Footnotes:

1Предполагается, что входные и выходные БП перечислены в соответствии с их упорядоченностью в X и Z.

2Через ]a[ обозначается ближайшее сверху к a целое число; основание 2 у логарифмов опускается.

3 Подстановка констант вместо некоторых входных переменных СФЭ подразумевает, что ``константные'' входы схемы, а также те элементы, на входах которых появляются константы, последовательно устраняются применением тождеств [`0] = 1, [`1] = 0, x·0 = 0, xЪ1 = 1, x·1 = xЪ0 = x до тех пор, пока это возможно.


File translated from TEX by TTH, version 2.70.
On 31 May 2000, 16:09.