Изменения
Нет описания правки
# КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
# Расссмотрим функцию $f$, построим ее СДНФ. Заменим в этой формуле все $\vee$ на $\wedge$ и наоборот. Получится СКНФ некоторой функции $g$. Для каких функций $f$ выполнено $f=g$?
# Для каждого класса Поста проверьте, существует ли функция, которая лежит в этом классе Поста, но не лежит ни в одном из четырех других.
# Для каждого класса Поста проверьте, существует ли функция, которая не лежит в этом классе Поста, но лежит в четырех остальных.
# Будем говорить, что функция существенно зависит от переменной $x_i$, если существует два набора аргументов, различающихся только значением $x_i$, на которых функция принимает различные значения. Сколько существует булевых функций от $n$ аргументов, существенно зависящих от всех аргументов? Достаточно привести рекуррентную формулу.
# Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая лежит во всех 5 классах Поста.
# Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая не лежит ни в одном классе Поста.
# Булева функция $f(x_1, x_2, \ldots, x_n)$ называется форсируемой, если существует такое назначение $x_i=const$ , что для любых значений других переменных значение функции является константой. Например, $x_1 \wedge x_2$ является форсируемой, поскольку при $x_1 = 0$ значение функции равно 0 для любого значения $x_2$. Для каждой функции от двух переменных определите, является ли она форсируемой.
# Булева функция называется симметричной, если ее значение не меняется при любой перестановке ее переменных. Сколько существует симметричных функций от $n$ переменных?
# Какие симметричные булевы функции являются пороговыми?
# Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций
# Докажите, что любую монотонную функцию можно выразить через "и", "или", 0 и 1.
# Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану
# Говорят, что формула находится в 2-КНФ (или форме Крома). если она имеет вид $(t_{11}\vee t_{12})\wedge(t_{21}\vee t_{22})\wedge\ldots$, где $t_{ij}$ представляет собой либо переменную, либо ее отрицание (в каждом дизъюнкте ровно два терма). Докажите, что если булеву функцию $f$ можно задать в форме Крома (в виде 2-КНФ), то выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = f(z_1, ..., z_n) = 1$ $\Rightarrow f(\langle x_1, y_1, z_1\rangle, ..., \langle x_n, y_n, z_n \rangle) = 1$
# Докажите, что если выполнено следствие: $f(x_1, ..., x_n) = f(y_1, ..., y_n) = f(z_1, ..., z_n) = 1$ $\Rightarrow f(\langle x_1, y_1, z_1\rangle, ..., \langle x_n, y_n, z_n \rangle) = 1$, то булеву функцию $f$ можно задать в форме Крома.
# Докажите, что если булеву функцию $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$ можно задать в форме Хорна
# Докажите, что $x_0\oplus x_1\oplus\ldots\oplus x_{2m} = \langle \neg x_0,s_1,s_2,\ldots,s_{2m}\rangle$, где $s_j=\langle x_0,x_j,x_{j+1},\ldots,x_{j+m-1},\neg x_{j+m},\neg x_{j+m+1},\ldots,\neg x_{j+2m-1}\rangle$, для удобства $x_{2m+k}$ обозначет то же, что и $x_k$ для $k \ge 1$.
# Докажите, что биномиальный коэффициент $C_n^k$ нечетен тогда и только тогда, когда в двоичной записи $k$ единицы стоят только на тех позициях, где в двоичной записи $n$ также находятся единицы (иначе говоря, двоичная запись $k$ доминируется двоичной записью $n$ как двоичным вектором).
# Докажите "метод треугольника" построения полинома Жегалкина по таблице истинности.
