Бінарні відношення

1. Скільки існує різних відношень із множини $A$ у множину $B$, якщо $\vert A\vert = n$, $\vert B\vert = m$ (будемо говорити: $n$-множина i $m$-множина)?

2. Скільки є таких відношень $R$ із $n$-множини в $m$-множину, що

   1. $\forall x: \exists y: xRy$,

   2. $\forall y: \exists x: xRy$.

3. Яку особливість має граф відношення $R$ з $А$ в $В$, якщо:

   1. $xRy \land xRz \implies y = z$;

   2. $xRy \land zRz \implies x = z$;

   3. $\forall x: \exists y: xRy$;

   4. $\exists y: \forall x: xRy$;

   5. $\forall y: \exists x: xRy$;

   6. $\exists x: \forall y: xRy$;

   7. $\lnot \forall x: \exists y: xRy$;

   8. $\forall x: \lnot \exists y: xRy$;

   9. $\lnot \forall y: \exists x: xRy$;

   10. $\forall y: \lnot \exists x: xRy$;

   11. $\lnot \exists x: \forall y: xRy$;

   12. $\exists x: \lnot \forall y: xRy$.

4. Які з наведених нижче відношень у множині цілих чисел є рефлексивними, транзитивними, симетричними й антисиметричними:

   1. $x < y$;

   2. $x \le y$;

   3. $\vert x\vert = \vert y\vert$;

   4. $x + y = 0$;

   5. $\vert x\vert > y$;

   6. $\vert x\vert \ge y$;

   7. $x = y$;

   8. $x + 1 = y$;

   9. $\vert x - y\vert = 1$;

   10. $\vert x - y\vert \le 1$;

   11. $x$ ділиться на $y$;

   12. $x$ не ділиться на $y$.

5. Скільки існує різних рефлексивних, симетричних, антисиметричних відношень у $n$-елементній множині?

6. Довести, що максимум за частковим порядком не є єдиним.

7. Навести приклади відношень:

   1. Рефлексивного та симетричного, але не транзитивного;

   2. Рефлексивного і транзитивного, але не симетричного;

   3. Симетричного і транзитивного, але не рефлексивного.

8. Довести, що якщо $R$ — відношення часткового порядку, то $R^{-1}$ також є частковим порядком.

9. Довести, що для лінійно впорядкованої множини поняття мажоранти (міноранти) і максимума (мінімума) збігаються.

10. Довести, що серед будь-яких шести осіб знайдуться або три попарно знайомих, або три попарно незнайомих.

Назад до питань

Назад на головну