Задачи для самостоятельного решения. 1. Докажите, что для любых множеств X, Y, Z

1. Докажите, что для любых множеств X, Y, Z

а)

б)

в)

2. Изобразите граф бинарного отношения «иметь одинаковый остаток при делении на 2», заданного на множестве однозначных натуральных чисел.

3. .

а)задайте ρ перечислением пар; б)постройте граф ρ; в)задайте ρ таблицей; г) постройте график ρ.

4. Задайте с помощью характеристического свойства бинарное отношение график, которого изображён на рисунке 32.

Рис. 32 Рис. 33

5. а) Задайте перечислением бинарное отношение ρ, граф которого изображён на рисунке 33.

б) По графу бинарного отношения ρ (Рис. 33) изобразите его график.

6. Сформулируйте свойства, которыми обладают бинарные отношения, графы которых изображены на рисунках 34 (а, б, в) и не обладает ни одно бинарное отношение, графы которых изображены на рисунках 34 (г, д):

Рис.34

7. Найдите область определения и область значений для каждого из следующих отношений, заданных на множестве А = {1,2,3,4,5,6,7,8,9} и укажите какими свойствами (рефлексивностью, симметричностью, транзитивностью, антисимметричностью, антирефлексивностью) оно обладает:

а)

б)

в)

г)

д)

е)

8. Укажите, какими свойствами (рефлексивностью, симметричностъю, транзитивностью, антисимметричностью, антирефлексивностью) обладает бинарное отношение:

а)

б)

9. Найдите ошибку в следующем рассуждении: «Пусть ρ симметрично и транзитивно. Возьмём элемент х и такой у, что хρу. В силу симметричности ρ имеем уρх. В силу транзитивности получим хρx, то есть ρ рефлексивно».

10. Пользуясь теоретико-множественной и логической символикой объясните когда бинарное отношение не антисимметрично.

11. Пусть бинарное отношение ρ = {(а, b),(b, а),(а, а)} задано на множестве А = {а, b}. Найдите ошибку в следующем рассуждении и объясните причину этой ошибки: «ρ транзитивно, так как высказывание истинно. Действительно, множество А содержит только два элемента, поэтому в любом случае посылка ложна, но тогда импликация всегда истинна».

12. Докажите построением соответствующих примеров, что свойства рефлексивности, антисимметричности и транзитивности бинарных отношений независимы между собой, то есть никакое из них не следует из двух других.

13. Как можно быстрее из данных бинарных отношений выберите отношение эквивалентности:

а) «<» на множестве R;

б) «» на множестве Z;

в) отношение «подобия» на множестве треугольников плоскости;

г) «» на множестве прямых плоскости отношение;

д) «иметь общее начало» на множестве лучей плоскости.

14. Докажите, что отношение ρ является эквивалентностью на множестве А и найдите соответствующее фактор-множество А / ρ, если

а) А = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, (х имеет тот же остаток при делении на 4, что и y).

б) А = N, (х имеет тот же остаток при делении на 4, что и y).

15. Постройте граф отношения эквивалентности , где А = {а,b, с, d, е}, такой, что, .

16. Найдите классы эквивалентности отношения эквивалентности ρ, граф которого изображён на рисунке 35:

Рис.35

17. Найдите классы разбиения множества А = {0, 1, 2, 3, 4,}, если на нём задано отношение эквивалентности: ρ = {(0, 0),(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (3, 4), (4, 3), (4, 4)}.

18. Пусть А = {0,1,2,3,4,5}. Покажите, что подмножества A₁ = {0,3}, А₂ = {1,4}, А₃ = {2,5} образуют разбиение множества А: Запишите множество пар из , принадлежащих соответствующему отношению эквивалентности.

19. Можно ли множество прямых разбить на классы с помощью отношений:

а) «Иметь одну общую точку пересечения»;

б) «параллельности»?

20. Для данной теоремы выявите логическую структуру и сформулируйте теоремы: а) обратную; б) противоположную; в)противоположную прямой; г) противоположную обратной. Установите их истинность или ложность: «Любое отношение эквивалентности осуществляет разбиение множества А на классы эквивалентности». Сформулируйте эту теорему в терминах «необходимо и достаточно».

21. На рисунках 36 (а,b,с) изображены графы бинарных отношений. Какой из них задаёт отношение а) эквивалентности; б) порядок; в) функцию?

Рис.36

22. Проверьте, является или нет отношение ρ на множестве А = {а, b, с} отношением порядка? Будет ли ρ линейным порядком, строгим порядком?

