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

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

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

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

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

Бинарное отношение R на одном множестве A является подмножеством $ 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), - это множество $ \ lbrace y \: | \: (x, y) \ in R \: for \: some \: x \: in \: A \ rbrace $

Примеры

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

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

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

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

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

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

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

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

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

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

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

Типы отношений

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

• Полная связь между множествами X и Y - это множество $ 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 (2, 1), (3, 2) \ rbrace $

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

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

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

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

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

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

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

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

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

  Пример - Соотношение $ R = \ lbrace (1, 2), (2, 3), (1, 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 $ на множестве $ A = \ lbrace 1, 2, 3 \ rbrace $ является отношением эквивалентности, поскольку оно рефлексивно, симметрично и транзитивно.