Matemática Discreta - Relações
Sempre que os conjuntos estão sendo discutidos, a relação entre os elementos dos conjuntos é a próxima coisa que surge. Relations pode existir entre objetos do mesmo conjunto ou entre objetos de dois ou mais conjuntos.
Definição e Propriedades
Uma relação binária R do conjunto x a y (escrita como $ xRy $ ou $ R (x, y) $) é um subconjunto do produto cartesiano $ x \ vezes y $. Se o par ordenado de G for invertido, a relação também muda.
Geralmente, uma relação n-ária R entre os conjuntos $ A_1, \ dots, \ e \ A_n $ é um subconjunto do produto n-árico $ A_1 \ times \ dots \ times A_n $. A cardinalidade mínima de uma relação R é Zero e a máxima é $ n ^ 2 $ neste caso.
Uma relação binária R em um único conjunto A é um subconjunto de $ A \ vezes A $.
Para dois conjuntos distintos, A e B, tendo cardinalidades m e n respectivamente, a cardinalidade máxima de uma relação R de A para B é mn .
Domínio e alcance
Se houver dois conjuntos A e B, e a relação R tiver par de ordens (x, y), então -
o domainde R, Dom (R), é o conjunto $ \ lbrace x \: | \: (x, y) \ em R \: para \: algum \: y \: em \: B \ rbrace $
o range de R, Ran (R), é o conjunto $ \ lbrace y \: | \: (x, y) \ in R \: for \: some \: x \: in \: A \ rbrace $
Exemplos
Vamos, $ A = \ lbrace 1, 2, 9 \ rbrace $ e $ B = \ lbrace 1, 3, 7 \ rbrace $
Caso 1 - Se a relação R é 'igual a' então $ R = \ lbrace (1, 1), (3, 3) \ rbrace $
Dom (R) = $ \ lbrace 1, 3 \ rbrace, Ran (R) = \ lbrace 1, 3 \ rbrace $
Caso 2 - Se a relação R for 'menor que', então $ R = \ lbrace (1, 3), (1, 7), (2, 3), (2, 7) \ rbrace $
Dom (R) = $ \ lbrace 1, 2 \ rbrace, Ran (R) = \ lbrace 3, 7 \ rbrace $
Caso 3 - Se a relação R é 'maior que' então $ R = \ lbrace (2, 1), (9, 1), (9, 3), (9, 7) \ rbrace $
Dom (R) = $ \ lbrace 2, 9 \ rbrace, Ran (R) = \ lbrace 1, 3, 7 \ rbrace $
Representação de relações usando gráfico
Uma relação pode ser representada por meio de um gráfico direcionado.
O número de vértices no gráfico é igual ao número de elementos no conjunto a partir do qual a relação foi definida. Para cada par ordenado (x, y) na relação R, haverá uma aresta direcionada do vértice 'x' ao vértice 'y'. Se houver um par ordenado (x, x), haverá um loop automático no vértice 'x'.
Suponha que haja uma relação $ R = \ lbrace (1, 1), (1,2), (3, 2) \ rbrace $ no conjunto $ S = \ lbrace 1, 2, 3 \ rbrace $, pode ser representado pelo seguinte gráfico -
Tipos de Relações
o Empty Relation entre os conjuntos X e Y, ou em E, é o conjunto vazio $ \ emptyset $
o Full Relation entre os conjuntos X e Y é o conjunto $ X \ vezes Y $
o Identity Relationno conjunto X é o conjunto $ \ lbrace (x, x) | x \ in X \ rbrace $
A relação inversa R 'de uma relação R é definida como - $ R' = \ lbrace (b, a) | (a, b) \ in R \ rbrace $
Example - Se $ R = \ lbrace (1, 2), (2, 3) \ rbrace $ então $ R '$ será $ \ lbrace (2, 1), (3, 2) \ rbrace $
Uma relação R no conjunto A é chamada Reflexive se $ \ forall a \ in A $ está relacionado a a (aRa mantém)
Example - A relação $ R = \ lbrace (a, a), (b, b) \ rbrace $ no conjunto $ X = \ lbrace a, b \ rbrace $ é reflexiva.
Uma relação R no conjunto A é chamada Irreflexive se nenhum $ a \ em A $ está relacionado a a (aRa não é válido).
Example - A relação $ R = \ lbrace (a, b), (b, a) \ rbrace $ no conjunto $ X = \ lbrace a, b \ rbrace $ é irreflexiva.
Uma relação R no conjunto A é chamada Symmetric se $ xRy $ implica $ yRx $, $ \ forall x \ in A $ e $ \ forall y \ in A $.
Example - A relação $ R = \ lbrace (1, 2), (2, 1), (3, 2), (2, 3) \ rbrace $ no conjunto $ A = \ lbrace 1, 2, 3 \ rbrace $ é simétrico.
Uma relação R no conjunto A é chamada Anti-Symmetric se $ xRy $ e $ yRx $ implica $ x = y \: \ forall x \ in A $ e $ \ forall y \ in A $.
Example - A relação $ R = \ lbrace (x, y) \ para N | \: x \ leq y \ rbrace $ é antissimétrica, pois $ x \ leq y $ e $ y \ leq x $ implica $ x = y $ .
Uma relação R no conjunto A é chamada Transitive se $ xRy $ e $ yRz $ implicam em $ xRz, \ forall x, y, z \ em A $.
Example - A relação $ R = \ lbrace (1, 2), (2, 3), (1, 3) \ rbrace $ no conjunto $ A = \ lbrace 1, 2, 3 \ rbrace $ é transitiva.
Uma relação é um Equivalence Relation se for reflexivo, simétrico e transitivo.
Example - A relação $ R = \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2), (1,3), (3,1) \ rbrace $ no conjunto $ A = \ lbrace 1, 2, 3 \ rbrace $ é uma relação de equivalência, pois é reflexiva, simétrica e transitiva.