Изменения

Тогда давайте построим дешифратор <tex>n</tex>-to-<tex>2^n</tex> (это значит, что у дешифратора имеется <tex>n</tex> входов и <tex>2^n</tex> выходов), на вход ему подадим значения на входах <tex>s_0</tex>, <tex>s_1</tex>, <tex>\ldots</tex>, <tex>s_{n-1}</tex>, а выходы этого дешифратора обозначим как <tex>y_0</tex>, <tex>y_1</tex>, <tex>\ldots</tex>, <tex>y_{2^n-1}</tex>, а потом с помощью гейта <tex>AND</tex> соединим выход <tex>y_i</tex> дешифратора с входом <tex>x_i</tex> мультиплексора, потом соединим все гейты с выходом <tex>z</tex> с помощью гейта <tex>OR</tex>. Давайте разберёмся, почему эта схема правильная: очевидно, что если входы <tex>s_0</tex>, <tex>s_1</tex>, <tex>\ldots</tex> <tex>s_{n-1}</tex> кодируют вход <tex>i</tex>, то это значит, что только <tex>y_i</tex> выход дешифратора будет иметь <tex>1</tex>, тогда как на остальных выходах будет <tex>0</tex>, значит, что значения на входах <tex>x_0</tex>, <tex>x_1</tex>, <tex>\ldots</tex>, <tex>x_{i-1}</tex>, <tex>x_{i+1}</tex>, <tex>\ldots</tex>, <tex>x_{2^n-1}</tex> на ответ никак повлиять не могут. Теперь, если на входе <tex>x_i</tex> было <tex>0</tex>, то на выходе <tex>z</tex> будет <tex>0</tex>, если же на входе <tex>x_i</tex> был <tex>1</tex>, то на выходе <tex>z</tex> будет <tex>1</tex>.