75
правок
Изменения
→Доказательство: дописал
* '''Блок A''' - дешифратор, которому на вход подали 1 и <math>(x_1, x_2, ..., x_k)</math> в качестве двоичного представления числа.
Число элементов <math>L_A \sim 2^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>-й полосы.
Число элементов <math>L_B \leq (s - 1) \cdot (t(1) + t(2) + ... + t(p)) < sp \cdot 2^{s}</math>
* '''Блок C''' - схемная реализация всех <math>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</math>.
Число элементов <math>L_C \sim p \cdot 2^{n - k} = \frac{2^n}{s}</math>* '''Блок D''' - мультиплексор, получающий на вход все <math>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</math> и параметры функции <math>x_{k + 1}, x_{k + 2}, ..., x_n</math> в качестве двоичного представления числа. Число элементов <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^{k + s} \leq \frac{2^n}{n}</math>* <math>L_C \sim p \cdot 2^{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> Итого, имеем схему с итоговым числом элементов <math>\sim \frac{2^n}{n}</math>, откуда следует, что <math>size_B (f) \lesssim \frac{2^n}{n}</math>, '''ч.т.д.'''
