75
правок
Изменения
продолжаем перечитывать рецензию
== Представление функции ==
[[Файл:Lupanov fig1.png|330px450px|thumb|right|Рис. 1. Описываемая таблица истинности, разделённая на полосы]]
Поделим аргументы функции на два блока: первые <tex>k</tex> и оставшиеся <tex>(n - k)</tex>.
{{
Определение|definition=
'''Сорт''' столбца полосы {{---}} [[Отношение эквивалентности#Классы эквивалентности | класс эквивалентности]] среди столбцов одной полосы, к которому рассматриваемый столбец принадлежит (два столбца [[Отношение эквивалентности | эквивалентны]], если совпадают по значениям).
}}
Число сортов столбцов <tex>i</tex>-й полосы обозначим как <tex>t(i)</tex>. Понятно, что для любой полосы <tex>t(i) \leq 2^s</tex> (для последней <tex>t(p) \leq 2^{s'}</tex>).
{{
Определение|definition=
'''Мультиплексор''' (''англ.'' multiplexer) {{---}} логический элемент, получающий на вход
* <tex>2^n</tex> булевых значений;
* <tex>n</tex>-значное число <tex>x</tex> в двоичном представлении
}}{{
Определение|definition=
'''Дешифратор''' (или демультиплексор, ''англ.'' demultiplexer) {{---}} логический элемент, получающий на вход
* булево значение <tex>z</tex>;
* <tex>n</tex>-значное число <tex>x</tex> в двоичном представлении
}}
{|
|[[Файл:Mux_demux.png|500px|thumb|right|Мультиплексор слева, дешифратор справа]]
|}
== Доказательство ==
* '''Блок A''' {{---}} дешифратор, которому на вход подали 1 и <tex>(x_1, x_2, ..., 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> {{---}} выдал ли дешифратор "1" на <tex>l</tex>-м выходе <tex>i</tex>-й полосы.
