!Л0СЮВСЮ1/1 opjiKiiA alt^iuV, 01"ди1л : :::^i-Lc:;o,A ргболол;:
И ОРДЕНА ТРУдО»30Г0 1?ЛСНОгО Лч\>.*Л. i ГО^УмЛРСТ^ПШ
УНИВЕРСИТЕТ км. М.Ъ.Х. :1'Гл)?-А
Меха пи tec -м* *: ема а я ч ос i *к л ь* t к;* _' -
L.E. I/UaHOB
АСИМПТОТИЧЕСКИЕ СЦЕНКИ СЛОЖНОСТИ УПРАВЛЯЩИХ СИСТЕМ
Учебное пособие
Издательство Московского университета
1Э84

УДК 519.95
Лупанов О.Б. Асимптотические оценки сложности управляющих
систем, - М.: Изд-во Моск. ун-та, 1984, 138 ©.
Учебное пособие охватывает значительную часть курса
"Элементы дискретной математики и математической кибернетики",
читаемого на механико-математическом факультете МГУ, на
протяжении 10 лет, а также часть материала, предусмотренного
обязательной частью программы кандидатского экзамена по
специальности 01.01.09 (Математическая кибернетика). В пособии
рассматриваются основные классы "дискретных" управляющих систем
(контактные схемы, формулы, схемы из функциональных элементов).
Описываются простейшие методы синтеза, метод Шеннона,
асимптотически наилучшие методы синтеза, метод каскадов. Приводятся
примеры применения принципа локального кодирования.
Для студентов и аспирантов.
Рецензенты:
проф. В.Б.Кудрявцев;
докт. физ.-мат. наук Ю.И.Янов
Олег Борисович Лупанов
АСИШТОТИЧВСКИЕ ОЦЕНКИ СЛОЖНОСТИ УПРАВШШЦИХ СИСТЕМ
Заведующий редакцией С.И.Зеленский
Редактор Ф.И.Горобец
Технический редактор Е.Д.Захарова
Подписано к печати 11,10.84» Формат 60х9Сг/16. Бумага
офсетная * I* Офсетная печать* Услф печ. л. 8, 5.
Уч.=изд. л. 5,23. Тираж 1000 экз.
Заказ 20ВЧ Цена 15 коп. Заказное
Ордена "Знак Почетап издательство Московского университета
103009, Москва, ул. Герцена, 5/7.
Типография ордена "Знак Почета" изд=ва МГУ.
II9899, Москва, Ленинские горы
m Издательство
077@2)-64 - заказная Московского университета, 1984 г.

Оглавление
Введение ; 5
Глава I. Схемы из функциональных элементов
§ I. Определение схем из функциональных элементов 8
§ 2. Некоторые свойства функции L(F} 13
§ 3. Простейшие методы синтеза 15
§ 4. Метод Шеннона 19
§ 5. Метод каскадов 23
§ 6. Асимптотически наилучший метод 26
Глава П. Контактные схемы
§ 7. Общие сведения 33
§ 8. Метод Шеннона и метод каскадов 37
§ 9. Разбиение множества наборов на сферы .... 44
§ 10. Реализация системы конъюнкций 49
§ II. Асимптотически наилучший метод 54
§ 12. Асимптотика функции L (п) 58
Глава Ш. Формулы в базисе { & , V,"" } и SC -схемы
§ 13, Связь мевду формулами в базисе { &, V, ~~}
и 3? -схемами. Простейшие оценки сложности . . 62
§ 14. Асимптотически наилучший метод 64
§ 15. Асаштотика функции ЛЛ (Н) 71
"лава 1У. Схемы из функциональных элементов в
произвольном базисе
§ 16. Обобщенное разложение 75
§ 17. Асимптотически наилучший метод 77
§ 18. Оценка числа схем данной сложности 84
§ 19. Нижние оценки для функции L ( F^) .... 92
§ 20. Некоторые дальнейшие результаты о схемах
из функциональных элементов и формулах в
пг^ ""^вольном базисе 95
3

5 21. Схемы из функциональных элементов с
задержками 97
Глава У. Схемы для функций из специальных классов
§ 22. Некоторые специальные вектор-функции 108
§ 23. Симметрические функции П1
§ 24. Вычисление значений фуы'дии на
последовательных наборах ПЗ
§ 25. Ненулевые инвариантные классы Яблонского . . • *16
§ 26. Вектор-функции с ограниченным множеством
значений 122
§ 27. Монотонные вектор-функции 124
§ 28. Принцип локального кодирования 134
Литература 136

Введение
Задача синтеза управляющих систем [I] является одной из
основных задач кибернетики. В общих чертах эта задача может
быть сформулирована ел едущим образом. Задан запас
элементарных средств (например, формулы для элементарных функций, или
функциональные элементы, или интегральные схемы, или
подпрограммы и т.д.). Заданы правила построения из них более
сложных образований - схем. Задан, наконец, способ наховдения по
схеме реализуемой ею функции. Задача состоит в получении для
каждой функции схемы, реализующей эту функцию. Как правило,
эта задача имеет неоднозначное решение (например, при
построении контактной схемы для функции алгебры логики или
программы для вычисления значений некоторой функции). Поэтому задача
синтеза уточняется: требуется построить не вообще какую-нибудь
схему для данной функции, а в том или ином смысле наилучшую.
При таком подходе качество каждой схемы характеризуется
значением некоторого параметра, т.е. предполагается, что
каждой схеме S сопоставлено неотрицательное число L(S)-
сложность схемы S (это может быть вес схемы, ее
стоимость, занимаемый схемой объем и т.д.), и считается, что
схема S тем лучше, чем меньше Z-(S)
В этих условиях задача ставится так: для кавдой функции
-Г требуется найти реализующую ее схему S , на которой
Zj(S) достигает минимума. Обозначим этот минимум через
Обычно имеется тривиальный метод нахождения такоЛ
экстремальной схемы, связанный с перебором всех схем
определенной сложности, однако он малоэффективен, так как для его
осуществления требуется очень много шагов. В связи с этим задача
может быть несколько видоизменена. В случае реализации функ-
1х-2084 5

ции алгебры логики новая постановка задачи выглядит так.
Вводится функция L,(p*) = rna3cZ,(f), где максимум берется по
всем функциям от П аргументов. Требуется найти метод
синтеза схем, позволяющий для любой функции от п аргументов
построить схему S » Для которой L(S) близко к L(ri) ,
например L.(S)r\ L> (ti) . Такой подход был предложен К.Э.
Шенноном [2] в 1949 г. при рассмотрении контактных схем и дан
наилучший по порядку метод синтеза контактных схем.
В данном учебном пособии принят асимптотический подход к
решению задачи синтеза. С его позиций исследуются некоторые
традиционные классы управляющих систем (схемы из
функциональных элементов, контактные схемы, контактные ЗС -схемы, т.е.
формулы в базисе <? , V , ~" ).
Пособие условно можно разбить на две части. В главах 1-1У
рассматривается задача синтеза схем для одной функции алгебры
логики. При этом приводится несколько методов синтеза "разной
стеяени сложности" . Оказывается (и это естественно), что
более простые из рассматриваемых методов дают более сложные
схемы. "Сила" различных методов иллюстрируется в применении к
схемам из функциональных элементов в базисе <?<. # V , ~~
(§ 3-6). Для остальных классов управляющих систам описываются,
как правило, лишь разработанные автором асимптотически
наилучшие методы [3].
В главе V рассматривается задача синтеза схем для функций
(и систем функций), допускающих существенно более простую
схемную реализацию, чем это возможно в общем случае. Эта
задача также впервые была рассмотрена в упомянутой работе
К.Э.Шеннона. Впоследствии многими авторами был выделен целый ряд
классов таких функций и были найдены более экономные методы
синтеза для введенных ранее и вновь построенных классов.
Весьма общий результат был получен СВ. Яблонским, который описал
континуальное семейство таких классов ("инвариантные классы")
[4, 5]. Затем автором этого пособия был предложен общий
подход к синтезу схем для функций из специальных классов -
"принцип локального кодирования". Этот метод позволяет для функций
из многих классов получать существенно более простые схемы по
сравнению с общим случаем [б]. В главе 3 принцип локального
кодирования иллюстрируется на нескольких примерах и дается его
неформальное описание (в применении к синтезу схем из
функциональных элементов).
Включенный в учебное пособие материал составляет значи-
6

тельную часть содержания спецкурсов "Математическая теория
синтеза управляющих систем1*, "Элементы дискретной математики
и математической кибернетики", в течении многих лет
читавшихся автором на механико-математическом факультете МГУ, а также
часть материала, предусмотренного обязательной частью
программы кандидатского экзамена по специальности 01.01.09
"математическая кибернетика". Основу учебного пособия составляют статьи
автора [7, б], а также [8]; в дальнейшем ссылки на эти статьи
как правило будут опускаться.
Предполагается знакомство читателя с элементами алгебры
логики. Не определяемые здесь понятия и термины (полнота
системы функций, дизъюнктивная нормальная форма - д.н.ф., граф и
т.д.) можно найти, например, в учебнике СВ. Яблонского [9].
Нумерация формул в каждом параграфе - самостоятельная;
теорем и лемм - общая.
В пособии используются следующие обозначения:
0 - знак сложения по модулю 2;
loa Q - двоичный логарифм Q ;
[PJ - наибольшее целое число, не превосходящее а ;
]QL - наименьшее целое число, не меньшее а ;
СХп<л &n, - неравенство, справедливое при достаточно
больших п ;
Оп^ 6a
Qn? ^a 1- существует положительная константа С , та-
I кая что
an=0Fn)J an<-cbn;
On
Ci^i,... - некоторые константы.
Автор пользуется случаем выразить искреннюю благодарность
В.М. Храпченко, отредактировавшему первоначальный вариант
рукописи, и Ф.И. Горобец, сделавшей много полезных замечаний.

Глава I
Схемы из функциональных
элементов
§ I. Определение схем из
функциональных
элементов
Определение схемы из функциональных элементов
распадается на две части. Сначала определяется один вспомогательный
объект - "сеть", а уже затем с его помощью определяется схема.
Понятие "сеть" играет чисто вспомогательную роль и
используется только для определения схемы из функциональных элементов;
оно отличается от другого, более известного понятия под тем же
названием (см. § 7), и поэтому здесь использованы кавычки.
"Сеть"строится из полюсов и элементов. Полюсы будем
изображать маленьхша
кружками (рис.1,а),
Кавдый элемент
имеет несколько
входов,
занумерованных числами
1,2,..., и один
выход (в частности,
допускаются элемен-
*) 6) ты без входов).
Элементы будем
изображать в виде
треугольников с от-
Рис. I ростками (рис.1,6);
отростки сверху соответствуют входам элемента, а отросток сни-
8

зу - его выходу. В приводимом ниже определении индуктивно
определяется "сеть" и множество ее вершин.
Определение "сети" .1. Полюс есть
"сеть". Он является (единственной) вершиной этой "сети".
П. Если Si и S9 - "сети" без общих вершин, то их
объединение есть "сеть" (рис. 21 Вершинами этой "сети"
являются вершины исходных "сетей".
Ь
Рис. 2
Ш. Если 5 " "сеть" и Е элемент, все входы и
выход которого не являются вершинами "сети" S > то
результат присоединения (т.е. отождествления) всех входов элемента
L к некоторым вершинам ясеги» S есть »сеть# (рис.3);
Рис. 3
при этом к одной вершине "сети" могут присоединяться различ-
9

ные входы, но каждый вход присоединяется только к одной
вершине. Вершинами новой "сети" являются вершины "сети" $ и
выход элемента С .
Непосредственно из определения "сети" вытекают следующие
два свойства "сети":
1. Никакой элемент "сети" не присоединен своим выходом ни
к полюсу, ни к выходу другого элемента "сети".
2. Вершины "сети" можно занумеровать натуральными числами
так, что выход любого элемента имеет номер больший, чем номер
каждого из его входов. Поэтому в "сети" не существует
последовательности вершин 0< , аг ,..., ат , где am=Qt,
такой что при t = 1 , ..., m-{ вершина Qj является
входом некоторого элемента, а GU+i - его выходом. Другими
словами, "сеть" не содержит ориентированных циклов из
элементов.
Отметим, что любую "сеть" можно получить, соблюдая
следующий порядок ее построения: сначала нужное число раз
применяется п.1 определения "сети", затем п.П, и, наконец, п.Ш.
Две "сети" ${ и S2 называются изоморфными, если
можно установить взаимно однозначное соответствие между
1) полюсами "сети" S< и полюсами "сети S2 ;
2) элементами "сети" S< и элементами "сети" ?2
так, что соответствующие элементы имеют одинаковое число
входов и их одинаково занумерованные входы присоединены к
выходам соответствующих элементов или к соответствующим полюсам
(тем самым устанавливается взаимно однозначное соответствие
мевду вершинами обеих "сетей").
Определение схемы. Схемой из
Функциональных элементов называется "сеть", в которой
1) казвдому полюсу приписана одна из переменных Xt ,...,
Х^ ,..., причем, разным полюсам - разные переменные,
полюсы называются также входами схема:
2) каждому элементу Е с Z входами поставлена в
соответствие некоторая функция алгебры логики ^ е ( 1^ 1 ,...,
1^г), существенно зависящая от Z аргументов (при Z =0
функция <^Е есть константа) и называемая функцией элемента
Е ; элемент Е с сопоставленной ему функцией ^Е
называется функциональным элементом:
3) некоторой вершине приписано число I; некоторой
вершине (быть может, совпадающей с первой) приписано число 2 и т.д.;
некоторой вершине приписано число гп . Вершины, которым
приписано хотя бы одно из чисел, отмечены символом * . Эти
10

вершины называются выходами схемы; I - м выходом будем
называть (единственный) выход, которому приписано число I (и,
может быть, другие числа).
Схему с la входами, выходам которой приписаны числа
I,,,., m , будем называть ( а , гп )-схемой.
Функции, реализуемые схемой, определяются следующим
образом (будет указан процесс сопоставления функций вершинам
схемы);
1) каждому входу схемы сопоставляются функция, равная
переменной, приписанной этому входу;
2) пусть всем вершинам, к которым присоединены входы
элемента Е схемы, уже сопоставлены функции. Тогда выходу этого
элемента сопоставляется функция <-fE( f*,..., fa:>), где
Ч Е ( 4i »•••» ^i) "* ФУНКЦИЯ элемента Е , а <Ш) -
функция, сопоставленная той вершине, с которой соединен t -й вход
элемента ?[ (рис. 4).
х^хг
(xivxz)Z(x1vxz)=x&xz
Рис. 4
В результате этого процесса каадой вершине схемы будет
юпоставлена некоторая функция.
Схема по определению реализует упорядоченную систаму
ункций (вектор-функцию)
II

где Г^ ( Xj ЭСп.) -функция, сопоставленная { -му
выходу. Такие системы функций будем называть ( h, , ГП) -
функциями.
Две схемы называются изоморфными, если они получены из
изоморфных "сетей* так, что
1) соответствующим входам (долюсам) приписаны одинаковые
переменные;
2) функции соответствующих элементов равны;
3) выходам одной схемы соответствуют выходы другой и,
наоборот, множества номеров соответствующих друг другу выходов
совпадают.
Очевидно, что изоморфные схемы реализуют одинаковые
(упорядоченные) системы функций. В дальнейшем изоморфные
схемы ("сети") различаться не будут.
Если функции всех элементов схемы S принадлежат
множеству б . то будем говорить, что схема S есть схема в
базисе Б (или й§д Б ) (при этом не требуется, чтобы
каждая функция из Б была функцией некоторого элемента схемы
?) . Заметим, что здесь, в отличие от работ по исследованию
вопросов функциональной полноты (например, [9, гл.1; 10,
гл.1 J ) функции базиса не предполагаются независимыми.
Множество всех функциональных элементов, функции которых
принадлежат базису D , будем также называть базисом и .
В дальнейшем мы будем пользоваться следующим правилом
"последовательного соединения схем".
Пусть
1) ( Kl, k ) - схема S реализует ( М, к ) -
функцию ( (А ( Х1 ...., Х^) ffc( X, ,..., Ха));
( ГП , I )-схема S& реализует ( m , Z ) - функцию
( *1Д,,,-«Ут>,-с»9г( Ч • 4т»-
2) Схемы blj и cr; не имеют общих вершин.
При присоединении каждого i -го входа схемы В (г)
к некоторому (одному) ^) ( i )-му выходу схемы S*1' и
стирания переменных, приписанных входам схемы S^ (рис. 5),
получается ( гг , I )-схема, реализующая ( Гъ , t ) -
функцию ( К1 ( Х< ,..., Ха) flj( Xt ..... Ха)). где
ru ( х, • • • • • Xn,) = (J ^ (j^ (xt,..., xn),. •., -^(p^C xf,
• • • t Xj^/ / •
Это правило вытекает из определений "сети", схемы и
системы функций, реализуемой схемой (можно, например, к схеме
12

о ^пристраивать
схему по
одному элементу).
Очевидно
следующее угвервдение.
Вели б -
йодная система функций.
то Ддд любой ФУЧЙНА
алгебры дсадвд f
базцее Б » реади-
H&i&g элемента
L. в схеме S
будем называть
последовательность ее
элементов Е(,(,....Ец,
обладающую свойства-
nut= t ;
2) один из
входов элемента
Ей
t
присоединен х выходу
S .
Гис. 5
элемента Li: ? B ^ } ^ t);
3) выход элемента Ец есть выход схемы
Число t будем называть длиной цепи. Схему S будем
называть неприводимой, если для каадого ее элемента Е в схеме
существует цель этого элемента•
Очевидно, что от всякой схемы можно перейти к
неприводимой схеме, не изменяя системы функций, реализуемой схемой, и
яе увеличивая числа ее элементов (для этого достаточно
последовательно отбрасывать элементы, выходы которых не являются
выходами схемы и на присоединены ни к каким входам других
элементов схемы).
§2. Некоторые свойства
функции Z, ( F)
Будем рассматривать схемы в полном конечном базисе Б •
Пусть каждому функциональному элементу Е из множества
D поставлено в соответствие положительное число /дЕ)- вед
13

этого элемента.
Сложность схемы S определим как сумму весов всех ее
элементов; обозначим эту величину через L($>) • Положим
Lb(F) = rrunZ-(S) , где минимум берется по всем схемам в
базисе U , реализущим систему функций Г .
Имеет место
Теорема I. [п]. Для любых двух (конечных) бази-
сов БА и иг существуют такие две положительные конотацты
Ct и с2 , что для любой системы Функций F
Z.s, (F)
Доказательство. Пусть S - схема в базисе
Ьг , реализующая Г и удовлетворяющая условию Z_,(S)=Z-5 (l)
Сопоставим кавдому элементу С * базиса LL некоторую
схему Ь* в базисе D1 , реализующую функцию элемента Li •
После этого в схеме S кавдый элемент Qj, заменим схемой
Dj . В результате получится схема Ь в базисе D i ,
реализующая Г . Пусть П, у - число элементов L у в схеме
/ / с?. \ •
Ь и С = max , х г- ч (С > О , так как веса всех
г t L(Ej) 2
элементов обоих базисов положительны). Тогда
и
Ш = 1_и}и^)
Таким образом,
Lbi(F)±US*)^c?L(S) = czLBa(F).
Тем самым правое неравенство из (I). доказано. Левое
доказывается аналогично. / сг / \
Обозначим через L Б ( •"/ G J минимальную сложность
схемы (в базисе D ), которую надо присоединить к схеме, ре-
14

ализувдей G » чтобы полученная схема реализовала Г
Очевидно, что
L6{F)<Lb(G)+Lb(F/g).
Пусть f - конечное множество (упорядоченных) систем
функций; через Zj6(<-T) будем обозначать тасс/^Б(р) ,
где Г пробегает множество j . В частном случае, когда
jF - множество всех функций от аргументов ОС, ,..., ЭС^,
вместо ЛБ(*0 бУДем употреблять также обозначение Z^C^1).
Иными словами, Zj5(rt) = maxLB(f) , где максимум берется
по всем функциям Р от аргументов Х< ,..., ^п •
§3. Простейшие методы
синтеза
В § 3-6 будут рассмотрены некоторые методы синтеза схем
из функциональных элементов в базисе ? , V »
Элементы, которым сопоставлены функции & , V . ~~ »
будем называть соответственно конъюнктором. дизъюнктором и
инвертором. Веса элементов предполагаются равными единице.
Поэтому сложность каждой схемы равна числу элементов в ней. В
дальнейшем в обозначениях сложности схем символ данного
базиса будем опускать.
В этом параграфе будут описаны два простейших метода.
I. Метод синтеза, основанный на ьлоделировании совершенной
д.н.ф. Пусть € = ( 6i ,..., б^ ). Рассмотрим конъюнкцию
Kg =X1<... Х^. Схема для К^ , приведенная на рис.6,
оостоит из П инверторов, присоединенных к входам схемы, и
цепочки из П - 1 конъюнкторов с W входами; i -й вход
цепочки присоединяегся либо к ь =му входу схемы, если б^= I,
либо к выходу i -го инвертора, если б^= 0. Очевидно, что
Z.(K,)^2n-i. 0)
Пусть ? ( Сс,,,..., ЭСа) - произвольная функция и
\\i V...V ГЛ^- ее совершенная д,н.ф. Схема для f
строится из m схем для конъюнкций К i и цепочки из m - i
дизъюнкторов (цепочка имеет m входов), "объединяющей"
выходы схем для конъюнкций (рис. 7). Таким образом, учитывая (I),
15

