MA265 Semana 2.2a Inducción matemática

Matemática Discreta Relaciones • Representación matricial • Dígrafos • Trayectorias • Relación R n y R ∞ Unidad 1: Teoría de Conjuntos, Lógica proposicional y relaciones Logro de la sesión Al finalizar la sesión estarás preparado para: Representar una relación en notación de conjuntos, de forma matricial y mediante dígrafos. Bibliografía • Profesores UPC – Libro digital – Relaciones: Definición y Representación • Johnsonbaugh R. (2005). Matemáticas Discretas, sexta edición. Editorial Pearson, México. Revisar páginas desde 116 hasta 118. • Epp S. (2012). Matemáticas discretas con aplicaciones . México, D.F. Cengage Learning. Revisar páginas desde 442 hasta 448. Bibliografía textos de consulta. Bibliografía multimedia. Conjunto producto Si A y B son conjuntos no vacíos, se define el conjunto producto o producto cartesiano A  B como: 𝐴  𝐵 = {(𝑎, 𝑏) / 𝑎  𝐴 y 𝑏  𝐵} Ejemplo 1 Sea 𝐴 = 𝑎, 𝑏, 𝑐 𝑦 𝐵 = 1; 2 , halle el producto cartesiano 𝐴  𝐵 Solución: 𝐴  𝐵 = { 𝑎, 1 , 𝑎, 2 , 𝑏, 1 , 𝑏, 2 , 𝑐, 1 , 𝑐, 2 } Teorema : Para dos conjuntos finitos no vacíos cualesquiera A y B , se cumple que:  A  B  =  A  .  B  Ejemplo 2 Halle el número de elementos del producto cartesiano 𝐴  𝐵 , del ejemplo 1 Solución:  A  B  = Conjunto producto (3)(2 ) =6 Relaciones Sean A y B conjuntos no vacíos. Una relación R de A a B es un subconjunto de A  B. • Si R  A  B y ( a , b )  R , se dice que a está relacionada con b por R y se escribe a R b . • Si A = B , R  A  A es una relación sobre A . • Si a no está relacionado con b mediante R , se escribe ( a , b )  R . • El dominio de R (Dom( R )) es el conjunto de todos los primeros elementos de los pares ordenados que forman R . • El rango de R (Ran( R )) es el conjunto de todos los segundos elementos de los pares ordenados que forman R . Ejemplo : Dada la relación R = {(1; 2), (1; 3), (2; 2), (2; 3), (3; 2),(4; 1)} definida sobre A = {1; 2; 3; 4}, determine el dominio y rango de R. Solución: Dom( R ) = {1; 2; 3; 4} Ran( R )= {1; 2; 3}, Matriz de una Relación Si A y B son conjuntos finitos con n y p elementos respectivamente, y R es una relación de A a B, se representa R por la matriz de orden n  p , M R =  m ij  , la cual se define por: 𝑚 𝑖𝑗 = ൝ 1, 𝑠𝑖 (𝑎 𝑖 , 𝑏 𝑗 ) ∈ 𝑅 0, 𝑠𝑖 (𝑎 𝑖 , 𝑏 𝑗 ) ∉ 𝑅 Ejemplo : Sea R = {(1; 2), (1; 3), (2; 2), (2; 3), (3; 2)} una relación definida en A = {1; 2; 3}, entonces: 𝐷𝑜𝑚(𝑅) = {1; 2; 3}, 𝑅𝑎𝑛(𝑅) = {2; 3} y 𝑀 𝑅 = 1 2 3 1 2 3 0 1 1 0 1 1 0 1 0 Matriz de una Relación Dígrafos Sea A un conjunto finito y R una relación sobre A . Trace un pequeño círculo para cada elemento de A y marque el círculo con el elemento correspondiente de A . Estos círculos se denominan vértices . Trace una flecha, a la que se llama lado, arco o arista , del vértice a i al vértice a j si y solamente si a i R a j . La representación gráfica resultante de R se llama gráfica dirigida o dígrafo de R . e a d c b Dígrafos R es una relación sobre A = {a, b, c, d, e} M R = 𝑎 𝑏 𝑐 𝑑 𝑒 𝑎 𝑏 𝑐 𝑑 𝑒 1 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 1 Entonces su dígrafo es: Ejemplo: Grado interno y externo Si R es una relación sobre un conjunto A y a  A , entonces: • El grado interno de a es el número de elementos b  A tal que ( b , a )  R. • El grado externo de a es el número de elementos b  A tal que ( a , b )  R . e a d c b Grado interno y externo Ejemplo : En el dígrafo mostrado, el grado interno de c es 3 y el grado externo de c es 0. Ejercicio: Dar tres ejemplos 1 . __________________________ 2 . __________________________ 3 . __________________________ x Gr Int(x) Gr Ext(x) a b c 3 0 d e x Gr Int(x) Gr Ext(x) a 3 4 b 2 3 c 3 0 d 1 1 e 3 4 M R = 𝑎 𝑏 𝑐 𝑑 𝑒 𝑎 𝑏 𝑐 𝑑 𝑒 1 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 1 Trayectorias Trayectorias Una trayectoria de longitud n de a a b es una secuencia finita:  : 𝑎, 𝑥 1 , 𝑥 2 , 𝑥 3 , … … , 𝑥 𝑛−1 , 𝑏 que comienza con a y termina con b tal que: 𝑎𝑅𝑥 1 , 𝑥 1 𝑅𝑥 2 , 𝑥 2 𝑅𝑥 3…