Список заданий по ДМ 2021 осень — различия между версиями
(Пустой список ДЗ) |
|||
| Строка 1: | Строка 1: | ||
| − | + | # Постройте пример рефлексивного, симметричного, но не транзитивного отношения | |
| + | # Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения | ||
| + | # Постройте пример отношения, которое не симметрично и не антисимметрично | ||
| + | # Постройте пример отношения, которое симметрично и антисимметрично | ||
| + | # Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа. | ||
| + | # Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение? | ||
| + | # Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение? | ||
| + | # Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричным их а) объединение? б) пересечение? | ||
| + | # Напомним, что композиция отношений $R$ и $S$ это отношение $T=RS$, где $xTy$, если найдется $z$, такой что $xRz$ и $zSy$. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивной их композиция? | ||
| + | # Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричной их композиция? | ||
| + | # Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака? | ||
| + | # Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность | ||
| + | # Докажите, что $(RS)^{-1} = S^{-1}R^{-1}$. | ||
| + | # Композицией функций $f : A \to B$ и $g : B \to C$ называется $g \circ f$, что $(g \circ f)(x) = g(f(x))$. Докажите, если $f$ и $g$ инъективны/сюръективны/биективны, то то же свойство верно и для их композиции. | ||
| + | # Отношение $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$ функционально? | ||
| + | # Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $a + d = b + c$ на ${\mathbb N} \times {\mathbb N}$ отношением эквивалентности? | ||
| + | # Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности? | ||
| + | # Может ли отношение частичного порядка быть отношением эквивалентности? Если да, то в каких случаях? | ||
| + | # Можно ли в определении отношения эквивалентности убрать требование рефлексивности отношения, потому что оно следует из симметричности и транзитивности? | ||
Версия 21:21, 9 сентября 2021
- Постройте пример рефлексивного, симметричного, но не транзитивного отношения
- Постройте пример рефлексивного, антисимметричного, но не транзитивного отношения
- Постройте пример отношения, которое не симметрично и не антисимметрично
- Постройте пример отношения, которое симметрично и антисимметрично
- Пусть $R$ и $S$ - рефлексивные отношения на $A$. Будет ли рефлексивным их а) объединение? б) пересечение? В этом и следующих заданиях, если ответ отрицательный, при демонстрации контрпримера удобно использовать представление отношения в виде ориентированного графа.
- Пусть $R$ и $S$ - симметричные отношения на $A$. Будет ли симметричным их а) объединение? б) пересечение?
- Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивным их а) объединение? б) пересечение?
- Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричным их а) объединение? б) пересечение?
- Напомним, что композиция отношений $R$ и $S$ это отношение $T=RS$, где $xTy$, если найдется $z$, такой что $xRz$ и $zSy$. Пусть $R$ и $S$ - транзитивные отношения на $A$. Будет ли транзитивной их композиция?
- Пусть $R$ и $S$ - антисимметричные отношения на $A$. Будет ли антисимметричной их композиция?
- Определим $R^{-1}$ следующим образом: если $xRy$, то $yR^{-1}x$. Выполнено ли соотношение $RR^{-1} = I$, где $I$ - отношение равенства? Выполнен ли закон сложения степенией $R^iR^j=R^{i+j}$, если $i$ и $j$ разного знака?
- Пусть $R$ обладает свойством $X$. Будет ли обладать свойством $X$ отношение $R^{-1}$? Следует проанализировать $X$ - рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность
- Докажите, что $(RS)^{-1} = S^{-1}R^{-1}$.
- Композицией функций $f : A \to B$ и $g : B \to C$ называется $g \circ f$, что $(g \circ f)(x) = g(f(x))$. Докажите, если $f$ и $g$ инъективны/сюръективны/биективны, то то же свойство верно и для их композиции.
- Отношение $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$ функционально?
- Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $a + d = b + c$ на ${\mathbb N} \times {\mathbb N}$ отношением эквивалентности?
- Является ли отношение $R$, такое что $(a, b) R (c, d)$, если $ad = bc$ на ${\mathbb Z}^+ \times {\mathbb N}$ отношением эквивалентности?
- Может ли отношение частичного порядка быть отношением эквивалентности? Если да, то в каких случаях?
- Можно ли в определении отношения эквивалентности убрать требование рефлексивности отношения, потому что оно следует из симметричности и транзитивности?
