Декартово произведение множеств. Бинарные отношения

и Y: С = Х × У Х={а,b,c,d} И Y={Α,Β}. C={,,,,,,,} Порядок следования пар в множестве С может быть любым, но расположение элементов в паре строго задано и определяется порядком следования перемножаемых множеств.

паре множеств Х и Y.
Когда пара (x,y) ∈R, то говорят, что элемент х находится в отношении R к элементу у.
Отношение R может быть задано перечислением всех пар элементов , входящих в данное отношение, или некоторым свойством, выражаемом в виде формулы исчисления предикатов с двумя свободными переменными х и у.
R={⏐F(x,y)}.
Например:
R={⏐y=x2}
R={⏐x

Бинарные отношения

∈N>⏐n1>n2}.
При этом пара чисел (5, 3) удовлетворяет отношению R, а пара (3, 5) не удовлетворяет отношению R.
B теории бинарных отношений часто используются другие формальные способы записи того же самого:
х R y (5 «больше» 3)
«Больше» ⊂ <числовое множество>×<числовое множество> .

Бинарные отношения

пересечении xi и yj ставится некоторый символ.

Способы задания бинарных отношений

yj задается матрицей М, строки которой задаются элементами множества X, а столбцы – элементами множества Y.
M=⎢⎢mij ⎢⎢m×n – матрица отношения
Например, зададим матричным способом отношение, заданное выше табличным способом:

Способы задания бинарных отношений

соединяется стрелкой с yi .
Такая картинка называется граф-отношение.

Способы задания бинарных отношений

отношении к самому себе.
Пусть R – бинарное отношение на множестве Х, т.е. R=X×Х.
Отношение R рефлексивно, если для любого х∈Х имеет место х R х.
Например, отношения между числами в выражениях а = а или а ≥ а обладают свойством рефлексивности, так как для каждого а есть пара (а, а), находящаяся в данном отношении.

Общие свойства отношений

в данном отношении к самому себе.
Пусть R – бинарное отношение на множестве Х, т.е. R=X×Х.
Отношение R антирефлексивно, если для любого х∈Х не имеет место х R х.

Общие свойства отношений

Например, отношения между числами в выражениях а > c обладает свойством антирефлексивности, так как нет ни одной пары (а, а), находящейся в этом отношении.

xi и xj, влечет за собой и наличие этого же отношения между элементами обратной пары (xj, xi).
Пусть R – бинарное отношение на множестве Х, т.е. R=X×Х.
Отношение R симметрично, если
(xi, xj) ∈ R ↔ (xj, xi) ∈ R.

Общие свойства отношений

Например, отношение неравенства на множестве чисел обладает свойством симметричности, так как если а ≠ с, то и с ≠ а.

xi и xj, влечет за собой отсутствие этого отношения между элементами обратной пары (xj, xi).
Пусть R – бинарное отношение на множестве Х, т.е. R=X×Х.
Отношение R асимметрично, если
(xi, xj) ∈ R ↔ (xj, xi) ∉ R, т.е. R ∩ R-1=∅
Если отношение асимметрично, то оно и антирефлексивно.

Общие свойства отношений

Например, отношения между числами в выражениях а > c обладает свойством асимметричности, так как если для пары (а, с) справедливо отношение а > c, то для пары (с, а), отношение с > а не имеет места.

(xi, xj) и наличие этого же отношения у обратной парой (xj, xi), возможно только в том случае, если xi= xj.
Пусть R – бинарное отношение на множестве Х, т.е. R=X×Х.
Отношение R антисимметрично, если
(xi, xj) ∈ R & (xj, xi) ∈ R ↔ xi= xj

Общие свойства отношений

Например, отношение между числами (а, с) в выражении а ≥ с обладает свойством антисимметрии, так как отношение « ≥ » справедливо и для обратной пары только в том случае, если а = с.

находится в данном отношении ко второму элементу, а второй элемент находится в этом же отношении к третьему элементу, то первый элемент находится в этом отношении к третьему элементу.
Пусть R – бинарное отношение на множестве Х, т.е. R=X×Х.
Отношение R транзитивно, если
(xi, xj) ∈ R & (xj, xк) ∈ R → (xi, xк) ∈ R.

Общие свойства отношений

Например, отношение между числами (а, b) в выражении а > b обладает свойством транзитивности, так как если отношение « > » справедливо для пары а > b и справедливо для пары b > c, то оно справедливо и для пары а > c.