Ley de conjuntos

Teoría
 de
 la
 Computación
 

1
 

Teoría
 de
 la
 Computación
 

•  Actividad en Clase 1 •  Exposición de Tema •  Actividad en Clase 2 •  Tarea
 

2
 

Actividad en clase 1

Teoría
 de
 la
 Computación
 

1.  Expresar en extensión el conjunto {x|x E N, x < 10}. 2. Expresar en intención el conjunto {4, 6, 8, 12, 14, 16}. 3. ¿Cuál es eltamaño del conjunto {!} (esto es, cuántos elementos contiene)? 4. Sean los conjuntos A = {a, b}, B = {1, 2, 3}. Calcular las siguientes operaciones: a) (A U B) − A b) A U (B − A) c) 2AUB d) A X (AUB)
3
 

Teoría
 de
 la
 Computación
 

• Equivalencias de conjuntos
Una equivalencia de conjuntos es útil para reemplazar una expresión con operaciones de conjuntos por otraequivalente pero más conveniente. Generalmente más simple. Ej: (AC ! BC )C = A " B

4
 

Teoría
 de
 la
 Computación
 

• Equivalencias de conjuntos
• Algunas equivalencias frecuentes son: • Leyes conmutativas conjuntos A y B. • Leyes distributivas • Leyes de Morgan • Doble complemento
A ! (B " C) = (A ! B) " (A ! C), A " (B ! C) = (A " B) ! (A " C)

A ! B = B ! A, A " B = B "A

para los

(A ! B)C = A C " BC , (A " B)C = A C ! BC (AC )C = A

5
 

Teoría
 de
 la
 Computación
 

• Relaciones y funciones de Conjuntos
- Derivan directamente del producto cartesiano de conjuntos. - Una relación es todo subconjunto de un producto cartesiano. Ej: La relación ! contiene los pares de números naturales tales que el primer componente es menor o igual alsegundo: {(1, 1), (1, 2), (1, 3), (2, 3), . . .}
6
 

Teoría
 de
 la
 Computación
 

• Relaciones y funciones de Conjuntos
Esta definición matemática de relación no parece tener mucho que ver con la idea intuitiva de que una cosa “tiene relación con otra”, pero en realidad ambas nociones sí corresponden. Por ejemplo, dado un conjunto de personas P = {Leonor, Elías, Arturo,Marta}. ¿Cuál es el producto cartesiano P X P?

7
 

Teoría
 de
 la
 Computación
 

• Relaciones de Conjuntos
Estamos familiarizados con la familia vista como una relación entre personas. Consideremos más específicamente la relación “x es padre de y”. Del producto cartesiano anterior, cuyos pares (x, y) corresponden a relaciones “x es padre de y”, un subconjunto de esteproducto cartesiano sería, {(Leonor, Arturo),(Leonor, Marta), (Elías, Arturo), (Elías, Marta)} consideremos que Leonor y Elías son padres de Arturo y Marta. Obviamente considerando la relación establecida no cualquier subconjunto corresponde a la misma.
8
 

Teoría
 de
 la
 Computación
 

• Relaciones de Conjuntos
- Inverso de una relación R.- Denotada como R-1 es aquella donde seinvierte el orden de los pares ordenados. Esto es: R-1 = {(x,y) | (y,x) E R}. Ej: Inverso de la relación {(1,2),(2,3),(1,3)} es {(2,1),(3,2), (3,1)}. - Relación Reflexiva.- Se dice que una relación binaria D X D es reflexiva cuando contiene todos los pares de la forma (x,x), para x E D. Ej: si D = {1,2,3}, la relación en {1,2,3} X {1,2,3} con los elementos {(2,2),(2,3),(3,3),(1,2),(1,1),(1,3)} esreflexiva, pero {(2,2),(2,3),(1,2),(1,1),(1,3)} no lo es.
9
 

Teoría
 de
 la
 Computación
 

• Relaciones de Conjuntos
- Relación simétrica.- si y solo si siempre que contiene un par (x,y) también contiene (y,x). Ej: {(2,2),(1,2),(1,1),(2,1)} es simétrica, pero {(2,2),(2,3),(3,3),(1,2),(1,1)} no lo es. - Relación Transitiva.- siempre que contiene los pares (x,y) y (y,z)también contiene (x,z). Ej: la relación {(2,3),(1,2), (1,1),(1,3)} es transitiva, pero {(2, 3), (1, 2), (1, 1)} no lo es. - Cerradura Reflexiva.- Corresponde a la menor extensión de R, expresada como R ! ! que sea reflexiva. Sólo agrega pares ordenados necesarios. Ej: La cerradura reflexiva de R1 = {(2,3),(1,2),(1,1),(1,3)} es {(2,3),(1,2),(1,1),(1,3),(2,2),(3,3)}.
10
 

• Relaciones de...