Xj X<i
••• /\ ••• T
\-1^,либо-либо
Рис. 6
приходим к следующему утверждению.
ЕСЛД SQSQPiffiJBqag. ДсЗ.«&. tyqjrail | ( 3Cf ,..-• ЭСп,) fifi-
даржт. m .уод.здн.уодй ( гп » 4 ), ig
Z, ({) ^ 2mn. B)
Так как гп ^ 2^ , то для произвольно!! функции
-Г ( Xt ,..., X п ) f не равной тождественно 0 , имеем
Функция, тождественно равная U , мокет быть
реализована схемой, изображенной на рис. 8. Поэтому (при П>1 )
L(n) 4 n2rt+1.
1б

/fi
m
Рис. 7
2. Модификация предыдущего ме-
тода^ заюняающаяся в совместной
реализации^ конъюнкций. Цусть
^^1
*rj
2* конъюнкций вида
Лемма I.
система всех
¦Ч
/Ла„)~ 2
п.
Доказательство.
Очевидно, что каждая конъюнкция
из
си
'« • • • «*» »v
Ха) является конъюнкцией двух
... 0с?т из
-f»• • • i
конъюнкций: X/
П

и
^(^.....зО
°m-M
am„ ... х„- из Q„.„(inH ^).
Z(Qa/Qm,Qn.J<2". «)
-m+1 • ' • ~n
Поэтому (рис. 9 )
х1
1_
Qm(xf,...,xm)
\х%.х*т
/Г
Lm+f
Хп
1
чп-т(хт+1*—->Хп)
Рис. 9
Из (I) следует, что
Z.(QnL 2mBm-iL тг"-, А@„.„)«(гг-тJ"-т'!
Поэтому, учитывая B) из § 2 и C), имеем
Z,(aj4 2,b+m2rn+1 - Ы-тJп~т+\
И

Положим теперь ГП = |_ р J . Тогда
m2"Uf2^
а
-5-+г
(п-тJЛ-'т4^G+027 +
2
С другой стороны, очевидно, что при П > 2
(каждая конъюнкцив реализуется на выходе некоторого элемента).
Лемма доказана.
Используя лемму I, можно усовершенствовать предыдущий
метод синтеза, заменив в схеме на рио. 7 верхнюю часть схемы,
реализующую конъюнкции "раздельно", схемой, реализующей их
"совместно". При этом для любой функции f ( oct ,..., эса)
(не равной О тождественно) имеем
L(fHZ,(QftW\
и в силу леммм I
Поэтому
L(nL- 2-2a
§4. Метод Шеннона
Описываемый в этом параграфе метод предложен К.Э.
Шенноном [2] в 1949 году для контактных схем. В последующие года
этот метод применялся другими авторами для других классов
схем. Здесь метод излагается применительно к схемам из
функциональных элементов.
Разложим функцию f ( Х1 ,..., эсп) по П-'к
переменным
19

Схема Ь для функции f строится из трех блоков (подсхем)
(рис. ГО):
Х<
Хл-
П-к
Хп-.
п-к+1
2П
Qn-k(xu — *Xn-k)
Vk(Xa-k+f9...9Xn)
р(Хп-к+1,...,Хп)9
f(&i9...96n-k9Un-*+1>"9Xn)
Рис* 10
1) блока, реализушего ^^.к v^t > •*•» ^а-О >
2) блока, реализующего систему ^(^.^^,...,30^)
всех С функций от переменных 0Ca.^+o ... , ЗСа ;
20

3) блока, осуществляющего соединение первых двух блоков
в соответствии с (I).
Заметим, что два первые блока не зависят ст реализуемой
функции f , а зависят только от разбиения аргументов
функции f на два подмножества: (х11...|х^к}и {ха_^,..., оса].
В третьем блоке на каждый член разложения (I) приходится
не более одного конъюнктора и не более одного дизъюнктора.
Таким образом
Ш±цап_куихУ2-2~«. B)
Исходя из того, что каждую функцию из Vf< можно
реализовать тривиальным способом (см. стр. 16 ), получаем оценку
ДЮ< *2*+< 2г\ (в)
Заметим, что систему функций \Л можно было бы реализовать
существенно более экономно, однако это не повлияло бы на
получаемую ниже асимптотическую оценку сложности всей схемы.
Из B), C) и леммы I имеем
Z,(SL 3-2n-N-1<2kV*
Положим (при достаточно больших П, )
k=[lo<j(n- 3 loyn)].
Тогда
loa(n-2>by n)-i<k<lo<% (n-з toy n),
2 Y < 2 4П-ЗЦ n,
k 2n
22 4
M3
Поэтому
F-2084

Таким образом,
Поясним, из каких соображений было выбрано значение к .
Введем обозначение
Ш,ь)-з?+±??. D,
« ?
Нам bw^,o найти (целочисленное) значение к таким
образом, чтобы Zj ( П. , К ) было возможно меньше. Для этого
можно было бы средствами дифференциального исчисления найти
значение к0 , при котором достигается минимум функции
Zj ( П , к ) при фиксированном W , и затем взять целое
число, "близкое к ко ". В данном случае этот прием привел бы
к цели сравнительно быстро. Мы однако поступим иначе - при
помощи более грубых рассуждений найдем значение к , при
котором Zj ( IT t k ) принимает не минимальное значение, а
"близкое" к нему, и найдем это значение Zj ( Н, , К ). Это
оправдано тем, что мы ищем не абсолютный минимум, а
"асимптотический". Кроме того, в следующих параграфах (для других классов
схем) будут описаны методы синтеза, характеризующиеся большим
числом параметров, а в таких случаях "аналитический' подход
является весьма трудоемким.
Итак, займемся поиском "почти оптимального" значения к .
Заметим, чго с ростом к первое слагаемое ? в D),
убывает, а второе слагаемое Г) возрастает, причем ? убывает
гораздо медленнее, чем возрастает Т) . Пусть к' -
значение к , при котором ?=Г) . Вели теперь к' "немного
уменьшить", то ? "почти не увеличится", а Г) "сильно
уменьшится". Поэтому оптимальным значением к должен быть
"немного уменьшенный" корень уравнения § = X).
Найдем сначала (с нужной точностью) k # Из уравнения
i-r}
получим
22

п = 2*+ 2к'+ loyW - Icj j • E)
Беря в правой части E) одно первое слагаемое, получаем
п
е. пока еще
к'^Цп,, ! = -^, t? = 2^-2^D и t^g, те ^
слишком велико.
Следующее приближение к получится, если в E) взять
два слагаемых в правой части и во второе из них подставить
значение первого приближения: П=? + 2 к' . Тогда
Попробуем теперь в выражении для К под знаком
логарифма вычесть из П не 2^^ , а, скажем, 3>toan. При
этом п п
Мы добились нужного соотношения между ?> и Т) .
Вспоминая теперь, что \\ должно быть целым, положим
k= [fo(j (la-3 lochia)].
Зто и есть выбранное на стр. И значение к .
§5. Метод каскадов [42]
Этот метод является усовершенствованием метода Шеннона.
Он учитывает некоторые свойства функций и благодаря этому
позволяет для многих функций строить сравнительно простые схемы.
Идея этого метода и его связь с методом Шеннона нагляднее
всего проявляются п^и синтезе контактных схем (см. н;,же, стр.4Ь ).
I. Газгожение фуцедии. Пусть -Г ( ОС1 ,..., ЗСа ) (или
II * ' " * *' *"** п '» Т 2 1 »•••» *-С п '» • • • » г m, ^ ^t » • • •»
Хп)) есть функция (соответственно система функций),
подлежащая реализации. Образуем последовательность множеств функций:

Gi=(9i,^---»0»--M9ifci(«i.---x^)},
посредством следующего индуктивного процеоош. Множество G0
совпадает с множеством реализуемых функций. Пусть множество
G^ уже построено. Рассмотрим такие 2 kj, функций:
Множество Gi+4. по определению состоит из всех различных
функций, встречающихся среди этих 2^<i функций. В частности,
Grv-i есгь множество {ос1,Х1, 0 , i } или некоторое его
подмножество.
Из определения множеств (л^ вытекает следующее свойство:
(I) дат* Фзгезши 9 (ос* ••••• xn.-i > да.
G?i ( 0 4 I ^ И-2) может быть представлена в виде
9(^ 3cJa^&l OV^K'-.^-i-i),
2. Построение схомы. Схема строится в соответствии с
только что описанным разложением, но пв обратном порядке".
Сначала реализуются все функции из Ga.( . Затем на основе
свойства (I) реализуются все функции из G а-г ; при этом
используется один инвертор (на все множество G п-г ) и по
два конъшктора и один дизъюнктор на каждую функцию из G гъ-г
и т.д.
Пример. Ддя функции Xi ® Хг® . . . ® Хп
множество G0 состоит из одной функции Х?® Хг® . . . ©Х^;
множество CJ. при 1 ^ t 4- IX " 1 состоит из двух функций:
Xi® ... <0Х*,..(. flXt©.. -©Sc^-i© 1.
Соответствующая схема изображена на рис. II. Эта схема не является
минимальной по числу элементов (ср. со схемой рис. 4), а лишь ил-
24

Xi
Xn-1
Рис. II

люстрирует применение метода каскадов.
Замечание. Здесь был описан метод синтеза,
опирающийся на разложение функции по переменным, взятым в таком
порядке: ха, Х^,... , Хг. Очевидно, что можно использовать
и любой другой порядок Х^, Хц,..., 3CirtH.Сложность схемы,
вообще говоря, зависит от этого порядка переменных.
§6. Асимптотически наилучший
метод
i. Специальное представление функций. Функция f(xi9..^Xn)
может быть задана табл. I, в которой значение f (#<,..., &п)
Таблица ?
-к i^rv-K+tv
функции Г на наборе ( б,,... , ба-к , 6^_к +1 > • • •' ^а /
помещается на пересечении столбца, соответствующего
(б*,..., ffrv-O» и строки, соответствующей ( б^к+1,..., О-
Разобьем строки таблицы I на полосы At , •••. Ар по ^>
строк в полосе (последняя полоса модет содержать меньшее
число строк). Ясно, что
2Ь

-к
Пусть f± - функция, совпадающая с f на полосе А{, и
равная 0 вне этой полосы. Очевидно, что
ffr, ж*) = V fji ,1,0 =
"X^У « f''-1- fA-Ал- х.) -
feV ^ ^'-X^ i fi^-6-K.«^ ^).
Заметим, что каждая из функций ?F^..., б^.^Х^^-и, ••• > ^Са)
задается одним столбцом таблицы для функции Г^ и поэтому
принимает значение 1 не более чем на 6 наборах; число
различных функций ДОП ..., 6^, Х^^+1,..., xj (при
фиксированном i ) не превосходит 26.
2. Метод синтеза. Схема S для функции -Г строится
на основе представления (I) и состоит из 6 блоков (соединение
блоков условно показано на рис. 12; двойной линией отмечен
блок, содержащий "почти все* элементы схемы, что будет видно
из дальнейшего).
1. Блок А реализует Q^ (зс^ .. .,ХЛ.к);
2. Блок D реализует Ot^ CCri-.^+?,---t ЗСгО»
/.(ВLк2*+\
3. Елок С реализует все различные функции
fi(*o--»?ri-M ^-k+o-^rO'Из сказанного выше
следует, что для реализации одной такой функции (с использованием
конъюнкций, реализованных блоком В ) требуется не более 6
дизъюнкторов (или один конъюнктор, если функция равна 0);
Л(СLРб26
27

Рис. 12
4. Блок IJ реализует все функции
Р
/.(D)* P2""k
5. Едок G осуществляет умножение
(oci,...xa^)-pF1,...,6rt.f., эс^.ьи,..., ^rv);
Z.(G)-2ft-*
28

6. Наконец, блок F ревизует функцию ffo,-.., ЗСЛ)
как дизъюнкцию функций, реализованных блоком G ;
Таким образом,
L(S)=L(A)+L(B)+L(C)+L(D)+L(G)+L(n<
Положим
4< = [3 toy /г] , 6 « [|г - 5 1щ ft].
Тогда
(п-**0г"'*"-0(-?), к2к*' - 0(n5<ojм),
fi-iVo(^-ikO*o(^)),
2-462'»2"-k(t-0(^)).
Поэтому
L(nL^(l.0(i^)).
Поясним, из каких соображений бшхи выбраны энагъния к
и 6 . Введем обозначение
29

L(n,k.J)-MИJ"-k*Vf<2**, + (9B^25). ,„
2n <* ^ Г
Если А -^ ft, , то о(р ^ — ; если же 6 > П, , то
y>nZ > — . Таким образом, всегда Z, (ft, k, б) ^ -— .
Попытаемся подобрать значения параметров а и 6 так,
чтобы
Z,(n,k,-ib-. C)
on prv
Из C) следует, что -г- =°(Р^- -тг > т.е. i^n.
С другой стороны, из C) следует, что 6 2 = X ^ гх •
Поэтому 6 <: 1Я - ^OQ П + о ( 1). Таким образом,
6~ п,
и в выражении для Л(п,, 'к, б) при условии C) главной
частью является слагаемое <Ы1Ъ = -^- <ч, -2— , а любое дру-
{ 2п\ * ri
roe слагаемое есть о ( ——) . Поэтому для того, чтобы имело
место C), необходимо (а в случае 6 ~ П и достаточно)
выполнение условий
ус— 0, D)
(п-кJп'к
— о,
2п/п E)
к 2к
2%
6 г6
о,
F)
2
-~ 0.
а-к G)
30

Из D) следует, что к * > boCL П, • . Кроме того, ранее
было замечено, что 6 <?¦ П- >Соа ri + o( 4) . Попробуем
теперь искать к в виде k = Съ loy П , а 4 - в виде
6 = rt-C^oan • Тогда условие F) выполняется при любых С3
и С4 , а остальные условия могут быть заменены
эквивалентными условиями
С3>1, D')
С3>2, E')
с4 >с3 + 1. G<)
Этим условиям удовлетворяют, например, числа Са =3, С,= 5.
Заметим еще, что если сумму B) исследовать более
аккуратно, то можно установить, что
^,к,б)»4->с5^),
где С5 - положительная константа. Если теперь искать
значения параметров к , 6 , при которых величина Zj(n, к, б)
оценивается сверху аналогичным образом:
то окажется, что параметры К , 6 необходимо должны
иметь вид
Итак, нами доказана
Теорема 2 [в, 7].
^-?A-о(-*аг>)).
Ниже (§19) будет показано, что
А(П.)>,— • F)
31

На самом деле в § 19 будет установлено больше (см. теорему
15): для любого О 0 доля функций f CCt ,.... 0Са).
для которых ра
Z.(f(x ,зс0)^A-е)-^,
стремятся к 0 с ростом П , т.е. для почти всех функций
т V 3Cf t • • •» *^-п '
ЦК*< ха))?-?.
Теорема 3 JjB, 7j
on
Таким образом, описанный в этом параграфе гютод синтеза
является асимптотически наилучшим.
Заметим еще, что при малом числе переменных и при
указанных выше значениях параметров построенные этим методом
схемы сильно отличаются от оптимальных. Тем не менее некоторый
вариант этого метода может быть использован и при малых П,
Для этого надо, во-первых, экономно реализовывать блоки А ,
В и С и, во-вторых, при каждом П специальным образом
подбирать параметры к и 6 t чтобы минимизировать сумму,
аналогичную сумме B).

