Задачи для самостоятельного решения
Пусть , а - отношения на , определенные следующим образом:
,
,
,
.
Какое из отношений является
а) симметричным, б) рефлексивным,
в) транзитивным, г) антисимметричным.
Постройте графы, соответствующие данным отношениям.
Определите свойства следующих отношений:
а)
;
б)
;
в)
;
г)
.
Постройте бинарное отношение на множестве
а) рефлексивное, симметричное, не транзитивное;
б) рефлексивное, антисимметричное, не транзитивное;
в) рефлексивное, не симметричное, транзитивное;
г) не рефлексивное, антисимметричное, транзитивное.
Пусть . Опишите наименьшее рефлексивное отношение на множестве .
Пусть
и бинарное отношение на множестве
.
Опишите следующие отношения:
а) наименьшее
симметричное отношение на
,
содержащее
,
б) наименьшее симметричное и рефлексивное отношение на , содержащее ,
в) наибольшее симметричное отношение, содержащееся в ,
г) наименьшее транзитивное отношение на , содержащее .
Перечислите упорядоченные пары, принадлежащие отношениям, заданным на множестве
а)
;
б)
;
в) транзитивное
замыкание
,
г) транзитивное
замыкание
.
Пусть бинарные отношения
и
заданы на одном и том же множестве
.
Проверьте справедливость утверждения
«если
отношения
и
обладают
свойством
,
то отношение
также обладает свойством
»,
если отношения
заданы в следующей таблице,
№ |
1 |
2 |
3 |
4 |
5 |
6 |
|
|
|
|
|
|
|
а в качестве свойства выступает
а) рефлексивность, б) антирефлексивность,
в) симметричность, г) антисимметичность, д) транзитивность.
Установите, является ли каждое из приведенных ниже отношений отношением эквивалентности. Для каждого отношения эквивалентности постройте классы эквивалентности.
а)
,
б)
,
в)
на множестве
,
г)
на множестве прямых на плоскости,
д)
,
где
,
Установите, является ли каждое из перечисленных ниже отношений на множестве эквивалентностью. Для каждого отношения эквивалентности постройте классы эквивалентности.
а)
и
есть отношение, заданное условием
,
если
,
б)
- множество упорядоченных пар целых
чисел и
,
если
,
в)
и
,
если
,
г)
и
,
если
.
Какое из приведенных ниже отношений является отношением частичного порядка на
?
а)
,
б)
,
в)
,
г)
.
Являются ли следующие отношения частичным порядком?
а)
,
б) на множестве
людей
определено условием:
,
если
и
являются братом и сестрой,
в) на множестве
всех упорядоченных пар положительных
целых чисел
определено условием:
,
если
,
и если
,
то
.
Постройте диаграммы Гессе для следующих частично упорядоченных множеств
:
а)
,
,
б)
,
,
в)
и
,
если
делит
нацело,
г)
,
где
и
,
если
делит
нацело, если
,
то
делит
нацело,
д)
- множество положительных целых чисел,
которые делят 27 нацело, и
,
если
делит
нацело.
Для каждого частичного порядка из предыдущего упражнения перечислите элементы:
а) не сравнимые с
,
б) не сравнимые с
,
в) не сравнимые с
,
г) не сравнимые с
.
Диаграмма Гессе частичного порядка на множестве
показана на рис 2.
Рис. 2.
Перечислите элементы отношения и найдите минимальный и максимальный элементы частично упорядоченного множества .
Для данного отношения , заданного на множестве
выполните следующие действия:
а) постройте для
соответствующий граф
;
б) достройте до отношения эквивалентности и укажите соответствующее фактор-множество;
в) достройте до отношения частичного порядка, укажите максимальные и минимальные элементы, а также несравнимые элементы;
г) достройте до отношения линейного порядка, укажите наибольший и наименьший элементы;
д) достройте до отношения строгого порядка.
Замечание. Отношение достраивается с помощью введения минимально необходимого числа дополнительных ребер.
№ |
|
№ |
|
1 |
|
6 |
|
2 |
|
7 |
|
3 |
|
8 |
|
4 |
|
9 |
|
5 |
|
10 |
|
