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

<wikitex>

Дискретная математика, алгоритмы и структуры данных, 1 семестр

1. Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение?
2. Пусть $R$ и $S$ - симметричные отношения на A. Будет ли симметричным их а) объединение? б) пересечение?
3. Пусть $R$ и $S$ - транзитивные отношения на A. Будет ли транзитивным их а) объединение? б) пересечение?
4. Пусть $R$ и $S$ - антисимметричные отношения на A. Будет ли антисимметричным их а) объединение? б) пересечение?
5. Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?
6. Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность
7. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их композиция?
8. Пусть $R$ и $S$ - антисимметричные отношения на A. Будет ли антисимметричным их композиция?
9. Постройте пример рефлексивного, симметричного, но не транзитивного отношения
10. Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения
11. Пусть $R$ - транзитивное антисимметричное отношение. Постройте минимальное отношение $S$, такое что $S^+ = R$
12. Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?
13. Является ли пара $\{x\to y, \neg x\}$ базисом?
14. Является ли набор $\{x \to y, \langle xyz\rangle, \neg x\}$ базисом?
15. Является ли набор $\{{\mathbf 0}, \langle xyz \rangle, \neg x\}$ базисом?
16. Можно ли выразить "и" через "или"?
17. Выразите медиану 5 через медиану 3
18. Выразите медиану $2n+1$ через медиану 3
19. Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану
20. Докажите, что любую функцию, кроме тождественной единицы, можно записать в СКНФ
21. Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций
22. Булева функция называется пороговой, если $f(x_1, x_2, \ldots, x_n) = 1$ тогда и только тогда, когда $a_1x_1+a_2x_2+\ldots+a_nx_n \ge b$, где $a_i$ и $b$ - вещественные числа. Докажите, что "и" и "или" - пороговые функции.
23. Приведите пример непороговой функции
24. Рассмотрим булеву функцию $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$
25. Говорят, что формула имеет вид 2-КНФ, если она имеет вид $(t_{11}\vee t_{12})\wedge(t_{21}\vee t_{22})\wedge\ldots$, где $t_{ij}$ представляет собой либо переменную, либо ее отрицание (в каждом дизъюнкте ровно два терма). Предложите полиномиальный алгоритм проверки, что формула, заданная в 2-КНФ имеет набор значений переменных, на которых она имеет значение 1.
26. КНФ называется КНФ Хорна, если в каждом дизъюнкте не более одной переменной находится без отрицания. Пример: $x\wedge(x \vee \neg y \vee \neg z) \wedge (\neg x \vee \neg t)$. Предложите полиномиальный алгоритм проверки, что формула, заданная в форме КНФ Хорна имеет набор аргументов, на котором она равна 1.
27. Докажите, что если булеву функцию $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$
28. Докажите, что если выполнено следствие: $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$ можно задать в форме Крома.
29. Докажите, что если булеву функцию $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$
30. Докажите, что если выполнено следствие: $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$ можно задать в форме Хорна
31. Постройте схему из функциональных элементов для операции медиана трех над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
32. Постройте схему из функциональных элементов для операции $x \oplus y \oplus z$ над базисом $\{ \vee, \wedge, \neg\}$. Постарайтесь использовать минимальное число элементов.
33. Предложите способ построить схему для функции $x_1 \oplus ... \oplus x_n$ над базисом $\{ \vee, \wedge, \neg\}$ с линейным числом элементов.
34. Докажите, что не существует схем константной глубины для функций $x_1 \vee ... \vee x_n$, $x_1 \wedge ... \wedge x_n$, $x_1 \oplus ... \oplus x_n$.
35. Постройте схему линейного размера для мультиплексора.
36. Постройте схему линейного размера для дешифратора.
37. Что получится, если в матричном умножителе заменить элементы "and" на элементы "or"?
38. Докажите, что для функции "большинство из $2n+1$" существует схема из функциональных элементов глубины $O(\log n)$
39. Докажите, что для сложения не существует схемы глубины $O(1)$
40. Контактной схемой называется ориентированный ациклический граф, на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют контактами, а вершины - полюсами). Зафиксируем некоторые значения переменным. Тогда замкнутыми называются ребра, на которых записана 1, ребра, на которых записан 0, называются разомкнутыми. Зафиксируем две вершины $u$ и $v$. Тогда контактная схема вычисляет некоторую функцию $f$ между вершинами $u$ и $v$, равную 1 на тех наборах переменных, на которых между $u$ и $v$ есть путь по замкнутым ребрам. Постройте контактные схемы для функций "и", "или" и "не".
41. Постройте контактную схему для функции "xor".
42. Постройте контактную схему для функции медиана трех.
43. Докажите, что любую булеву функцию можно представить контактной схемой.
44. Постройте контактную схему "xor от $n$ переменных", содержащую $O(n)$ ребер.
45. Постройте контактную схему "большинство из $2n+1$ переменных", содержащую $O(n)$ ребер.
46. Постройте контактную схему, в которой для каждого из $2^n$ наборов конъюнкций переменных и их отрицаний есть пара вершин, между которыми реализуется эта конъюнкция, используя $O(2^n)$ ребер
47. Докажите, что любую функцию можно представить контактной схемой, содержащей $O(2^n)$ ребер

</wikitex>