MA265 Sesión 10.1b Ejercicios de Funciones booleanas y mapa de Karnaugh (1)

UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 1 Permutaciones CONTENIDO Unidad 3: RELACIONES Y FUNCIONES 3.4 Funciones de permutación ▪ Definición ▪ Permutación inversa ▪ Composición de permutaciones ▪ Ciclos en una permutación ▪ Transposiciones ▪ Periodo de una permutación UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 2 Permutaciones En esta sección se estudia las biyecciones de un conjunto 𝐴 a si mismo. Es un tema muy importante en el caso que 𝐴 sea finito. Las biyecciones en un conjunto finito tienen una variedad de aplicaciones en la Matemática, ciencias de la computación y física. Definición Una biyección p de un conjunto A a si mismo ( p : A → A ) se denomina permutación de A . Notación Si 𝐴 = {𝑎 1 , 𝑎 2 , . . . , 𝑎 𝑛 } es un conjunto finito y 𝑝 es una biyección en 𝐴 , se enlista los elementos de A y los valores de la función 𝑝(𝑎 1 ), 𝑝(𝑎 2 ), … … , 𝑝(𝑎 𝑛 ) de la siguiente forma: 𝑝 = ( 𝑎 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 . Ejemplo 1 Sea 𝐴 = {1, 2, 3} . Todas las permutaciones de 𝐴 son: 𝑝 = ( 1 2 3 1 2 3 ) 𝑝 = ( 1 2 3 1 3 2 ) 𝑝 = ( 1 2 3 2 1 3 ) 𝑝 = ( 1 2 3 2 3 1 ) 𝑝 = ( 1 2 3 3 1 2 ) 𝑝 = ( 1 2 3 3 2 1 ) En el ejemplo, el conjunto 𝐴 tiene 3 elementos y hay 6 permutaciones. Teorema: Si A = { a 1 , a 2 , ..., a n }, es un conjunto que contiene n elementos, entonces hay n ! permutaciones en A . Permutación inversa Dada una permutación p en un conjunto 𝐴, se define la permutación inversa p – 1 así: (𝑎, 𝑏) ∈ 𝑝 −1 ↔ (𝑏, 𝑎) ∈ 𝑝 Ejemplo 2 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 5 3 7 6 2 4 1 ) UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 3 𝑝 −1 (1) = 5 𝑦𝑎 𝑞𝑢𝑒 𝑝(5) = 1 𝑝 −1 (2) = 3 𝑦𝑎 𝑞𝑢𝑒 𝑝(3) = 2 𝑝 −1 (3) = 7 𝑦𝑎 𝑞𝑢𝑒 𝑝(7) = 3 𝑝 −1 (4) = 6 𝑦𝑎 𝑞𝑢𝑒 𝑝(6) = 4 𝑝 −1 (5) = 2 𝑦𝑎 𝑞𝑢𝑒 𝑝(2) = 5 𝑝 −1 (6) = 4 𝑦𝑎 𝑞𝑢𝑒 𝑝(4) = 6 𝑝 −1 (7) = 1 𝑦𝑎 𝑞𝑢𝑒 𝑝(1) = 7 Composición de permutaciones Si consideramos dos permutaciones p y q, si primero “actúa” q y después, sobre el resultado que se obtiene, “actúa” p , resulta otra permutación que llamamos “compuesta de p y q ” y se representa por 𝑝 ∘ 𝑞 , o también por 𝑝𝑞 . Se denomina también producto de permutaciones. Ejemplo 3 Si p = {(1, 3), (2, 4), (3, 2), (4, 5), (5, 1)} y q = {(1, 2), (2, 1), (3, 5), (4, 4), (5, 3)}, entonces el producto de permutaciones (o composición de permutaciones) es 𝑝 ∘ 𝑞 = ( 1 2 3 4 5 3 4 2 5 1 ) ∘ ( 1 2 3 4 5 2 1 5 4 3 ) = ( 1 2 3 4 5 4 3 1 5 2 ) 𝑝 ∘ 𝑞 = {(1, 4), (2, 3), (3, 1), (4, 5), (5, 2)} Observación El producto (composición) de permutaciones es una permutación. Ciclo de longitud r Sean b 1 , b 2 , ..., b r elementos distintos del conjunto A = { a 1 , a 2 , ..., a n }. La permutación p : A → A 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 permutación cíclica de longitud r o ciclo de longitud r , y es denotado por: ( b 1 b 2 ... b r ). Se puede escribir el ciclo también comenzando en cualquier 𝑏 𝑖 , 1 ≤ 𝑖 ≤ 𝑟, y moviéndose en sentido de las manecillas del reloj. Observaciones • Un ciclo en un conjunto A es de longitud 1 si y solo si es la permutación identidad I A . • El producto de dos ciclos no necesariamente es un ciclo. Ejemplo 4 Sea 𝐴 = {1, 2, 3, 4, 5} . El ciclo (4 1 3) de longitud 3, denota la permutación: 𝑝 = ( 1 2 3 4 5 3 2 4 1 5 ) Los ciclos (4 1 3), (1 3 4), (3 4 1) denotan la misma permutación para 𝐴 . UPC – Departamento de Ciencias – MATEMATICA DISCRETA (MA265) Profesores MA265 4 Ciclos disjuntos Se dice que dos ciclos de un conjunto A…