а) ρ = {(а, а), (b, с), (а, b), (а, с)};

б) ρ = {(а, а), (b, b), (с, с), (b, а), (а, с)};

в) ρ = {(а, а), (b, b), (с, с), (b, а), (а, b)};

г) ρ = {(а, а), (b, b), (с, с), (а, b), (b, с), (а, с)}.

23. Пусть f – бинарное отношение, заданное на паре множеств А = {1, 2, 3, 4} и В = {1, 4, 9, 16}. Является или нет отношение f функцией? Если да, найдите Dom f и Im f и изобразите f графом:

a) f = {(1, 1), (2, 1), (3, 1), (4, 1)};

б) f = {(1, 1), (2, 4), (3, 9), (4, 16)};

в) f = {(2, 4), (3, 9)};

г) f = {(1, 4), (2, 4), (3, 1), (3, 9), (4, 9)}.

24. Пусть f – бинарное отношение, заданное на паре множеств А = В = R. Какой из графиков отношения f является графиком функции (Рис. 37)?

Рис.37

25. Определите, является ли бинарное отношение f:

1) функцией, 2) отображением, 3) инъективной функцией, 4) сюръективной функцией, 5) биективной функцией, 6) биекцией, 7) обратимой функцией? Поставьте «+» или «-» под каждым номером в соответствующем столбце таблицы21.

Таблица21

26. Запишите символически приведённые ниже определения:

а) Отображение f: Х→Y представляет собой инъекцию, если два любых различных элемента из Х имеют своими образами при отображении два различных элемента из Y.

б) Отображение f: Х→Y представляет собой сюръекцию, если для каждого элемента у из множества Y найдётся элемент х из множества X, такой, что х отображается в у.

27. Как можно быстрее из данных бинарных отношений ; где А = {а, k, d}, В = {b, с, е}, выберите биекцию:

1) ρ = {(а, b), (а, с), (d, е)};

2) ρ = {(а, b), (k, b), (d, е)};

3) ρ = {(а, b), (k, с)};

4) ρ = {(а, e), (k, b), (d, c)};

5) ρ = {(а, b), (k, с), (d, с)}.

28. Приведите примеры и контрпримеры понятий:

1) декартово произведение двух множеств (дать геометрическую интерпретацию);

2) бинарное отношение (задать различными способами);

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

4) отношение эквивалентности, классы эквивалентности, фактор-множество;

5) разбиение множества;

6) отношение порядка, линейный порядок;

7) функция, отображение, инъективная функция, сюръектив-ная функция, биективная функция, биекция.

29. Разбейте на 4 группы (по какому-либо признаку) бинарные отношения, заданные перечислением пар на множестве А={1,2,3,4,5}; Р₁={(1,2), (2,1),(1,3)}; Р₂={(2,2),(2,4)}; Р₃={(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1)}; Р₄={(1,2),(2,3),(4,5)}; Р₅={(1,2),(2,3),(1,3)}; Р₆= {(1,2), (1,3), (1,4)}; Р₇ = {(3,4), (4,5)}; Р₈={(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)}.

30. Решите задачу, используя граф бинарного отношения.

Класс выставил на соревнование по плаванию команду мальчиков. В неё входили: Витя, Коля, Андрей, Саша. Коля проплыл дистанцию быстрее Андрея, но медленнее Саши. Андрей затратил на ту же дистанцию времени больше, чем Витя, который плавал медленнее Коли. Как распределились роли в соревнованиях?

31. Если бинарное отношение ρ на множестве А симметрично, транзитивно и Dom ρ= А или Im ρ= А, то ρ рефлексивно. Докажите.

32. Докажите, что всякое симметричное и антисимметрич-ное бинарное отношение транзитивно.

33. Найдите в вузовских учебниках и приведите примеры, иллюстрирующие роль отношения эквивалентности в математике (в алгебре и геометрии).

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

35. Найдите все бинарные отношения на множестве А, которые одновременно являются отношением эквивалентности и порядка.

36. Выявите структуру приведённых ниже задач, установите полноту условия (достаточность, недостаточность, избыточность) данных задач. Если данных недостаточно, то дополните условия задач (самостоятельно выбрав данные) и решите их.

а) В нашем лесу мастера своего дела обучают других. Кто раньше всех научился плести корзины, если: мышь училась у ежа; заяц учил белку; барсук учил зайца, а ёж был учителем дятла.

б) Известно, что f - инъективное отображение множества А в трёхэлементное множество В, кроме того, . Будет ли f сюръективным отображением множества А в В?