Книги и конспекты / Шпоры / 5
.pdfАлгебра отношений. Бинарные отношения на S.
Любому бинарному отношению а можно определить обратное отношение â такое что: yâx => xay.
Матрица отношения ||âij|| отношения â получается транспонированием ||аij|| отношения а.
Если а адает ункцию а f â g то f и g – в аимообратные биекции
Компо иция бинарных отношений: x(αβ)z если существует yϵY , xαy, yβz. x->z: α: x,y; β: y,z
=>z( )x
Бинарное отношение между множеством S и им самим – бинарное отношение на множестве S(X=Y=S)
Бинарное отношение на множестве S относительно компо иции обра ует алгебраическую систему которая ассоциативна и в качестве единицы имее отношение равенства.
Рассмотрим α на множестве S.
е – отношение равенства.
xey=>x=y
αe=eα=α
x(αe)y=> z |
S: |
1)xαz zey => xαz и z=y => xαy; |
|
2)x(eα)y => |
z S zαy xez => x=z zαy => xαy |
Закон ассоциативности: α(βγ) = (αβ)γ |
|
Свойство ре |
лексивности: x S, xαx |
xαy yαx => α-ассиметричное отношение
xαy yαx => x=y =>α-антисиметричное отношение
xαy, yαz => xαz => z- тран итивное отношение
Пусть α – бинарное отношение между множествами X и Y а β – между B и Y. Декартово прои ведение γ=α x β определяется как отношение между AxB и Y вида:
(a b)γ y => aαy и bβy yγ(a b) => yαa и yβb.