1AMA0265 Sesion 3.2 Induccion - Invariante[Diapo]

UPC – Departamento de Ciencias – Matemática Discreta (MA265) Profesores MA265 Relaciones: Definición, representación CONTENIDO UNIDAD Nº3: RELACIONES Y FUNCIONES 3.1 Definición y representación de relaciones. ▪ Introducción ▪ Relación ▪ Matriz de una relación ▪ Dígrafos ▪ Trayectorias ▪ Relación 𝑅 𝑛 y 𝑅 ∞ UPC – Departamento de Ciencias – Matemática Discreta (MA265) Profesores MA265 Relaciones: Definición, representación Introducción En la vida cotidiana se hace necesario clasificar y ordenar individuos (cosas, animales, personas o números), de una u otra manera. Precisamente buscando llegar a los procesos de clasificación y ordenación de todo aquello que posee características intrínsecas, se estudiará en este capítulo el concepto de relación. Este capítulo tiene como finalidad estudiar las relaciones binarias (relación entre dos elementos a y b de dos conjuntos A y B respectivamente), desde el punto de vista discreto. Las relaciones son de fundamental importancia en el área de computación. Una estructura compuesta de datos, tal como un arreglo, lista, árbol, es generalmente usada para representar simultáneamente a un conjunto de datos y a una relación que se cumple entre los miembros del conjunto. Definición Si 𝐴 y 𝐵 son conjuntos no vacíos, se define el producto cartesiano 𝐴 × 𝐵 como: 𝐴 × 𝐵 = {(𝑎; 𝑏)/𝑎 ∈ 𝐴 ∧ 𝑏 ∈ 𝐵} Ejemplo 1 Dados los conjuntos 𝐴 = {1; 2; 3; 4} y 𝐵 = {𝑎; 𝑏; 𝑐} determinar el producto cartesiano 𝐴 × 𝐵 : 𝐴 × 𝐵 = {(1; 𝑎), (1; 𝑏), (1; 𝑐), (2; 𝑎), (2; 𝑏), (2; 𝑐), (3; 𝑎), (3; 𝑏), (3; 𝑐), (4; 𝑎), (4; 𝑏), (4; 𝑐)} Se observa que: |𝐴 × 𝐵| = |𝐴||𝐵| Definición Sean 𝐴 y 𝐵 conjuntos no vacíos. Una relación 𝑅 de 𝐴 en 𝐵 es un subconjunto de 𝐴 × 𝐵 . Ejemplo 2 Dados los conjuntos 𝐴 = {2; 3; 4} y 𝐵 = {3; 6; 16} , hallemos la relación R “ d ivide” de 𝐴 en 𝐵 . Primero hallemos el producto cartesiano 𝐴 × 𝐵 : 𝐴 × 𝐵 = {(2; 3), (2; 6), (2; 16), (3; 3), (3; 6), (3; 16), (4; 3), (4; 6), (4; 16)} La relación R es el conjunto de pares ordenados (𝑥; 𝑦) 𝑡𝑎𝑙 𝑞𝑢𝑒 𝑥 𝑑𝑖𝑣𝑖𝑑𝑒 𝑎 𝑦 , se puede decir también que "𝑥 𝑒𝑠 𝑑𝑖𝑣𝑖𝑠𝑜𝑟 𝑑𝑒 𝑦" y se representa así: 𝑥|𝑦 . 𝑅 = {(2; 6), (2; 16), (3; 3), (3; 6), (4; 16)} Se observa que 𝑅 es un subconjunto de 𝐴 × 𝐵 ▪ Si 𝑅 ⊆ 𝐴 × 𝐵 y (𝑎; 𝑏) ∈ 𝑅 , se dice que 𝑎 está relacionada con 𝑏 por 𝑅 y se escribe 𝑎𝑅𝑏 . ▪ Si 𝐴 = 𝐵 , 𝑅 ⊆ 𝐴 × 𝐴 , es una relación sobre 𝐴 . UPC – Departamento de Ciencias – Matemática Discreta (MA265) Profesores MA265 Dominio El dominio de 𝑅 ( Dom(𝑅) ) es el conjunto de todos los primeros elementos de los pares ordenados que forman 𝑅 . Rango El rango de 𝑅 ( Ran(𝑅) ) es el conjunto de todos los segundos elementos de los pares ordenados que forman 𝑅 . Ejemplo 3 Sea 𝐴 = {2; 3; 4; 8} y sea 𝑅 la relación sobre 𝐴 definida por (𝑥; 𝑦) ∈ 𝑅 si 𝑥 < 𝑦 . 𝑅 = {(2; 3), (2; 4), (2; 8), (3; 4), (3; 8), (4; 8)} . 𝐷𝑜𝑚(𝑅) = {2; 3; 4} 𝑅𝑎𝑛(𝑅) = {3; 4; 8} Matriz de una relación Si 𝐴 y 𝐵 son conjuntos finitos con 𝑛 y 𝑝 elementos respectivamente, y 𝑅 es una relación de 𝐴 en 𝐵 , se representa 𝑅 por la matriz de orden 𝑛 × 𝑝 , 𝑀 𝑅 = [𝑚 𝑖𝑗 ] , la cual se define por 𝑚 𝑖𝑗 = { 1, 𝑠𝑖 (𝑎 𝑖 ; 𝑏 𝑗 ) ∈ 𝑅 0, 𝑠𝑖 (𝑎 𝑖 ; 𝑏 𝑗 ) ∉ 𝑅 Ejemplo 4 Sea 𝐴 = {4; 5; 8} y 𝑅 la relación sobre 𝐴 definida por (𝑥; 𝑦) ∈ 𝑅 si 𝑥 + 𝑦 ≥ 10 . 𝑅 = {(4; 8), (5; 5), (5; 8), (8; 4), (8; 5), (8; 8)} Entonces: 𝑀 𝑅 = 4 5 8 4 5 8 [ 0 0 1 0 1 1 1 1 1 ] . Dígrafos Una forma de visualizar una relación en un conjunto 𝐴 es dibujar su dígrafo (palabra derivada de gráfico dirigido). Se Traza un pequeño círculo para cada elemento de A y se rotula el círculo con el elemento correspondiente de A. Estos círculos se denominan vértices. Luego, se traza una flecha, a la que se llama lado, arco o arista, del vértice 𝑎 𝑖 al vértice 𝑎 𝑗 si y solamente si 𝑎 𝑖 𝑅𝑎 𝑗 . La representación gráfica resultante de 𝑅 se llama gráfica dirigida o dígrafo de 𝑅 . UPC – Departamento de Ciencias – Matemática Discreta…