Изменения
Нет описания правки
# Транзитивный остов. Задано антисимметричное транзитивное отношение $R$ на $X$. Предложите полиномиальный алгоритм построения отношения $S$, такого что $S^+=R$, причем в $S$ содержится минимальное число пар элементов.
# В предыдущем задании требование транзитивности опустить нельзя. Задано антисимметричное отношение $R$ на $X$. Докажите, что если существует полиномиальный алгоритм построения отношения $S$, такого что $S \subset R$ и $S^+=R^+$, причем в $S$ содержится минимальное число пар элементов, то можно проверить, есть ли в графе гамильтонов цикл (цикл, проходящий по каждой вершине графа ровно один раз) за полиномиальное время.
# СКНФ. Будем называть формулу для функции совершенной конъюнктивной нормальной формой, если ее эта формула является конъюнкцией клозов, каждый из которых представляет дизъюнкцию переменных и их отрицаний, причем каждая переменная встречается в каждом клозе ровно один раз. Докажите, что любую функцию, кроме тождественной 1, можно представить в виде СКНФ.
# Стрелка Пирcа (NOR) - булева функция $a \downarrow b = \neg (a \vee b)$. Выразите в явном виде ""и"", ""или"" и ""не"" через стрелку Пирса
# Штрих Шеффера (NAND) - булева функция $a \uparrow b = \neg (a \wedge b)$. Выразите в явном виде ""и"", ""или"" и ""не"" через штрих Шеффера
# Функция $f$ называется самодвойственной, если $f(\neg x_1, \ldots, \neg x_n) = \neg f(x_1, \ldots, x_n)$. Сколько существует самодвойственных функций от $n$ аргументов?
# Булева функция называется пороговой, если $f(x_1, x_2, \ldots, x_n) = 1$ тогда и только тогда, когда $a_1x_1+a_2x_2+\ldots+a_nx_n \ge b$, где $a_i$ и $b$ - вещественные числа. Докажите, что ""и"", ""или"", ""не"" - пороговые функции.
# Приведите пример непороговой функции
# Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{x\oplus y, x = y\}$?
# Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{x\to y, {\mathbf 0}\}$?
# Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{\langle xyz\rangle, \neg x\}$?
# Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{{\mathbf 0}, \langle xyz\rangle, \neg x\}$?
# Можно ли выразить ""и"" через ""или""?
# Можно ли выразить $\oplus$ через $=$?
# Медиана $2n+1$ булевского значения равна 1 если и только если среди аргументов больше 1. Выразите медиану 5 через медиану 3
# Выразите медиану $2n+1$ через медиану 3
# Рассмотрим булеву функцию $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$
# КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
