Изменения
Нет описания правки
# Докажите, что если булеву функцию $f$ можно задать в форме Хорна, то выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = 1 \Rightarrow f(x_1\wedge y_1, ..., x_n \wedge y_n) = 1$
# Докажите, что если выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = 1 \Rightarrow f(x_1\wedge y_1, ..., x_n \wedge y_n) = 1$, то булеву функцию $f$ можно задать в форме Хорна
# Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
# Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
# Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов.
# Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$.
# Докажите, что не существует схем константной глубины для функций $x_1 \oplus ... \oplus x_n$.
# Докажите, что не существует схемы константной глубины для сложения.
# Постройте схему из функциональных элементов с тремя входами: $x, y, z$ и одним выходом. Значение на выходе равно $x$, если $z=0$ и $y$, если $x=1$. Используйте базис из всех не более чем бинарных функций.
# Мультиплексор - функциональная схема с $n = 2^k + k$ и одним выходом. Обозначим первые $2^k$ входов как $x_0, x_1, \ldots, x_{2^k-1}$, а оставшиеся $k$ как $y_0, y_1, \ldots, y_{k-1}$. Выход мультиплексора равен $x_i$, где $i$ --- число, двоичное представление которого подано на входы $y_0, y_1, \ldots, y_{k-1}$. Постройте схему линейного от $n$ размера для мультиплексора.
# Дешифратор - функциональная схема с $k + 1$ входом и $n = 2^k$ выходами. Обозначим первые $k$ входов как $y_0, y_1, \ldots, y_{k-1}$, а последний как $z$. Обозначим выходы дешифратора как $x_0, x_1, \ldots, x_{2^k-1}$. Значение на выходах дешифратора 0 на всех выходах, кроме $x_i$, где $i$ --- число, двоичное представление которого подано на входы $y_0, y_1, \ldots, y_{k-1}$, а на выходе $x_i$ равно значению $z$. Постройте схему линейного размера для дешифратора.
# Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
</wikitex>
