Дискретная математика — отношения

Всякий раз, когда обсуждаются наборы, возникает следующая взаимосвязь между элементами наборов. Отношения могут существовать между объектами одного и того же набора или между объектами двух или более наборов.

Определение и свойства

Бинарное отношение R из множества x к y (записанное как xRy$xRy$ или R(x,y)$R (x, y)$) является подмножеством декартового произведения x timesy$x \ times y$. Если упорядоченная пара G перевернута, отношение также меняется.

Обычно n-арное отношение R между множествами A1, dots, и An$A_1, \ dots, \ и \ A_n$ является подмножеством n-арного произведения A1 times dots timesAn$A_1 \ times \ dots \ times A_n$. Минимальная мощность отношения R равна нулю, а максимальная — в этом случае n2$n ^ 2$.

Бинарное отношение R на одном множестве A является подмножеством A timesA$A \ times A$.

Для двух различных наборов, A и B, имеющих мощности m и n соответственно, максимальная мощность отношения R от A к B равна mn .

Домен и Диапазон

Если есть два набора A и B, и отношение R имеет пару порядка (x, y), то —

• Области R, Dom (R), является множество $ \ lbrace x \: | \: (x, y) \ in R \: for \: some \: y \: in \: B \ rbrace $

• Диапазон R, Ran (R), — это множество  lbracey|(x,y) inRforsomexinA rbrace$\ lbrace y \: | \: (x, y) \ in R \: for \: some \: x \: in \: A \ rbrace$

Области R, Dom (R), является множество $ \ lbrace x \: | \: (x, y) \ in R \: for \: some \: y \: in \: B \ rbrace $

Диапазон R, Ran (R), — это множество  lbracey|(x,y) inRforsomexinA rbrace$\ lbrace y \: | \: (x, y) \ in R \: for \: some \: x \: in \: A \ rbrace$

Примеры

Пусть A= lbrace1,2,9 rbrace$A = \ lbrace 1, 2, 9 \ rbrace$ и B= lbrace1,3,7 rbrace$B = \ lbrace 1, 3, 7 \ rbrace$

• Случай 1 — Если отношение R ‘равно’, то R= lbrace(1,1),(3,3) rbrace$R = \ lbrace (1, 1), (3, 3) \ rbrace$

  Dom (R) =  lbrace1,3 rbrace,Ran(R)= lbrace1,3 rbrace$\ lbrace 1, 3 \ rbrace, Ran (R) = \ lbrace 1, 3 \ rbrace$

• Случай 2 — Если отношение R «меньше», то R= lbrace(1,3),(1,7),(2,3),(2,7) rbrace$R = \ lbrace (1, 3), (1, 7), (2, 3), (2, 7) \ rbrace$

  Dom (R) =  lbrace1,2 rbrace,Ran(R)= lbrace3,7 rbrace$\ lbrace 1, 2 \ rbrace, Ran (R) = \ lbrace 3, 7 \ rbrace$

• Случай 3 — Если отношение R «больше чем», то R= lbrace(2,1),(9,1),(9,3),(9,7) rbrace$R = \ lbrace (2, 1), (9, 1), (9, 3), (9, 7) \ rbrace$

  Dom (R) =  lbrace2,9 rbrace,Ran(R)= lbrace1,3,7 rbrace$\ lbrace 2, 9 \ rbrace, Ran (R) = \ lbrace 1, 3, 7 \ rbrace$

Случай 1 — Если отношение R ‘равно’, то R= lbrace(1,1),(3,3) rbrace$R = \ lbrace (1, 1), (3, 3) \ rbrace$

Dom (R) =  lbrace1,3 rbrace,Ran(R)= lbrace1,3 rbrace$\ lbrace 1, 3 \ rbrace, Ran (R) = \ lbrace 1, 3 \ rbrace$

Случай 2 — Если отношение R «меньше», то R= lbrace(1,3),(1,7),(2,3),(2,7) rbrace$R = \ lbrace (1, 3), (1, 7), (2, 3), (2, 7) \ rbrace$

Dom (R) =  lbrace1,2 rbrace,Ran(R)= lbrace3,7 rbrace$\ lbrace 1, 2 \ rbrace, Ran (R) = \ lbrace 3, 7 \ rbrace$

Случай 3 — Если отношение R «больше чем», то R= lbrace(2,1),(9,1),(9,3),(9,7) rbrace$R = \ lbrace (2, 1), (9, 1), (9, 3), (9, 7) \ rbrace$

