Список заданий по ДМ 2023 осень

1. Постройте пример рефлексивного, симметричного, но не транзитивного отношения
2. Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения
3. Постройте пример отношения, которое не симметрично и не антисимметрично
4. Постройте пример отношения, которое симметрично и антисимметрично
5. Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.
6. Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение?
7. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?
8. Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричным их а) объединение? б) пересечение?
9. Композиция отношений $R$ и $S$ это отношение $T=RS$, где $xTy$, если найдется $z$, такой что $xRz$ и $zSy$. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивной их композиция?
10. Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричной их композиция?
11. Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?
12. Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность
13. Докажите, что $(RS)^{-1} = S^{-1}R^{-1}$.
14. Композицией функций $f : A \to B$ и $g : B \to C$ называется $g \circ f$, что $(g \circ f)(x) = g(f(x))$. Докажите, если $f$ и $g$ инъективны/сюръективны/биективны, то то же свойство верно и для их композиции.
15. Отношение $R \subseteq A \times B$ называется функциональным, если $R^{-1} R \subseteq I$. Правда ли, что если $R \subseteq A \times B$ и $S \subseteq B \times C$ функциональны, то $RS \subseteq A \times C$ функционально?
16. Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $a + d = b + c$ на ${\mathbb N} \times {\mathbb N}$ отношением эквивалентности?
17. Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?
18. Может ли отношение частичного порядка быть отношением эквивалентности? Если да, то в каких случаях?
19. Можно ли в определении отношения эквивалентности убрать требование рефлексивности отношения, потому что оно следует из симметричности и транзитивности?
20. Для решения этой серии вам необходимо самостоятельно изучить понятие СДНФ. В этой задаче вам необходимо построить СКНФ. Будем называть формулу для функции совершенной конъюнктивной нормальной формой, если ее эта формула является конъюнкцией клозов, каждый из которых представляет дизъюнкцию переменных и их отрицаний, причем каждая переменная встречается в каждом клозе ровно один раз. Докажите, что любую функцию, кроме тождественной 1, можно представить в виде СКНФ.
21. Стрелка Пирcа (NOR) - булева функция $a \downarrow b = \neg (a \vee b)$. Выразите в явном виде ""и"", ""или"" и ""не"" через стрелку Пирса
22. Штрих Шеффера (NAND) - булева функция $a \uparrow b = \neg (a \wedge b)$. Выразите в явном виде ""и"", ""или"" и ""не"" через штрих Шеффера
23. Функция $f$ называется самодвойственной, если $f(\neg x_1, \ldots, \neg x_n) = \neg f(x_1, \ldots, x_n)$. Сколько существует самодвойственных функций от $n$ аргументов?
24. Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{x\oplus y, x = y\}$?
25. Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{x\to y, {\mathbf 0}\}$?
26. Медиана $\langle xyz\rangle$, также известная как функция большинства или функция голосования, равна 1, если из трех ее аргументов хотя бы два равны 1. Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{\langle xyz\rangle, \neg x\}$?
27. Можно ли ""и"", ""или"" и ""не"" выразить через функции из множества $\{{\mathbf 0}, \langle xyz\rangle, \neg x\}$?
28. Можно ли выразить ""и"" через ""или""?
29. Можно ли выразить $\oplus$ через $=$?
30. Медиана $2n+1$ булевского значения равна 1 если и только если среди аргументов больше 1. Выразите медиану 5 через медиану 3
31. Выразите медиану $2n+1$ через медиану 3
32. Булева функция называется пороговой, если $f(x_1, x_2, \ldots, x_n) = 1$ тогда и только тогда, когда $a_1x_1+a_2x_2+\ldots+a_nx_n \ge b$, где $a_i$ и $b$ - вещественные числа. Докажите, что ""и"", ""или"", ""не"" - пороговые функции.
33. Приведите пример непороговой функции. Поясните, почему из предыдущего номера не следует, что любая функция является пороговой.
34. Рассмотрим булеву функцию $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$
35. КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
36. Расссмотрим функцию $f$, построим ее СДНФ. Заменим в этой формуле все $\vee$ на $\wedge$ и наоборот. Получится СКНФ некоторой функции $g$. Для каких функций $f$ выполнено $f=g$?
37. Для каждого класса Поста проверьте, существует ли функция, которая лежит в этом классе Поста, но не лежит ни в одном из четырех других.
38. Для каждого класса Поста проверьте, существует ли функция, которая не лежит в этом классе Поста, но лежит в четырех остальных.
39. Будем говорить, что функция существенно зависит от переменной $x_i$, если существует два набора аргументов, различающихся только значением $x_i$, на которых функция принимает различные значения. Сколько существует булевых функций от $n$ аргументов, существенно зависящих от всех аргументов? Достаточно привести рекуррентную формулу.
40. Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая лежит во всех 5 классах Поста.
41. Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая не лежит ни в одном классе Поста.
42. Булева функция $f(x_1, x_2, \ldots, x_n)$ называется форсируемой, если существует такое назначение $x_i=const$ , что для любых значений других переменных значение функции является константой. Например, $x_1 \wedge x_2$ является форсируемой, поскольку при $x_1 = 0$ значение функции равно 0 для любого значения $x_2$. Для каждой функции от двух переменных определите, является ли она форсируемой.
43. Булева функция называется симметричной, если ее значение не меняется при любой перестановке ее переменных. Сколько существует симметричных функций от $n$ переменных?
44. Какие симметричные булевы функции являются пороговыми?
45. Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций
46. Докажите, что любую монотонную функцию можно выразить через "и", "или", 0 и 1.
47. Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану
48. Говорят, что формула находится в 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$
49. Докажите, что если выполнено следствие: $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$ можно задать в форме Крома.
50. Докажите, что если булеву функцию $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$
51. Докажите, что если выполнено следствие: $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$ можно задать в форме Хорна
52. Докажите, что $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$.
53. Докажите, что биномиальный коэффициент $C_n^k$ нечетен тогда и только тогда, когда в двоичной записи $k$ единицы стоят только на тех позициях, где в двоичной записи $n$ также находятся единицы (иначе говоря, двоичная запись $k$ доминируется двоичной записью $n$ как двоичным вектором).
54. Изучите и докажите "метод треугольника" построения полинома Жегалкина по таблице истинности.
55. Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
56. Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$, используя не более 8 элементов. Элемент для ""не"" также считается.
57. Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов и глубиной $O(\log n)$.
58. Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(n2^n)$ элементов.
59. Докажите, что любую булеву функцию от $n$ аргументов можно представить схемой из функциональных элементов, содержащей $O(2^n)$ элементов.
60. Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
61. Докажите формулу разложения Шеннона по переменной $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)$
62. Для булевых векторов $\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)$.
63. Докажите равенства $\alpha \wedge(\beta\vee\gamma)=(\alpha \wedge\beta)\vee(\alpha\wedge\gamma)$ и $\alpha \vee(\beta\wedge\gamma)=(\alpha \vee\beta)\wedge(\alpha\vee\gamma)$.
64. Будем говорить, что булевый вектор $\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$ является частичным порядком.
65. Докажите. что $\alpha$ префиксно мажорирует $\beta$ тогда и только тогда, когда $\overline{\beta}$ префиксно мажорирует $\overline{\alpha}$ ($\overline{\alpha}$ означает побитовую инверсию).
66. Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlywedge \beta$, такой что $((\alpha \ge_p \gamma) \wedge (\beta \ge_p \gamma)) \Leftrightarrow (\alpha\curlywedge\beta)\ge_p\gamma$. Предложите алгоритм построения такого вектора.
67. Докажите, что для любых двух векторов $\alpha$ и $\beta$ существует и единственный вектор $\alpha \curlyvee \beta$, такой что $((\gamma \ge_p \alpha) \wedge (\gamma \ge_p \beta)) \Leftrightarrow \gamma\ge_p(\alpha\curlyvee\beta)$. Предложите алгоритм построения такого вектора.
68. Докажите равенства $\alpha \curlywedge(\beta\curlyvee\gamma)=(\alpha \curlywedge\beta)\curlyvee(\alpha\curlywedge\gamma)$ и $\alpha \curlyvee(\beta\curlywedge\gamma)=(\alpha \curlyvee\beta)\curlywedge(\alpha\curlyvee\gamma)$.
69. Будем называть функцию $f$ регулярной, если из $x \le_p y$ следует, что $f(x) \le f(y)$. Как связаны регулярные и монотонные функции?
70. Докажите, что если функция $f$ является пороговой и $a_1 \ge a_2 \ge \ldots \ge a_n \ge 0$, то $f$ является регулярной.
71. Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(3^n)$.
72. Опишите алгоритм, выполняющий преобразование Мебиуса, который работает за время $O(2^n n)$.
73. Будем кодировать k, g и p двумя булевыми значениями, 00 для k, 11 для g и 01 или 10 для p. Разработайте в явном виде схему для композиции действия на перенос. У нее должно быть 4 булевых входа (два входных действия) и 2 булевых выхода - действие-композиция. Используйте любой удобный базис.
74. Докажите, что для суммы $n$-битных чисел не существует схемы глубиной $O(1)$.
75. Докажите, что для произведения $n$-битных чисел не существует схемы глубиной $O(1)$.
76. Докажите, что не существует схемы глубиной $O(1)$, которая проверяет, будет ли переполнение, при суммировании двух $n$-битных чисел.
77. Докажите, что для функции ""большинство из $2n+1$"" существует схема из функциональных элементов глубины $O(\log n)$
78. Мультиплексором называется схема, которая имеет $2^n+n$ входов и один выход. Обозначим входы как $x_0, x_1, \ldots, x_{2^n-1}, y_0, y_1, \ldots, y_{n-1}$. На выход подается то же, что подается на вход $x_i$, где $i$ - двоичное число, которое кодируется входами $y_0, \ldots, y_{n-1}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для мультиплексора.
79. Дешифратором называется схема, которая имеет $n+1$ входов и $2^n$ выходов. Обозначим входы как $y_0, y_1, \ldots, y_{n-1}, x$, а выходы как $z_0, z_1, \ldots, z_{2^n-1}$. На все выходы подается 0, а на выход $z_i$ то же, что подается на вход $x$, где $i$ - двоичное число, которое кодируется входами $y_0, \ldots, y_{n-1}$. Постройте схему линейного (от суммарного количества входов и выходов) размера для дешифратора.
80. Пусть $n = 2^m - 1$, задано $n$ булевых входов $x_1, x_2, \ldots, x_n$. Постройте схему размера $O(n)$ и глубины $O(m)$, которая по этим входам выдает $m$ выходов $y_0, y_1, \ldots, y_{m-1}$, которые задают двоичное число $k = \overline{y_{m-1}y_{m-2}\ldots y_1 y_0}$, такое что $k = 0$, если все входы равны $0$, иначе $k = \max\{j\,|\,x_j = 1\}$.
81. Постройте схему, которая имеет $n$ входов $x_1, x_2, \ldots, x_n$ и $n$ выходов $y_1, \ldots, y_n$, где $y_k = x_1 \wedge x_2 \wedge \ldots \wedge x_{k-1}\wedge x_{k+1}\wedge \ldots \wedge x_n$ ($k$-й выход равен конъюнкции всех входов, кроме $k$-го). Схема должна использовать базис $\{\wedge, \vee, \neg\}$ и содержать не более $3n$ функциональных элементов.
82. Предложите схему для сравнения целых чисел без знака глубины $\log n$.
83. Предложите схему для сравнения целых чисел со знаком в дополнительном коде глубины $\log n$.
84. В матричном умножителе вместо элементов ""и"" поставили элементы ""или"". Можно ли получить с помощью этого умножителя произведение чисел, используя $O(n)$ дополнительных элементов? Вы можете добавить эти элементы в произвольные места в схеме для умножителя.
85. Будем интерпретировать битовые строки длины $n$ как целые числа с соответствующей двоичной записью. Заданы $n$-битные числа $v_0 < v_1 < \ldots < v_{m-1}$. Предложите алгоритм за $O(m)$, который по заданным числам и числу $j$ находит все такие пары индексов $i, k$, что $v_i \oplus 2^j = v_k$. Считайте, что операции с числами выполняются за $O(1)$.
86. Докажите, что $(x \oplus 3x) \wedge ((x \oplus 3x) >> 1)=0$, где $>>$ означает битовый сдвиг вправо.
87. Предложите алгоритм, который для заданного $d \ge 3$ вычисляет $x^y\bmod 2^d$ для заданных $x$ и $y$, где $x$ нечетен, используя $O(d)$ сложений и битовых операций и одно умножение на $y$.
88. Для каких бинарных коммутативных операций $\circ$ выполнен распределительный закон для медианы $w\circ\langle xyz \rangle = \langle x\circ w, y \circ w, z \circ w\rangle$?
89. Можно ли выразить медиану трех через медиану пяти?
90. Будем называть длиной ДНФ количество вхождений перменных в нее. Например, $(x\wedge y)\vee (\neg x \wedge z)$ имеет длину 4. Постройте ДНФ минимальной длины для функции $x_1 \oplus x_2 \oplus \ldots \oplus x_n$.