Глава П
Контактные схемы
§7. Общие сведения
Контактной схемой; называется неориентированная сеть (т.е.
неориентированный граф с выделенными вершинами - полюсами [9,
с.158] ), каждому ребру которой приписана некоторая булева
переменная с отрицанием или без него. Ребро вместе с приписанной
ему буквой Х(Г(б' = О, 1 ) называется контактом переменной
DC , а точнее, замыкающим контактом, если О" = 1 , и разщ-
каюрм контактом, если (Г = О . Контакт Xs считается
замкнутымt когда Х^ =1 , и разомкнутым, когда ОС?" = 0 .
По определению, цепь схемы замкнута, когда замкнуты все ее
контакты, и разомкнута, когда разомкнут хотя бы один ее контакт.
Каадой паре полюсов схемы (не обязательно различных)
ставится в соответствие булева функция (проводимость между
этими полюсами), определенная на наборах значений всех
переменных, приписанных контактам схемы, и равная I тогда и только
тогда, когда в схеме существует замкнутая цепь между этими
полюсами (в частности, функция тождественно равна I, если полюса
совпадают, и тождественно равна 0, если в схеме вообще нет
цепей мевду этими полюсами). Говорят также, что схема реализует
сопоставленные ей функции, двухполюсная система реализует
единственную булеву функцию (если не считать двух тривиальных
функций, товдественно равных I), называемую иначе
проводимостью схемы.
Легко видеть, что проводимость контакта X (т.е.
схемы, состоящей из одного контакта X6 ) равна Xs , а
проводимость цепи из контактов ОС;4 , . . . , х/* оавна
Х^ 1 . . . х^ k . Очевидно также, что проводимость
цепи тождественно равна 0 тогда и только тогда, когда в ней
3-2084
33

встречаются два противоположных контакта одной переменной ( X
и X ). С другой стороны, цепь с проводимостью xtLl ... xtv*,
1; Ф i>? при i 4= ь , содержит не менее, чем по одному
контакту Х^ \...,ЗС^1^ и не содержит никаких других кон-
1 * 6i
тактов. Такую цепь мы будем иначе называть цепью х, 1---
<ч„ l
. • • X,- к и, если не оговорено противное, будем
ъ к
считать, что она соединяет полюса схемы. Очевидно, что
проводимость схемы, имеющей цепи г\а ,..., Г\т (и не имеющей
других цепей с ненулевой проводимостью), равна V Г\ .
1=1 ь
(Разумеется, дизъюнкцию можно, было бы брать и по всем цепям,
т.е. включая цепи с нулевой проводимостью.)
Например, схема (с полюсами C(t и G, ), изображенная
на рис. 13, реализует функцию
f (xd7x2,x3)=x1x2x3Yx1x2x3V а^х^v х1х2х3=х1©х2©х3
Рис. 13

Приведенное математическое определение функции,
реализуемой контактной схемой, отражает "физическую" сторону дела.
Например, "математическая схема" на рис. 13 соответствует
"физической схеме" на рис. 14.
^Г
D
D
—г
D
-а.
Рис. 14
Контакт, изображенный на рис. 15,а, разомкнут при невоз-
бувденной обмотке реле и замкнут при возбужденной обмотке;
контакт на рис. 15,6, наоборот, замкнут при невозбужденной
обмотке реле и разомкнут при возбувденной обмотке.
Соответствие между состояними "физической схемы" и ее математической
модели установим, считая, что обмотка возбуждена тогда и
только тогда, когда соответствующая переменная равна I. В этих
условиях контакт "физической схемы", соответствующий контакту
ОС (математической модели), разомкнут, когда X = О , и
замкнут, когда X = I. Поэтому для каждого набора значений
переменных значение функции, реализуемой "математической
схемой", равно I, тогда и только тогда, когда "физическая схема"
35

проводит ток.
-и- -п-
а) б)
Рис. 15
Очевидно, что если схема Ь< реализует функцию ? ,
а схема S2 - функцию «рг , то в результате параллельного
(последовательного) соединения этих схем получается схема,
реализующая f t V f 2 ( f <? f) .
Далее, легко видеть, что любая функция алгебры логики
•f ( Xt ..... Ха) может быть реализована контактной схемой.
Для этого достаточно, например, соединить параллельно цепи
X.1 ... Хп , соответствующие членам совершенной д.н.ф.
(для функции, товдественно равной 0, можно взять схему,
состоящую из двух изолированных полюсов). Такая схема содержит
не более М Z контактов.
Сложность контактной схемы Ь определим как число ее
контактов, обозначим эту величину через L* (S) . Определим
далее функции, аналогичные введенным в § 2 для схем из
функциональных элементов:
ZjK («р) = тга L*(S) , где минимум берется по всем
контактным схемам, реализующим функцию -Г ;
LjK (п.) =• гпах/-,к (г) , где максимум берется по всем
функциям Г от аргументов X ^,..., X п .
Только что описанный "тривиальный" метод синтеза дает
оцеяку LK(nLti2n. .
36

§8. Метод Шеннона и
метод каскадов
I. Луда Шеннона. Контактная схема называется ( 1 , к )-
долюсником. если в ней некоторый полюс считается входным, а
остальные к полюсов - выходными (при этом мы будем
допускать, что полюс может быть входом и выходом схемы
одновременно). Обычно с ( 4 , к )-полюсником связывают систему из к
функций, каждая из которых реализуется мевду входом и
некоторым выходом. Аналогично определяется ( к , 1 )-лолюсндк и
соответствующая ему система из к функций, реализуемых между
а входами и выходом.
( 4 , к )-полюсник называется разделительным, если
проводимость мевду любыми двумя его выходами товдественно ра^на
0.
Заметим, что функции, реализуемые разделительным ( 4 ,
к)-полюсником попарно ортогональны (т.е. конъюнкция любых
двух из них товдественно равна 0).
Лемма 2 [2]. Пусть А - разделительный ( 1 , к)-
полюсник. В - произвольней ( I , 1 )-полюсник. Пусть
далее Г. - проводимость между входом а и i - м выходом
схемы А ж а« - проводимость между t - м входом и
выходом Ь схемы В . Пусть, наконец, t - и выход схемы
А A4 14 4ч) присоединен к j, ( ь )-му рщд, (&<§ш В
(см. рис. 16) (при этом разные выходц схемы А могут
присоединяться к одному и тому же входу схемы В )• Тогда полу-
Д0ИДЙД ,<ЙШЙ S реализует между входом а и выводом б
Доказательство. Кавдая цепь в схеме S
(мевду Q и и ) однозначно разбивается на четное число
отрезков (кавдый из которых, кроме, может быть, первого и
последнего, содержит не менее чем по одному контакту), лежащих в
схемах А и В : первый отрезок лежит в А » второй в В »
Зх-2084 37

третий (если он есть) снова в А , четвертый в В и т.д.
Границами мевду этими отрезками служат общие полюсы схем А
и В , являющиеся выходными в А и входными в В .
В схеме возг/омь. цепи двух типов:
1) цепи, шев^ие един отрезок в схеме А ;
2) цепи, имение не менее двух отрезков в схеме А .
Легко виде:ь, что дизъюнкция проводимостей цепей первого
типа равна функи:,т/м определяемой формулой (I). Кавдая цепь
второго типа имеот л;.оводимость, равную нулю, ибо ее второй
отрезок в схеме А соединяет различные выходы схемы А и, в
силу разделигим;ос?м этой схемы, имеет нулевую проводимость.
Тем самым :емма доказана.
Заме f i о. Если схема U имеет не более двух
входных полюсов, -о формула (I) остается справедливой и при
неразделительном ( 1 , к )-полюснике А , так как в данном
случае цепи второго типа в схеме S отсутствуют. В
частности, если просто объединяются (отовдествляются) выходы схемы
(т.е. вся езеема В состоит из одного полюса), то формула (I)
переходит в формулу
У ft
(I1)
38

2. Контактное Дерево. Обозначим через L^ ( Qa)
минимальное число контактов, достаточное для построения
контактного A,2^ )-полюсника, реализующего (между входом и
выходами) Qa( Xj ,..., Эс^)- систему всех конъюнкций вида
•*-1 • - • ^п •
Система конъюнкций U^ ( Х1 ,..., 0Са) может быть
реализована ( 1, 2п')-полюсником, называемым контактным деревом
(рис. 17). Легко видеть, что контактное дерево содержит
2-2a -2 контактов.
Рис. 17

Таким образом,
A(Qft)«2-2*-2.
Очевидно, что если в контактном дереве объединить
(отождествить) выходы, соответствующие конъюнкциям из совершенной
д.н.ф. произвольной функции f ( Xt,..., Xa), то
проводимость получившейся схемы мевду входом и новым выходом будет
равна -f ( Xt ,..., Ха). Такой метод синтеза дает оценку
L^(n)<2-2n
Заметим, наконец, что контактное дерево является
разделительным ( 1,2Л) -полюс ником.
гп
3. Универсальный многополюсник. B,1 )-полюсник будем
называть универсальным, если он реализует (мевду входами и
выходом) все 22Л функций f (X.,..., Ха).
I рИ
Теорема 4 [2]. Существует универсальный B , 1 )-
полюсник Ua с числом контактов, не превосходящим 2*22Kt.
Доказательство. Построение схемы проводится
индукцией по П . Схема U^ для П, = I изображена на рис.
18 (здесь один из входных полюсов совпадает с выходным, но для
входы <
Рис. 18
большей наглядности этот полюс "раздвоен"; возле каждого из
входных полюсов написана соответствующая ему функция). Имеем
40

Допустим теперь, что можно построить универсальный
[2 ,1 )-полюсник U п_± так, что
Схема U^ получается из схемы ^Ja-i следующим об-
)азом (рис. 19). Для каждой функции Г ( Х4 ,..., ЭС^)
выбивается новая вершина - входной полюс схемы \Jn . Эта функция
Рис. 19
излагается по последнему аргументу:
Зсли обе функции ^(х{1...,Хп_{,0) И f С^, ...,Ха-1 Л)
)тличны от нуля, то выбранный полюс соединяется контактами ЭС,
i Хп с голи входами схемы Un,^ , на которых
реализуются функции f(x4,...,iR.lf0) и f (х^-.^х^И) с°-
)Тветственно (здесь мы воспользовались тем фактом, что схема,
состоящая из полюса и контактов Ха и ЭСп , есть раздели-
'ельный A,2)-полюсник; поэтому, с одной стороны, после ее
41

присоединения на ее входе реализуется -Г ( Х1 ,..., Х^), a
с другой стороны, ее присоединение не изменяет функций,
реализуемых многополюсником LI^-i ). Если одна (или обе) из
этих функций равна нулю, то соответствующий ей контакт в
схему не включается. Поэтому "не будет использовано" 22
контактов Х^ и столько ае контактов ХЛ . Таким образом,
Z.(UJ=L(UKM)*2-22"-2-2J
рП.-1
и, учитывая индуктивное предположение, получаем
Теорема доказана.
4. Метод Шеннона. Разложим функцию
С ( 0С1 ,..., Ха ) по П - к переменным
Схема S для функции -Р образуется из контактного дерева,
реализующего все конъюнкции X*1 ... X ,?"? (это
A,2 )-полюсник), и универсального многополюснику.. -
(теорема 4), реализующего все 22 функций от аргументов
гн
^п-к+и ""> ^п (эго B,1 )-полюсник).
Выход дерева, на котором реализуется конъюнкция
Х{ ... Х^.^ , присоединяется к тому входу
универсального многополюсника, на котором реализуется функция
f (etl . . ., 6a-k , Х^^,.. Mi^. В силу леммы 2
полученная схема реализует функцию Г ( Xlf..., Xa).
Ясно, что
п-к 2*
aSL 2-2^2'2
B)
42

о П+2
Теорема 5 [2].
а>>* * •
Доказательство. Для получения этой оценки
достаточно в неравенстве B) положить fc = [ >?оа (п, - 2 -?oaia)J .
Замечание!. Более детальный анализ суммы
2* 2""*+2*2* показывает, что rnia B' 2"""*+ 2'22 )
on. k
равен о^(гг) — , где 2 ^°^(п,)^4 , причем
^uno^(a)=2, Zimo((n) =4.
Замечание 2. Оценка /^(п)? ^
Movier быть получена и в том случае, если вместо универсального
многополюсника, описанного в теореме 4, взять схему,
реализующую все функции от к аргументов тривиальным образом -
раздельно - на основе совершенной д.н.ф., т.е. со сложностью, не
' превосходящей к 2 2
5, Метод каскадов для
контактных схем. Разложение функции
описано в § 5,
Построение схемы. Сначала реализуются все
функции из G п_± . Соответствующая схема имеет не более 2
контактов (самый*худший случай изображен на рис. 20). Затем, с
учетом свойства (I) (стр.2*/ ) реализуются все функции из Gn-2'
при этом на кавдую функцию тратится один контакт Х^.^ и
один контакт X^_4 и т.д.
Пример. Для функции ЗС1 © ... ®Хп схема
изображена на рис. 21.

ХП-1
О
о
Я/1-1
рис.го
Puc.Zi
§9. Разбиение множества
наборов на сферы
В этом параграфе описывается специальное разбиение
множества всех двоичных наборов определенной длины, с помощью
которого в следующем параграфе будет построена схема дяя
реализации системы конъюнкций, более простая, чем контактное
дерево. ^
Будем рассматривать наборы о( =(оA,#..>о(Г1)из
нулей и единиц. Расстоянием мевду двумя наборами СХ и J&
будем называть число разрядов, в которых эти наборы различа-
44

ются; это число будем обозначать через d (&, j$).
Пусть о@ - произвольный набор. Множество наборов С<
таких, что d(S,S0) = I, будем называть (единичной) сферой
с центром 0@ . Множество наборов о( таких, что
d(S , с50)^ I, будем называть (единичными) шаром с центром
So-
Определим теперь подмножество П наборов длины
П*=2~{ (по существу, совпадающее с кодовым множеством
Хемминга [13] ). Сначала рассмотрим одно вспомогательное
множество Н0 . Его удобно задать прямоугольной матрицей,
строки которой образуют наборы из Н0 • Матрица имеет 2 ~ъ~1
строк и Гц = 2-1 столбцов (табл. 2). Левые 2 о ~1
столбцов этой матрицы образуют единичную матрицу; в правых
столбцах произвольным образом расставлены всевозможные
различные наборы длины t , имеющие не менее двух единиц (число
таких наборов равно 2^-?-1, т.е. их столько же, сколько
строк в матрице). В верхней части табл. 3 приведен пример
матрицы для 1=3.
Таблица 2
Множество П состоит из~всевозможных линейных
комбинаций наборов из Н0 (в смысле поразрядного сложения по
mod2 - см. табл. 3). Так как наборы из HQ линейно
независимы, то
н
содержит
2г1-1-1
1 О
наборов.
лемма з [13]. ^ддмвда между тирад раздмдач
45

Таблица 3
s,
S2
&»
S4
0
I
0
0
1 0
0
St 1
ckz 0
01ъ О
&4 0
адЗз i
a,®^ i
St©S4 1
S2©of3 0
O^®^ 0
olz(t)ol4 0
Sfi® Sf2©a3 1
S1®o^2©S4 1
^©о(з©о/4 I
аа©аэ®а4
0
0
1
0
0
0
0
1
0
0
1
0
0
1
1
0
1
i
0
1
0
0
1
0
0
0
0
1
0
0
1
0
1
0
1
1
0
1
1
0
0
0
1
0
0
0
0
1
0
0
1
0
1
1
0
1
1
1
1
1
0
1
0
1
1
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
1
0
1
0
1
i
1
0
0
1
1
0
0
0
1
0
~q]
I
1
I
0
0
I
I
I
I
I
I
0
0
0
0
0
0
I
о^е&г©^©^
46

Доказательство. Очевидно, что расстояние
мевду двумя наборами равно числу единиц в их сумме (по mod 2),
Далее, сумма любых двух наборов из м снова есть набор из
П . Поэтому достаточно показать, что любой набор из П ,
отличный от нулевого, содержит по крайней мере три единицы.
Пусть N(o0, N((^) , lN2(pO есть соответственно число
единиц в наборе СУ , число единиц в первых 2 - ? ~ { его
разрядах, число единиц в последних ь его разрядах. Ясно,
что N^^IN^)"*" ГЧ2(<3).Из определения множества Ц
следует, что дяя каждого ненулевого набора о( из Н N^)>i.
Дяя завершения доказательства рассмотрим три случая.
1) N{ (<5) = I. Тогда 5е Н0 и N2(<3)^2.
Поэтому N (<3 ) ^ 3.
2) N^^) = 2. Тогда Сх есть сумма некоторых двух
наборов S1 и 5B из П0 . Но так как 6({ и Ыг
различаются в каких-то из последних {, разрядов, то N0(9^)^ 1-
Поэтому N (оО ^ 3.
3) Nd(<5Q^3. Тогда и [М E0* 3.
Лемма доказана.
Лемма 4. Дяя любого натурального L существует
разбиение множества всех наборов длдщц 2 * на попарно не
пересекающиеся сферы.
Доказательство. В качестве центров сфер
возьмем все наборы оС = (о@, сХ^ ...,о( / \ такие, что
^Фь-ч^О6 ^»а °^о произвольно (т.е. либо 0,
либо I).
Эти сферы попарно не пересекаются. В самом деле, пусть
0( и р1 - центры двух различных сфер. Если о! ф ]& ,
то на основании леммы 3 d (o(, G ) ^ 3, поэтому
U \& ,Д)> 3 и даже шары с центрами 0(' и fi1 не
пересекаются. Если Сх =JB , то о@ Ф 0О . Сфера с цент-
47

ром <Ы содержит наборы
(A.d! ^.4).M^ CaO-'^A-'^-z'Vi)-
Сфера с центром J3' содержит наборы
(^,4»--M^2«.1\(j5e,51,ot2,...>o^.1),...,(ipe,cyi,...o^2,^M).
Отсюда видно, что эти сферы не пересекаются.
Наконец, эти сферы содержат все наборы, так как они
попарно не пересекаются, каждая из них содержит 2 ^ наборов, а
всего сфер 2*2 "
Лемма 5. Пусть Lf ( ozt ЭС^ ) - характеоисти-
Ч9ркая,фдакдия сф.зрц,с дедтррм ( ^ t ,..., J5Z ) *. Хо.ГДа
(г) ч&,..^-^---&*?*2Г'--*? (*<^
*6 5?
A)Ч,(эсо...,хг)сс/а:^=0 при Цу (и^.^г).
Доказательство очевидно; заметим лишь, что
Y(x„...,=c,) = :x:*'z,V.x,*»V...
..^.^^..x^V.-.V^a*'1'
Первое утверадение леммы 5 показывает, что любую
конъюнкцию из дизъюнктивной нормальной формы (I) характеристической
функции сферы ^ можно "выщепить" умножением Lp на
некоторую переменную или ее отрицание.
х Эта функция равна I на тех и только тех наборах,
которые составляют указанную сферу.
48

§ 10. Реализация системы
конъюнкций
Опишем способ построения A,2 )-полюсника, реализующего
Q ( х хп) и асимптотически в два раза более
экономного, чем контактное дерево.
Сначала построим схемы, каждая из которых реализует часть
этих конъюнкий. Пусть Ц> (Xj ,..., Хг ) -
характеристическая функция сферы Ф с центром ( J2>± ,..., ]Зг ) и I -
схема, реализующая Ц> и построенная в соответствии с
формулой (I) из § 9. Таким образом,
Присоедщши к выходу (т.е. к одному из полюсов) схемы I
вход контактного дерева 2D , реализующего все- конъюнкции
вида U,1 . . . Uq^ (множества \ Х1,..., Хг| и
[ц ,..., U "I не пересекаются), а к каждому из 2 _выхо-
дов этого дерева - по пучку контактов ЗС1 р±у ..., хг г
(рис. 22).
Полученную схему назовем D^0 ) - схемой. Эта схема
содержит менее
контактов. Из леммы 5 следует, что \ 4~>Q )-схема реализует
всевозможные конъюнкции вида
xi •••a'S-4 х? ^? + 1 --"Ч Vi •4'
Число этих конъюнкций равно 2 'Е . Так что при выполнении
некоторых соотношений между п и 2 на одну конъюнкцию в
среднем приходится приблизительно один контакт (в контактном
дереве - два).
Легко видеть, что^Ц-^П] -схема не является
разделительной. Тем не менее имеет место
Лемма 2s. Утверждение леммы 2 останется
справедливым, если а качестве схемы Д дзд?& (ф, оЛ -схему.
4-2084 49

Рис. 22
Доказательство почти полностью повторяет
доказательство лемш 2» В случае цепи второго типа второй ее
отрезок в схеме Д либо проходит через два контакта одного
лучка Х^ * и Хи * (рис. 23,а), либо содержит
отрезок, расположенный внутри контактного дерева jD
(входящего в схему А ) и соединяющий два различных его выхода
(рис. 23,6). В первом случае проводимость К цепи равна О,
ибо в силу утверждения (JI) леммы 5
К^ Ч(х«.---.аО**х*-0.
Во втором случае также К = о из-за разделитальности
контактного дерева D.
50

а
а
Рис. 23
1ем самым лемма доказана.
Теорема 6 [з].
Z.K(QJ~2a.
Доказательство. Пусть Z = 2 , р - нату-
:альное; 'Z ^ П, . Рассмотрим разбиение множества всех набо-
:ов (из нулей и единиц) длины Z на попарно не
пересекающееся с^еры, судестзущее в силу леммы 4. Число raiaix с?ер
:авно -~- . для какдой с$еры *-Р построим (+, ft-о )-схему
;здесь(^1),..,^гг.г)=(х^1>..мХгг) ). Входа всех этих ехал
объединил (,ис. И4). Получившаяся схама реализует все коныонк-
л

с/б#^#"с/б##Х> с/б''\г#Ъ/б##\)
Рис. 24
? бп
ции вида Xt 4 . . . ССп . Число контактов в этой схеме не
превосходит (см. (I) )
1^(гг+гп-г^2»"гг)=22г+~ + 2п.
Ceo90-2lo<jrx)]
Положим Z = 2 . Тогда
!L?*3i < г 4 a - 2 ^0, а,
С другой стороны, очевидно, что L. ь, ( Ua) ^ 2 .
Заметим, что более экономная реализация
характеристических функций сфер (например, с применением контактного дерева
или с использованием вместо схем | эквивалентных им схем,
содержащих по 3^-2 контактов) не влияет на вид полученной
52

верхней оценки.
Теорема 6 показывает, что контактное дерево не является
минимальной схемой и что число контактов может быть
уменьшено асимптотически в два раза. На рис. 25 изображена схема,
реализующая все элементарные конъюнкции 5 аргументов, содержащая
0110
1Н1
Х5 Х$
х5 Хс х5 х5 х5 х* х5 х5
А* *Jb» *>?& *к& ъкь *h& *А* *h
Ч14^ *№Р Х1*№X1» ьщ* х& *да *w
Рис. 25
меньшее число контактов F0), чем соответствующее дерево F2)
(в этой схеме характеристические функции сфер реализованы
более экономно, чем в схеме, построенной описанным выше
способом). Э.Ф. Мур показал [14], что в классе разделительных схем
4Y-2084 53

контактное дэрево является минимальной схемой.
§ 'II. Асимптотически наилучший
метод
Теорема 7 [з].
U(n)<%(i*0(&)).
Доказательство. I. Специальное
представление функций. Пусть 2 = 2Р ,
р - натуральное; 7, < П • Рассмотрим разбиение
множества всех наборов дяины 7 на попарно не пересекающиеся сферы
(лемма 4). Обозначим через L^• ( х1 ,..., ЭСг)
характеристическую функцию i-й сферы ( I й \ ^ 9 ) '
Пусть -Г ( Xi ,..., Ха) - произвольная функция.
Рассмотрим функции
fcCCi.---»0 = 4),Cci,...aq8)ff3c1(...,acrt)) |=1,...,^-
Очевидно, что
,V»"f-
Пусть центром i -й сферы является набор (й; ^, •»• fii,z)-
Тогда функция Г- полностью определяется своими значениями
ва 2 с наборах
(вне этого множества функция Г; равна нулю) и может быть
задана табл. 4; здесь к - новый параметр, к< П-2.
1с
Таблица имеет 2 строк, соответствующих всевозможным наборам
(бп_к<м,..., 5а) значений переменных Xn.fc+1> ...,3:^
и *г 2 а~ "в столбцов, соответствующих таким наборам
( ^1» • • •» 6,г -4с) значений переменных Эс4,..., ЭСП.^ }
4i F4,..., б^) = 1 т.е. ( 6i бг ) имеет вид
что
54

Таблица 4
-n-Ы
6
H-K+ i • •
о
6t
6,п-к
V-O
fr
s
a
s^s
На пересечении
столбца, соответствующего ( б,,..., ffai^ ),и строки,
соответствующей ( &п„ь+1 ,..., бп ), помещается значение
функции fj, на наборе (?1§...§ ба ).
Строки табл. 4 "разобьем на полосы А/»•••» Ар по
б строк б полосе (последняя полоса может содержать меньшее
число строк). Очевидно, что
Пусть
равная
где
f j,i " ФУНК[ХИЯ, совпадающая с Г- на полосе А^ и
О вне этой полосы. Очевидно, что
г'/г р
f-V V f. • ,
55

Заметим, что кавдая функция {V (^,...,6^,^.^,..., ЗС^)
обращается в единицу не более, чем на 5 наборах, и что
число различных функций fк t ( &i, • • •> 6п_к,Хп_ш,...}Xn) при
фиксированных 1 и I не превосходит 26.
2. Метод синтеза. Схема S для функции Г
SCI") '
i t естъ
( tj, П-К-2)-схема, реализующая конъюнкции, соответству-
щие таким наборам ( 6$ ,..., 6 п-к )» чго
4i ( ^i »•••• <*г ) = I. Эта схема содержит не более
2z + 2n-*-z+i +2Лс"гг контактов (см. (I), § 10).
SB) 5
i I есть B , 1)-полюсник, реализующий
всевозможные различные функции f^fo,-А-к ,ЭСа_к+4,...,хл).
Схема S; t может быть построена следующим образом: дая
каждой функции f • t (б4,..., ба.^ ,хгг.|с+4,...,Хп)берется схема,
соответствующая совершенной дизъюнктивной нормальной форме этой
функции (она содержит не более 6к контактов), и эти схемы
объединяются своасж выходавш (рис. 26). Таким образом, схема
Si; содержит не более ? k 2 контактор. Далее, каждый
h с («
выход схемы о- • соединяется с некоторым входом схемы
~ (г) hb q CD
о . -ь , а именно выход схемы °v,i » реализующий
Xft... х??^к • соединяется с входом схемы о :ь
реализующим {11(б1,..мб^^,Ха^+0...,ХГ1>ПолУчвнная в
Результате этих соединений двухполюсная схема Si i в силу
леммы 2 реализует функцию f i,{ • Соединив параллельно все
схемы S; t , получим схему S дая исходной функции Г.
Таким образом, число контактов в схеме S не превос-
56

ходит
где
L =АВ,
Л ?' / ?^ \ ГУ
А= — (-Т + 1) (число схем S«,i >>
B)
^=1г+1п'^ъ*^2'Х~к''гг+^26 (сложность одной схемы
Sj.i ).
Рис. 26
Положим
(эти значения параметров выдраны на основании соображений,
аналогичных приведенным на стр. 22. ) Тогда
51

*2 = nf-L\ 2п+™ mn(±\-rfL\)
Из B) - D) следует, что
Тем самым теорема доказана.
§ 12, А с и м п т о т и к а функции
Две контактные схемы называются изоморфными, есл;;
существует изоморфизм их сетей, при котором соответствующим ребрам
приписаны одинаковые символы ( Xt, Х^ ). Очевидно, что
изоморфные схемы реализуют одинаковые системы функций, в
частности изоморфные двухполюсные схемы реализуют одну и ту же
функцию.
Очевидно также, что можно ограничиться рассмотрением
схем, не содерясащих изолированных вершин, отличных от полюсов,
ибо удаление таких изолированных вершин не изменяет н/.
функций, реализуемых схемой, ни числа контактов в ней.
Обозначим через С а число сочетаний с повторениями
из О элементов по и . Существует взаимно однозначное
соответствие меаду сочетаниями с повторениями из Q
элементов по О и (обычными) сочетаниями из а + Ь - 1
элементов по Ь • сочетанию с повторениями из а элементов по fa
mc;;l4o сопоставить набор длины О + fe - 1 из нулей и единиц,
иг^чадй Ъ единиц и 0-1 нулей, в котором число
единиц перед первым нулем равно числу вховдений в сочетание с
58

повторениями первого элемента, число единиц между t -м и
( t + D-м нулем равно числу вховдеяий (t + 1)-го элемента;
число таких наборов равно числу обычных сочетаний из а + 6-1
элементов по 6 . Таким образом,
гь - сь
Пусть Dn - число неизоморфных двухполюсных сетей с
Я ребрами, не содержащих изолированных вершин, отличных от
полюсов.
Л е м м а б.
SK4(c,h)K
Доказательство, Пусть К ^ 1 .
Очевидно, что число вершин в кавдой такой сети не превосходит
2h + 2. Поэтому число сортов ребер (т.е. пар вершин, которые
могут образовывать ребра) не превосходит 2 = CZh+2 + C2h+2 =
— 2 П. + 5rt *3 (первое слагаемое в средней части равенства
соответствует ребрам с различными концами, второе - ребрам с
совпадающими концами, т.е. петлям). Так как мы не различаем
изоморфные сети, то можно предполагать, что полюсами каждой
сети являются две первые вершины. Число S ^
рассматриваемых сетей поэтому не превохсодит числа сочетаний с
повторениями из *2 элементов до Н .т.е.
Пусть N( П.,^) - число неизоморфяых двухполюсных
контактных схем, которые имеют не более К ребер, не содержат
изолированных вершин, кроме, может быть, полюсов, и содержат
контакты лишь из множества [ Х1,..., Х^, х4,..., X }.
* Неравенство К! > ( "г*) легко доказывается иядукци-
ей по л. с использованием неравенства И + -р- V <е.
59

Лемма 7. К1/ ч , .4ic
Ы(п,к)^(сьпк)и.
Доказательство. Кавдая из рассматриваемых
схем может быть получена из сети с тем же числом ребер в
результате приписывания каздому_ребру одного из 2 п символов
Хх Ха , Х? Ха . Поэтому
NfokkZ Bn)\^ZBcrih)h4(c8rik)k
Тем самым лемма доказана.
Л е м м а 8. (К.Э. Шеннон [2] ). Для дюбого б > О
Lk(n)>^(i~e\
причем доля функций f ( Xd X^ ), для которых
тШША Д ДДЮ. ,Q. JP.QfiT.flM (Я .
Доказательство этой леммы, основанное на
использовании общего приема Риордана - Шеннона [15] ,
является неэффективным в том смысле, что не указываются явно
функции алгебры логики, допускавдие лишь сложную схемную
реализацию; устанавливается лишь то, что число "простых" функций
"мало".
Рассмотрим некоторую функцию k(ft) , и пусть о( (п.) -
доля функций Г (Xt ,..., ЭСп,)# Для которых
Поскольку каждая из этих функций может быть реализована
схемой сложности не более "К(Гь), причем разные функции
реализуются разными схемами, число этих функций не превосходит
числа схем сложности не более "к (К), т.е.
о((пJ2Гг4 N (п,к(п))
60

loyal (n)? 1оуЫ(п,кЫ)-^П-
Положим теперь 1^(rt) = — A ~С); и пусть W —*<хэ .
Тогда, используя лемму 7, имеем
1ф (п,к{п))-2\ ~(^ХпЩ))-гп=-аЩ-^).
Последнее выражение стремится к — оо ПрИ г\ -—. оо .
Поэтому о((п) —¦ 0 , и тем самым лемма доказана.
Замечание. Если использовать более точную оценку
уш S^ : SK ^ [С9 ^г^) (см. [*1б] ), то для
Z_, (h,) можно получить оценку (при достаточно больших ft )
Lk(.)>f() + B-e)^).
Из теоремы 7 и леммы 8 непосредственно следует
Теорема 8 [з].
* la

Гла ва Ш f _
Формулы в базисе ^ <ч> V, ] и
5Г -схемы
§ 13, Связь между формулами в
базисе i^iV, j и ^-схемами.
Простейшие оценки сложности
В этой главе будем рассматривать формулы в базисе
1\ , V, J. Сложность формулы S определим как число
символов переменных в ней; обозначим эту величину через /J(S) «
Например, формула
иглоет слсжнссть 8. В силу соотношений
ЧЛУе^Ча' Ч^Чг^Ч^Чг^ Ч = Ч
от произвольной формулы Ь можно перейти к формуле, выра-
:кающей ту же функцию, что и О , той же сложности, что и
S , но такой, что знаки отрицания встречаются в ней лишь
над символами переменных. Например, формуле (I) соответствует
.ормула
. .лечу е дальнейшем можно ограничиться рассмотрение:/, ^рмул
... гс спецкатььсгс ы:ла.
:г

Двухполюсвая контактная схема называется
параллельно-последовательной или, короче, JT -схемой, если она получена
из параллельно-последовательной сети (см. [97, с.171]).
Проводимость 3t -схемы нетрудно выразить в виде формулы, если
воспользоваться правилами параллельного и последовательного
соединения схем, которые приведены в § 7. Это пороадает (хорошо
известное) соответствие между Ж -схемами и формулами
специального вида (указанного выше), при котором контакту эс
соответствует буква Xе , параллельному соединению - операция
V , последовательному соединению - операция & , и
наоборот. Ясно, что такое соответствие сохраняет реализуемую
функцию и сложность (для формул - число символов переменных, для
Sl -схем - число контактов). Например, формуле B)
соответствует $Г-схема (рис. 27).
х5
Рис. 27
Определим функции LTl({) н L?:(n)\ L% (f) = rn^/^(f),
где минимум берется по всем Ж -схемам (формулам в базисе
[&.V, ~}). реализующим функцию f ; L%(ri) = maxL^(f),
где мавсшум берется по всем функция:/. С от аргументов
JLj , • • • , **~ r\ •
Нами уже получены оценки
(контактная схема, соответствующая совершенной д.н.ф. -
стр. 36 - является ЭС -схемой) и
63

Lx(n) ^2-гп
(схема, получающаяся из контактного дерева в результате
объединения некоторых выходов - сгр. Цо - и отбрасывания "лишних"
контактов, также является ЗС -схемой).
§ 14. Асимптотически наилучший
метод
Теорема 9 [17] .
Доказательство. I. Специальное
представление функций. Пусть Ъ = 2^,
р -натуральное; Z ^ Н, . Рассмотрим разбиение множества
всех наборов длины Z на попарно не пересекающиеся сферы
(лемма 4). Обозначим через ^- ( Х1 ,..., 0Сг )
характеристическую функцию i -й сферы (l^t^V
Пусть -Г ( dZt ,..., Ха) - произвольная функция.
Разобьем ее аргументы на три группы
< у ' * , > V у
г к п-к-г
Кавдая функция
б = Owk + i,---» О,
принимает значения, отличные от нуля, лишь на наборах вида
64

где
(б ,...,6' ^) - произвольный набор. Поэтому Г <g
может бить задана табл. 5.
Таблица 5
-^г+i -
0
6г+1
1
- • ЗС^ + к
. .0
... {
... \ ...
1
1
1
]
}
}
'«S
'/
Строки таблицы соответствуют наборам ( бг+1 ,.. м б^ + ^ ),
столбцы - наборам i -й сферы ( ? штук).
Разобьем строки табл. 5 на полосы А4 ,..., Ар » по
6 строк в полосе (последняя полоса может содержать меньшее
число б' строк). Очевидно, что
2*
Пусть
f),?.i
P«-r + 1
функция, совпадающая с
(I)
fi.'
на полосе
А{, и равная 0 вне ее. Столбцы матрицы, соответствующей
функции Г • -g^ , разбиваются на группы одинаковых мевду
собой столбцов. Пусть Т - произвольный набор дяины
(точнее, "высоты") 6 (или 4' , если i = р ); обозначим
через и i-ъ \ Ф группу столбцов, равных *€ в полосе
/Л{, (для некоторых (^6,1,^ ) группа D i^ i,?
оказаться пустой). Пусть Г;7 ; » - функция, сов-
65
может
падающая с -f: -> ; на столбцах из b, -г : ^ и
5-2084

пуст ая
группа
но равна
сортов
^ тоадествен-
имеет столбцы 2-х
равная 0 в остальных случаях (если П; ^ ; е*
J) °»ъ»^
, го соответствующая функция Г- -g • ;
на 0). Матрица для функции Г. _•'. V
а) столбцы из D * <g ^ ^ , равные Т в полосе A{
и состоящие из нулей вне А; ;
б) остальные столбцы, состоящие сплошь из нулей.
Поэтому фунщия -Г; -g i ^ может быть представлена в виде
конъюнкции двух функций, зависящих соответственно от Xt
г + i1
(рис. 28):
fy&iX
fe«,H*4,...>4,)
rC«
•А ? /
'•{
—п—!—'—1—п
И l til
' ! ! ! !
1_| L 1 1 1 1
B1
Рис* 20

1) функции Г . « . « , равной I на столбцах из
Dj^^i^ и равной 0 в остальных случаях;
2) функции f ^ ^ f B матрице которой все столбцы
равны Ч в полосе At и состоят из нулей вне А{,
В силу леммы 5
(О (з)
о
(дизъюнкция берется по множеству номеров Ь, столбцов из
Таким образом, функцию Г можно представить в виде
f(* *0-^(«, Ю ( V =&?•' • »'.
Р
" ( V V f * (х „ a„k) f ^ (ос,, ...;*,))).р)
Заметим еще, что поскольку группы D i^L *? пРа
фиксированных t,!?, i попарно не пересекаются, а число
столбцов в таблице 5 равно 2 , то
(s) ^ - (з)
Mf^H-
2. М е т о д синтеза. Рассмотрим представление
B) функции .f ( ос4 ,..., 0Са). Формула S для функции
Г будет строиться в соответствии с
fi?

|^4?r*;ta*,, ч^ь «i
Ф
S*&i?
^_
^r
^j
L
>j,2,t
sb*
4^
D)
r
Si
Будем последовательно строить « полформулы (в фигурных
скобках) и оценивать их сложность (некоторые подформулы
будут выбираться неэкономно; однако на сложность всей формулы
асимптотически это не окажет влияния)* , N
1) В качестве формулы Ь^ для фунвдии f^^G^+i»1"»
• • • у Х"ь + ic) берем совершенную дизъюнктивную
нормальную форму последней. Так как эта функция обращается в
единицу не более чем на 6 наборах значений своих
аргументов, то
w*
• С»)
2) Функция ? v 7, ь % есть Дизъюнга1ия некоторых
переменных или их отрицаний (см. с. 67 ). В силу C)
Z.L(S)tZ,iS)-z.
6S

s) L(S'. ^-n-k-z+LQ^n+piz+ikZ5).
e) ЦЗ^ТЦЗ\^гп'к'\п+Р{г+5к2%
7) В качестве формулы *-Р; Для функции Lp. (x^.-.CXL)
берем совершенную дизъюнктивную нормальную форму последней.
e>as)=f^(^K(sJ)>|V^-'(n^t5k24))).
Рис* 29 иллюстрирует строение SC -схемы для ? .
Таким образом, учитывая (I), имеем
Положим
-2 = 2 ^ , ^e[2^^ri]f6»[^ii-2/aj^ri]
(эти значения параметров выбраны ва основавдж соображений,
аналогичных приведенным на с. 22 ).
Тогда
5х-2084
69

и
Поэтому
Pic* 29
=f(K^))-^<-°^)).
Теорема дмиаам.
ТО

