Изменения
Нет описания правки
# Приведите пример непороговой функции
# Рассмотрим булеву функцию $f$. Обозначим как $N(f)$ число наборов аргументов, на которых $f$ равна 1. Например, $N(\vee) = 3$. Обозначим как $\Sigma(f)$ сумму всех наборов аргументов, на которых $f$ равна 1 как векторов. Например, $\Sigma(\vee) = (2, 2)$. Докажите, что если для пороговой функции $f$ и функции $g$ выполнено $N(f) = N(g)$ и $\Sigma(f) = \Sigma(g)$, то $f = g$
# Постройте двойственную функцию для каждой функции от 2 аргументов.
# Сколько существует самодвойственных функций от $n$ аргуметов?
# Будем говорить, что функция существенно зависит от переменной $x_i$, если существует два набора аргументов, различающихся только значением $x_i$, на которых функция принимает различные значения. Сколько существует булевых функций от $n$ аргументов, существенно зависящих от всех аргументов? Достаточно привести рекуррентную формулу.
# Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая лежит во всех 5 классах Поста.
# Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая не лежит ни в одном классе Поста.
# Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций
# Докажите, что любую монотонную функцию можно выразить через "и", "или", 0 и 1.
# Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану
# Игра "два шага вперед, один назад". Задана булева функция от $n$ аргументов $f(x_1, \ldots, x_n)$. Играют два игрока: 0 и 1. Игроки делают ходы по очереди. Для хода используется вспомогательное значение $m$, исходно равное 0, кроме того исходно все значения переменных не определены. Ход заключается в следующем. Игрок либо увеличивает $m$ на 2, либо уменьшает на 1. После этого действия значение $m$ должно удовлетворять неравенству $1 \le m \le n$. Затем, если значение $x_m$ не определено, то игрок присваивает переменной $x_m$ значение на свое усмотрение. Если же значение $x_m$ определено, то оно меняется на противоположное. Игра заканчивается, когда все значения определены. Если значение функции $f$ на получившемся наборе переменных равно 1, то выигрывает 1, иначе выигрывает 0. Проанализируйте описанную игру для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ лексикографически строго меньше строки $x_nx_{n-1}\ldots x_1$.
