Matemáticas discretas - Relaciones

Siempre que se discuten los conjuntos, la relación entre los elementos de los conjuntos es lo siguiente que surge. Relations puede existir entre objetos del mismo conjunto o entre objetos de dos o más conjuntos.

Definición y propiedades

Una relación binaria R del conjunto xay (escrito como $ xRy $ o $ R (x, y) $) es un subconjunto del producto cartesiano $ x \ times y $. Si el par ordenado de G se invierte, la relación también cambia.

Generalmente, una relación n-aria R entre los conjuntos $ A_1, \ dots, \ y \ A_n $ es un subconjunto del producto n-ario $ A_1 \ times \ dots \ times A_n $. La cardinalidad mínima de una relación R es cero y la máxima es $ n ^ 2 $ en este caso.

Una relación binaria R en un solo conjunto A es un subconjunto de $ A \ times A $.

Para dos conjuntos distintos, A y B, que tienen cardinalidades m y n respectivamente, la cardinalidad máxima de una relación R de A a B es mn .

Dominio y rango

Si hay dos conjuntos A y B, y la relación R tiene un par de orden (x, y), entonces -

  • los domainde R, Dom (R), es el conjunto $ \ lbrace x \: | \: (x, y) \ en R \: para \: algunos \: y \: en \: B \ rbrace $

  • los range de R, Ran (R), es el conjunto $ \ lbrace y \: | \: (x, y) \ en R \: para \: algunos \: x \: en \: A \ rbrace $

Ejemplos

Sea, $ A = \ lbrace 1, 2, 9 \ rbrace $ y $ B = \ lbrace 1, 3, 7 \ rbrace $

  • Caso 1 - Si la relación R es 'igual a' entonces $ R = \ lbrace (1, 1), (3, 3) \ rbrace $

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

  • Caso 2 - Si la relación R es 'menor que' entonces $ 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 - Si la relación R es 'mayor que' entonces $ R = \ lbrace (2, 1), (9, 1), (9, 3), (9, 7) \ rbrace $

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

Representación de relaciones usando Graph

Una relación se puede representar mediante un gráfico dirigido.

El número de vértices del gráfico es igual al número de elementos del conjunto a partir del cual se ha definido la relación. Para cada par ordenado (x, y) en la relación R, habrá un borde dirigido desde el vértice 'x' al vértice 'y'. Si hay un par ordenado (x, x), habrá un bucle automático en el vértice 'x'.

Supongamos que hay una relación $ R = \ lbrace (1, 1), (1,2), (3, 2) \ rbrace $ en el conjunto $ S = \ lbrace 1, 2, 3 \ rbrace $, puede ser representado por el siguiente gráfico -

Tipos de relaciones

  • los Empty Relation entre los conjuntos X e Y, o en E, está el conjunto vacío $ \ conjunto vacío $

  • los Full Relation entre los conjuntos X e Y es el conjunto $ X \ times Y $

  • los Identity Relationen el conjunto X es el conjunto $ \ lbrace (x, x) | x \ in X \ rbrace $

  • La relación inversa R 'de una relación R se define como - $ R' = \ lbrace (b, a) | (a, b) \ in R \ rbrace $

    Example - Si $ R = \ lbrace (1, 2), (2, 3) \ rbrace $ entonces $ R '$ será $ \ lbrace (2, 1), (3, 2) \ rbrace $

  • Una relación R en el conjunto A se llama Reflexive si $ \ forall a \ in A $ está relacionado con a (aRa se mantiene)

    Example - La relación $ R = \ lbrace (a, a), (b, b) \ rbrace $ en el conjunto $ X = \ lbrace a, b \ rbrace $ es reflexiva.

  • Una relación R en el conjunto A se llama Irreflexive si ningún $ a \ en A $ está relacionado con a (aRa no se mantiene).

    Example - La relación $ R = \ lbrace (a, b), (b, a) \ rbrace $ en el conjunto $ X = \ lbrace a, b \ rbrace $ es irreflexiva.

  • Una relación R en el conjunto A se llama Symmetric si $ xRy $ implica $ yRx $, $ \ para todos los x \ en A $ y $ \ para todos y \ en A $.

    Example - La relación $ R = \ lbrace (1, 2), (2, 1), (3, 2), (2, 3) \ rbrace $ en el conjunto $ A = \ lbrace 1, 2, 3 \ rbrace $ es simétrico.

  • Una relación R en el conjunto A se llama Anti-Symmetric si $ xRy $ y $ yRx $ implica $ x = y \: \ forall x \ en A $ y $ \ forall y \ en A $.

    Example - La relación $ R = \ lbrace (x, y) \ con N | \: x \ leq y \ rbrace $ es antisimétrica ya que $ x \ leq y $ y $ y \ leq x $ implica $ x = y $ .

  • Una relación R en el conjunto A se llama Transitive si $ xRy $ y $ yRz $ implican $ xRz, \ forall x, y, z \ en A $.

    Example - La relación $ R = \ lbrace (1, 2), (2, 3), (1, 3) \ rbrace $ en el conjunto $ A = \ lbrace 1, 2, 3 \ rbrace $ es transitiva.

  • Una relación es una Equivalence Relation si es reflexiva, simétrica y transitiva.

    Example - La relación $ R = \ lbrace (1, 1), (2, 2), (3, 3), (1, 2), (2,1), (2,3), (3,2), (1,3), (3,1) \ rbrace $ en el conjunto $ A = \ lbrace 1, 2, 3 \ rbrace $ es una relación de equivalencia ya que es reflexiva, simétrica y transitiva.