Изменения
Нет описания правки
# Докажите, что биномиальный коэффициент $C_n^k$ нечетен тогда и только тогда, когда в двоичной записи $k$ единицы стоят только на тех позициях, где в двоичной записи $n$ также находятся единицы (иначе говоря, двоичная запись $k$ доминируется двоичной записью $n$ как двоичным вектором).
# Докажите "метод треугольника" построения полинома Жегалкина по таблице истинности.
# Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
# Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$, используя не более 8 элементов. Элемент для "не" также считается.
# Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов и глубиной $O(\log n)$.
# Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
# Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(n2^n)$ элементов.
# Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.
# Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
# Докажите формулу разложения Шеннона по переменной $x$: $f(x, y_2, y_3, \ldots, y_n)=x\wedge f(1, y_2, y_3, \ldots, y_n)\vee \neg x\wedge f(0, y_2, y_3, \ldots, y_n)$
# Для булевых векторов $\alpha$ и $\beta$ обозначим как $\alpha\vee\beta$ побитовое $\vee$ этих векторов, аналогично введём $\alpha \wedge \beta$. Обозначим как $\succeq$ отношение доминирования на булевых векторах, $\alpha\succeq\beta$, если для всех $i$ выполнено $a_i\ge b_i$. Докажите, что $\alpha \wedge \beta$ удовлетворяет свойству, что $(\alpha \succeq\gamma)\wedge(\beta \succeq \gamma) \Leftrightarrow (\alpha\wedge\beta)\succeq \gamma$. Докажите, что $\alpha \vee \beta$ удовлетворяет свойству, что $\left((\gamma \succeq \alpha) \wedge (\gamma \succeq \beta)\right) \Leftrightarrow \gamma\succeq(\alpha\vee\beta)$.
# Докажите равенства $\alpha \wedge(\beta\vee\gamma)=(\alpha \wedge\beta)\vee(\alpha\wedge\gamma)$ и $\alpha \vee(\beta\wedge\gamma)=(\alpha \vee\beta)\wedge(\alpha\vee\gamma)$.
# Будем говорить, что булевый вектор $\alpha = (a_1, a_2, \ldots, a_n)$ префиксно мажорирует вектор $\beta = (b_1, b_2, \ldots, b_n)$, если для любого $k$ выполнено $a_1+\ldots+a_k \ge b_1+\ldots+b_k$ и писать $\alpha \ge_p \beta$. Докажите, что отношение $\ge_p$ является частичным порядком.
# Докажите. что $\alpha$ префиксно мажорирует $\beta$ тогда и только тогда, когда $\overline{\beta}$ префиксно мажорирует $\overline{\alpha}$ ($\overline{\alpha}$ означает побитовую инверсию).
# Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlywedge \beta$, такой что $((\alpha \ge_p \gamma) \wedge (\beta \ge_p \gamma)) \Leftrightarrow (\alpha\curlywedge\beta)\ge_p\gamma$. Предложите алгоритм построения такого вектора.
# Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlyvee \beta$, такой что $((\gamma \ge_p \alpha) \wedge (\gamma \ge_p \beta)) \Leftrightarrow \gamma\ge_p(\alpha\curlyvee\beta)$. Предложите алгоритм построения такого вектора.
# Докажите равенства $\alpha \curlywedge(\beta\curlyvee\gamma)=(\alpha \curlywedge\beta)\curlyvee(\alpha\curlywedge\gamma)$ и $\alpha \curlyvee(\beta\curlywedge\gamma)=(\alpha \curlyvee\beta)\curlywedge(\alpha\curlyvee\gamma)$.
# Будем называть функцию $f$ регулярной, если из $x \le_p y$ следует, что $f(x) \le f(y)$. Как связаны регулярные и монотонные функции?
# Докажите, что если функция $f$ является пороговой и $a_1 \ge a_2 \ge \ldots \ge a_n \ge 0$, то $f$ является регулярной.
# Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(3^n)$.
# Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(2^n n)$.
