Изменения

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