Практическое занятие №5

1.Нарисовать диаграмму Хассе для каждого из следующих частично упорядоченных множеств:

a. множество с отношением «x делит y»

b. множество всех подмножеств множества с отношением «X – подмножество Y»

В обоих вариантах порядок считать строгим.

2.Пусть - отношение «x родитель y», - отношение «a брат b», определенные на множестве людей. Дать словесное описание отношениям , , , , .

3.Пусть X – множество точек плоскости, Y – множество окружностей на плоскости, Z – множество треугольников на плоскости; ; . Дать словесное описание композиции .

4.Пусть X – множество преподавателей института, Y – множество читаемых дисциплин, Z – множество академических групп; ; . Дать словесное описание композиции .

5.Пусть X – множество мужчин, Y – множество людей, Z – множество женщин; ; . Дать словесное описание композиции .

6.Найти , , , для отношений:

a.

b.

c.

d.

e.

f.

g.

h.

i.

j.

7.Доказать, что если , то

a.

b.

c.

8.Доказать, что для любых бинарных отношений

a.

b.

9.Доказать, что если отношение - симметрично, то отношение - симметрично.

10.Доказать, что если отношения , - антирефлексивны, то антирефлексивны и отношения , , .

11.

Примеры решения задач:

Пример 1: Найти , , , для отношения .

Решение: Так как - симметричное отношение (если , то ), то . Поэтому . Найдем . , так как для всякой пары чисел можно подобрать z такое, что верны неравенства и .

Пример 2: Найти , , , для отношения .

Решение: . Перепишем множество по-другому: . Тогда . , так как для любых можно подобрать такое z, чтобы одновременно выполнялись неравенства и . , так как для всякой пары можно найти z такое, чтобы удовлетворить неравенствам и .

Пример 3: Доказать, что объединение эквивалентностей, является эквивалентностью тогда и только тогда, когда .

Решение:

Дано: , - симметричные, рефлексивные и транзитивные бинарные отношения.

Доказать: .

Доказательство:

Пусть

Пусть

Дано: - симметричные, рефлексивные и транзитивные бинарные отношения;

Доказать: - симметрично, рефлексивно и транзитивно.

Доказательство:

Симметричность: Пусть - симметрично.

Рефлексивность: - рефлексивно.

Транзитивность: Пусть - транзитивно.