Elementos Discreto (Relaciones)

UNIVERSIDAD DE CARABOBO FACULTAD EXPERIMENTAL DE CIENCIAS Y TECNOLOGÍA DEPARTAMENTO DE COMPUTACIÓN GRUPO DE MATEMÁTICAS DE LA COMPUTACIÓN

ELEMENTOS DISCRETOS Febrero de 2008

Teoría de Relaciones • Una relación definida en los conjuntos A1, A2, …, An, es un subconjunto del producto cartesiano de A1 a An, es decir, R⊆A1×A2×…×An. Relación • R={(x1,x2, …, xn) / x1∈A1 ∧ x2∈A2 ∧…∧ xn∈An ∧ P(x1,x2, …, xn) ≡ v} (Relación n-aria) • (x1, x2, …, xn) ∈ R ↔ (x1, x2, …, xn) ∈ A1xA2x…xAn ∧ P(x1, x2, …, xn) ≡ v Relación Binaria Relación binaria definida en A Relación Terciaria Notación n=2, R ⊆ A1×A2, R = { (x1, x2) / x1∈A1 ∧ x2∈A2 ∧ P(x1, x2) } n=2, R ⊆ A2, R = { (x1, x2) / x1∈A ∧ x2∈A ∧ P(x1, x2) ≡ v } n=3, R ⊆ A1×A2×A3, R = { (x1, x2, x3) / x1∈A1∧ x2∈A2 ∧ x3∈A3 ∧ P(x1, x2, x3) } (x, y) ∈ R sepuede escribir como xRy. (x1, x2, …, xn) ∈ R se puede escribir (x1, x2, …, xn-1)Rxn. • Relación: Es una asociación de elementos entre conjuntos, sin restricciones. • Función: Es una asociación de elementos entre conjuntos, con la restricción: a cada elemento del dominio, le corresponde un solo elemento del codominio. • Conclusión: - Función es una relación especial; - Toda función es una relación;- Toda relación no es necesariamente una función. Sea R = { (x, y) / x∈A ∧ x∈ B ∧ P(x, y) ≡ v } Se definen: • Dominio: D(R) = { x / x∈A ∧ (x, y)∈R } • Rango: R(R) = { y / y∈B ∧ (x, y)∈R } • R. Inversa: R-1 = { (y, x) / (x, y)∈R }, R-1 ⊆ B×A • R. Identidad: Es una relación binaria R ⊆ A×A. IA = { (x, y) / x∈A ∧ y∈A ∧ x=y } o IA = { (x, x) / x∈A } • R. Universal: Es una relación binaria R ⊆ A×B. UA= { (x, y) / x, y ∈ A } • R. Vacía: Dado que ∅ ⊆ A para todo conjunto A, Podemos decir ∅ ⊆ A×A, por lo tanto R = ∅.

Relación vs. Función

Dominio, Rango y Relación inversa de una Relación

Tipos de Relaciones Definidas en A

Hecho Por: Kiara A. Ottogalli F.

UNIVERSIDAD DE CARABOBO FACULTAD EXPERIMENTAL DE CIENCIAS Y TECNOLOGÍA DEPARTAMENTO DE COMPUTACIÓN GRUPO DE MATEMÁTICAS DE LACOMPUTACIÓN

ELEMENTOS DISCRETOS Febrero de 2008

Sean

A = {a, b} B = {1, 2} R = {(a, 1), (a, 2), (b,1)} Grafico Cartesiano:

Grafo dirigido o Dígrafo: G = ((A∪B), R)

2 1 2
Diagrama Sagital:

R

a
Representación de las relaciones

1 a b

b
Matriz de Relación:

1
M=

2 1 0
2×2

A a b

R

B 1 2

a b

1 1

S o R = { (x, z)/ x∈A ∧ z∈C ∧ ∃y∈B[(x, y)∈R ∧ (y, z)∈S] }R S A B C Composición de Relaciones

x

y

SoR
Sean las relaciones: R: A → B S1: B → C S2: B → C T: C → D Entonces: • (S1 ∪ S2) o R = (S1 o R) ∪ (S2 o R) • (S1 ∩ S2) o R ⊆ (S1 o R) ∩ (S2 o R) • T o (S1 ∪ S2) = (T o S1) ∪ (T o S2) • T o (S1 ∩ S2) ⊆ (T o S1) ∩ (T o S2)
Hecho Por: Kiara A. Ottogalli F.

Algunas operaciones con relaciones

UNIVERSIDAD DE CARABOBO FACULTAD EXPERIMENTAL DECIENCIAS Y TECNOLOGÍA DEPARTAMENTO DE COMPUTACIÓN GRUPO DE MATEMÁTICAS DE LA COMPUTACIÓN

ELEMENTOS DISCRETOS Febrero de 2008

Propiedades de las Relaciones

Reflexividad

R es reflexiva ⇔ ∀x [x∈A⇒(x, x)∈R] No Reflexividad: R es no reflexiva ⇔ ∃x [x∈A ∧ (x, x)∉R] Arreflexividad: R es arreflexiva ⇔ ∀x [x∈A ⇒(x, x)∉R] R es simétrica ⇔ ∀x∀y [(x, y∈A ∧ (x, y)∈R)⇒(y, x)∈R] No Simetría: R es nosimétrica ⇔ ∃x∃y [x, y∈A ∧ (x, y)∈R ∧ (y, x)∉R]

Variantes

Simetría

Variantes

Asimetría: R es asimétrica ⇔ ∀x∀y [(x, y∈A ∧ (x, y)∈R)⇒(y, x)∉R] Antisimétrica: R es antisimétrica ⇔ ∀x∀y [(x, y∈A ∧ (x, y)∈R ∧ (y, x)∈R)⇒x=y] R es transitiva ⇔ ∀x∀y∀z [(x, y, z∈A ∧ (x, y)∈R ∧ (y, z)∈R)⇒(x, z)∈R] No transitiva: R es no transitiva ⇔ ∃x∃y∃z [x, y, z∈A ∧ (x, y)∈R ∧ (y, z)∈R ∧ (x, z)∉R]Atransitiva: R es atransitiva ⇔ ∀x∀y∀z [(x, y, z∈A ∧ (x, y)∈R ∧ (y, z)∈R)⇒(x, z)∉R]

Transitividad

Variantes

En la relación Vacío ∅

R=∅ ∅⊆A×A R es arreflexiva, no reflexiva, simétrica, asimétrica, no simétrica, transitiva, atransitiva y no transitiva.

En la relación Identidad

Sea A = {1, 2, 3} IA={ (x, x) / x∈A } = { (1, 1), (2, 2), (3, 3) } IA es reflexiva, simétrica, antisimétrica y...