Matemáticas Discretas TC1003cb.mty.itesm.mx/tc1003/lecturas/tc1003-102.pdfOrden Parcial Ejemplo 7...
Transcript of Matemáticas Discretas TC1003cb.mty.itesm.mx/tc1003/lecturas/tc1003-102.pdfOrden Parcial Ejemplo 7...
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 1/23
Matemáticas DiscretasTC1003
Relaciones entre Conjuntos: PropiedadesDepartamento de Matemáticas / Centro de Sistema Inteligentes
ITESM
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 2/23
Representación Alternativa para Relaciones
Sea A un conjunto y R una relación de A en A. Eneste caso diremos que R es una relación sobre A
o una relación en A.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 2/23
Representación Alternativa para Relaciones
Sea A un conjunto y R una relación de A en A. Eneste caso diremos que R es una relación sobre A
o una relación en A. Alternativamente al diagramade flechas del conjunto hacia si mismo:
a
b
c
a
b
c
a
b
c
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 3/23
Ejemplo
Si A = {1, 2, 3, 4} yR = {(1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (4, 1)} dibuje eldiagrama de flechas de las relación.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 3/23
Ejemplo
Si A = {1, 2, 3, 4} yR = {(1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (4, 1)} dibuje eldiagrama de flechas de las relación.Soluci on
1 2
34
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 4/23
Relación Reflexiva
Definici onSean A un conjunto y R una relación. Se dice que
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 4/23
Relación Reflexiva
Definici onSean A un conjunto y R una relación. Se dice que■ R es reflexiva si :
∀x, (x ∈ A → (x, x) ∈ R).
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 4/23
Relación Reflexiva
Definici onSean A un conjunto y R una relación. Se dice que■ R es reflexiva si :
∀x, (x ∈ A → (x, x) ∈ R).
Es decir, toda relación que sea reflexiva debe teneral menos n flechas (suponiendo que n es el númerode elementos de A):
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 4/23
Relación Reflexiva
Definici onSean A un conjunto y R una relación. Se dice que■ R es reflexiva si :
∀x, (x ∈ A → (x, x) ∈ R).
Es decir, toda relación que sea reflexiva debetener al menos n flechas (suponiendo que n es elnúmero de elementos de A): deben estar todaslas parejas (a, a) donde a barre todos loselementos de A.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 5/23
Ejemplos
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 5/23
Ejemplos
1 2
34
Relación no Reflexiva
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 5/23
Ejemplos
1 2
34
Relación no Reflexiva
1 2
34
Relación Reflexiva
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 5/23
Ejemplos
1 2
34
Relación no Reflexiva
1 2
34
Relación Reflexiva
Cada nodo debe tener un cíclo.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 6/23
Ejemplos
De acuerdo a la mtriz de adyacencia de unarelación:
1 · · ·...
. . .
0. . .
1 · · ·... 1
. . .
1
Relación No reflexiva Relación Reflexiva
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 6/23
Ejemplos
De acuerdo a la mtriz de adyacencia de unarelación:
1 · · ·...
. . .
0. . .
1 · · ·... 1
. . .
1
Relación No reflexiva Relación Reflexiva
En la diagonal principal debe haber sólo unospara relaciones reflexivas.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 6/23
Ejemplos
De acuerdo a la mtriz de adyacencia de unarelación:
1 · · ·...
. . .
0. . .
1 · · ·... 1
. . .
1
Relación No reflexiva Relación Reflexiva
En la diagonal principal debe haber sólo unospara relaciones reflexivas. En las no reflexivas hayal menos un cero.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 7/23
Relación Simétrica
Definici onSean A un conjunto y R una relación.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 7/23
Relación Simétrica
Definici onSean A un conjunto y R una relación. Se dice queR es simétrica si
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 7/23
Relación Simétrica
Definici onSean A un conjunto y R una relación. Se dice queR es simétrica si
∀x, y, ((x, y) ∈ R → (y, x) ∈ R).
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 7/23
Relación Simétrica
Definici onSean A un conjunto y R una relación. Se dice queR es simétrica si
∀x, y, ((x, y) ∈ R → (y, x) ∈ R).
Que no nos engañe la implicación: no dice quetengamos flechas de x a y para todo x y y:
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 7/23
Relación Simétrica
Definici onSean A un conjunto y R una relación. Se dice queR es simétrica si
∀x, y, ((x, y) ∈ R → (y, x) ∈ R).
Que no nos engañe la implicación: no dice quetengamos flechas de x a y para todo x y y: Diceque en caso de haber una flecha de x a y
debemos de tener una de y a x en las relacionessimétricas.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 8/23
Ejemplos
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 8/23
Ejemplos
1 2
34
Relación no simétrica
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 8/23
Ejemplos
1 2
34
Relación no simétrica
1 2
34
Relación Simétrica
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 9/23
Relación Antisimétrica
Definici onSean A un conjunto y R una relación.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 9/23
Relación Antisimétrica
Definici onSean A un conjunto y R una relación. Se dice queR es antisimétrica si
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 9/23
Relación Antisimétrica
Definici onSean A un conjunto y R una relación. Se dice queR es antisimétrica si
∀x, y, ((x, y) ∈ R ∧ (y, x) ∈ R → x = y).
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 9/23
Relación Antisimétrica
Definici onSean A un conjunto y R una relación. Se dice queR es antisimétrica si
∀x, y, ((x, y) ∈ R ∧ (y, x) ∈ R → x = y).
Cuando están las parejas (x, y) y (y, x) en larelación, es porque las parejas son (x, x).
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 10/23
Ejemplos
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 10/23
Ejemplos
1 2
34
Relación no Antisimétrica
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 10/23
Ejemplos
1 2
34
Relación no Antisimétrica
1 2
34
Relación Antisimétrica
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 11/23
Relación Transitiva
Definici onSean A un conjunto y R una relación.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 11/23
Relación Transitiva
Definici onSean A un conjunto y R una relación. Se dice queR es transitiva si
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 11/23
Relación Transitiva
Definici onSean A un conjunto y R una relación. Se dice queR es transitiva si
∀x, y, z, ((x, y) ∈ R ∧ (y, z) ∈ R → (x, z) ∈ R).
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 12/23
Ejemplos
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 12/23
Ejemplos
1 2
34
Relación no Transitiva
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 12/23
Ejemplos
1 2
34
Relación no Transitiva
1 2
34
Relación Transitiva
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 13/23
Relación de Equivalencia
Definici onSean A un conjunto y R una relación.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 13/23
Relación de Equivalencia
Definici onSean A un conjunto y R una relación. Se dice queR es una relación de equivalencia si
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 13/23
Relación de Equivalencia
Definici onSean A un conjunto y R una relación. Se dice queR es una relación de equivalencia si R es reflexiva,simétrica y transitiva.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 14/23
Ejemplos
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 14/23
Ejemplos
1 2
34
Relación no de Equivalencia
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 14/23
Ejemplos
1 2
34
Relación no de Equivalencia
1 2
34
Relación de Equivalencia
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 15/23
Relación de Orden Parcial
Definici onSean A un conjunto y R una relación.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 15/23
Relación de Orden Parcial
Definici onSean A un conjunto y R una relación. Se dice queR es una relación de orden parcial si
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 15/23
Relación de Orden Parcial
Definici onSean A un conjunto y R una relación. Se dice queR es una relación de orden parcial si R esreflexiva, antisimétrica y transitiva.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 16/23
Ejemplos
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 16/23
Ejemplos
1 2
34
Relación que no es Orden Parcial
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 16/23
Ejemplos
1 2
34
Relación que no es Orden Parcial
1 2
34
Relación de Orden Parcial
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 17/23
Ejemplo
Considere el conjunto
A = {1, 2, 3}
y la relación:
R =
{
(2, 2) , (2, 3) , (1, 2) ,
(1, 1) , (3, 3)
}
Indique cuáles propiedades tiene la relación.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 18/23
Ejemplo
Indica cuáles de las siguientes son relaciones deequivalencia:1. mod5 en los enteros2. La relación vecinos en los paises3. Primos en una familia4. ≥ en los enteros
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 19/23
Cerradura Transitiva de una Relación
Definici onSean A un conjunto y R una relación. La cerraduratransitiva de R es una relación R′que cumple:
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 19/23
Cerradura Transitiva de una Relación
Definici onSean A un conjunto y R una relación. La cerraduratransitiva de R es una relación R′que cumple:■ R′ es transitiva,
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 19/23
Cerradura Transitiva de una Relación
Definici onSean A un conjunto y R una relación. La cerraduratransitiva de R es una relación R′que cumple:■ R′ es transitiva,■ R ⊆ R′ (R′ contiene a R), y
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 19/23
Cerradura Transitiva de una Relación
Definici onSean A un conjunto y R una relación. La cerraduratransitiva de R es una relación R′que cumple:■ R′ es transitiva,■ R ⊆ R′ (R′ contiene a R), y■ Cualquier otra relación transitiva que contiene a
R también contiene a R′.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 19/23
Cerradura Transitiva de una Relación
Definici onSean A un conjunto y R una relación. La cerraduratransitiva de R es una relación R′que cumple:■ R′ es transitiva,■ R ⊆ R′ (R′ contiene a R), y■ Cualquier otra relación transitiva que contiene a
R también contiene a R′.Es decir, la cerradura transitiva de una relación R
es la más pequeña relación transitiva que contienea R.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 20/23
Ejemplos
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 20/23
Ejemplos
1 2
34
Relación
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 20/23
Ejemplos
1 2
34
Relación
1 2
34
Cerradura Transitiva
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 20/23
Ejemplos
1 2
34
Relación
1 2
34
Cerradura Transitiva
Cuidado: A veces hace falta una segunda pasadapara revisar si ya es transitiva.
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 21/23
Considere el conjunto
A = {1, 2, 3}
y la relación sobre A:
R =
{
(1, 1) , (1, 2) , (1, 3) ,
(2, 1) , (2, 2) , (3, 3)
}
Sólo de la siguiente lista indique cuáles parejasdeben aãdirse a R en la cerradura transitiva:1. (2, 3)
2. (3, 1)
3. (3, 2)
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 22/23
Partición de un Conjunto
Definici onSea A un conjunto no vacío. Una partición para A
es una colección de subconjuntos de A, A1,A2,. . . ,Am tal que
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 22/23
Partición de un Conjunto
Definici onSea A un conjunto no vacío. Una partición para A
es una colección de subconjuntos de A, A1,A2,. . . ,Am tal que■ Ningún subconjunto Ai es vacío:
∀i, Ai 6= ∅
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 22/23
Partición de un Conjunto
Definici onSea A un conjunto no vacío. Una partición para A
es una colección de subconjuntos de A, A1,A2,. . . ,Am tal que■ Ningún subconjunto Ai es vacío:
∀i, Ai 6= ∅
■ Los conjuntos no tienen elemento en común:
∀i, j, (i 6= j → Ai ∩ Aj = ∅)
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 22/23
Partición de un Conjunto
Definici onSea A un conjunto no vacío. Una partición para A
es una colección de subconjuntos de A, A1,A2,. . . ,Am tal que■ Ningún subconjunto Ai es vacío:
∀i, Ai 6= ∅
■ Los conjuntos no tienen elemento en común:
∀i, j, (i 6= j → Ai ∩ Aj = ∅)
■ La unión de los conjuntos es igual a A:
A1 ∪ A2 ∪ · · · ∪ Am = A
RepresentacionEjemplo 1ReflexivaEjemplo 2Ejemplo 3SimetrıaEjemplo 3AntisimetrıaEjemplo 4TransitividadEjemplo 5EquivalenciaEjemplo 6Orden ParcialEjemplo 7Ejemplo 8Ejemplo 9CerraduraEjemplo 10Ejemplo 11ParticionEjemplo 12
Relaciones entre Conjuntos: Propiedades Matemáticas Discretas - p. 23/23
Ejemplo
Indica cuáles de las siguientes son particiones delconjunto:
{1, 3, {5, 2}, 4}
1. {∅, {1, 3, {5, 2}, 4}}2. {{1}, {3, {5, 2}, 4}}3. {{{1, 3}}, {5, 2}, {4}}4. {{1}, {3}, {{5, 2}}, {4}}