Dom (R) =  lbrace2,9 rbrace,Ran(R)= lbrace1,3,7 rbrace$\ lbrace 2, 9 \ rbrace, Ran (R) = \ lbrace 1, 3, 7 \ rbrace$

Представление отношений с помощью графика

Отношение может быть представлено с помощью ориентированного графа.

Количество вершин в графе равно количеству элементов в наборе, из которого определено отношение. Для каждой упорядоченной пары (x, y) в отношении R будет направленное ребро от вершины ‘x’ до вершины ‘y’. Если есть упорядоченная пара (x, x), в вершине ‘x’ будет самоконтроль.

Предположим, что на множестве S= lbrace1,2,3 rbrace$S = \ lbrace 1, 2, 3 \ rbrace$ существует отношение R= lbrace(1,1),(1,2),(3,2) rbrace$R = \ lbrace (1, 1), (1,2), (3, 2) \ rbrace$, оно может быть представлен следующим графиком —

Пустая связь между множествами X и Y, или на E, является пустым множеством  emptyset$\ emptyset$

Полная связь между множествами X и Y — это множество X timesY$X \ times Y$

Отношение идентичности на множестве X — это множество $ \ lbrace (x, x) | x \ in X \ rbrace $

Обратная связь R ‘отношения R определяется как — $ R’ = \ lbrace (b, a) | (a, b) \ in R \ rbrace $

Пример — если R= lbrace(1,2),(2,3) rbrace$R = \ lbrace (1, 2), (2, 3) \ rbrace$, то R′$R '$ будет  lbrace(2,1),(3,2) rbrace$\ lbrace (2, 1), (3, 2) \ rbrace$

Отношение R на множестве A называется рефлексивным, если  foralla inA$\ forall a \ in A$ связано с a (выполняется aRa)

Пример . Отношение R= lbrace(a,a),(b,b) rbrace$R = \ lbrace (a, a), (b, b) \ rbrace$ на множестве X= lbracea,b rbrace$X = \ lbrace a, b \ rbrace$ является рефлексивным.

Отношение R на множестве A называется иррефлексивным, если a inA$a \ in A$ не связано с a (aRa не имеет места).

Пример — Соотношение R= lbrace(a,b),(b,a) rbrace$R = \ lbrace (a, b), (b, a) \ rbrace$ на множестве X= lbracea,b rbrace$X = \ lbrace a, b \ rbrace$ нерефлексивно.

Отношение R на множестве A называется симметричным, если из xRy$xRy$ следует yRx$yRx$,  forallx inA$\ forall x \ in A$ и  forally inA$\ forall y \ in A$.

Пример — Соотношение R= lbrace(1,2),(2,1),(3,2),(2,3) rbrace$R = \ lbrace (1, 2), (2, 1), (3, 2), (2, 3) \ rbrace$ на множестве A= lbrace1,2,3 rbrace$A = \ lbrace 1, 2, 3 \ rbrace$ симметричный.

Отношение R на множестве A называется антисимметричным, если из xRy$xRy$ и yRx$yRx$ следует x=y forallx inA$x = y \: \ forall x \ in A$ и  forally inA$\ forall y \ in A$.

Пример . Отношение R= lbrace(x,y) toN|x leqy rbrace$R = \ lbrace (x, y) \ to N | \: x \ leq y \ rbrace$ антисимметрично, так как x leqy$x \ leq y$ и y leqx$y \ leq x$ влечет x=y$x = y$.

Отношение R на множестве A называется транзитивным, если из xRy$xRy$ и yRz$yRz$ следует xRz, forallx,y,z inA$xRz, \ forall x, y, z \ in A$.

Пример — Соотношение R= lbrace(1,2),(2,3),(1,3) rbrace$R = \ lbrace (1, 2), (2, 3), (1, 3) \ rbrace$ на множестве A= lbrace1,2,3 rbrace$A = \ lbrace 1, 2, 3 \ rbrace$ является транзитивным.

Отношение — это отношение эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Пример — Соотношение R= lbrace(1,1),(2,2),(3,3),(1,2),(2,1),(2,3),(3,2),(1,3),(3,1) rbrace$R = \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2) , (1,3), (3,1) \ rbrace$ на множестве A= lbrace1,2,3 rbrace$A = \ lbrace 1, 2, 3 \ rbrace$ является отношением эквивалентности, поскольку оно рефлексивно, симметрично и транзитивно.