Изменения
Нет описания правки
# Булева функция $f(x_1, x_2, \ldots, x_n)$ называется форсируемой, если существует такое назначение $x_i=const$ , что для любых значений других переменных значение функции является константой. Например, $x_1 \wedge x_2$ является форсируемой, поскольку при $x_1 = 0$ значение функции равно 0 для любого значения $x_2$. Для каждой функции от двух переменных определите, является ли она форсируемой.
# Булева функция называется симметричной, если ее значение не меняется при любой перестановке ее переменных. Сколько существует симметричных функций от $n$ переменных?
# Игра "два шага вперед, один назад". Задана булева функция от $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$.
# Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)=x_1\oplus x_2\oplus \ldots\oplus x_n$.
# Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ не содержит двух единиц подряд.
# Проанализируйте игру "два шага вперед, один назад" для значений $n$ от 2 до 9 на функции $f(x_1, \ldots, x_n)$, равной 1, если строка $x_1x_2\ldots x_n$ представляет собой (возможно дополненную ведущими нулями) двоичную запись простого числа.
# Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
# Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
# Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов и глубиной $O(\log n)$.
# Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
# Докажите, что не существует схемы константной глубины для сложения.
# Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.
</wikitex>
