Propiedades de las relaciones

Course: Álgebra Discreta

Date: February 13, 2023 8:34 PM Status: Done Year: 2022

• Propiedades de las relaciones

  • Definición de reflexividad ↓

    • $R \text{ es reflexiva} \Leftrightarrow \forall x \in A, (x,x)\in R

      

      • Todos los nodos se relacionan con sí mismos
      • Es reflexiva is tiene todos 1s en la diagonal de la matriz $A$.

    • $R\text{ no es reflexiva}\iff \exists x\in A,(x,x)\notin R$

      

  • Definición de arreflexividad ↓

    • $R\text{ es arreflexiva }\iff \forall x\in A,(x,x)\notin R$

      

      • No hay ningún nodo que se relacione consigo mismo.
      • Es arreflexiva cuando tiene todo 0s en la diagonal.

  • Definición de relación simétrica ↓

    • $R\text{ es simeˊtrica }\iff \forall (x,y)\in A[(x,y)\in R\Rightarrow (y,x)\in R]$

      

      • Es simétrica cuando la matriz es simétrica.
      • En el digrafo, todas las relaciones son bidireccionales.

    • $R\text{ no es simeˊtrica }\iff \exists x,y\in A/[(x,y)\in R\wedge (y,x)\notin R]$

      

      • Cuando existe una relación que no es bidireccional.

  • Definición de relación asimétrica ↓

    • $R\text{ es asimeˊtrica }\iff \forall (x,y)\in A[(x,y)\in R\Rightarrow (y,x)\notin R]$

      

      • Cuando no existe ninguna relación que sea simétrica o bidireccional

  • Definición de relación antisimétrica ↓

    • $R\text{ es antisimeˊtrica }\iff x,y\in A/[(x,y)\in R\wedge (y,x)\in R\Rightarrow x=y]$

      

      • Es antisimétrica cuando la única relación simétrica es la de la diagonal, el nodo consigo mismo.

  • Definición de relación transitiva ↓

    • $R\text{ es transitiva }\iff x,y,z\in A,[(x,y)\in R\wedge (y,z)\in R\Rightarrow (x,z)\in R]$

        ![https://remnote-user-data.s3.amazonaws.com/cEXE_Q3i0-JFNjSkBE-MFTpFcCviR-orJXEXyETlJ0JqL_PT8YQUBA87ooDY0OsDH4xgh9SPb_1zOQj3Q9NSvHpBB0cOeOgScFzoJu6KIqUhVFXfGEvpn1j8AMkGEsly.png](https://remnote-user-data.s3.amazonaws.com/cEXE_Q3i0-JFNjSkBE-MFTpFcCviR-orJXEXyETlJ0JqL_PT8YQUBA87ooDY0OsDH4xgh9SPb_1zOQj3Q9NSvHpBB0cOeOgScFzoJu6KIqUhVFXfGEvpn1j8AMkGEsly.png)
        
      

      • Si existe una trayectoria de longitud 2 entre $x$ y $z$, entonces existe una trayectoria de longitud 1 entre ellos.

    • $R\text{ es atransitiva }\iff x,y,z\in A,[(x,y)\in R\wedge (y,z)\in R\Rightarrow (x,z)\notin R]$

        ![https://remnote-user-data.s3.amazonaws.com/FR_jeqvTvxgv8L3snOVQn7_VtIYqVyF10Yeu4jzM_BhR-ZsQR3D2cFMHGqAYAugkgheWIbUpZh81v2-JYtu32sA-VQ2OtlztwrBkDffcq-edKIZp4FJTnqbdsTomnyeg.png](https://remnote-user-data.s3.amazonaws.com/FR_jeqvTvxgv8L3snOVQn7_VtIYqVyF10Yeu4jzM_BhR-ZsQR3D2cFMHGqAYAugkgheWIbUpZh81v2-JYtu32sA-VQ2OtlztwrBkDffcq-edKIZp4FJTnqbdsTomnyeg.png)
        
      

  • Cómo determino analíticamente la transitividad? ↓

    

    • Veo primero la matriz de $R^2$, y si hay trayectoria de longitud 2, entonces tiene que haber trayectoria de longitud 1 en la matriz de $R$