75
правок
Изменения
начал викифицировать
{{
Теорема|statement=
Любая [[Определение булевой функции | булева функция ]] от <tex>n</tex> аргументов <tex>f(x_1, x_2, ..., x_n)</tex> при базисе <tex>B = \{\neg, \lor, \land\}</tex> имеет [[Реализация булевой функции схемой из функциональных элементов#Схемная сложность | схемную сложность ]] <tex>size_B (f) \lesssim \frac{2^n}{n}</tex>.
}}
{{
Определение|definition=
'''Сорт''' столбца полосы - [[Отношение эквивалентности#Классы эквивалентности | класс эквивалентности]], к которому столбец принадлежит (два столбца эквивалентны, если совпадают по значениям).
}}
Число сортов столбцов <tex>i</tex>-й полосы обозначим как <tex>t(i)</tex>. Понятно, что для любой полосы <tex>t(i) \leq 2^s</tex> (для последней <tex>t(i) \leq 2^{s'}</tex>).
== Ссылки ==
* [http://en.wikipedia.org/wiki/Multiplexer Wikipedia - Multiplexer]
== Литература ==
* Яблонский С.В. Введение в дискретную математику, изд. Наука, 1986, стр. 361 - более обобщённое доказательство, частично взятое за основу.
