Изменения

Давайте переберём всевозможные варианты значений на входах. Поскольку у нас $n$ входов, то отсюда следует, что всевозможных вариантов - $2^n$. Давайте будем строить такую построим логическую схему дешифратора рекурсивным способом: допустим, т.е. сначала построим дешифратор что мы построили схему для $n-1$ элемента, а потом сольём теперь попробуем слить $n$-ый элемент выход с предыдущими $n-1$ элементамивыходами. Допустим, что Для $n = 1$. Тогда очевидно, что всевозможных вариантов всего двасхема выглядит тривиальным образом: $s_0 = 0$ или $s_0 = 1$. Давайте от входа $s_0$ мы выведем отходят два провода, один из них, поканапрямую соединён с выходом $z_0$, не будем трогать, а другой соединим соединён с гейтом $NOT$. Если количество входов было равно $1$, то мы перебрали всевозможные варианты, т.е. давайте соединим провод без гейта $NOT$ с выходом $z_0$, а с гейтом гейт $NOT$ - соединён с выходом $z_1$. ДопустимОчевидно, что при $n \geqslant 2=1$у нас схема линейно зависит от количество входов и выходов. Тогда Теперь допустим, что мы построили дешифратор можем построить схему для $n-1$ элементавходов. Теперь сольём Тогда $n$-ый вход соединим с дешифратором для $n1-to-12$ входов. У такого , и потом соединим каждый выход дешифратора $2^{n-1}$ выходов. У входа $s_-to-{2^{n-1}}$ может быть два варианта значений: $0$ и с каждым выходом дешифратора $1$. Давайте поставим $-to-2^n$ с помощью гейтов $AND$ и , потом соединим эти соответствующие гейты соответственно с выходами $z_i$. Очевидно, что мы увеличил размер схемы по сравнению со схемой дешифратора для ${n-1}$-to-входа на ${2^{n$ гейтов и бесконечно малое, по сравнению с размером схемы для $n$ элементов, элементов дешифратора $1-1}}to-2$.