Метод Лупанова синтеза схем — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Разделение на полосы: ещё одна плохо читаемая формула)
(не показаны 44 промежуточные версии 7 участников)
Строка 1: Строка 1:
== Формулировка ==
 
 
{{
 
{{
 
Теорема|statement=
 
Теорема|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>.
+
Любая [[Определение булевой функции | булева функция]] от <tex>n</tex> аргументов <tex>f(x_1, x_2, \ldots, x_n)</tex> в базисе <tex>B = \{\neg, \lor, \land\}</tex> имеет [[Реализация булевой функции схемой из функциональных элементов#Схемная сложность | схемную сложность]] <tex>size_B (f) = O\left(\dfrac{2^n}{n}\right)</tex>.
 
}}
 
}}
  
 
== Представление функции ==
 
== Представление функции ==
[[Файл:Lupanov fig1.png|330px|thumb|right|Рис. 1. Описываемая таблица истинности, разделённая на полосы]]
+
[[Файл:Lupanov fig1.png|450px|thumb|right|Рис. <tex>1</tex>. Описываемая таблица истинности, разделённая на полосы]]
Для начала поделим аргументы функции на два блока: первые <tex>k</tex> и оставшиеся <tex>(n - k)</tex>.
+
Поделим аргументы функции на два блока: первые <tex>k</tex> и оставшиеся <tex>(n - k)</tex>.
  
Для удобства дальнейших рассуждений представим булеву функцию в виде таблицы, изображённой на рис. 1.
+
Для удобства дальнейших рассуждений представим булеву функцию в виде таблицы, изображённой на рис. <tex>1</tex>. Строки индексируются значениями первых <tex>k</tex> переменных, столбцы — значениями оставшихся <tex>(n - k)</tex>; таким образом, на пересечении столбца и строки находится значение функции для соответствующего набора аргументов.
* '''По горизонтали''' на ней представлены все значения <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>.
 
  
 
== Разделение на полосы ==
 
== Разделение на полосы ==
Разделим таблицу на горизонтальные полосы шириной <tex>s</tex> (последняя полоса, возможно, будет короче остальных; её длину обозначим <tex>s'</tex>). Пронумеруем полосы сверху вниз от 1 до <tex dpi="145">p=\left\lceil\frac{2^k}{s}\right\rceil</tex>.
+
Разделим таблицу на '''''горизонтальные полосы''''' шириной <tex>s</tex> (последняя полоса, возможно, будет короче остальных; её ширину обозначим <tex>s'</tex>). Пронумеруем полосы сверху вниз от <tex>1</tex> до <tex dpi="145">p=\left\lceil\dfrac{2^k}{s}\right\rceil</tex>.
  
Рассмотрим независимо некоторую полосу. Среди её столбцов при небольшом <tex>s</tex> будет много повторений, поэтому введём понятие '''''сорта''''' столбца.
+
Рассмотрим независимо некоторую полосу. Заметим, что среди её столбцов при небольшом <tex>s</tex> будет много повторений; далее про одинаковые столбцы, находящиеся в одной полосе, будем говорить, что они одного '''''сорта'''''.
 
{{
 
{{
 
Определение|definition=
 
Определение|definition=
'''Сорт''' столбца полосы {{---}} [[Отношение эквивалентности#Классы эквивалентности | класс эквивалентности]], к которому столбец принадлежит (два столбца эквивалентны, если совпадают по значениям).
+
'''Сорт''' некоторого столбца данной полосы {{---}} его [[Отношение эквивалентности#Классы эквивалентности | класс эквивалентности]] по отношению поэлементного равенства столбцов данной полосы.
 
}}
 
}}
Число сортов столбцов <tex>i</tex>-й полосы обозначим как <tex>t(i)</tex>. Понятно, что для любой полосы <tex>t(i) \leq 2^s</tex> (для последней <tex>t(i) \leq 2^{s'}</tex>).
+
Число сортов столбцов <tex>i</tex>-й полосы обозначим как <tex>t(i)</tex>. Понятно, что для любой полосы <tex>t(i) \leqslant  2^s</tex> (для последней <tex>t(p) \leqslant  2^{s'}</tex>).
  
 
== Функция для одной полосы ==
 
== Функция для одной полосы ==
[[Файл:Lupanov_fig2.png|330px|thumb|right|Рис. 2. Значения, возвращаемые функцией <tex>g_{ij}</tex>]]
+
[[Файл:Lupanov_fig2.png|330px|thumb|right|Рис. <tex>2</tex>. Значения, возвращаемые функцией <tex>g_{ij}</tex>]]
 
Пусть для некоторого <tex>i</tex>
 
Пусть для некоторого <tex>i</tex>
* <tex>\beta_{j}</tex> {{---}} столбец <tex>i</tex>-й полосы <tex>j</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_1^l, \sigma_2^l, \ldots, \sigma_k^l)</tex> {{---}} аргументы функции, соответствующие <tex>l</tex>-й строке <tex>i</tex>-й полосы.
 
Тогда введём булеву функцию
 
Тогда введём булеву функцию
  
<tex>g_{ij}(x_1, x_2, ..., x_k) = \begin{cases}  
+
<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, ..., x_k) = (\sigma_1^l, \sigma_2^l, ..., \sigma_k^l) \\
+
     \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{else}
+
     0, \mbox{ otherwise}
 
\end{cases}</tex>
 
\end{cases}</tex>
  
Другими словами, если строка, соответствующая аргументам функции <tex>x_1, x_2, ..., x_k</tex>, находится в <tex>i</tex>-й полосе, то функция возвращает значение, записанное в столбце сорта <tex>j</tex> для этой строки. Если же эта строка находится в другой полосе, то функция вернёт 0. Иллюстрация принципа работы функции <tex>g_{ij}</tex> приведена на рис. 2.
+
Другими словами, если строка, соответствующая аргументам функции <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}, ..., \sigma_{n})</tex> складывается из столбцов соответствующих сортов в полосах,
+
Поскольку изначальный столбец <tex>(\sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_{n})</tex> складывается из столбцов соответствующих сортов в полосах,
<tex dpi="145">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 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}, ..., \sigma_{n})</tex>.
+
где <tex>j_i</tex> {{---}} номер сорта столбца полосы <tex>i</tex>, являющегося соответствующей частью столбца <tex>(\sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_{n})</tex>.
  
== Мультиплексор и дешифратор ==
+
== Мультиплексор и демультиплексор ==
Для упрощения доказательства теоремы введём элементы '''''мультиплексор''''' и '''''дешифратор'''''.
+
{{main|Мультиплексор и демультиплексор}}
 +
 
 +
Для упрощения доказательства теоремы будем использовать элементы '''''мультиплексор''''' и '''''демультиплексор'''''.
 
{{
 
{{
 
Определение|definition=
 
Определение|definition=
'''Мультиплексор''' {{---}} логический элемент, получающий на вход
+
'''Мультиплексор''' (''англ.'' multiplexer) {{---}} логический элемент, получающий на вход
 
* <tex>2^n</tex> булевых значений;
 
* <tex>2^n</tex> булевых значений;
 
* <tex>n</tex>-значное число <tex>x</tex> в двоичном представлении
 
* <tex>n</tex>-значное число <tex>x</tex> в двоичном представлении
Строка 52: Строка 50:
 
}}{{
 
}}{{
 
Определение|definition=
 
Определение|definition=
'''Дешифратор''' {{---}} логический элемент, получающий на вход
+
'''Демультиплексор''' (''англ.'' demultiplexer) {{---}} логический элемент, получающий на вход
 
* булево значение <tex>z</tex>;
 
* булево значение <tex>z</tex>;
 
* <tex>n</tex>-значное число <tex>x</tex> в двоичном представлении
 
* <tex>n</tex>-значное число <tex>x</tex> в двоичном представлении
и выводящий <tex>z</tex> на <tex>x</tex>-й из своих <tex>2^n</tex> выходов. На все остальные выходы элемент выдаёт 0.
+
и выводящий <tex>z</tex> на <tex>x</tex>-й из своих <tex>2^n</tex> выходов. На все остальные выходы элемент выдаёт <tex>0</tex>.
 
}}
 
}}
[[Файл:Mux_demux.png|400px|thumb|right|Рис. 3. Мультиплексор слева, дешифратор справа]]
+
{|
Иллюстрации элементов приведены на рис. 3.
+
|[[Файл:Mux_demux.png|500px|thumb|Мультиплексор слева, демультиплексор справа]]
 +
|}
  
Можно доказать, что оба элемента представимы схемами с числом элементов <tex>\sim 2^n</tex> с помощью базиса <tex>B</tex>.
+
Оба элемента представимы схемами с числом элементов <tex>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).
В качестве доказательства ниже будет предложен вариант такой схемы для произвольной функции <tex>f(x_1, x_2, ..., x_n)</tex> (представление Лупанова). Для удобства поделим схему на блоки:
+
 
* '''Блок A''' {{---}} дешифратор, которому на вход подали 1 и <tex>(x_1, x_2, ..., x_k)</tex> в качестве двоичного представления числа.
+
[[Файл:Lupanov_scheme.png|550px|Иллюстрация частного случая представления Лупанова, описанного здесь]]
* '''Блок B''' {{---}} схемная реализация всех <tex>g_{ij}</tex>. Функцию <tex>g_{ij}</tex> можно реализовать как <tex dpi="145">\bigvee\limits_{\beta_l = 1} y_{il}</tex>, где <tex>y_{il}</tex> {{---}} выдал ли дешифратор "1" на <tex>l</tex>-м выходе <tex>i</tex>-й полосы.
+
 
* '''Блок C''' {{---}} схемная реализация всех <tex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</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> в качестве двоичного представления числа. '''''Результат работы схемы''''' {{---}} вывод мультиплексора.
+
* '''Блок 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 = [n - 2\log_2 n]</tex>; <tex>k = [\log_2 n]</tex>. Тогда число элементов в блоках
+
Положим <tex>s = \lfloor n - 2\log_2 n\rfloor</tex>; <tex>k = \lfloor\log_2 n\rfloor</tex>. Тогда число элементов в блоках
* <tex dpi="145">L_A \sim 2^k \lesssim \frac{2^n}{n}</tex>
+
* <tex>L_A = O(2^k) = O(2^{\log_2 n}) = O(n)</tex>
* <tex dpi="145">L_B \leq (s - 1) \cdot (t(1) + t(2) + ... + t(p)) < sp \cdot 2^s = 2^{k + s} = \frac{2^n}{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 dpi="145">L_C \sim p \cdot 2^{n - k} = \frac{2^n}{s} \sim \frac{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 dpi="145">L_D \sim 2^{n - k} = \frac{2^n}{n}</tex>
+
* <tex>L_D = O(2^{n - k}) = O\left(\dfrac{2^n}{n}\right)</tex>
  
Итого, имеем схему c числом элементов <tex>\sim \frac{2^n}{n}</tex>, откуда следует, что <tex>size_B (f) \lesssim \frac{2^n}{n}</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]
 
* [http://en.wikipedia.org/wiki/Multiplexer Wikipedia {{---}} Multiplexer]
== Литература ==
 
* Яблонский С.В. Введение в дискретную математику {{---}} М.:"Наука", 1986 {{---}} стр. 361
 
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория: Схемы из функциональных элементов ]]
 
[[Категория: Схемы из функциональных элементов ]]

Версия 00:47, 30 декабря 2018

Теорема:
Любая булева функция от [math]n[/math] аргументов [math]f(x_1, x_2, \ldots, x_n)[/math] в базисе [math]B = \{\neg, \lor, \land\}[/math] имеет схемную сложность [math]size_B (f) = O\left(\dfrac{2^n}{n}\right)[/math].

Представление функции

Рис. [math]1[/math]. Описываемая таблица истинности, разделённая на полосы

Поделим аргументы функции на два блока: первые [math]k[/math] и оставшиеся [math](n - k)[/math].

Для удобства дальнейших рассуждений представим булеву функцию в виде таблицы, изображённой на рис. [math]1[/math]. Строки индексируются значениями первых [math]k[/math] переменных, столбцы — значениями оставшихся [math](n - k)[/math]; таким образом, на пересечении столбца и строки находится значение функции для соответствующего набора аргументов.

Разделение на полосы

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

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

Определение:
Сорт некоторого столбца данной полосы — его класс эквивалентности по отношению поэлементного равенства столбцов данной полосы.

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

Функция для одной полосы

Рис. [math]2[/math]. Значения, возвращаемые функцией [math]g_{ij}[/math]

Пусть для некоторого [math]i[/math]

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

Тогда введём булеву функцию

[math]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{ otherwise} \end{cases}[/math]

Другими словами, если строка, соответствующая аргументам функции [math]x_1, x_2, \ldots, x_k[/math], находится в [math]i[/math]-й полосе, то функция возвращает значение, записанное в столбце сорта [math]j[/math] для этой строки. Если же эта строка находится в другой полосе, то функция вернёт [math]0[/math]. Иллюстрация принципа работы функции [math]g_{ij}[/math] приведена на рис. [math]2[/math].

Вывод исходной функции для фиксированной части параметров

Поскольку изначальный столбец [math](\sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_{n})[/math] складывается из столбцов соответствующих сортов в полосах, [math]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)[/math], где [math]j_i[/math] — номер сорта столбца полосы [math]i[/math], являющегося соответствующей частью столбца [math](\sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_{n})[/math].

Мультиплексор и демультиплексор

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

Определение:
Мультиплексор (англ. multiplexer) — логический элемент, получающий на вход
  • [math]2^n[/math] булевых значений;
  • [math]n[/math]-значное число [math]x[/math] в двоичном представлении
и возвращающий значение на [math]x[/math]-м входе.
Определение:
Демультиплексор (англ. demultiplexer) — логический элемент, получающий на вход
  • булево значение [math]z[/math];
  • [math]n[/math]-значное число [math]x[/math] в двоичном представлении
и выводящий [math]z[/math] на [math]x[/math]-й из своих [math]2^n[/math] выходов. На все остальные выходы элемент выдаёт [math]0[/math].
Мультиплексор слева, демультиплексор справа

Оба элемента представимы схемами с числом элементов [math]O(2^n)[/math] с помощью базиса [math]B[/math].

Доказательство

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

Иллюстрация частного случая представления Лупанова, описанного здесь

Для удобства поделим схему на блоки:

  • Блок A — демультиплексор, которому на вход подали [math]1[/math] и [math](x_1, x_2, \ldots, 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] — выдал ли демультиплексор [math]1[/math] на [math]l[/math]-м выходе [math]i[/math]-й полосы.
  • Блок C — схемная реализация всех [math]f(x_1, x_2, \ldots, x_k, \sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_n)[/math]. (здесь [math]\sigma_i[/math] - фиксированные параметры, см. п. [math]3.1[/math])
  • Блок D — мультиплексор, получающий на вход все [math]f(x_1, x_2, \ldots, x_k, \sigma_{k + 1}, \sigma_{k + 2}, \ldots, \sigma_n)[/math] и параметры функции [math]x_{k + 1}, x_{k + 2}, \ldots, x_n[/math] в качестве двоичного представления числа. Результат работы схемы — вывод мультиплексора.

Положим [math]s = \lfloor n - 2\log_2 n\rfloor[/math]; [math]k = \lfloor\log_2 n\rfloor[/math]. Тогда число элементов в блоках

  • [math]L_A = O(2^k) = O(2^{\log_2 n}) = O(n)[/math]
  • [math]L_B \leqslant (s - 1) \cdot (t(1) + t(2) + \ldots + t(p)) \lt sp \cdot 2^s = n \cdot \dfrac{2^n}{n^2} = \dfrac{2^n}{n}[/math]
  • [math]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)[/math]
  • [math]L_D = O(2^{n - k}) = O\left(\dfrac{2^n}{n}\right)[/math]

Итого, имеем схему c числом элементов [math]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)[/math], откуда следует, что [math]size_B (f) = O\left(\dfrac{2^n}{n}\right)[/math], что и требовалось доказать.

См. также


Источник информации

  • Яблонский С.В. Введение в дискретную математику — М.:"Наука", 1986 — стр. 361
  • Wikipedia — Multiplexer