Изменения

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

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

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

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

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

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

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

[[Файл:Lupanov_fig2.png|330px|thumb|right|Рис. <tex>2</tex>. Значения, возвращаемые функцией <tex>g_{ij}</tex>]]

* <tex>\beta_{j}</tex> {{---}} произвольный столбец <tex>i</tex>-й полосы <tex>j</tex>-го сорта;(точное положение столбца далее не будет иметь значения, по определению сорта)* <tex>(\sigma_1^l, \sigma_2^l, ...\ldots, \sigma_k^l)</tex> {{---}} аргументы функции, соответствующие её значениям в <tex>l</tex>-й строке <tex>i</tex>-й полосы.

<tex>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}

Другими словами, если строка, соответствующая аргументам функции <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> складывается из столбцов соответствующих сортов в полосах,<texdpi="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>.

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

'''Мультиплексор''' (''англ.'' multiplexer) {{---}} логический элемент, получающий на вход

'''ДешифраторДемультиплексор''' (''англ.'' demultiplexer) {{---}} логический элемент, получающий на вход

и выводящий <tex>z</tex> на <tex>x</tex>-й из своих <tex>2^n</tex> выходов. На все остальные выходы элемент выдаёт <tex>0</tex>.

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

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

[[Файл:Lupanov_scheme.png|400px|thumb|right|Иллюстрация частного случая представления Лупанова, описанного здесь]] В качестве доказательства ниже будет предложен вариант такой схемы для произвольной функции <tex>f(x_1, x_2, ...\ldots, x_n)</tex> (представление Лупанова, ''англ.'' 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> можно реализовать как <texdpi="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 \sim = O(2^k \lesssim \frac{) = 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{2^n}{k + sn^2} = \fracdfrac{2^n}{n}</tex>* <tex>L_C \sim = O(p \cdot 2^{n - k} ) = O\left(\dfrac{p}{n} \cdot 2^n\right) = O\left(\fracdfrac{2^n}{s} \sim right) = O\left(\fracdfrac{2^n}{n - 2\log_2 n}\right)</tex>* <tex>L_D \sim = O(2^{n - k} ) = O\fracleft(\dfrac{2^n}{n}\right)</tex>

Итого, имеем схему с итоговым c числом элементов <tex>L_A + L_B + L_C + L_D = O(n) + O\sim 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\lesssim left(\fracdfrac{2^n}{n}\right)</tex>, '''''ч.т.дчто и требовалось доказать.'''''

== Ссылки См. также ==*[[Реализация_булевой_функции_схемой_из_функциональных_элементов|Реализация булевой функции схемой из функциональных элементов]]*[[Простейшие_методы_синтеза_схем_из_функциональных_элементов|Простейшие методы синтеза схем из функциональных элементов]]*[[Контактная_схема|Контактная схема]]  == Источник информации ==* Яблонский С.В. Введение в дискретную математику {{---}} М.:"Наука", 1986 {{---}} стр. 361