Ejercicios Aplicaciones de Funciones booleanas-Solucionario

Matemática Discreta Funciones • Funciones de Permutación Logro de la sesión Al finalizar la sesión, el estudiante estará preparado para identificar si una función es una permutación, determinar la composición de permutaciones y el periodo de una permutación. Bibliografía • Profesores UPC – Libro digital – Permutaciones. • Bernard Kolman , (1997). Estructuras de Matemáticas Discretas para la Computación. México. Revisar páginas desde 181 hasta 188. Bibliografía textos de consulta. Una biyección p de un conjunto A a si mismo ( p : A → A ) se denomina permutación de A . Notación Si A = { a 1 , a 2 , ..., a n } es un conjunto finito y p es una biyección en A , se enlista los elementos de A y los valores de la función p ( a 1 ), p ( a 2 ), ...., p ( a n ) de la siguiente forma: Funciones de permutación 𝑝 = 𝑎 1 𝑎 2 … 𝑎 𝑛 𝑝(𝑎 1 ) 𝑝(𝑎 2 ) … 𝑝(𝑎 𝑛 ) Observación Si p es una permutación de un conjunto finito A = { a 1 , a 2 , ..., a n }, entonces la sucesión p ( a 1 ), p ( a 2 ), . . . , p ( a n ) es solo un reordenamiento de los elementos de A . 𝑝 = 𝑎 1 , 𝑝(𝑎 1 ) , 𝑎 2 , 𝑝(𝑎 2 ) , … , 𝑎 𝑛 , 𝑝(𝑎 𝑛 Funciones de permutación Ejemplo 01 La función 𝑝 es una permutación de A 1 2 3 4 1 2 3 4 𝑝 A A Ejemplo 02 Si 𝐴 = 1, 2, 3, 4 , justifique por qué la función p no es una permutación de 𝐴 , donde 𝑝 está determinada por la siguiente correspondencia: 𝑝 1 = 2, 𝑝 2 = 3, 𝑝 3 = 1 𝑦 𝑝 4 = 2 𝑝 = 1 2 3 4 4 3 2 1 𝑝 = 1, 4 , 2, 3 , 3, 2 , (4, 1) Producto de permutaciones Ejemplo 03 Dadas las permutaciones 𝑝 y 𝑞 , sobre el conjunto 𝐴 = 1, 2, 3, 4, 5 𝑝 = {(1, 3), (2, 4), (3, 2), (4, 5), (5, 1)}, y 𝑞 = {(1, 2), (2, 1), (3, 5), (4, 4), (5, 3)} , entonces el producto de permutaciones 𝒑 ∘ 𝒒 , o composición de permutaciones es: Observación El producto de permutaciones es una permutación. 𝑝 1 2 3 4 A 5 1 2 3 4 A 5 1 2 3 4 A 5 𝑞 𝑝 ∘ 𝑞 𝑝 ∘ 𝑞 = 1 , 4 , 2, 3 , 3, 1 , 4, 5 , 5, 2 Permutación inversa En el conjunto 𝐴 = 1, 2, 3, 4, 5, 6, 7 se define la permutación: 𝑝 = 1 2 3 4 5 6 7 7 5 2 6 1 4 3 La permutación inversa 𝒑 −𝟏 es: 𝑝 −1 = 1 2 3 4 5 6 7 Ejemplo 04 𝑝 1 2 3 4 A 5 6 7 1 2 3 4 A 5 6 7 𝑝 −1 1 2 3 4 5 6 7 Teorema Si A = { a 1 , a 2 , ... , a n }, es un conjunto que contiene n elementos, entonces hay n ! permutaciones en A . Definición Sean 𝑏 1 , 𝑏 2 , … , 𝑏 𝑟 , todos elementos distintos del conjunto 𝐴 = {𝑎 1 , 𝑎 2 , … , 𝑎 𝑛 } , la permutación 𝑝: 𝐴 → 𝐴 definida por: p ( b 1 ) = b 2 , p ( b 2 ) = b 3 , ... , p ( b r - 1 ) = b r , p ( b r ) = b 1 , y p ( x ) = x si x  A y x  { b 1 , b 2 , ..., b r } se denomina ciclo de longitud r , y es denotado por ( b 1 b 2 ... b r ) . Ciclo de longitud r Se puede escribir el ciclo también comenzando en cualquier 𝑏 𝑖 , 1 ≤ 𝑖 ≤ 𝑟, y moviéndose en sentido de las manecillas del reloj. Ciclo de longitud r Ejemplo 05 Dada la permutación a. Reescriba la permutación p como un ciclo. b. ¿Cuál es la longitud del ciclo? 𝑝 = 1 2 3 4 5 6 7 7 5 2 4 1 6 3 c. Escriba ciclos equivalentes al obtenido en (a). d. ¿Si un ciclo 𝑞 de un conjunto A es: 𝑞 = (2 3 4 1) , entonces 𝐴 ={1, 2, 3, 4}? Solución 𝑝 = (1 7 3 2 5) 1 7 3 2 5 Solución Longitud 5 Solución 𝑝 = (7 3 2 5 1) 𝑝 = (3 2 5 1 7) 𝑝 = (2 5 1 7 3) 𝑝 = (5 1 7 3 2) Solución No pues podemos tener 𝑞 = 1 2 3 4 5 6 7 2 3 4 1 5 6 7 Observaciones • Un ciclo en un conjunto A es de longitud 1 si y solo si es la permutación identidad 1 A . Ejemplo Si 𝐴 = 1, 2, 3 , la permutación 1 𝐴 es: 1 𝐴 = 1 2 3 1 2 3 • El producto de dos ciclos no necesariamente es un ciclo. Producto de ciclos disjuntos Definición Se dice que dos ciclos de un conjunto A son disjuntos si ningún elemento de A aparece en ambos ciclos. Ejemplo 06 En el conjunto 𝐴 = 1, 2, 3, 4, 5 , 6 : • Los ciclos (1 3 2) y (2 4 6) no son disjuntos. • Los ciclos (3 2 1) y (4 5) son disjuntos. Teorema Una permutación de un conjunto finito que no sea la identidad o un ciclo, puede escribirse como un producto de ciclos disjuntos de longitud mayor o igual que 2. Ejemplo 07 Sea…