§15. Асимптотика функции
L%(n)
Пусть N«. (lTf 'k) - число формул в базисе |?,V, J ,
которые содержат не более К символов переменных» содержат
символы переменных лишь из множества \ зс1 ,..., Х^} и
таких, что знаки отрицания встречаются в них лишь над символами
переменных.
Лемма 9 рб],
Ngr(a»4ci1n)k.
Доказательство. Легко видеть, что кавдая из
рассматриваемых формул, содержащая l> I ^ К , символов
переменных, содержит I - { символов операций ? и
V , не более I, ~ 1 левых скобок и не более 1*1
правых скобок. Общее число символов в ней не превосходит 4 I.
Дописав к ней некоторое число раз символ Q 9 получим слово
длины 4 U в алфавите
[(, )Л^,а,х11...,хги5с1>..., 5са]^
содержащее не более \\ букв из алфавита.
Л "¦(_ Х1э ...,Х1г, Х1э..., SC^J.
Поэтому
N^EС>0 V*"*« ^ Е *1 < (С|| п?
(при каждом г места для букв из Л могут быть выбраны
не более чем С.^ способами; на эти места буквы из X
могут быть расставлены B П.) способами; на остальные
4ft - I мест буквы (,),<?, V, Q могут быть расставле-
71

ш !• белее чем 5 ~ способами).
1«ма доказана.
Замечание. Из последней леммы следует, что число
неизоморфвых параллельно-последовательных сетей с к
ребрами не превосходит Cfe (параллельно-последовательные
сети могут быть описаны формулами, содержащими лишь одну
букву из X - см. [к]).
Лемма 10 [l5j. Ддд ДТЙРГР 6 > 0
.р ( X, ,..., Ха ), ДМ ЯРТ.9РЮ
g, юртом la .
Доказательство. Достаточно показать» что при
2п
tog ri
Мж(п.к.(г0)
2«*
Из леммы 9 имеем
о.
Последнее выражение стремится к — оо дрм ^ —^ ^
Тем самым леша доказана.
72

Из теоремы 9 и леммы 10 непосредственно следует
Теорема 10 [17].
toy a
Замечание. Можно показать» что верхняя оценка
теоремы 9 достигается на SL -схемах глубины 3 (т.е. на
схемах, соответствующих формулам типа конъюнкций дизъюнктивных
нормальных форм или дизъюнкций конъюнктивных нормальных форм)
[18] . Более того» достаточно использовать для каждого П и
всех функций Г ( ОС4,...» ССа) одну % -сеть глубины
3 [19]. Для схем глубины 2 соответствующие оценки неверны.

Глава ГУ
Схемы из функциональных
элементов в произвольном
базисе
Рассмотрим теперь схемы из функциональных элементов в
произвольном полном конечном базисе Б (см* § I), веса
элементов предполагаются положительными. Для каждого элемента
t с числом входов ^(l.) ^ 2 рассмотрим величину
ЯЕ) л
х — и будем называть ее приведенным весом элемента
?(t)-l
ff • Основной результат этой главы -*
Теорема II [&]•
?де О - минимум приведенных весор элементов базиса D
Следствие, Бели в базисе D для кавдого
элемента L с числом входов Ъ ( t) ^ 2 выполнено условие
Р(Е)=«г(Е)-4 . «»
п
^¦00-4"
Метод синтеза, дакщий верхнюю оценку (асимптотически
наилучший метод), излагается в § 17; нижняя оценка доказывается
в § 19.
74

Для случая, когда сложность схемы определяется как число
ее элементов» из теоремы II непосредственно следует
асимптотическое равенство для соогветствущей функции Z-g (ft)*
Теорема II.
Б k-1 n
7
Ш ^ - 1ИВВ.ШМ№Яав ЧЮЮ КИИ». У WSHWW3. ММ»
(Напомним - см. определение схемы из функциональных элементов
- что у каждого элемента все его входы являются
"существенными").
§16. Обобщенное разложение
Для того чтобы в схеме основную часть составляли
элементы, имеющие минимальный приведенный вео# при синтезе
используется специальное представление функции, являющееся обобщением
обычного разложения функции по подмножеству переменных.
Введем одно обозначение. Пусть о1 ,..., 62а -
всевозможные различные наборы (из нулей и единиц) дайны Q ,
причем б^=( А ..... б^а ). 1? = I.....2*.
Соответствующую набору §L конъюнкцию iiV .. . ^а*а
будем сокращенно обозначать Ку (U|MM Уа)#
Лемма II (см. [8] ). ДурТЬ ЙИКШ Ffc^--., VJ
существенно зависит от всех ^воих N аргументов, примем
N >/ 2а . Тогда оущерши?,jams йшни ^Df#e'^a»w)'
{4$ 4 2* д и здлм ими N > 2d ) темгс йтаяот
¦**Wi. ••-.</*)• 2*< ? 4 N , что
FWv--'?a*wA^
f*« ' 75

Доказательство. Так как функция Г
существенно зависит от всех своих аргументов, то дяя каждого
h » { ds. П 4: 2а » найдутся такие константы С^х »
t? ?^1М. что
Покажем, что функции ЦЛ и X а , фигурирующие в
формулировке леммы, кояшо спределить следупцим образом:
Щ.*>) =
S<? ' если ? * $»
[иэф с если ^ - ? (*^2°,1^2а),
Б самом деле, для произвольного Т) имеем, с одной стороны,
и, с другой стороны,
2°
Лемма доказана.
Следствие. Произвольная функция
76

f ( 4i Vе» • z.i z*> ) M0JKeT 6ытъ пред"
ставлена в виде
•••^V-44(^^ CO
Замечание, Легко убедиться в том, что если
F ( lfx ^2a > =^tV .-• V Uta , то
С ^ = О, i ^ h,? 4 2 a, и функции tf? определя-
<>a
ются однозначно и даеют вид
В этом случае представление (I) превращается в обычное разло-
дение функции по аргументам 11 L ,•.., L±a . Таким
образом, представление (I) является прямым обобщением обыыного
разложения.
§ 17. Асимптотически наилучший
метод
I. Специальное представление
функций. Пусть Г (х4 Ха ) - произвольная
функция. Рассмотрим ее задание посредством таблицы I,
разрезанной на р полос (см. с. 26 ), D^ -^— + i
Функция -Г мокет быть представлена в виде
Р
где
fitfCxu^..MxOsfiC3,xu+lf...f хл).
77

Пусть ср - функция базиса, имеющая наименьший
приведенный вес. Обозначим число существенных аргументов функции С^
через d + i ; ясно, что d > О и Р(Ч>)=.ЯС' •
Доложим
и рассмотрим функцию
Очевидно, что функция Ч^ существенно зависит от всех
своих Zu + 1> 2 аргументов (в логике, знач-
ность которой более двух, этот факт, вообще говоря, неверен).
Пусть о^ ,..., C2n-1<-u - всевозможные различные
наборы длины Гъ - 'к - U «На основании леммы Н и
следствия из нее существуют функции
X
(*u+1 *,_0> 2"^««*М.
такие, что для любых возможных пар (i,o)
fi)g(*u+i,--.*j=^(H\(*u+I ***.fa (За-^-.^д
• • ч Ф2м-1с-и (^u+ii—i^a-k'fsg (^2*-*-u> X ^-"k+i ',M»3Cri))»
Введем обозначения
78

n-fc-u
^Jxu+1,...,xn.k) = ^(xu+1,...,Xn.k>6), 14^42 Д-0.1.
Тогда
^(^^.•••^^.^¦^^(^.••м^^изф^х^,..,^
2. Метод синтеза. Схема S ддя функции
Г строится на основе представления (I) и разложения B) и
состоит из 8 блоков (рис, 30):
1^1
&U+f %П-к хп-к+1 хп
ULJ LJJ U^
\ V4
\ I л I
I н I
Рис. 30
:. Блоки А4 . Af . А3 реализуют Qu (xv'...f Xu)f
79

^a-k-i/^u+i' •'•' Хп-к)' ^^хп.-к + 1» •••» хл)
соответственно-;
Л(А,)=0(ги),
Л(А>0B"-к-и),
(см. лемму I и теорему I).
2. Еюк и реализует всевозможные различные функции
f* б" ( ?,**'n-fc+{'",'^v) как Дизъюнкции (не более чел 6 )
конъюнкций из QLCCfl_k+jr..lXft) . Число этих функций не
превосходит р 26 • Поэтому
ZXB)=0(p4 26).
3. Ьпок С реализует все функции
Y^fcu+n-» *n_k) и TL^(xutil..., xn.k)
как дизъюнкции конъюнкций из U^^^-u v^u+i» •••» ^n-O*
Число функций HVtf равно 2 ; число функций
"Tl^ не превосходит и ( и - константа), поэтому
А(С) = 0Bг(п-к-и)).
4. Блок D реализует всевозможные различные функции
в соответствии с представлением
80

4^ (xu+i'—' ^n-k'fi.g Г^п-к+1'-' ^nl"
Очевидно, что
Z,(D)=0(P262^-U).
5, Елок Сл реализует все функции
f * 2 ( ^u+l »--4^cri) в соотвегствии с С2). При этом
каждая функция Ср реализуется подсхемой S ф »
образованной цепочкой из Z элементов для функции ^f (яс-
цо, что L(Sfo) = ^ Р(^) =4P^d ). Этот блок содержит
основную часть элементов; его сложность оценивается точно:
L(G) =ргс1р2м.
6. Елок Н реализует функцию -р ( 3Ct ,..., ЗГ^ )
в соотвегствии с (I). Очевидно, что
L(H)= 0(P2U).
Таким образом,
Z,(SKj3*dp2u + 0Bu) + 0B*-fc-u) + 0B1c) +
+ 0(рб24)+0Bг^"^) + 0(р26+п~к~и) + 0 (р 2>*).
Положим
6-2084
81

Тогда .
MS)<.p?A-0(^)).
Такш образом, доказана
Теорема 12 [в]. Ддд ддйою, ДМДОЮ, .KpflffMLQItt .03.-
где р - минимум приведенных весов элементов базцса Б
Из этой теоремы можно извлечь
Следствие. Для любого полного конечного базиса
Б
существует константа С ? такая, что для любого П
Для дальнейшие приложений нам понадобится одно обобщение
георемы 12. ^
Сопоставим каждому набору Ь = ( <Й? ,..., 6а ) длины
П число |^ l^zL^i 2. . Рассмотрим класс
вектор-функций, принимающих на первых S) наборах
произвольные значения и равных @,..., 0) на остальных. Точнее, пусть
П=] IoqJ [ и S ,m класс ( ft , П )-функций
р , удовлетворяющих условию | Г (^ ) | = 0 , если
Теорема 13 ?б]. Если последовательность пар
( ^ I . ггг^) удовлетворяет, лдавадм *
* При ЛГЦ ^ 2 условие I следует из 2.
82

2) tott mi _ о
Доказательство почти полностью повторяет доказательство
теоремы ?2. Отличие состоит только в следующем. Во-первых,
функции задаются "неполными" таблицами, соответствующими лухь
первым >)• наборам; число строк в них равно 1 ${/2П{~**- Г
и соответственно р^ = J Ч/^г^ L • Во-вторых,
несколько иначе выбираются параметры к , 6 , U : ix...
mi ^-2 , то
если ГП; > / , тс
4=[ni-kt-2%K-kt)].
В условиях теоремы 13 справедлива
Теорема 14 [б].
Верхняя оценка дается теоремой 13. Нижняя оценка будет
получена нлже, в § 19.
83

пусть LB(n.m)=L0(T2"tm)
{т.е. рассматриваются произвольные ( П , m )-функции).
Теорема 15 [б]. Бели последовательность пар
( П^ , ГГЦ ) удовлетворяет условиям
1) ГЦ — во,
2) loQFTU
г* -о.
го
§18, Оценка числа схем данной
сложности
В этом и следующем параграфах будут получены нижние
оценки для функции Z* g {к) « некоторого ее обобщения.
Приведем сначала некоторые оценки для числа графов.
Обозначим через К . (t) число разбиений натурального
числа t на С упорядоченных, неотрицательных слагаемых.
Как известно *,
М _ nl~i
Пусть Ut - число неизоморфных деревьев с К
ребрами.
Лемма 12.
Доказательство этой леммы при СХЪ*Ц приведено, например,
в [7, с. 90; 9, с. 154] .
* Каждому такому разбиению срответствует расстановка (с
повторениями ) v - 1 запятых в наборе из t единиц;
запятые можно ставить между единицами, до них и после них -
всего t + i мест.
84

Пусть S-K,fc ~ "гасло неизоморфных связных графов с 1ь
ребрами и # вершинами.
Лемма 13.
с ^Л^*{
Доказательство. В любом связном графе с и
вершинами можно выделить подграф, содержащий все вершины и
являющийся деревом. Поэтому любс/1 из рассматриваемых градов
можно получить следующим образом.
?) Выбирается дерево с 6 вершинами (и 6-1
ребрами) - б силу леммы 12 не более С^ возможностей.
2) "Оставшиеся" ребра ( И -6 +1 штук) "одними
концами" присоединяются к вершинам. Число N способов
присоединения равно числу сочетаний с повторениями из и
элементов по К-*б + 1 , т.е.
3) Каждый из "вторых концов" присоединяется к любой
вершине; число способов равно б*.
Окончательно имеем
Пусть ^ 1я fe k " число неизоморфных графов, имеющих
\i ребер, Ь вершин и к связных компонент.
Лемма 14 (см. [б]).
ЬНД* 4 Cis Ь
Доказательство. Обозначим через Jt
множество упорядоченных систем из f< пар чисел ((Ь^оД
• • • > (К k,Ьк)), Удовлетворяющих условиям
h1th2+,„ + hk = 'h . U{>/ О ; (I)
fl-fe+1 ^ О (условие того, чтобы существовал
связный граф с ini ребрами и Ь^ вершинами).
6х-2084
85

Очевидно, что
S. ,k^L П S, . 4 о)
К'Ь'к A i=i *Н'6* fc
4. (число элементов в J ь ) ( ГГШЭС I I О л о ).
Легко видеть, что число элементов в множестве Jj, не
превосходит . Далее, в силу леммы 13 и {1 ),
к К
(г)
< П c14V6i 6v*i+1 = c14Kt66K+k.
Окончательно, используя C), имеем
Ska«4 Rk(h) RKF)c,:"V-6*k=
<DCW) Ь
Лемма доказана.
Следствие, Число Ь^ с ^ неизоморфных
графов, имеющих \\ ребер, Ь вершин и не более к
связных компонент, не превосходит
В самом деле,
Ь6

Su l=2- S^^4 2_ cis 6 ^
<c16c15 fe ^ct7 6
Пусть 7lR( П,, m, Z^) - множество неприводимых
( \n 9 m. )-схем из функциональных элементов в базисе D
слояшости не более L , входам которых приписаны
переменные ОС! ,..., Хп . Пусть Ng(n,m,Z/)-число
неизоморфных схем из У1 С П, ГП, L,).
Лемма 15 (см. [б] ).
N6(a,m,LL(c6(A^))^ + "t2m,
иг р - чтт пиши им» тот юн» Б .
Доказательство. Пусть элементы базиса суть
t_ 1 ,..., L х и пусть они имеют Z j ,..., Z* входов
и веса У л ,..., STa соответственно. Пусть Z = miri P;
и 2 = max 2 1.
Из определения числа о следует, что если *2v > 2, то
р. ^ '
D^ *- . Таким образом, при всех '2; (в том числе и
При 1: = О, I)
•гг 1 4 т-Pj. (i)
Поставим в соответствие каждой из рассматриваемых схем
ориентированный граф, вершинам и ребрам которого приписаны не-
87

которые символы, следующим образом.
?. Входы схемы ( П штук) сохраняются (в виде вершин);
по-прежнему приписаны символы переменных
2. Каждый элемент
t
заменяется вершиной ос и
*2* инцидентными ей и направленными к ней ребрами,
занумерованными числами I,..., *2* . Начало ребра с номером
? ( ? = I,..., 1j ) присоединяется к вершине,
соответствующей тому входному полюсу или элементу, к которому (к
выходу которого) был присоединен ? -й вход элемента Q •
Вершине оС приписывается символ элемента L ; .
3. Выходы схемы (точнее, вершины, происшедшие из
элементов, выходы которых были выходами схемы, или из входов,
одновременно являющихся выходами) отмечаются символом х ;
нумерация выходов сохраняется.
Например, на рис. 31,6 изображен граф, соответствующий
схеме рис. 31,а.
6)
Рис. 31

Очевидно, что по графу исходная схема восстанавливается
однозначно (с точностью до изоморфизма).
Пусть п, = ( Kj, гг2 ,..., rt^ ) - произвольный
набор из целых неотрицательных чисел и пусть Л ? -
множество схем из бЬ^ (/Я,ЛГ1,А) , имеющих Ylj элементов
L. ; ( 1 =!,•.., 5 ); пусть N ? - число
неизоморфных схем из ft Л . Очевидно, что
N6(n,mfZ.)=ZN B)
Ji h
где сумма берется по всем наборам Н , удовлетворяющим
условию
)¦' ' '
Эти наборы будем называть допустимым^. Обозначим число
допустимых наборов через 13 (/J) . Из B) имеем
NB(n.m,Z.)^D(Z)TOxNc . u>
К г1
Оценим отдельно JJ (/л) и N л .
Т. Из определения I и из C) имеем
ы * " ?
Из E) получаем
Поэтому
F)
(здесь использовалось неравенство 1 + X ^ ? ).
П. Введем обозначения
K=ZkJt К'=Г^Ц, h"-K'-K-t(Vi)hr
89

з (I), C), E) следует, что
h< -f L,
h'*&piY$L-
h'-h.v<(-f-?K
Граф, соответствуют!!! схеме из fl Г
G)
(8)
(9)
, обладает следу-
щими свойствами.
A) Этот граф имеет Ух + К вершин и К ребер.
Число его связных компонент не превосходиг П + JTI (в
силу неприводимости исходной схемы кавдал связная компонента
графа либо содержит вершину, отмеченную символом * - их не
более ГП, либо представляет собой изолированную вершину,
которой приписан символ Х± - их не более П ).
B) Некоторым П, вершинам приписаны символы
переменных СС^ , •••» ЗС|г*
C) Некоторые вершины отмечены символом я и им
приписаны числа I, ..., ГП , причем каждое число приписано ровно
одной отмеченной вершине, но некоторым из этих вершин может
быть приписано несколько (не менее одного) чисел.
D) Каадой из п вершин, которым не приписаны
символы переменных, приписан один из символов Е1 ,..., Ел .
E) Каадому ребру приписано направление и одно из чисел
I,..., о •
Рассмотрим теперь множество Л г ориентированных
графов, обладающих свойствами A)-E). Обозначим число
(неизоморфных) графов из этого множества через к? . Среди этих
графов встречаются все графы, соответствующие схемам из Tlfi .
Поэтому
Nfi i RK~. да,
Оценим сверху число К ? . Каящый граф из #1 <~
может быть построен следующим образом.
I. Выбирается неориентированный граф с П + К
вершинами, К1 ребрами, состоящий не более чем из П. + m
90

связных компонент. В силу следствия из леммы 14 это можно
сделать не более, чем
^ n + h+h ч-n + m, / . >h-(t\+\f)+r\+n\
ct7 (n + h)
-C|^-2^^(ri + 4i)K+l
способами.
2. Вершинам приписываются П + m символов Хг,
?2 »•••> ОС ^, I, 2t...f m (каждый символ приписывается
один раз; одной вершине может быть приписано несколько
символов) - ( |а + K)n,'*"rri возможностей.
3. Вершины, которым приписано хотя бы одно из чисел
I,..., га , отмечаются символом х - однозначно.
4. Каждой из вершин, которым не приписаны символы
Хмм,, Ха » приписывается один из символов
Е^ ,..*, С^ - не более 6 возможностей.
5. Все ребра ориентируются - 2 возможностей.
6. Каадому ребру приписывается одно из чисел
Таким образом,
К'
I»..., Z - Z возможностей.
Зтсюда и из G)-(9) следует, что для всякого допус.им.го пабо-
ра 1г\
nK^i'>)L""nin+$a>1"'"
ь\

Отсюда и из D), F), A0) имеем
NB(ri,,n,Zj<(cJZ.+rO)±A + n + 2'n.
Тем самым лемма доказана.
§19. Нижние оценки для
функции L ( J п)
Ifyc.Tb J = ( J i f J 2 »•••» t/i ,...)-
последовательность классов вектор-функций, такая, что j^
состоит из ( Пх , ГП.± )-функций, зависящих от аргументов
OCi . ••¦» ЭС^ • Пусть М -\Ji) - число вектор-функ-
f i
н(/4)-цмш JU>^gv
Теорема 16 [б]. Пусть
^^^ __ Q (I)
Го^Ж
j(/4)
A6(/J>,pJ(/i),
где р - минцмум приведенных весов элементов _базиса D ,
причем для любого ? > О доля вектор-4улкдий г из
J^ , Для_котсщшс L б ( F) ^ (l"~S)jO J (fj), схремит.ся
к С при t —* оо
Доказательство основано на использовании
того же общего приема Риордана - Шеннона, что и в
доказательстве леммы 8 (§ 12).
Для доказательства теоремы достаточно рассмотреть
реализацию вектор-функций из ^ схемами из З^бО^ГП^А) *
установить, что при любом ? > 0 и Ь —- <х> вели-
9Z

чина
удовлетворяет соотношению
Ns(nt,mt,Z.(i))
MU)
Из (I) следует, что П *" °° .
(здесь и нике мы опускаем аргументы у функций М , П, J, Z,,
а также индексы у m и П ).
Далее (учитывая лемму 15, B) и (I) имеем
ЫБ (n,m,L)
М
^ (A-е) J+п+2m) (>Ц СБ + %((l-e)jo J*n)b Н =
/too
' М
=(l-e+o@)J(^J+o(i))-H4i-e+o(i))^(%H+o(^H))-
-Нв-еН + о(Н).
Последнее выражение стремится к — оо при {, —*. ©о#
Тем самым теорема доказана.
Применения тесреглы 16.
Доказательство я и к ь з &, о и с н л л
теоремы II.
В этом случае Jп -класс всех оу^ ,-*ли sjt»'_ * .ч..
от П. аргументов. •,:: стал ГП-i , Гм( J^-Z , N(/^ = 2

ПосГо^у на основании теоремы 16 имеем
2п
LBM >^p
П
Доказательство нижней оценки
теоремы 3.
Ота теорема - частный случай теоремы 11' . Базис состоит
лз элементов, имеющих один или дёа вхоца; веса всех элементов
равны 1. Поэтому р = f.
Доказательство нижней оценки
теоремы 14.
л/.еюг место равенства Гч(^):=2г г JC/-)^ ——
Hi mi>
Поскольку '°9 *{, ^ ^i » Т0
ru+mj ^ ( I09 ^ + пггу) ( log flj + lo? n-ij) _
— — -+- •+. 2 + I
Последняя сумма стреми гс:: к нулю в силу усдсвил теоремы 13
(третье слагаемое гл?.ьссрлруется вторыь,). Поэтому, на основании
теоремы 16,
T,,.iEe::(ribL.e выше выкладки показывает, что условия теоре-
i этгв*'1а.'епгны условию (I) теоре*:ь 16.
rJ4

§ 20. Некоторые дальнейшие
результаты о схемах
функциональных элементов
и формулах в произвольном
базисе
В этом параграфе приводятся без дсказательс~ва некоторые
результаты.
I. Формулы в произвольном о а з п-
с е. Обычно рассматриваются два определения сложности формул:
а) Сложность формулы О - число
символов переменных в S . Это определение соответствует
принятому выше (§ 13).
б) Каждой базисной функции цр (или, проще, символу
Lf ) сопоставляется положительное число Z^*(Lp) - вес и
(подобно тому, как в случае схем из функциональных элементов)
сложность Z- v S) формулы Ь определяется как сумма
весов всех символов функций в Ь
^ На основе этих двух определений сложности формул
естественным образом вводятся функции /-Б({),L*c(f)»^-«g(^), ^g
Сосуществует следующая связь между этими двумя
определениями сложности. Если базис Б не содержит функций от 0 и ?
переменных и вес любой базисной пункции, зависящей от t
переменных, равен i - 1 , то L. (S) ^L, ( S) + 1 ;
поэтому и для любой функции Г в этом случае
Для функций Z^g(ri)- и /Lr6(rt) справедливы
следующие утверждения.
Т е -» о с» м а 17. Для любого конечного базиса Б
9S

Теорема 18 [17]. Для любого конечного базиса Б
LB Ы~ р
п
loyn '
где р - мшщмум прит-^д^гщ весов базисных Функций.
Теорему 17 легко вывести из теоремы 18, но не наоборот.
2. Схемы из функциональных
элементов. Можно рассматривать схемы из функциональных
элементов в базисе Б (с заданными весами элементов), в которых
выход любого базисного элемента Е присоединен не более
чем к г ( Е ) входам других элементов. Это ограничение
содержательно объясняется тем, что при воздействии на кавдый
вход элемента расходуется определенная энергия, и
ограниченная мощность каждого элемента не позволяет ему воздействовать
на сколь угодно большее число входов других элементов.
Базис Б, в котором элементам д Е сопоставлены числа
j ( Е ), будем обозначать через Б Г Теперь обычным образом
можно ввести функции ^*g ( f) и ^§ (п) • й*еет место
следующее утвервдение.
л
Теорема 19 [20]. Если в Б имеется элемент Е
у. ¦ур.ур.рргр *г(Е)^4и t(E)^ 2 . з&
^в (гх) ~ Cg If.
где С ? - некоторая положительная констадта,.
Замечание. Константа С л определяется
следующим образом.
Пусть Р • = min. Р ( Е),
W 2(E)»t,j(E)>j
R(^}1^j2>^.^-bvHt^2-/2)^ Qfe.b^^CK-^rp-^r1^
г
Тогда
96

Сл = m i п.
В
A
Очевидно, что для любого базиса Б
Однако, если для того элемента Е , приведенный вес
которого равен р , выполнено условие t(E)><j(E) » го
С* = О.
Б F
В частности, так будет, если для любого элемента U
выполнено условие j ( Е ) ^ *? ( Е ) С2°]•
Заметим еще, что если для кавдого элемента t
выполнено условие i ( Е) ~ 1 .^0 для кавдой функции Г
W-^(f).
и поэтому в силу теоремы 18
2а
L+M - р
Щп
§21* Схемы из функциональных
элементов с задержками
Рассмотрим скачала схемы из функциональных алементов
специального вида в базисе [ <? , V, j.
Цепь элемента L (см. с. i3 ), некоторые вход
которого присоединен к входу схемы, будем называть главной.
Неприводимую схему D будем называть однородной, если все ее
7-2084
97

главные цепи имеют одну и ту же длину. Это (общее для всех
главных цепей) число будем называть глубиной схемы и
обозначать символом Т ( S).
Содержательный смысл этого понятия состоит в следующем:
предполагается, что каждый элемент имеет задержку, равную I;
в этом случае однородная схема обладает тем свойством, что
информация от входов схемы к входам каадого ее элемента приходит
одновременно, на выход схемы информация поступает с задержкой,
равной глубине.
Определим теперь функции:
| (г) - минимальная глубина однородной схемы, реализующей
f ;
Т * (гъ) = max ПГ (f) » гДе максимум берется по всем
функциям Г от аргументов X t ,..., X п ;
La (f)- минимальное число элементов в однородной схеме,
реализующей Г ;
lS(n) = maac Z** ( f) » гДе максимум берется по всем
функциям Г от аргументов хг »•••# Ха .
Очевидно, что для любой функции Г
L4f)>L(f),
а поэтому и
L'(n)>,L(n). ш
Асимптотически наилучший метод синтеза схем из
функциональных элементов с задержками получается в результате
небольшой переделки метода из § 6. Следует лишь выбирать подсхемы с
асимптотически минимальной глубиной и "согласовывать" глубину
подсхем, присоединяемых к входам одной подсхемы. Ниже
приводится подробное описание такой переделки.
Установим сначала некоторые вспомогательные факты.
Лемма 16. Для любого \п существует однородная
схема $п , реэддэУВДая функцию 1^ .,, V 0СП , и такая.
D ACSJ4 п + ]Цп[;
98

2) T(SJ =] b<jn,[.
Аналогичное утверащение справедливо для Функции зс?#..<? Хг
Доказательство. Каждое число П
заключено мевду соседними степенями двойки: 2 < М ^ 2 .
Доказательство леммы может быть проведено индукцией по </
Для ( =0 и I = I имеем соответственно П = I, П = 2.
Схемы для этих случаев с выполнением условий I) и 2)
изображены на рис. 32.
х1
о
Рис. 32
Индуктивный переход. Пусть
г*'1<П4 21п П'= ]~[. Тогда
Схема b n состоит из П, элементов, объединящих входы
попарно (в случае нечетного М у последнего элемента
входы отождествлены) и схемы о ^ , объединяющей выходы этих
элементов (рис. 33). Используя индуктивное предложение, имеем
T(SJ = l+T(SjH+]eo^'[ = ]Xo?n[.
99

Viae. 33
«i
Следствие, l-ля люсчл конъюнкции Х?
существует однородаая схема Р п , реализующая
. X
• *п
и такая, что
«rv
П
2) t(s;)=]/o9m[m.
Схема для ЗС/. • • ЭС**' состоит из одного яруса
элементов, реализующих X . v (X реализуется одним инвертором,
X - одним конъюнктором с отовдествленными входами) и схемы
для конъюнкции, о которой говорится в лемме 16. На рис. 34
приведен пример схемы для Х1 Хг Х3 .
Л е м м а 17. Ддя. любой однородной схемы S с рдшзм
выходом
100

Рис. 34
Доказательство. Разобьем все элементы схемы
5 на ярусы #711э..., ?TtT(Sy 371^ - это шюиестзо всех
элементов Е , цепи которых (все цепи - в силу однородности
схемы) имеют длину i . Цусть ГП^ - число элементов в
371^ • Из условия леммы следует, что П\х = 1. Далее, так как
кавдый элемент имеет ке более двух входов, то
Поэтому
т. . ^ 2 т.
i+i г
т. 4 2
i-i
T(S)
T(S)
i-i
,T(S)
Z,(S)=X m^X 2w=2l^;-i <2
,T(S)
1=1
t=l
101

Xi Xn-k
У - У.
Xn-k+1
X
5
z
г I
¦
2?
F
Рис. 35

Лемма 18.
Т*Ы ъ п.
Доказательство. Пусть Г - функция, на
которой достигается /_, (п,) f и S - схема, на которой
достигается Г (f) . Тогда
r(*y»T4f) = T(s), B)
Из B) и C) в силу леммы 17 имеем
T*(n) > lo<jL*(n),
откуда, учитывая (I) и теорему 3, получаем доказываемое
асимптотическое неравенство*
Теорема 20 (см. [21] ). f) L (n)~ — ;
2) Т*(гО-П;
3) Щ nMQVQ С > 0 Д дя да<?9Й ФРУЦад
| ( DCt ,..., Ха) от достаточно большого числа
переменны^ существует реализующая ее однородная схема S тщсая.»
что п
A(SL(l + e)t ,
T(S) 4 (i+e) п.
Доказательство. Нижние оценки дяя
соотношений I) и 2) следуют из (I), теоремы 3 и леммы lb. Верхние
оценки в I) и 2) следуют из 3). Укажем теперь способ
построения схемы В , удовлетворяющей условно 3).
Схема S (рис.35) получается в результате некоторой
переделки схемы, описанной в § 6. Здесь используется то же
разложение произвольной функции Г ( эс^,..., эсп); отличие
состоит в том, что блоки А , В , С , 2D , G » F
4 103

долены быть одкородными схемами, а также должна Оыть
"согласованы" глубины блока А и "цепочки блоков" В » С t
О . Значения параметров "к и 6 б^утся те лее, что и
в § 6:
^-[з%г1] ? б=[п-5^09м].
Тогда
Р-
2к 2к
а
1. Блок А реализует Q^^ @С1Э...Э а а„ к); каждая
конъюнкция реализуется схемой S'rt^k ч..Г:Дстъ/.е ;:з
леммы 16);
2. Елок D реализует аналогичны;., ос.азо:/.
Z.(BL2kBkt]b^t)'!0(n3to9rx);
Т(В) = ]Ц1<[м.
3. Глск L» ревизует все различные {уькции
fiC^.'-'A^i^a-k+it--^)-^^^ не равная С, ,еал;;зует.
ся одной ехшой для дизъюнкции длины 6 (леша 16)
(некоторые входы в случае необходимости сгоадесгвляягсО; функция
О реализуется одной схемой для конъюнкции длины 5 ,
входы которой присоединяются к выходам схаш В :ак, итсбы
использовались по крайней мере две различных конъюнкции:
Л(СLРг6(НЦ4) = 0(-^):
Т(С)= ]Ь^[.

4. Елок D реализует все функции
Р
Z.(D)<2~V]<°9p[bf.
Т С D) - ] to, P[.
5. Суммарная глубина схем Q , С . D равна
]Ц4<[+ ] /Цб[ + ]Цр[+1~зЦ п,
т.е., во-первых, она имеет порядок ^0A W и, во-вторых, она
больше, чем глубина схемы Д • Для согласования глубин этих
схем присоединим к кавдому выходу схемы А цепочку из конъ-
юнкторов с отовдествленными входами соответствующей длины
(порядка ?qQ 1Я ). Для полученной схемы Z имеем
ACZ)-o(-f).
T(Z)-T(B>T(C)+T(D)-T(A).
6. Елок G осуществляет умножение
(xf\..Dc^;K)f(^ .U4k+i ^);
Z.(G)«z*-fc-0(-?).
T(G)=l.
7. Елок г реализует функцию -f ( Х1>#.., Х^ )
как дизъюнкцию функций, реализованных блоком G ;
L(FH2~k=0(-^).
T(F)=rx-k.
Таким образом, для всей схемы S имеем
8-2084
105

T(S>T(B)*T(C)*T(D)+T(G)tT(F)~T(F)~n.
Теорема доказана.
Заметим еще, что в схеме Р "почти вся сложность"
сосредоточена в блоке 2 , а "почти вся глубина" - в
блоке р .
Возможна более общая постановка задачи (в случае схем в
произвольном базисе). Каздому функциональному элементу
сопоставлен, как обычно, положительный вес Р( Е) и
некоторое положительное число i (Е) - задержка элемента L
Для каадого элемента и с числом входов ^(Е.) >г 2 рас-
смотрим величину- тр% и назовем ее приведенной задержкой
элемента и .
Задержкой цепи схемы Ь будем называть сумму
задержек ее элементов (таким образом, в частном случае, когда все
элементы базиса имеют задержку, равную I, задержка цепи равна
ее длине). Неприводимую схему S » все главные цепи
которой имеют одинаковые задержки, по-прежнему будем называть
однородной. Это (общее для всех главных цепей) число будем
называть задержкой схемы S и обозначать символом Т (S) .
В случае полного базиса Б (т.е., если кавдая функция
может быть реализована однородной схемой /*27 ) вводятся функции
ТБ* ({О, ТБ* (П) и L Б (f), Z- Б ( П,) , аналогичные
определенным выше функциям Т* ( f) , I ( М) , L* (-[*) , L. ( П,).
Если задержки всех элементов базиса соизмеримы, то
справедливо следующее утвервдение, которое приводится здесь без
доказательства.
* 2п
Теорема 21 [21]. l) Z^ ( la) ^/> — ,
где р - минимум приведенных весов элементов базиса.
2) т; (п)***,
где *С - минимум приведенных задержек элементов базиса.
106

3) Для любого 6 > 0 и для любой Функции
Г ( X, ,..., ОСп) от достаточно большого числа переменных
существует реализующая ее. однородная схема S такая^что
L(S) 4 (l-C)pf,
T(S) 4 (i-e)Tia-
Теорема показывает, что асимптотически минимальная
сложность и асимптотически минимальная задержка могут быть
обеспечены в одной схеме, хотя fi и X достигаются, вообще
говоря, на разных элементах. Это возможно, так как "почти вся
сложность" и "почти вся задержка" сосредоточены в разных
частях схемы (ср. с замечанием к теореме 20).
В случае несоизмеримых задержек ситуация несколько
сложнее [21].

Глава X
Схемы для функций из
специальных классов
§ 22. Некоторые специальные
вектор-функции
В этом параграфе описываются некоторые вспомогательные
вектор-функции, допускающие существенно более простую
реализацию, чем это возможно в общем случае, и использующиеся при
построении схем для функций (и вект'ор-функций) из специальных
классов. Для этих вспомогательных вектор-функций будут
приведены здесь простейшие оценки.
I. Вектор-функция сложения Z.^ .
Эта ( 2 п, п + 1 .)-функция по цифрам двух П -разрядных
чисел определяет \п + i цифру их суммы:
z^ca.js)-? , ^ irl-iai + iji.
Лемма 19.
где С Б2 ~ константа.
Это неравенство вытекает из "школьного" алгоритма
сложения.
2. Вектор-функция вычитанияД^,
Эта ( 2 rt, ГЬ + 4 )-функция по цифрам двух ft -разрядных
108

чисел определяет знак их разности и П, цифр этой разности,,
если разность неотрицательна:
\&pHl$)> где
fd-o, |ГНан;-|,ваи|а|>ив|;
0 = 1, Jf - произвольный набор,
если | <3 | < | р | .
Лемма 20.
^Б(ХLСБд1ч,
где с - - константу.
Б А
3. Функция сравнения ОЗа . Эта
функция сравнивает два h, - разрядных числа:
, ч Го, если |5| >|?|,
* J | I. если |5|< IjSl.
Таким образом, СО п представляет собой старший разряд
вектор-функции вычитания А ^ . Поэтому справедлива
Лемма 21.
L Б (CJJ < СБС0 П,,
где СС11 -masisaia-
4. Вектор-функция подсчета
числа единиц в наборе 21 ^ • . Эта
(h., J'tOo(h. + l)L) - Функция по произвольному набору
с* = ( <^4 ,..., о(а) определяет число единиц в нем:
гг
1_\&У% где | jB)= Л 0СЛ
1=1
(сумма - не по модулю 2, а обычная!).
8х-2084
109

Лемма 22 [6 J.
?ДЗ
5Z{
- константа,.
Доказательство. Рассмотрим сначала случай
W = 2 . Процесс вычисления вектор-функции Z. п,
состоит из нескольких этапов. Сначала разобьем разряды входного
набора на пары (с* 4 , <^г ), ( °^ » °*4 >».... ^zt-v^Z** * "
всего 2
г-i
пар. Сложим одноразрядные числа в каждой
паре B4"x сложении). Это можно сделать (лемма 19) с по-
мощью схемы сложности не более 2 CgE* 1 . Получится
штук 2-разрядных чисел. Разобьем теперь эти числа
>*-!
на пары - 2
•г-г
пар. Сложим двухразрядные числа в каадой
паре B* сложений), и т.д. На i -м шаге надо будет
произвести 2 г~ъ сложенней i -разрядных чисел (со слож-
ностью не более 2 ^sz ь ); в результате получится 2
штук ( L + I) - разрядных чисел. Наконец, после ? -го
шага имеем окончательный результат - одно ( Z + 1)-разрядное
число. Пример такого вычисления показан в табл. 6 (младшие
разряды расположены слева). Таким образом,
4^4^^/I^C. 2*1 jl-Zc^f.
Таблица 6
0
1
10
1
I
01
но
0
I
10
оно
I
I
01
но
0
00110
0
00
I
I
01
010
I
I
01
I
l\
Oil
001
оно
но

Рассмотрим теперь общий случай. Пусть 2 < 14 2 .
Схема для 2. п получается из схемы для ^-2г в
результате присоединения 2 - п, входов последней к выходу
блока, реализующего константу 0 (сложность этого блока равна
некоторой константе Сго ). Поэтому
Лемма полностью доказана,
§23. Симметрические функции
Функция Г ( Dc1 ,..., ОС п ) называется симметрцче-
рко^ если она не изменяется при любой перестановке
аргументов.
Из определения симметрической функции следует, что она
принимает одно и то же значение на всех наборах с
фиксированным числом единиц. Следовательно, симметрическая функция
f ( Xi Э^п) полностью определяется
последовательностью 5с = («Я о $ ^i $•••> ^rt), где 3C<i - значение^
функции ^ на (любом) наборе, содержащем Ь единиц и .
П - i нулей. Поэтому число симметрических функций от п.
аргументов равно 2
Обозначим через J* n класс всех симметрических
функций
f
Т е
( ^Ci , ••
о р е м а
• » ^п,)*
22 [б].
^ Б ^ * п) <~s
п
Доказательство. Нижняя оценка тривиальна,
ибо число входов ( П , I)-схемы равно h/ и (при ГЪ > '2)
в случае симметрических функций, отличных от констант, к
каждому из входов схемы присоединен вход по крайней мере одного
элемента.
Hi

Верхняя оце
ков (рис. 36).
н к а. Схема состоит из двух бло-
оХ
Рис. 36
(следствие из теоремы 12),
Теорема доказана.
Елок А ,-еализует
вектор-функцию Х? .Он имеет п,
входов и ] loy ( Г1 + 1)[
выходов. Его сложность не
превосходит Сб2:* Ги (лемма 22).
Елок В по двоичной
записи числа Ь единиц во
входном наборе (всей схемы)
выдает 5С{, . Этот блок реализует
некоторую функцию от ] 1Щ (ft, + i) i
аргументов. Поэтому он может
быть построен со сложностью не
более 2С1 л П*{ = О(И)
Б Ь}(п+1) '
Эта теорема показывает, что в классе схем из
функциональных элемеятов симметрические функции реализуются с линейной
(относительно числа Переменных) сложностью.
Пусть § * - кяасс всех симметрических ( П f ГГ1 )-
функций (т.е. систем из ГП симметрических функций от П
аргументов). Пользуясь теоремами 13 и 16 можно доказать
следующее утверадение.
Теорема 23 [б]. Вслц П. —- <?о,
гги
loq ГТК ^ q
S3.
п.,-
ш

§24, Вычисление значений
функции на последовательных
наборах
Расположш наборы из нулей и единиц длины rt в
порядке возрастания их "арифметических" значений (младшие разряды
расположены слева):
(О, О, О,..., О), (I, 0, 0,..., 0), (О, I, 0,..,, 0),...,
(I, It I,..., I). (I)
Заметим, что наборы, у которых некоторые старшие компоненты
^+1 6 п. фиксированы, расположены в списке (?)
подряд •
Рассмотрим теперь следующую задачу. Пусть J* ( ЭС1
ЭС п) - произвольная функция алгебры логики и пусть р -
некоторое натуральное число. Требуется построить схему с П,
входами и р выходами, которая до любому набору
Ъ =F1>...t^a) вычисляет значение функции Г на
наборе ?" и еще на р -1 наборах, следующих за Ъ
(в смысле указанной нумерации; при этом будем считать, что за
набором (I, I,..., I) следует набор @, 0 0)). Пусть
La (n) - минимальное число такое, что для любой функции
от П. аргументов можно построить схему с указанными
свойствами сложности не более L, Б ( П).
Теорема 24 [б].
Р 2п
L6(n)^ р —
Доказательство. Очевидно, что
р .
L- (и) ) Ьс (я) • Отсюда, учитывая теорему II,
получаем
¦LB(n)>,p~.
Установим теперь верхнюю оценку. Пусть Г ( 3Ct ,...,
Хп) - произвольная функция алгебры логики от П
аргументов. Пусть fc - параметр, удовлетворящий условиям:
4^к^П. и n- к-*оо (п-*с*>). Для каждого
ИЗ

набора 6 в (р-?+0..., ^к) образуй последовательность
5Tgi из нулей и единиц длины 2^ + р - I следующим
образом: выпишем "в естественном порядке" значения функции Г на
выборах. @,0, .1.,0, ^*+1 6^ ), A,0 0, 61с+1 ,
...» 6rv )» •••» (!• !••...It 6^+ ? ,..., <6rv ^ и еще на
p- I наборах, следующих за набором (!,,,,,!, 6к+1 ,...,
С п.). Последовательность §t^\ обладает тем свойством,
что для любого набора 6 = Ft 6k, 6^+j 6а)
(оканчивающегося поднабором % = ( 6 ^+i ,.... 6Л ))
значение функции Г на наборе ^ и на р - I наборах,
следующих за d , содержится в ЭС^ -ер его разрядах,
расположенных подряд (рис. 37). Место этого куска длины
однозначно определяется набором ( 6t ,..., йк ).
^аг^
f(<si9..j5n-h9O9...9090)
f(el9...96n-k90,...9p9i)
f(<9i,...,6n-b>Gn-k+l>~><*n)
f(crf9...96n-k,1,"fW)
Рис. 37
Искомая схема S состоит из двух блоков А и D
(рис. 38). <k ~ ~
I. Елок А имеет П -1< входов и 2 + р - I
114

Рис. 38
выходов. Он по набору 8'= (й-к+i, • ••,^п.) выдает последо-
Ьвательность St^i и реализует 2 + р - I функций от
П - *к аргументов. На основании теоремы II блок может
быть построен так, что
Z.(AHj3B**p-0-7^.
2. Блок D по последовательности 3cgi и набору
( ё< ,..., 6^ ) выделяет в %^i p разрядов,
являющихся значениями функции Г на наборе Ъ = F
1 »• • •»
I наборах, следующих за <$.
^н ••••• йа ) и на
Этот блок реализует р функций от 2 + р - I + k
аргументов. На основании следствия теоремы 12 блок В
жет быть построен гак, что
^(вкрс;4—— = о(гг)
'к .
мо-
2^+р-4 + +с
115

(напомним, что р - константа). Фактически для реализации
этой системы функций требуется гораздо меньшая сложность, но
нам достаточно этой очень грубой оценки.
Таким образом,
Положим
к- ЦЧп]
Тогда
п-к^п, п-'к-оо, 2*ч-р-4~2* 22 = 0 {-).
Следовательно,
Z.(SKp^.
Теорема доказана.
§25. Ненулевые инвариантные
классы Яблонского
Класс <-ft функций алгебры логики будем называть
инвариантным [4,5], если он замкнут относительно следущих
операций:
1) подстановка констант на места каких угодно
переменных;
2) переименование переменных (без отовдествления);
3) добавление или изъятие несущественных переменных х.
Обозначим через ^ множество функций из
зависящих от М переменных Х1 ,..., ЭС^, а через Р^Гп
- число Э1их функций.
х Ддя дальнейшего здесь существенна лишь первая
операция.
116

Лемма 23 Гб]. Пррдеддвдтш&ОА.ть ЧЦред у р (п)
стремится, не возрастая, к пределу, причем. диаоййРт.н.»-
дус.ургр. шгадаадтшр. ладвд,оа ^
1< torn / рлЛО 4 2.
« torn / р (П)
Доказательство. Пусть f (х(,...,ЗСа,Ха+1)
- произвольная функция от П +1 переменных из Q .
Тогда функции f(xh..M Xn, 0) и f @C|f...f ХЛ|-1)
принадлежат Ц ; эта пара функций полностью определяет
функцию f(xit..., Х„+1) .Поэтому РЛгЫКР* (л)
>*¦*,
Тал самым, с учетом того, **о Рд( fO ^ It яоша
доказана, г ,
Положим теперь ^Ш\/Рд 0^ =2 . Тогда
О ^ 6 q -4 1 • Число & q назовем параметром класса
СУ , а классы, для которых бы ^ 0, - ш&?§?вш. Из
определения 6^ следует, что для ненулевого инвариантного
класса (У
Pa М - 2 ? ? > (I)
где ?д(П,) —» 0 при la -*¦ <*>.
теорема 25 [б]. Дваь Cjf - аадуцедой вдаи-
QBTHUft M3Qff Q дарад^ДШ 6 . Тогда
П7

Доказательство. Нижняя оценка
следует из (I) и теоремы 16.
Верхняя оценка. Пусть к - параметр,
удовлетворяющий условиям: ^lurv, k-*><*>, а-к -* **(п. -*•«),
Рассмотрим все функции Q ( Xj ,..., Х^ ) из (У .В
силу (I)
где С(Ю —* 0 при к ~^°° . Поэтому разные фуяющи
Q ( Xt »•••> Х^ ) из 0^ можно закодировать разными
наборами ( XА ,..., Т^ ) из нулей и единиц длины:
J*]^P(j(k)[=62kD*rt10),
где б (к) -* 0 при fc-*- оо . Заметим, что ^4 2.
Пусть теперь Г (Xf ,..., Хп ) - произвольная
функция из Q , зависящая от П аргументов. Рассмотрим
2Л"к функций I* ( X, Xk,6^+1 ^*»2|
и их коды ( Xi ,..., *Г^ ) (здесь используется тот факт, *
что все эти функции принадлежат классу U ). При фин*' 'gj-
ванной функции Г каждая цифра кода однозначно опредй( ет-
ся набором ( 6. ,..., 6П ). Иными словами, существуют
такие & фунюцш алгебры логики от П~ 'к аргументов,
зависящие от ?,
''i ( ^fc+l • •••• хм )> ^ = I ^ •
что для любого набора ( 6^ + ^ ($п ) набор
< ^ < 6*+< <V ) V<^1 6п )
является кодом функции ? (Х1,..., Х^, 6 ^+< ,..., 6а).
Схема S для функции Г состоит из трех блоков
А , D и С , соединенных мезду собой (рже. 39):
118

Xf Xk
i±7
Рис. 39
I. Елок А реализует функции ^ ( X ^+i ,..., ХЛ ),
t = I,..., I • На основании теоремы II блок А может быть
юстроен так, что
(n-fc
[см. B) )• Отметим, что строение блока А зависит от
исходной функции С •
2. Блок D не зависит от функции Г , а определяется
1ишь кодированием всех функций а ( Xt ,..., Х^ ) из СУ
Этот блок по коду произвольной функции Q (Xt ,..., Х^) из
OS (набору длины ъ ) выдает последовательность ее
значений на всевозможных 2 наборах значений аргументов.
Таким образом, блок В реализует 2 * функций от I аргу-

ментов. На основании следствия из теоремы 12 блок В может
быть построен так, что
L(BL 2kc:~-=0B2).
3. Елок С по последовательности значений функции
Qr( ОС, ,..., Xfe) и набору ( 61 ,..., Й^ ) выбирает
значение, соответствующее этому набору. Этот блок фактически
реализует некоторую фунюдоо от 2 + к аргументов и поэтому
может быть построен так, что
L (О 4 с6' ^т = 0(г!).
Заметим, что эта функция может быть реализована существенно
проще, но нам достаточно этой очень грубой оценки. Блок С
не зависит ни от функции -f , ни от кодирования функций из
ч ¦
Таким образом,
Положим 1^= L"r lot! la] . Тогда
2k / 2Я\
|<-^оо, n-'k^ia)n-k-*<*>, 2 =0{~).
Следовательно,
Теорема доказана.
Замечание I. Теорема об асимптотике функции
^ ( v / (^ыла Доказана С .В, Яблонским для случая
контактных схем [5]. При этом было замечено, что эта теорема
справедлива и для других способов реализации функций, в частности,
для схем из функциональных элементов. Здесь было приведено
120

другое доказательство.
Замечание 2. Из доказательства теоремы 25
следует, что для любого нулевого инвариантного класса Q
справедливо соотношение
?. (Г)-<>(-?)•
Этот факт был установлен С «В, Яблонским [4] .
Подробнее об инвариантных классах см. [5] .
§26. Вектор-функции с
ограниченным множеством
значений
Докажем одно обобщение теоремы 14. Пусть П-
ГП =] ^09/ь[ и GL *'/** - класс ( П , m )-фунвдий F ,
обладающих свойствами
^ D |Ftf)|</*-4;
2) | F(S) | = 0, вела | В! > ^ .
Очевидно, чго
содержит /? различных вектор-функций.
Теорема 25. Дур,ТА.Д00Дед0ЮУ.адМ9РТЬ. Д&Р ( ^i,ttj
удоа&д9дэр.мет уадрдадм г
/^ > г,
log ^09 /tj
*,
Тодца
6 ^ *о<?(^4/0
9-2084
121

Доказательство. Нижняя оценка следует из
теоремы 16 (и оценки числа вектор-функции в UL г*^ъ ).
Верхняя оценка. Для каждого 1 возмояшк
два случая:
Случай I. Из (I) следует, что
(см. (<) )• В силу условий нашей теоремы условия теоремы
13 выполнены. Поэтому для подпоследовательности значений ь ,
подпадающих под рассматриваемый случай,
в силу того, что ХС. —* «^ .
Случай 2. В этом случае доказательство аналогично
доказательству теоремы 25. Пусть *
k=]- ^ Ь^[ . B)
Тогда К —* оо . Рассмотрим все вектор-функции из IX .
Их число равно ^ . Поэтому разные вектор-функции из
(X % J** можно закодировать разными наборами ( %А ,..-. V^ )
из нулей и единиц длины
/v»
X
Индекс i опускаем.
Г22

4c r~ jL.
l=]lo)/t [«]2*Jo$/i[~2 lo(jjtx. C)
Кодирование устроил так, чтобы вектор-функции,
принимающей в качестве значений лишь нулевок набор ("нулевой вектор-
функции") соответствовал наоор @,..., 0).
Пусть теперь Г ( ЗС1 ,..., Х^ ) - п.оязвольнад
вектор-функция из OL • Тогда для люоогс ласора
б' =F^41 f., 6Л) вектору уккцкя
F ( Х1 ,..., Х^ , 6ui ,..., 6п ) принадпи ''?
множеству 01 > , причем, если I'S'I ^ J ~р^к L » то
р ( Х1 ,..., ЭС^. , 6^+1 ,..., 6п ) есть "нулевая
вектор-функция".
Схема S для вектор-функции Г состоит из трех
блоков A f В и С
1. Блок А по наоору *&' = ( 6 ^+j ,..., 6а )
выдает набор ( Т1 ,..., *Cj ), сосгветствущий вектор-функции
Г ( Xt ,..., Х^ ; 6^+1 ,..., 6п). Б силу условия,
наложенного на кодирование, этот блок реализует некоторую век-
гО' I V 1 ^ Г ^
тор-функцию из J ' , где V = J -г* [Л т>* .
Так как /Ц ^ ^0(^ ч , то из B), C) (и условий теоремы)
следует, что выполнены условия теоремы 13. На основании
теоремы 13 блок А может быть построен так, что
1 Щ{У1) rloy(Uo<}f)
2. Елок Jj по набору ( Tj ,..., % ? > выдает
последовательность значений соответствующей вектор-функции из
(X '' на всех 2 входных наборах. Таким образом, блок
D реализует ГП 2 функций от v аргументов. В силу
следствия теоремы 12 блок J3 может быть построен так,
что
123

A(BLC;m2^y=0B2^/*).
3. Елок U по последовательности значений вектор-
функции из OL J* и набору ( ^i ,..., 6^) выбирает одно
значение (набор длины ГП = J ?oa/tL ). Этот блок реализует m
функций от 4< + m 2 аргументов и поэтому может быть
построен так, что
6 к +т 2*
Таким образом.
Из B) и условия JUL- ^ Хш V^ следует, что последнее
слагаемое есть О ( г ) . Это означает, что
4 Щ) '
L(S) 4 Р
} Хщ/л>
Щ(Э /од/0 '
Теорема полностью доказана.
§27. Монотонные вектор-функции
Будем называть ( П, 9 ГП )-функцию Г монотонно^,
если из \Ы | ^ | ^1 следует IF(<3)D |F(ji)|. Например.
B,2)-функция rt (табл. 7) монотонная, а B,2)-функция
Гг не является монотонной (табл. 8 задает те же функции,
но вместо наборов выписаны их "арифметические значения").
yyj rt,m
Обозначим через //О класс всех монотонных ( ГЦ ГП )-
124

функций.
г
6
00
10
01
II
Габлвда 7
F,(g).
10
01
01
01
FaF)
00
1 01
10
1 II
Таблица 8
161
0
I
2
3
11 F«g)l
i
2
2
2
ilFeg)l
0
2
I
3
I. Грубая оценка для
Лемма 24.
LE(W'm)<C6]Mrx2m
Доказательство. Пусть г - произвольная
вектор функция из Til * . Обозначим через 0(^
минимальный (по "арифметическому значению") набор, обладающий
свойством
\Fd3li)\>i
(для некоторых "больших" t набор &{ может быть не
определен). Например, для "вектор-функции", заданной табл. 9,
Зо = @,0,0), 5, = 32 = (хд.о), % = (о,о,п,
«.
ЗГ5 = A.0,1), Зб = A,1,1), набор S.
не
определен.
Из определения наборов о(^ (и монотонности FEc) )
следует, что всегда, когда |5^|4|х|<1оЫ , имеет
место t^ I г(х)| < t . Поэтому разряды (± вектор-
функции ( 1|1 ,..., 4^) = F ( 3Ct ЭСа ) могут
быть вычислены следующим образом:
9х-2084
125"

Таблица 9
*, *a х»
0 0 0
10 0
0 10
1 I 0
0 0 1
1 0 I
Oil
III
«*i Нг %
0 0 0
0 0 0
0 0 0
о i о
0 10
1 0 I
I 0 I
oil
и вообще _ i
(Бели для некоторого Ь набор о({ не определен, го
соответствующая "часть формулы" опускается).
Отсюда, в силу леммы 21, следует утверждение леммы 24.
2. Вспомогательная
вектор-функция. Рассмотрим B + fc , 4< )-фунюцш ^/^^ # кото-
рая преобразует набор ( Т , о( ), где t = Ct, .....T.jj ),
& = ( <*! o(fc),BHa6op р = ( J3, ,..., J^),
такой, что [ J3 | есть число единиц в наборе <С , стоящих
126

левее ( I of | + I)-го нуля (если в наборе Ъ нет нуля с
этим номером, то J3 может быть любым).
Л е м м а 25 [б].
Ae(Wfc)<CwK2fc.
Доказательство. Схема для ЧУ ^ строится
в соответствии со следуздим алгоритмом (общий вид схемы
изображен на рис. 40). С правой стороны страницы приведены
верхние оценки сложности отдельных частей схемы.
1. Образуется поразрядная инверсия набора ? -
набор f = (Tt V ). 0B*)
2. Для каждого t ( t =I 2 )
вычисляется число нулей, стоящих в первых i разрядах
набора Т . Оно равно <Ci +...+ <C^ . Это
делается при помощи 2 штук к -разрядных сумматоров
2_, »•••# A.pk • H* ВХОД сумматора 2- •
подается Х^ и выход сумматора Z.. (на второй
вход сумматора zl1 подается набор из нулей). U(i<2 )
3. Аналогичным образом для кавдого
Ь ( i si|MM 2 ) вычисляется число единиц,
стоящих в первых i разрядах набора Т . Это
делается при помощи 2 штук К -разрядных сум-
«аторов Z? Г$ • 0 (К2*)
4. При помощи 2 штук схем сравнения
С2 ^ »¦•¦, С22* (лемма 21) наборы на выхо-
у (о) у (о)
дах схем Z_t ,..., Z_ ^к сравниваются с
наборе»* о/ . Схема ?2 {, реализует функцию
k)^ (S , *>i ), где 8^ - набор на выходе
схемы zL * • На выходах схем Я2 ^
получается набор @,0,..., ОД,..., I), в котором первая
единица стоит на том месте i = i 0 , где впер-
127

Рис. 40

вые выполняется неравенство | Ы I < I о^ \ .
Очевидно, что l^1Ul^l + I, а \Ъ- -|=|Э|Э
т.е. ( I с*1 + 1)-й нуль стоит в i 0 -м разряде.
Поэтому искомое значение вектор-функции у\[ к
(обозначим его через р) выдает сумматор
5. Набор (О,О,...,О,!,...,!) преобразуется в
набор ? =@,0,...,С1Д,0,...,0) (единица стоит
лишь под первой единицей первого набора). Это
делает схема Т (рис. 41). 0B*)
Рис. 41
6. Схемы Р? ,..., Ур* "пропускают" даль-
ше результат лишь того сумматора 2_ • » номер
to
которого соответствует единице набора Z • Схош
Р: состоит из |с штук подсхем для конъш&ош;
V CD
она умножает поразрядно набор на выходе Z. * на
L -й разряд набора о . Набор р получается
на выходе схемы Pie . Остается его "направить" в
фиксированное место.
7. Наборы на выходах схем г~ поразрядно
складываются. Это делает схема V ; на ее i -м
выходе образуется дизъюнкция' 1 -х выходов всех П/, лъх
схем Д . ' О (к 2Х)
0(K2k)
129

Лемма доказана*
3. Точная оценка для
Теорема 27 [б] .
Доказательств о. I. Закодируем монотонные
( П , П )-функции наборами из нулей и единиц. С этой
целью монотонной вектор-функции F поставим в
соответствие набор 5? » обладающий следующими свойствами:
а) набор 31 имеет длину 2 ~ i и содержит 2а
нулей и 2 - единиц;
б) в наборе ЗС число единиц, расположенных левее
( i + 1 )-го нуля, равно I Г B ) | , где ог -
двоичная запись числа i , т.е. t = |^M (тем самым
между нулями набора Зс и наборами 3 значений
аргументов вектор-функции F устанавливается
взаимно-однозначное соответствие). Например, монотонной C,3)-функции,
заданной табл. 10, соответствует набор
St = @,1,1,0,0,1,0,0,1,0,1,1,0,0,1)
Таблица 10
ъ
0 0 0
10 0
0 10
110
0 0 1
10 1
0 11
III
161
0
I
2
3
4
5
6
7
F F)
0 0 0
0 10
0 10
I I 0
I I 0
0 0 1
Oil
Oil
IFg)
0
2
2
3
3
4
6
6
130
L. (дП'1'п).

(для удобства в таблице указаны не только наборы Ъ и г (б),
но и их "арифметические значения" \ё> I и | г(<§)| ).
Очевидно, что соответствие между вектор-функциями из
Tfi ,1г и наборами, обладающими свойством а), является
взаимно однозначным. Таким образом, число М п монотонных
( И , П )-функций равно L а+4 . Используя
формулу Стирдинга, получаем отсюда
2. Нижняя оценка
р ГЬ + {
непосредственно следует из B) и теоремы 16.
\ 3. Верхняя оценка. Пусть г -
произвольная монотонная ( П , М )-функция и Ji соответстБуший
ей набор. Разобьем набор I яа 2 кусков длины 2
где 4< - параметр, удовлетворяющий условиям:
4^ 4с ^ ГЦ Г1-к-*оо(К-*о^Схема S ДДЯ вектор-функции Г
состоит из блоков А , В , С ,Ъ , A .W. X
(рис, 42),
1. Блок А по входному набору Ъ определяет номер
куска, в котором находится нуль последовательности 5г ,
соответствующий набору ^ , и выдает двоичную запись этого
номера (нумерация начинается с нуля). Этот блок реализует
монотонную ( ft , П -к )-функцию. Поэтому, на основании
леммы 24,
L(A) = 0(n2a-*).
2, Клок D по номеру куска выдает соответствующий
кусок *С . Этот блок реализует ( П-к, 2 )-функцию, В
силу теоремы II
131

L(B)±P2 -^.
3. Блок С по номеру куска определяет число единиц,
находящихся во всех кусках с меньшими номерами и выдает его
двоичную запись. Это ( n-'k , гг )-функция. На основании
следствия теоремы 12
?(С)-0(п-^).
Эту вектор-функцию можно реализовать гораздо проще, но для
общей оценки это несущественно.
Рис. 42
4. Блок Ц по номеру куска выдает набор ^ , со-
132

отвегсгвущий первому нулю этого куска. Это ( П ~ fc, П, )-
функция;
n-fc
№)-o(*-^l
Эту вектор-функцию можно реализовать гораздо проще, но для
общей оценки это несущественно.
5. Блок А вычисляет разность I ex I = I о I "" I о I ;
эта разность определяет номер (в куске X ) нуля,
соответствующего набору <? • В силу лешы 20
L (А)= 0(м).
6. Елок Vv no T и 0( определяет число
единиц в Т , расположенных левее нуля; соответствующего Ъ •
В силу леммы 25
Z.(N)«0(l<2k).
7. Блок Z. складывает числа, выдаваемые блоками С
и N • Полученная сумма равна числу единиц, расположенных
в наборе 31 левее нуля, соответствующего ^ .- Иными
словами, набор, выдаваемый блоком 2 , есть значение вектор-
функции р на наборе €> . В силу лешы 19
Таким' образом,
Ш*р^+0(ц?Г*)+0(кг*).
Положим к = L3 >t0O nj . Тогда
Р n+i
USLp^-.
Теорема доказана.
133

§28. Принцип локального
кодирования
Во всех приведенных выше примерах классов функций (или
вектор-функций), допускающих существенно более простую
реализацию, чем это возможно в общем случае, применялся один общий
прием - принцип локального кодирования. Этот принцип основан
на использовании специального кодирования функций,
учитывающего специфику класса реализуемых функций и обладающего
некоторыми дополнительными свойствами.
В случае симметрических функций кодом функции был список
ее значений на яаборах с разным числом единиц; в случае
функций I* (X, ,..., ОС^)ю ненулевых инвариантных классов -
последовательность "номеров" функций ? (^г-^й^+о^А)
и т.д. Выбор кода является неформальной частью применения
этого принципа. Дополнительные свойства кодирования состоят в
следущем.
1. Кодирование является "локальным" в том смысле, что для
вычисления значения функции Г на каждом конкретном наборе
значений аргументов не нужно знать весь код функции Г ,
а достаточно знать его "небольшой кусок".
2. Сравнительно просто вычисляются "координаты" этого
куска (например, номер куска, если код разбит на куски
одинаковой длины; номер первого разряда и длина куска, если куски
имеют различную длину), т.е. существует "простая" схема,
осуществляющая эту операцию.
3. По куску кода и набору О (а также, если удобно,
то по "координатам" указанного куска кода) значение функции
на наборе 'ё вычисляется сравнительно просто.
Очевидно, что всякая функция допускает тривиальное
локальное кодирование - достаточно кодом функции объявить
столбец ее значений. Но при таком кодировании для многих функций
схемы слишком сложны. Вообще, в первом приближении можно
считать, что схема получается тем проще, чем короче код. Однако,
если кодирование сделать, например, "пустым", переложив всю
информацию о функции в декодирование, то тогда будет очень
сложным декодирование. Если же на декодирование наложено
условие "простоты", то длина кода ограничена снизу "энтропией"
класса (т.е. логарифмом числа) рассматриваемых функций, и схе-
134

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

Литература
1. Яблонский СВ. Основные понятия кибернетики. - В кн.:
Проблемы кибернетики, выл. 2. М.: Физматгиз, 1959, с.7~38.
2. Shannon СЕ. The synthesis Gf two-terminal switching
circuits. - Bell Syst. Techn. J., 1949, v.28,j?l, p. 59-98.
(Русский перевод: Шеннон К. Работы по теории информации и
кибернетике. М.: ИИ, 1963, с.59-101.)
3. Лупанов О.Б. О синтезе контактных схем. - ДАН СССР, 1958,
т. П9, Л I, с.23-26.
4. Яблонский СВ. О классах функций алгебры логики,
допускающих простую схемную реализацию. - УМН, 1957, г.12, вып.6,
с.189-196.
5. Яблонский СВ. Об алгоритмических трудностях синтеза
минимальных контактных схем. - В кн.: Проблемы кибернетики,
вып.2. М.: Физматгиз, 1959, с.75-121.
6. Лупанов О.Б. Об одном подходе к синтезу управляпцих систем
- принципе локального кодирования. - В кн.: Проблемы
кибернетики, вып.14. М.: Наука, 1965, с.31-110.
7. Лупанов О.Б. О синтезе некоторых классов управляющих систем.
- В кн.: Проблемы кибернетики, вып.10. М.: Физматгиз, 1963,
с.63-97.
8. Лупанов О.Б. Об одном методе синтеза схем. - Изв. вузов,
Радиофизика, 1958, т.1, Я I, с.120-140.
9. Яблонский СВ. Введение в дискретную математику. М.: Наука,
1979.
Ю.Яблонский СВ. Введение в теорию функций fc - значной
логики. - В кв.: Дискретная математика и математические
вопросы кибернетики / Под ред. СВ. Яблонского и О.Б. Лупано-
ва. М.: Наука, 1974, с.9-66.
136

11. Muller D.E. Complexity in electronic switching circuits.-
IRE Transactions, EC-5, 1956,^-1, p.15-19.
12. Поваров Г.Н. Математическая теория синтеза контактных
(I, k )-полюсников. - ДАН СССР, 1955, т.100, № 5, с.909-
912.
13. Hamming R.W. Error detecting and error correcting codes.-
Bell Syst. Techn. J., 195o, v.29,^5, p.147-160.
(Русский перевод: Коды с обнаружением и исп^влением
ошибок. М.: ИД, 1956, с.7-22).
14. Moore E.F. Minimal complete relay decoding networks.-
IBM J. research and development, 1960, v.4,j/J 5,
p.525-531.
(Русский перевод: Кибернетический сборник, вып.6. М.: ЙД,
1963, с.139-152).
15. Riordan J., Shannon C.E. The number of two-terminal
series-parallel networks.- J. Math, and Phys., 1942,
v.21, J/s 2, p.83-93.
(Русский перевод: Шеннон К. Работы по теории информации и
кибернетике. М.: ИЛ, 1963, с.46-58)
16. Лупанов О.Б. Об асимптотических оценках числа графов и
сетей с П ребрами. - В кн.: Проблемы кибернетики,
вып.4. М.: Физматгиз, I960, с.5-21.
17. Лупанов О.Б. О сложности реализации функций алгебры
логики формулами. - В кн.: Проблемы кибернетики, вып. 3. М.:
Физматгиз, I960, с.61-80.
18. Лупанов О.Б. О реализации функций алгебры логики
формулами из конечных классов (формулами ограниченной глубины) в
базисе <? , V , . - В кн.: Проблемы кибернетики,
вып. 6. М.: Физматгиз, 1961, с.5-14.
19. ЛупаноЕ О.Б. О сложности универсальной
параллельно-последовательной сети глубины 3. - Труды Ш АН СССР, 1973,
т.133, с.127-131.
20. Лупанов О.Б. Об одном кяассе схем из функциональных
элементов (формулы с частичной памятью). - В кн.: Проблемы
кибернетики, вып.7. М.: Физматгиз, 1962, с.61-114.
21. Лупанов О.Б. О схемах из функциональных элементов с
задержками. - В кн.: Проблемы кибернетики, вып.23. М.:
Наука, 1970, с.43-61.