75
правок
Изменения
сделал тире по шаблону
Для удобства дальнейших рассуждений представим булеву функцию в виде таблицы, изображённой на рис. 1.
* '''По горизонтали''' на ней представлены все значения <tex>f(\sigma_1, \sigma_2, ..., \sigma_k, x_{k + 1}, x_{k + 2}, ..., x_n)</tex> (здесь и далее <tex>\sigma</tex> {{- --}} фиксированное значение, <tex>x</tex> {{--- }} переменное);
* '''По вертикали''' на ней представлены все значения <tex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</tex>.
Таким образом, легко заметить, что значение <tex>f(x_1, x_2, ..., x_n)</tex> находится на пересечении строки <tex>x_1, x_2, ..., x_k</tex> и столбца <tex>x_{k + 1}, x_{k + 2}, ..., x_n</tex>.
{{
Определение|definition=
'''Сорт''' столбца полосы {{- --}} [[Отношение эквивалентности#Классы эквивалентности | класс эквивалентности]], к которому столбец принадлежит (два столбца эквивалентны, если совпадают по значениям).
}}
Число сортов столбцов <tex>i</tex>-й полосы обозначим как <tex>t(i)</tex>. Понятно, что для любой полосы <tex>t(i) \leq 2^s</tex> (для последней <tex>t(i) \leq 2^{s'}</tex>).
[[Файл:Lupanov_fig2.png|330px|thumb|right|Рис. 2. Значения, возвращаемые функцией <tex>g_{ij}</tex>]]
Пусть для некоторого <tex>i</tex>
* <tex>\beta_{j}</tex> {{- --}} столбец <tex>i</tex>-й полосы <tex>j</tex>-го сорта;* <tex>(\sigma_1^l, \sigma_2^l, ..., \sigma_k^l)</tex> {{--- }} аргументы функции, соответствующие её значениям в <tex>l</tex>-й строке <tex>i</tex>-й полосы.
Тогда введём булеву функцию
Поскольку изначальный столбец <tex>(\sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_{n})</tex> складывается из столбцов соответствующих сортов в полосах,
<tex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_{n}) = \bigvee\limits_{i = 1}^p g_{ij_i}(x_1, x_2, ..., x_k)</tex>,
где <tex>j_i</tex> {{- --}} номер сорта столбца полосы <tex>i</tex>, являющегося соответствующей частью столбца <tex>(\sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_{n})</tex>.
== Мультиплексор и дешифратор ==
{{
Определение|definition=
'''Мультиплексор''' {{- --}} логический элемент, получающий на вход
* <tex>2^n</tex> булевых значений;
* <tex>n</tex>-значное число <tex>x</tex> в двоичном представлении
}}{{
Определение|definition=
'''Дешифратор''' {{- --}} логический элемент, получающий на вход
* булево значение <tex>z</tex>;
* <tex>n</tex>-значное число <tex>x</tex> в двоичном представлении
[[Файл:Lupanov_scheme.png|400px|thumb|right|Иллюстрация частного случая представления Лупанова, описанного здесь]]
В качестве доказательства ниже будет предложен вариант такой схемы для произвольной функции <tex>f(x_1, x_2, ..., x_n)</tex> (представление Лупанова). Для удобства поделим схему на блоки:
* '''Блок A''' {{- --}} дешифратор, которому на вход подали 1 и <tex>(x_1, x_2, ..., x_k)</tex> в качестве двоичного представления числа.
Число элементов <tex>L_A \sim 2^k</tex>
* '''Блок B''' {{--- }} схемная реализация всех <tex>g_{ij}</tex>. Функцию <tex>g_{ij}</tex> можно реализовать как <tex>\bigvee\limits_{\beta_l = 1} y_{il}</tex>, где <tex>y_{il}</tex> {{--- }} выдал ли дешифратор "1" на <tex>l</tex>-м выходе <tex>i</tex>-й полосы.
Число элементов <tex>L_B \leq (s - 1) \cdot (t(1) + t(2) + ... + t(p)) < sp \cdot 2^{s}</tex>
* '''Блок C''' {{- --}} схемная реализация всех <tex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</tex>.
Число элементов <tex>L_C \sim p \cdot 2^{n - k} = \frac{2^n}{s}</tex>
* '''Блок D''' {{- --}} мультиплексор, получающий на вход все <tex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</tex> и параметры функции <tex>x_{k + 1}, x_{k + 2}, ..., x_n</tex> в качестве двоичного представления числа.
Число элементов <tex>L_D \sim 2^{n - k}</tex>
'''''Результат работы схемы''''' {{- --}} вывод мультиплексора.
Положим <tex>s = [n - 2\log_2 n]</tex>; <tex>k = [\log_2 n]</tex>. Тогда
Итого, имеем схему с итоговым числом элементов <tex>\sim \frac{2^n}{n}</tex>, откуда следует, что <tex>size_B (f) \lesssim \frac{2^n}{n}</tex>, '''ч.т.д.'''
== Ссылки ==
* [http://en.wikipedia.org/wiki/Multiplexer Wikipedia {{- --}} Multiplexer]
== Литература ==
* Яблонский С.В. Введение в дискретную математику, изд. Наука, 1986, стр. 361 {{- --}} более обобщённое доказательство, частично взятое за основу.
