Понятие бинарного отношения. Операции над бинарными отношениями.
Теоретические вопросы ;
Определение n - местного, одноместного (унарного),
бинарного, тернарного отношений. Примеры унарного, бинарного, тернарного отношений. Способы задания бинарного отношения. Объединение, пересечение, разность, дополнение бинарных отношений.
Обратное бинарное отношение. Композиция бинарных отношений . Докажите : композиция бинарных отношений не коммутативна, ассоциативна.
9. 1. Бинарное отношение задано высказывательной
формой. Задайте его: а) парами б) таблицей.
1. А = {-1, 0, 1, 2, 3} а, в а + в 2Z
2. А = {n N , n 10}, а, , в в = rеst (а, 4).
3. А = {-2, -1, 1, 2, 5}, а, , в а + в 0 а > в.
4. А = {-1, 0, 1, 2, 4, 5}, а
в а
в (а
в а + в-
простое число).
9.2.
, ,
.Найдите
о ,
о ,
,
,
,
,
если
1. =
, =
,
=
, 2. = {(х,у), у =
-
2х + 3}, =
,
= {(х, у), у= 2х - 1}
3. х у у = 2х + 5, х у у = 3х + 5 ,
= {(1; 0), (2 ; 1),(3; 2), (4; 1), (5; -5)}
4. х у
у =
+ 1, =
,
=
.
9.3. Заданы отношения = на А = {-1,0,2,-3,3}.
Найдите
, 
,
,
о 
,
,
\ .
1. х у х + у < 0, х у х у 0,
2. х у х + у х у х, у
простое число взаимно простые
3.
х у
х = у
х у
у = х
4.
х у
х
у
х у
НОК (х, у) = х
у.
9. 4. Для любых отношений , , , заданных на множестве А, докажите:
1.
(
)
= 
,
2. ( - )
=
\
3.()
= (
)
, 4. ( о
)
=
о
5.
(
)
=
6. ( ) о =( о ) ( о ),
7. ( ) о ( о ) ( о )
8. о () (о) (о).
9. ( \ )о ( о ) \ ( о ),
10. о ( \ ) ( о ) \ ( о ).
З А Н Я Т И Е № 10.
Свойства бинарных отношений.
Теоретические вопросы:
Запишите свойства бинарных отношений: рефлексивность, cимметричности, транзитивности, антирефлекcивности, антисимметричности, связности.
Запишите, что означает - свойство нерефлексивности,
несимметричности, нетранзитивности, несвязности.
Является ли свойство антирефлекcивности отрицанием свойства рефлексивности, а свойство антисимметричности
отрицанием свойства симметричности?
10. 1. Пусть - бинарное отношение на множестве А. Докажите:
1.
= симметрично
=
. 2. -
транзитивно 
3.
- антирефлексивно
= ,
= {(а, а), а А}
4.
- антисимметрично
.
5.
- связно
6.
- рефлексивность
.
10. 2. Выясните , двумя способами будет ли бинарное отношение , заданное на множестве А = {1,2,3,} обладать свойствами рефлексивности, симметричности, транзитивности, антисимметричности, связности, если
1. = {(1, 1),(1, 2),(2, 1),(2, -2),(3, 3),(2, 3)}
2. = {(2, 1),(2, 2),(1, 2),(3, 3),(3, 2),(2, 3)}
3. = {(2, 1),(2, 3)}
4. = {(1, 2),(2, 3),(1, 3),(2, 1),(1, 1),(2, 2)}
5. = {(2, 1),(3, 2),(3, 1),(1, 1),(2, 2),(3, 3)}
6. {(1, 1)}.
10. 3. Какими свойствами обладает отношение
1. х у
х у + 1 на Z 2. х
у
2х + у
3
на Z.,
3. Х У Х У = на Р(Z) 4 . х у у = | х| на R.
5. х у
х
+
у
> 4 на R 6. х у
х(у - 1)= 0 на R.
10. 4. Какими свойствами обладают отношения :
1. Параллельности на множестве прямых на плоскости.
2. Перпендикулярности на множестве прямых на плоскости
3. Подобия на множестве всех многоугольников.
4. Х У
Х симметрична У относительно прямой
,
Х, У - точки, не принадлежащие
.
5. “Быть родственником” на множестве людей.
6. “Быть знакомым” на множестве людей.
7. “Быть студентом одной группы” (одноклассником)
на множестве всех людей.
10.5 Найдите смежный класс
для
отношения , если :
1.
х у
3х + у
4 на R
,
а = 12; а = 9.
2. х у х > 2у на N, а = 10,
3.
х у
у
= х
+
1 на R
а = 100
4.
х у
lg у = х
+
1 = 3sin у на R, а = -
5. х у |3х + 2| > у на R , а = 5.
10.6. Докажите: для любых отношений и , заданных на
множестве А:
1. Если ,
- симметричны, то
,
,
,
\ - симметричны.
2. Если , -
рефлексивны, то 
,
о ,
,
- рефлексивны.
3. Если ,
- транзитивны, то
,
транзитивны.
4. Если , антирефлексивны, то , - антирефлексивны.
5. Если ,
рефлексивны, то
,
- антирефлексивны.
6. Если , - антисимметричны, то - антисимметричны.
З А Н Я Т И Е № 11.
Отношение эквивалентности
Теоретические вопросы : Определение отношения эквивалентности. В каком случае бинарное отношение не будет отношением эквивалентности? Понятие разбиения множества, класса эквивалентности, фактор-множества.
11.1. На множестве А = {1, 2, 3, 4, 5} задано отношение .
Найдите фактор множество А | . Какие из заданных
отношений будут отношениями эквивалентности?
1.
=
2.
=
3.
=
4.
5.
=
6.
=
7.
=
8.
=
11. 2. Докажите, что М - разбиение множества А = {1,2,3,4,5,6,7} Перечислите все элементы отношения эквивалентности соответствующего разбиению М.
1. М = {{1}, {2,5},{3}, {4,6,7,}}, 2. М= {{1,7},{2,4,5,6},{3}},
3. М= {{1,2,3,4,5,6,7}}, 4. М= {{ 1}, { 2}, { 3}, {4},{5},{6}, {7}}
5. М= {{1,2,4,},{5,6,7,} {3}, 6. M= {{1,2,3,4,},{5,6,7,}}
11. 3. Докажите, что отношение эквивалентности. Найдите
классы эквивалентности.
1. Х У Х и У - тезки, на множестве студентов Вашей
группы.
2. Х У Х и У ровесники, на множестве людей.
3. х у
х - у
10
на Z.
4. х у х - у Z на R.
5. х у х || у, на множестве прямых плоскости.
6. х у последняя цифра числа х совпадает с
последней цифрой числа у, на N.
7. х у х и у числа одного знака на Z.
8. х у
х
=
у
на R.
9. (а, в) (с, d) а + d = в +с на N х N.
10. (а, в) (с, d) аd = вс, на Z х Z.
11. х у Sin х = Sin у , на R.
12. х у
ху > 0 или х
+ у
=
0.
11. 4. Докажите, что - отношение эквивалентности на R и найдите класс смежности элементов а и в.
1. х у
|| х | -2| = || у | -2 |, а = 2, в = 1.
2. х у || х - 1| -3 | = || у- 1| -3 |, а = -2, в = 2.
3.
х у
|х
-
2| = |у
-
2|, а = 1, в = 0.
4.
х у
| (х - 1)
-
3 | а = 1, в = 0.
5.
х у
Sin
=
Sin
,
а =1, в = 2.
6.
х у
Sin
=
cos
,
а = 1, в = 2
7.
х у
Sin
= Sin
,
а = 1, в = 2.
8.
х у
|2IхI
-
2| = |2IуI- 2|, а = 2, в = 1.
9. х у |2 IхI- 4| = |2IуI- 4 |, а = 2, в = 1.
11.5. Найдите минимальное отношение эквивалентности
на множестве А = {1, 2, 3, 4, 5,} так, чтобы:
1. 1 2 и 2
3. 2. =
.
3. =
4. 5 1.
11.6. Пусть и - отношение эквивалентности на А.
Докажите:
1. 
,
- отношение
эквивалентности.
2. о - отношение эквивалентности и перестановки.
3.
,
\ ,
- не будут отношением эквивалентности.
11.7. Заданы отношения эквивалентности и .
Найдите
, 
,
:
1. а в а в ( mod 4), а в а в (mod 6).
2. а в а в (mod 5), а в а в (mod 3).
11. 8. Сколько различных отношений эквивалентностей можно
задать на множестве:
1. из двух элементов;
2. из трех элементов;
3. из четырех элементов?
З А Н Я Т И Е № 12.
Отношение порядка.
Теоретические вопросы: Определение нестрогого порядка, строгого порядка, линейного порядка. Понятие наибольшего,
наименьшего, максимального, минимального элемента. Число линейных порядков n - множества.
Упр 1. Выясните, является ли отношением порядка на А.
Определите тип порядка. Найдите экстремальные
элементы
1. = {(1, 2), (3, 2), (1, 3)}, А = {1, 2, 3}
2. = {(х, у), у = х + 2} , А = R.
3. = {(4, 2), (2, 3), (4, 3)}, А = {2, 3, 4, 5}.
4.
= {(х, у), х
<
у
},
А = |R; А = |N.
5.
= {( х, у), х
у},
А = Z, А = N
6. х у х делит у х < у , А = |N.
7. (а, в) (с, d) а < с (а = с в d), А = Z х Z.
Упр 2. Найдите экстремальные элементы на множестве
А относительно .
1. х у х делит у, А = N,
2. х у
х делится на у, А = N
=
N \ {1}.
3. х у
х делит у. А = N
{0}.
4. х у х делит на у. А = N {0}.
5. х у х делит у . А = N {1}.
6. Х
У Х
У, Х,У Р (М).
7. х у х < у, А = [0, ).
8. х у
х делится на у, А =Д
.
Д
-
натуральные .делители числа 30.
Упр 3. - отношение порядка на А. Изобразите диаграммой.
Найдите экстремальные элементы.
1.
х у
х делит у, А = Д
2.
х у
х делится на у А = Д
3.
х у
х делится у . А = Д
\{1}
4.
х у
х делит у, А = Д
\
{1}.
Упр 4. 1. Пусть : - строгий (нестрогий) порядок.
Каким будет ?.
2. Если - строгий
порядок, то
- нестрогий
порядок.
3. Если - нестрогий
порядок , то 
нестрогий
порядок.
4. Если отношения
порядка то 
отношения
порядка.
5. Если , - отношения строгого порядка. Каким
будет ?.
З А Н Я Т И Е № 13.