Дискретна математика Факультет кібернетики, 1 курс, інформатика, програмна інженерія / P13

Тема 3: Бінарні відношення та операції над ними.

Мета: Навчити діям з бінарними відношеннями, доводити тотожності, встановлювати закономірності між операціями над бінарними відношеннями.

Теоретичні питання: Визначення бінарного відношення, операцій над бінарними відношеннями.

Аудиторне завдання:

1.Довести, що . [6- 2.12.г]

2. Довести, що.

а) . [6- 2.18.в]

б) , для будь-якого відношення Q. [6- 2.18.а]

3. Довести, що , для будь-якого Q.

4.Знайти область визначення та область значень відношення R, а також R^-1, , , , де

_. [6- 2.8.а]

Домашнє завдання:

1.Довести, що . [6- 2.12.в]

2.Довести, що , для будь-якого відношення Q. [6-2.18.б]

3.Знайти область визначення та область значень відношення R, а також R^-1, , , , де

а) [6- 2.8.в]

б) [6- 2.8.г]

4.Для яких бінарних відношень . [6- 2.13]

Додаткове завдання:

1. Показати що:

1. для R, Q – відношень еквівалентності, RQ – не завжди відношення еквівалентності;

2. для R, Q – відношень еквівалентності, RQ – не завжди відношення еквівалентності;

3. для R, Q – іррефлексивних відношень, RQ – не завжди іррефлексивне відношення;

4. для R, Q – транзитивних відношень, RQ –транзитивне відношення.

2. Довести, що для довільних рефлексивних відношень R₁ та R₂ виконується R₁R₂ R₁R₂.

3. Довести, що композиція R₁ R₂ транзитивних відношень R₁ та R₂ є транзитивним відношенням тоді і тільки тоді, коли R₁R₂= R₂R₁.

4. Довести, що для рефлексивного і транзитивного відношення R виконується R R= R. Чи має місце обернене твердження?