Изменения

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

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

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

Другими словами, если строка, соответствующая аргументам функции <math>x_1, x_2, ..., x_k</math>, находится в <math>i</math>-й полосе, то функция возвращает значение, записанное в столбце сорта <math>j</math> для этой строки. Если же эта строка находится в другой полосе, то функция вернёт 0. Иллюстрация принципа работы функции <math>g_{ij}</math> приведена на рис. 2.==Мультиплексор и демультиплексор = Вывод функции для фиксированной части параметров ===Поскольку изначальный столбец <math>(\sigma_{k + 1}, \sigma_{k + 2}, \sigma_{n})</math> складывается из столбцов соответствующих сортов в полосах,<math>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, \sigma_{n}) = g_{1j_1} \vee g_{2j_2} \vee ... \vee g_{pj_p}</math>,где <math>j_l</math> - номер сорта столбца полосы <math>l</math>, соответствующего столбцу <math>(\sigma_{k + 1}, \sigma_{k + 2main|Мультиплексор и демультиплексор}, \sigma_{n})</math>.

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

'''Мультиплексор''' (''англ.'' 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).  [[Файл:Lupanov_scheme.png|550px|Иллюстрация частного случая представления Лупанова, описанного здесь]]  Для удобства поделим схему на блоки:* '''Блок A''' {{---}} демультиплексор, которому на вход подали <tex>1</tex> и <tex>(x_1, x_2, \ldots, x_k)</tex> в качестве двоичного представления числа.* '''Блок B''' {{---}} схемная реализация всех <tex>g_{ij}</tex>. Функцию <tex>g_{ij}</tex> можно реализовать как <tex dpi="145">\bigvee\limits_{\beta_l = 1} y_{il}</tex>, где <tex>y_{il}</tex> {{---}} выдал ли демультиплексор <tex>1</tex> на <tex>l</tex>-м выходе <tex>i</tex>-й полосы.* '''Блок 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>. Тогда число элементов в блоках* <tex>L_A = O(2^k) = O(2^{\log_2 n}) = O(n)</tex>* <tex>L_B \leqslant (s - 1) \cdot (t(1) + t(2) + \ldots + t(p)) < sp \cdot 2^s = n \cdot \dfrac{2^n}{n^2} = \dfrac{2^n}{n}</tex>* <tex>L_C = O(p \cdot 2^{n - k}) = 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}\right)</tex>* <tex>L_D = O(2^{n - k}) = O\left(\dfrac{2^n}{n}\right)</tex> Итого, имеем схему c числом элементов <tex>L_A + L_B + L_C + L_D = O(n) + O\left(\frac{2^n}{n}\right) + O\left(\dfrac{2^n}{n - 2\log_2 n}\right) + O\left(\dfrac{2^n}{n}\right) = O\left(\dfrac{2^n}{n}\right)</tex>, откуда следует, что <tex>size_B (f) = O\left(\dfrac{2^n}{n}\right)</tex>, что и требовалось доказать. == См. также ==*[[Реализация_булевой_функции_схемой_из_функциональных_элементов|Реализация булевой функции схемой из функциональных элементов]]*[[Простейшие_методы_синтеза_схем_из_функциональных_элементов|Простейшие методы синтеза схем из функциональных элементов]]*[[Контактная_схема|Контактная схема]]  == Источник информации ==* Яблонский С.В. Введение в дискретную математику {{---}} М.:"Наука", 1986 {{---}} стр. 361* [http://en.wikipedia.org/wiki/Multiplexer Wikipedia {{---}} Multiplexer]

* '''Блок A''' - дешифратор, которому на вход подали 1 [[Категория:Дискретная математика и <math>(x_1, x_2, ..., x_k)</math> в качестве двоичного представления числа.алгоритмы]]* '''Блок B''' - схемная реализация всех <math>g_{ij}</math>. Функцию <math>g_{ij}</math> можно реализовать как <math>\bigvee\limits_{\beta_l = 1} y_{il}</math>, где <math>y_{il}</math> - выдал ли дешифратор "1" на <math>l</math>-м выходе <math>i</math>-й полосы.* '''Блок C''' - схемная реализация всех <math>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</math>.[[Категория: Схемы из функциональных элементов ]]