Изменения

Любая [[Определение булевой функции | булева функция ]] от <mathtex>n</mathtex> аргументов <mathtex>f(x_1, x_2, ...\ldots, x_n)</mathtex> при в базисе <mathtex>B = \{\neg, \lor, \land\}</mathtex> имеет [[Реализация булевой функции схемой из функциональных элементов#Схемная сложность | схемную сложность ]] <mathtex>size_B (f) = O\lesssim left(\fracdfrac{2^n}{n}\right)</mathtex>.

[[Файл:Lupanov fig1.png|400px450px|thumb|right|Рис. <tex>1</tex>. Описываемая таблица истинности, разделённая на полосы]]Для начала поделим Поделим аргументы функции на два блока: первые <mathtex>k</mathtex> и оставшиеся <mathtex>(n - k)</mathtex>.

Для удобства дальнейших рассуждений представим булеву функцию в виде таблицы, изображённой на рис. 1.* '''По горизонтали''' на ней представлены все значения <mathtex>f(\sigma_1, \sigma_2, ..., \sigma_k, x_{k + 1}, x_{k + 2}, ..., x_n)</mathtex> (здесь и далее . Строки индексируются значениями первых <mathtex>\sigmak</mathtex> - фиксированное значениепеременных, столбцы — значениями оставшихся <math>x</mathtex> (n - переменное);* '''По вертикали''' на ней представлены все значения <math>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</mathtex>.Таким ; таким образом, легко заметить, что значение <math>f(x_1, x_2, ..., x_n)</math> находится на пересечении столбца и строки <math>x_1, x_2, ..., x_k</math> и столбца <math>x_{k + 1}, x_{k + 2}, ..., x_n</math>находится значение функции для соответствующего набора аргументов.

Разделим таблицу на '''''горизонтальные полосы ''''' шириной <mathtex>s</mathtex> (последняя полоса, возможно, будет короче остальных; её длину ширину обозначим <mathtex>s'</mathtex>). Пронумеруем полосы сверху вниз от <tex>1 </tex> до <mathtex dpi="145">p=\left\lceil\fracdfrac{2^k}{s}\right\rceil</mathtex>.

Рассмотрим независимо некоторую полосу. Среди Заметим, что среди её столбцов при небольшом <mathtex>s</mathtex> будет много повторений; далее про одинаковые столбцы, находящиеся в одной полосе, будем говорить, поэтому введём понятие что они одного '''''сорта''''' столбца.

'''Сорт''' некоторого столбца данной полосы {{- --}} его [[Отношение эквивалентности#Классы эквивалентности | класс эквивалентности, к которому столбец принадлежит (два столбца эквивалентны, если совпадают ]] по значениям)отношению поэлементного равенства столбцов данной полосы.

Число сортов столбцов <mathtex>i</mathtex>-й полосы обозначим как <mathtex>t(i)</mathtex>. Понятно, что для любой полосы <mathtex>t(i) \leq leqslant 2^s</mathtex> (для последней <mathtex>t(ip) \leq leqslant 2^{s'}</mathtex>).

[[Файл:Lupanov_fig2.png|330px|thumb|right|Рис. <tex>2</tex>. Значения, возвращаемые функцией <tex>g_{ij}</tex>]]Пусть для некоторого <mathtex>i</mathtex>* <mathtex>\beta_{j}</mathtex> {{- --}} произвольный столбец <mathtex>i</mathtex>-й полосы <mathtex>j</mathtex>-го сорта;(точное положение столбца далее не будет иметь значения, по определению сорта)* <mathtex>(\sigma_1^l, \sigma_2^l, ...\ldots, \sigma_k^l)</mathtex> {{- --}} аргументы функции, соответствующие её значениям в <mathtex>l</mathtex>-й строке <mathtex>i</mathtex>-й полосы.

<mathtex>g_{ij}(x_1, x_2, ...\ldots, x_k) = \begin{cases} \beta_{jl}& , \mbox{if } \exists l \in [1; s]~(x_1, x_2, ...\ldots, x_k) = (\sigma_1^l, \sigma_2^l, ...\ldots, \sigma_k^l) \\ 0&, \mbox{elseotherwise}\end{cases}</mathtex>

Другими словами, если строка, соответствующая аргументам функции <mathtex>x_1, x_2, ...\ldots, x_k</mathtex>, находится в <mathtex>i</mathtex>-й полосе, то функция возвращает значение, записанное в столбце сорта <mathtex>j</mathtex> для этой строки. Если же эта строка находится в другой полосе, то функция вернёт <tex>0</tex>. Иллюстрация принципа работы функции <mathtex>g_{ij}</mathtex> приведена на рис. <tex>2</tex>.=== Вывод исходной функции для фиксированной части параметров ===Поскольку изначальный столбец <mathtex>(\sigma_{k + 1}, \sigma_{k + 2}, ...\ldots, \sigma_{n})</mathtex> складывается из столбцов соответствующих сортов в полосах,<mathtex dpi="145">f(x_1, x_2, ...\ldots, x_k, \sigma_{k + 1}, \sigma_{k + 2}, ...\ldots, \sigma_{n}) = g_\bigvee\limits_{1j_1i = 1} \vee ^p g_{2j_2ij_i} (x_1, x_2, \vee ... \vee g_{pj_p}ldots, x_k)</mathtex>,где <mathtex>j_lj_i</mathtex> {{-- -}} номер сорта столбца полосы <mathtex>li</mathtex>, являющегося соответствующей частью столбца <mathtex>(\sigma_{k + 1}, \sigma_{k + 2}, ...\ldots, \sigma_{n})</mathtex>.

== Мультиплексор и дешифратор демультиплексор =={{main|Мультиплексор и демультиплексор}} Для упрощения доказательства теоремы введём будем использовать элементы '''''мультиплексор''''' и '''''дешифратордемультиплексор'''''.

'''Мультиплексор''' (''англ.'' multiplexer) {{- --}} логический элемент, получающий на вход* <mathtex>2^n</mathtex> булевых значений;* <mathtex>n</mathtex>-значное число <mathtex>x</mathtex> в двоичном представлениии возвращающий значение на <mathtex>x</mathtex>-м входе.

'''ДешифраторДемультиплексор''' (''англ.'' demultiplexer) {{--- }} логический элемент, получающий на вход* булево значение <mathtex>z</mathtex>;* <mathtex>n</mathtex>-значное число <mathtex>x</mathtex> в двоичном представлениии выводящий <mathtex>z</mathtex> на <mathtex>x</mathtex>-й из своих <mathtex>2^n</mathtex> выходов. На все остальные выходы элемент выдаёт <tex>0</tex>.

Иллюстрации элементов приведены на рис. 3 и 4{||[[Файл:Mux_demux.png|500px|thumb|Мультиплексор слева, демультиплексор справа]]|}

Можно доказать, что оба Оба элемента представимы схемами с числом элементов <mathtex>\sim O(2^n)</mathtex> с помощью базиса <mathtex>B</mathtex>.

В качестве доказательства ниже будет предложен вариант такой схемы для произвольной функции <mathtex>f(x_1, x_2, ...\ldots, x_n)</mathtex> (представление Лупанова, ''англ.'' Lupanov <tex>(k, s)</tex>-representation). Для удобства поделим схему на блоки:

* '''Блок A''' - дешифратор, которому на вход подали 1 и <math>(x_1, x_2, ..[[Файл:Lupanov_scheme.png|550px|Иллюстрация частного случая представления Лупанова, x_k)</math> в качестве двоичного представления числа.описанного здесь]]

Число элементов Для удобства поделим схему на блоки:* '''Блок A''' {{---}} демультиплексор, которому на вход подали <tex>1</tex> и <mathtex>L_A (x_1, x_2, \sim 2^kldots, x_k)</mathtex>в качестве двоичного представления числа.* '''Блок B''' {{--- }} схемная реализация всех <mathtex>g_{ij}</mathtex>. Функцию <mathtex>g_{ij}</mathtex> можно реализовать как <mathtex dpi="145">\bigvee\limits_{\beta_l = 1} y_{il}</mathtex>, где <mathtex>y_{il}</mathtex> {{--- }} выдал ли дешифратор "демультиплексор <tex>1" </tex> на <mathtex>l</mathtex>-м выходе <mathtex>i</mathtex>-й полосы.* '''Блок C''' {{---}} схемная реализация всех <tex>f(x_1, x_2, \ldots, x_k, \sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_n)</tex>. ''(здесь <tex>\sigma_i</tex> - фиксированные параметры, см. п. <tex>3.1</tex>)''* '''Блок D''' {{---}} мультиплексор, получающий на вход все <tex>f(x_1, x_2, \ldots, x_k, \sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_n)</tex> и параметры функции <tex>x_{k + 1}, x_{k + 2}, \ldots, x_n</tex> в качестве двоичного представления числа. '''''Результат работы схемы''''' {{---}} вывод мультиплексора.

Число Положим <tex>s = \lfloor n - 2\log_2 n\rfloor</tex>; <tex>k = \lfloor\log_2 n\rfloor</tex>. Тогда число элементов в блоках* <mathtex>L_A = O(2^k) = O(2^{\log_2 n}) = O(n)</tex>* <tex>L_B \leq leqslant (s - 1) \cdot (t(1) + t(2) + ... \ldots + t(p)) < sp \cdot 2^s = n \cdot \dfrac{s2^n}{n^2} = \dfrac{2^n}{n}</mathtex>* '''Блок C''' - схемная реализация всех <mathtex>fL_C = O(x_1, x_2, ..., x_k, p \sigma_cdot 2^{n - k + 1}, ) = O\left(\dfrac{p}{n} \cdot 2^n\right) = O\left(\dfrac{2^n}{s}\right) = O\left(\dfrac{2^n}{n - 2\log_2 n}\sigma_right)</tex>* <tex>L_D = O(2^{n - k + }) = O\left(\dfrac{2^n}{n}, ..., \sigma_nright)</mathtex>.

Число Итого, имеем схему c числом элементов <mathtex>L_A + L_B + L_C + L_D = O(n) + O\sim p left(\cdot frac{2^n}{n - k} = \fracright) + O\left(\dfrac{2^n}{sn - 2\log_2 n}</math>* '''Блок D''' - мультиплексор, получающий на вход все <math>f\right) + O\left(x_1, x_2, ..., x_k, \sigma_dfrac{2^n}{k + 1n}, \sigma_right) = O\left(\dfrac{k + 2^n}{n}, ..., \sigma_nright)</mathtex> и параметры функции , откуда следует, что <mathtex>x_size_B (f) = O\left(\dfrac{k + 12^n}, x_{k + 2n}, ..., x_n\right)</mathtex> в качестве двоичного представления числа, что и требовалось доказать.

Число == См. также ==*[[Реализация_булевой_функции_схемой_из_функциональных_элементов|Реализация булевой функции схемой из функциональных элементов <math>L_D \sim 2^{n - k}</math>]]*[[Простейшие_методы_синтеза_схем_из_функциональных_элементов|Простейшие методы синтеза схем из функциональных элементов]]*[[Контактная_схема|Контактная схема]]

Положим <math>s = [n - 5\log_2 n]</math>; <math>k = [3 \log_2 n]</math>. ТогдаИсточник информации ==* <math>L_A \sim 2^Яблонский С.В. Введение в дискретную математику {3 \log_2 n} \leq \frac{2^n---}{n}</math>* <math>L_B < sp \cdot 2^s = 2^М.:"Наука", 1986 {k + s} \leq \frac{2^n---}{n}</math>стр. 361* <math>L_C \sim p \cdot 2^[http://en.wikipedia.org/wiki/Multiplexer Wikipedia {{n - k} = \frac{2^k}{n - 5\log_2 n} \cdot \frac{2^n}{n^3} \sim \frac{2^n}{n}</math>* <math>L_D \sim 2^{n - k} \leq \frac{2^n}{n}</math>Multiplexer]

Итого, имеем схему с итоговым числом [[Категория:Дискретная математика и алгоритмы]][[Категория: Схемы из функциональных элементов <math>\sim \frac{2^n}{n}</math>, откуда следует, что <math>size_B (f) \lesssim \frac{2^n}{n}</math>, '''ч.т.д.''']]