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

Материал из Викиконспекты
Перейти к: навигация, поиск

<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$ - отношение на $A$. Рассмотрим $Tr(R)$ - пересечение всех транзитивных отношений на $A$, содержащих $R$. Докажите, что $Tr(R) = R^{+}$.
  12. Пусть $R$ - транзитивное антисимметричное отношение. Предложите способ за полиномиальное время построить минимальное отношение $S$, такое что $S^+ = R$.
  13. Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?
  14. В каком случае транзитивное замыкание отношения будет отношением эквивалентности?
  15. В каком случае транзитивное замыкание отношения будет отношением частичного порядка?
  16. Является ли пара $\{x\to y, \neg x\}$ базисом?
  17. Является ли набор $\{x \to y, \langle xyz\rangle, \neg x\}$ базисом?
  18. Является ли набор $\{{\mathbf 0}, \langle xyz \rangle, \neg x\}$ базисом?
  19. Можно ли выразить "и" через "или"?
  20. Выразите медиану 5 через медиану 3
  21. Выразите медиану $2n+1$ через медиану 3
  22. Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану
  23. Докажите, что любую функцию, кроме тождественной единицы, можно записать в СКНФ
  24. Докажите, что любую функцию от $n$ переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем $2^n\cdot poly(n)$, где $poly(n)$ - полином, общий для всех функций
  25. Булева функция называется пороговой, если $f(x_1, x_2, \ldots, x_n) = 1$ тогда и только тогда, когда $a_1x_1+a_2x_2+\ldots+a_nx_n \ge b$, где $a_i$ и $b$ - вещественные числа. Докажите, что "и" и "или" - пороговые функции.
  26. Приведите пример непороговой функции
  27. Рассмотрим булеву функцию $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$

</wikitex>