• Author / Uploaded
• ana

Citation preview

ESTRUCTURAS DISCRETAS II

Estructuras Discretas II Semigrupos Grupos Dra. Norka Bedregal Alpaca 1

Introducción

Semigrupos

Los grupos y semigrupos son estructuras algebraicas que se utilizan en Teoría de Codificación y en el estudio de máquinas de estado finito Dichas máquinas, reconocedoras de lenguajes, se usan en el diseño de compiladores . Es necesario manejar el concepto de operación binaria cerrada y, de acuerdo a las propiedades que cumpla se le dará un nombre a la estructura. Es así que podrá tratarse de semigrupo, semigrupo con neutro o grupo, y en algunos casos grupo abeliano.

2 Dra. Norka Bedregal Alpaca

Operaciones Binarias

Semigrupos

Definición Dado el conjunto A, se llama operación binaria interna sobre A a cualquier función f cuyo dominio es el producto cartesiano A × A y codominio A, esto es:

* :

A× A → A

(a, b ) → a * b Ejemplos:

La suma y el producto en los enteros modulares son operaciones internas. + : Z ×Z → Z

• : Z ×Z → Z 3 Dra. Norka Bedregal Alpaca

Operaciones Binarias

Semigrupos

Definición Dados los conjuntos A, B y C, una operación binaria externa es una función cuyo dominio es el producto cartesiano A × B y codominio C, esto es: * : A× B → C

(a, b ) → a * b Ejemplo:

La función * definida sobre los naturales y los polinomios con coeficientes reales es una operación externa, * :

IN × P(IR ) → P (IR ) * (n, p ( x) ) = n ⋅ p( x)

4 Dra. Norka Bedregal Alpaca

Operaciones Binarias

Semigrupos

Ejemplo: De forma similar se puede observar que la función definida sobre los enteros y las matrices de orden (m,n), es una operación externa * : Z × M m×n (Z ) → M m×n (Z )

(λ , M ) → *(λ , M ) = λM Notación: Recordar que las operaciones binarias se pueden denotar con el símbolo * o cualquier otro, como •, ∆, ■, □, ◊, ●, etc. Para indicar que en el conjunto A se ha definido la operación binaria * se escribe (A ; *) 5 Dra. Norka Bedregal Alpaca

Propiedades: Operaciones Binarias Propiedad asociativa: Si para cada a, b, c de A se verifica que

Semigrupos

(a * b) * c = a * (b * c) Propiedad conmutativa: Si para cada a, b de A se verifica que: a * b = b *a Ley de cancelación: Cancelación a la izquierda si para cada a, b, c de A se verifica que si a * b = a * c entonces b = c Propiedad distributiva: Si se tiene una segunda operación º y si para cada a, b, c de A se verifica que a º (b * c) = (a º b) * (a º c)

6

Dra. Norka Bedregal Alpaca

Propiedades: Operaciones Binarias

Semigrupos

Elemento neutro e de A : Si para cada a de A se verifica que a*e=e*a=a Elemento absorvente z de A: Si para cada a de A se verifica que a*z=z*a=z Elemento idempotente de A: Si se verifica que a*a=a Elemento simétrico de A: Si existe un elemento a0 de A tal que a * a0 = a0 * a = e

7 Dra. Norka Bedregal Alpaca

Propiedades: Operaciones Binarias Ejemplo

Semigrupos

Dado ( R ; ●) Se sabe que la multiplicación es cerrada en los reales es asociativa y tiene elemento neutro, que es el 1. Pero no todos los números reales tienen simétrico; en realidad hay sólo uno que no tiene simétrico, que es el cero Lo cual es suficiente para decir que no se cumple la propiedad de simétricos.

8 Dra. Norka Bedregal Alpaca

Propiedades: Operaciones Binarias Ejemplo

Semigrupos

Dado ( Z ; + ) La suma es cerrada en los enteros, es asociativa y tiene elemento neutro, que es el 0. También todos los números enteros tienen simétrico, que es el opuesto de cada uno

9 Dra. Norka Bedregal Alpaca

Propiedades: Operaciones Binarias

Semigrupos

Ejercicio Comprobar qué propiedades cumplen la operación siguiente º : Q × Q --> Q definida como p º q = p,

para todo p, q de Q

10 Dra. Norka Bedregal Alpaca

Semigrupos

Estructuras algebraicas Cuando se tiene uno o más conjuntos con una o varias operaciones binarias, con unas determinadas propiedades y unos determinados elementos notables, se tiene una estructura algebraica. A veces, si el conjunto sobre el que actúa una operación es finito A = {a1, a2, . . . , an} es posible representar dicha operación mediante una tabla de la forma

11 Dra. Norka Bedregal Alpaca

Estructuras algebraicas

Semigrupos

Las estructuras se presentan agrupando bajo un paréntesis el conjunto y las operaciones que actúan sobre él, como por ejemplo (A, *), (A, *, º) Ejemplo: Enteros modulares El conjunto Zn se define mediante una relación de equivalencia en Z llamada de congruencia módulo n, se dice que

Una de las operaciones internas que se pueden definir sobre este conjunto, se representa por +, y viene dada por

Con lo que se obteniendo que (Zn, +) es una estructura algebraica.12 Dra. Norka Bedregal Alpaca

Estructuras algebraicas

Semigrupos

Dado que Zn es finito, se puede representar dicha operación mediante una tabla. Por ejemplo se puede construir las tablas para Z2 y Z5:

13 Dra. Norka Bedregal Alpaca

Estructuras algebraicas

Semigrupos

Ejercicios Escriba las tablas para Z4 y Z5, y analice las diferencias Estudiar las propiedades de (Zn, +).

14 Dra. Norka Bedregal Alpaca

Semigrupo

Semigrupos

Semigrupos El conjunto S no vacío; es semigrupo si está dotado de una operación binaria * (interna) que verifica la propiedad Asociativa: a * (b * c) = (a * b) * c Semigrupo Conmutativo Se dice que el semigrupo S es un semigrupo conmutativo si se verifica, además la propiedad Conmutativa: a*b=b*a

15 Dra. Norka Bedregal Alpaca

Semigrupo

Semigrupos

Ejemplos: Son semigrupos conmutativos: El conjunto N provisto de la suma (N; +) El conjunto Z provisto del producto (Z; ·)

(℘( A),∪)

(℘( A),∩)

son dos semigrupos conmutativos.

Ejemplos: N con la operación

a*b=ab

no es un semigrupo.

Z con la operación de sustracción tampoco es semigrupo. Z con la operación de sustracción tampoco es semigrupo. 16 Dra. Norka Bedregal Alpaca

Sub-Semigrupo

Semigrupos

Sub-semigrupo Dado un semigrupo (S; *) y A S; se dice que A es un subsemigrupo si, restringiendo la operación * a los elementos de A se sigue teniendo una estructura de semigrupo, es decir (A; *) es también semigrupo.

Observación Es evidente que la única condición para que A sea subsemigrupo de S es que la restricción de * al conjunto A sea una operación binaria. Cuando un conjunto cumple esta condición se suele decir que A es cerrado para la operación.

17 Dra. Norka Bedregal Alpaca

Sub-semigrupo

Semigrupos

Ejemplo: En la figura, A no es subsemigrupo de S.

Ejemplos:

Dado el semigrupo (Z;+) El subconjunto 2Z de los enteros pares es subsemigrupo, en cambio el conjunto de los impares no lo es. En el semigrupo (A; f) el subconjunto de las funciones biyectivas S(A) es un subsemigrupo. 18 Dra. Norka Bedregal Alpaca

Monoide

Semigrupos

Monoide Dado un semigrupo (S; *) se dice que es un monoide si tiene elemento neutro, es decir, si existe un elemento e en S que vrifica:

e*a = a *e = a

∀a ∈ S

Observación Si además el semigrupo es conmutativo se le llama monoide conmutativo. Teorema En todo semigrupo, el elemento neutro, si existe, debe ser único. 19 Dra. Norka Bedregal Alpaca

Monoide Ejemplos:

Semigrupos

La estructura (N; +) es monoide En cambio, (Z+; +) no lo es, puesto que 0 ∉ Z + Las matrices reales Mn,m forman un monoide conmutativo con la operación + de matrices. Si se consideran las matrices cuadradas con el producto (Mn,n; •) se tiene un monoide no conmutativo.

20 Dra. Norka Bedregal Alpaca

Sub-Monoide

Semigrupos

Submonoides Dado un monoide (S; ), un subconjunto A de S es submonoide, si además de ser subsemigrupo, contiene al elemento neutro. Teorema Sea (S; *) un monoide y A S. Las condiciones necesarias y suficientes para que el subconjunto A sea submonoide son: 1) Que sea cerrado para la operación, es decir: a; b ε A → a * b ε A. 2) e ε A.

21 Dra. Norka Bedregal Alpaca

Semigrupos

Sub-Monoide

Ejemplo: Sea nZ el conjunto de los productos de un entero n por todos los elementos de Z. Si n > 1 se tiene que (nZ;+) son submonoides de (Z; +) Observe que (nZ; •) son subsemigrupos (y no submonoides) de (Z; •) (que si es monoide).

22 Dra. Norka Bedregal Alpaca

Semigrupos

El Semigrupo Libre de las cadenas Definición: Alfabeto Se llama alfabeto a un conjunto Σ al que se le exige que ningún elemento pueda ser formado por yuxtaposición de elementos del propio Σ. A los elementos de Σ se les llama también cadenas de longitud 1. Yuxtaponiendo dos elementos de Σ se obtiene un nuevo elemento de un conjunto de cadenas de longitud 2. Este proceso se puede extender recursivamente para formar cadenas de longitud n Si se denomina Entonces cada

se construye como: 23 Dra. Norka Bedregal Alpaca

El Semigrupo Libre de las cadenas

Semigrupos

El conjunto de todas las cadenas, de longitud mayor o igual que uno, se representa por

Cadena Nula Se considera la existencia de una cadena ε llamada cadena nula, que no pertenece a ningún , esta cadena tiene longitud 0. La cadena nula tiene la propiedad de dejar invariante a cualquier cadena por yuxtaposición, es decir

24 Dra. Norka Bedregal Alpaca

Semigrupos

El Semigrupo Libre de las cadenas

Semigrupo Libre de Cadenas Se denota por al conjunto formado por las cadenas de cualquier longitud, incluida la cadena nula. Este conjunto, dotado con la operación binaria de yuxtaponer dos cadenas, también llamada concatenación, verifica la propiedad asociativa, y además tiene elemento neutro ε. Se le conoce con el nombre de Semigrupo libre de las cadenas (aunque en realidad sea un monoide) y juega un importante papel en la teoría de lenguajes formales.

25 Dra. Norka Bedregal Alpaca

Semigrupos

Grupos Definición: Sea un conjunto G con una operación interna *, que verifica las siguientes propiedades: 1.

Asociativa

2.

Existe un elemento neutro

3.

Existencia de inversos: para

existe

Entonces, se dice que el par (G,* ) forma un grupo. 26 Dra. Norka Bedregal Alpaca

Grupos

Semigrupos

Grupo Abeliano: Sea (G,*) un grupo si cumple la propiedad conmutativa: entonces se dice que el grupo es conmutativo. Se emplea con mayor frecuencia el término de grupo abeliano en honor del matemático noruego Niels Henrik Abel (1802-1829). Ejemplo: El monoide (N, +) no es un grupo, puesto que ningún elemento, excepto el elemento neutro 0, tiene inverso. Los conjuntos (Z, +), (Q, +) (R, +) y (C, +) son todos grupos abelianos con la operación de adición, reciben el nombre de grupos abelianos aditivos. 27 Dra. Norka Bedregal Alpaca

Grupos

Semigrupos

Ejemplo: Los conjuntos (Z, •), (Q, •) (R, •) y (C, •) no son grupos. Sin embargo, los conjuntos (Q*, •) y (R*, •), donde Q* = Q − {0} R* = R − {0} son grupos abelianos multiplicativos Ejemplo: Dado un conjunto A el conjunto S(A) formado por todas las aplicaciones biyectivas A → A, junto con la operación composición de funciones forman un grupo.

28 Dra. Norka Bedregal Alpaca

Grupos

Semigrupos

Ejercicio: Dado un conjunto A, estudiar las propiedades que cumplen las estructuras • Conjunto potencia de A y la operación de unión de conjuntos • Conjunto potencia de A y la operación de intersección de conjuntos

29 Dra. Norka Bedregal Alpaca

Grupo de Permutaciones Ejemplo: Sea A = { f: X => X / f es función biyectiva}

Semigrupos

Siendo X = { 1, 2, 3 }

¿Cuáles serán los elementos de este conjunto A?

Observe que son las funciones biyectivas definidas en el conjunto {1,2,3} Por ejemplo, una función de dicho conjunto podría ser la que asigna: f(1) = 3 ;

¿Cuántas hay en total?

f(2) = 1 ;

f(3) = 2

30 Dra. Norka Bedregal Alpaca

Grupo de Permutaciones

Semigrupos

Como la función debe ser biyectiva, los valores 1, 2 y 3 deben aparecer exactamente una vez cada uno como imagen. Por lo tanto, lo que puede cambiar de una función a otra es únicamente el orden en que aparecen. En la función dada en el ejemplo anterior, el orden de las imágenes es: 3,1,2. También podría ser de otras formas. La cantidad de ordenamientos posibles de una cierta cantidad de elementos distintos, se denomina permutación y se calcula como el factorial de dicho número. En este caso hay tantas funciones como permutaciones de tres números, es decir P3 = 3! = 6 Sean las seis funciones A = { f1, f2, f3, f4, f5, f6}:

31

Dra. Norka Bedregal Alpaca

Semigrupos

Grupo de Permutaciones

Sabiendo de qué se trata el conjunto, considere la operación ○ que es la composición de funciones Hay que analizar si (A ; ○) es un grupo. ¿Recuerda cómo componer funciones? Por ejemplo, para calcular f2 ○ f3 , significa aplicar primero f3 y a continuación f2.

32 Dra. Norka Bedregal Alpaca

Grupo de Permutaciones Observe que es lo mismo que aplicar directamente la función f5 , o sea f2 ○ f3 = f5

Semigrupos

De la misma manera se deben hacer todas las composiciones. Como el conjunto es finito, conviene hacer una tabla:

33 Dra. Norka Bedregal Alpaca

Grupo de Permutaciones

Semigrupos

Análisis de las propiedades: 1.

Es operación binaria y cerrada, pues todos los resultados de la composición dieron elementos del mismo conjunto.

2.

La operación es asociativa, la composición de funciones en general es asociativa.

3.

Entonces como este es un subconjunto sigue cumpliendo la propiedad. En general, para todo x en el Dom: [f ○ (g ○ h )](x)

= f [(g ○ h)(x) ] = f [ (g ( h(x) )] = ( f ○ g ) [ h(x)] = [ (f ○ g ) ○ h ](x) 34 Dra. Norka Bedregal Alpaca

Grupo de Permutaciones 4.

La operación no es conmutativa, pues por ejemplo,

Semigrupos

f2 ○ f3 = f5

pero f3 ○ f2 = f4

5.

El elemento neutro es la función f1 , que es la función identidad.

6.

Los simétricos de los elementos son: f1’ = f1 f2’ = f2 f3’ = f3 f4’ = f5 f5’ = f4 f6’ = f6

Por lo tanto ( A ; ○ ) es un GRUPO y se le llama S3. Es un grupo NO Abeliano

35 Dra. Norka Bedregal Alpaca

Propiedades de los Grupos

Semigrupos

Sea (A ; *) un grupo con neutro e. Entonces siempre se cumplen las siguientes propiedades: 1.

El elemento neutro e es único.

2.

El elemento neutro es su propio simétrico: e' = e

3.

Propiedad involutiva del simétrico: para todo a en A: (a')' = a

4.

El simétrico de un elemento es único.

5.

Para todo a, b ϵ A: (a * b )' = b' * a'

6.

Las ecuaciones a * x = b y x * a = b tienen solución única.

7.

El único elemento idempotente es el elemento neutro. Es decir, si a * a = a => a = e

8.

Para todo a, b ϵ A: a’= b => b’= a 36 Dra. Norka Bedregal Alpaca

Elementos Regulares

Semigrupos

Reconocer los elementos regulares de un semigrupo permite trabajar de una manera más rápida y agilizar los cálculos. Definición: Sea (A,*) un semigrupo con neutro. El elemento a ϵ A es regular a izquierda si y sólo si: a*x=a*y

entonces

x=y

El elemento a ϵ A es regular a derecha si y sólo si: x*a=y*a

entonces

x=y

El elemento a ϵ A es regular si es regular a izquierda y a derecha. Es decir, los elementos regulares son los cancelables, o sea los que se pueden suprimir al estar operados en ambos miembros de una igualdad. 37

Dra. Norka Bedregal Alpaca

Elementos Regulares

Semigrupos

Ejemplo: En la adición de enteros, todos los elementos son regulares.

Ejemplo: En la multiplicación de reales, todos excepto el cero son regulares.

38 Dra. Norka Bedregal Alpaca

Elementos Regulares Ejemplo:

Semigrupos

Considere la siguiente operación en Q: x ∆ y = 3 • (x + y) Determinar si todos sus elementos son regulares. Como es conmutativa, se analiza solo a derecha: x∆a=y∆a

=>

3 • ( x + a) = 3 • ( y + a)

=>

x+a=y+a

=>

x=y

Por lo tanto, los racionales bajo esta operación son todos regulares.

39 Dra. Norka Bedregal Alpaca

Elementos Regulares Propiedad:

Semigrupos

En un grupo todos los elementos son regulares.

Demostración: Como en un grupo, todos los elementos tienen simétrico: a*x = a * y => a’ *a*x = a’ *a* y => ( a’ *a ) *x = ( a’ *a ) * y => e *x = e * y => x = y Análogamente se prueba a derecha. 40 Dra. Norka Bedregal Alpaca

Elementos Regulares

Semigrupos

Observaciones: Por ello, cuando se trabaja en un grupo, directamente se puede usar la propiedad cancelativa No hay necesidad de hacer todos los pasos involucrados (operar ambos miembros con el simétrico del elemento, asociar, obtener el neutro, y por propiedad del neutro llegar la igualdad en la que ya no figura dicho elemento). Si se trabaja en un semigrupo (que no llega a ser grupo), se puede cancelar sólo aquellos elementos que tiene simétrico.

41 Dra. Norka Bedregal Alpaca

Inversibles de un Semigrupo Definición:

Semigrupos

Sea (A ; *) un semigrupo con neutro. El conjunto de inversibles de A es: INV(A) ={a ϵ A/ a’ ϵ A}

Observación: O sea, es el conjunto de todos los elementos que tienen simétrico en el conjunto A respecto de la operación *

42 Dra. Norka Bedregal Alpaca

Inversibles de un Semigrupo Ejemplo:

Semigrupos

En ( Z ; • ) , los inversibles son solamente el 1 y el -1, pues los demás enteros no tienen inverso entero.

Ejemplo: 2) En ( R ; • ) , los inversibles son todos excepto el cero.

Ejemplo: En el conjunto de matrices cuadradas de nxn con elementos reales y la multiplicación ( Rnxn ; • ) , los elementos inversibles son las llamadas matrices inversibles o regulares, es decir aquellas cuyo determinante es distinto de cero. 43 Dra. Norka Bedregal Alpaca

Inversibles de un Semigrupo

Semigrupos

Ejemplo: En ( N0 ; + ) , el único elemento inversible es el cero, ya que los demás no tienen su opuesto en este conjunto. Ejemplo: En ( Z5 ; + ) , los inversibles son todos 0, 1, 2, 3 y 4 , o sea todos. Ejemplo: 6) En ( Z6 ; • ) , los inversibles son únicamente 1 y 5

44 Dra. Norka Bedregal Alpaca

Inversibles de un Semigrupo Propiedad:

Semigrupos

Sea (A ; *) un semigrupo con neutro. Entonces (INV (A) ; *) es grupo y se le llama Grupo de Inversibles del semigrupo (A; *).

Ejemplo: Con referencia al ejemplo anterior ( Z6 ; • ) , el conjunto {1 ,5 } es grupo multiplicativo. Su tabla:

45 Dra. Norka Bedregal Alpaca

Producto Cartesiano de Grupos

Semigrupos

Definición: Sean (G1 ; *1) y (G2 ; *2) dos grupos con neutros e1 y e2 respectivamente. En el conjunto G1 X G2 se define la siguiente operación * tal que: (a,b) * (c,d) = (a *1 c ; b *2 d) (G1 X G2 ; *) es grupo y se denomina grupo producto.

Ejemplo: Sean los grupos finitos (G1 ; *1) y (G2 ; ; *2) dados por las siguientes tablas:

46 Dra. Norka Bedregal Alpaca

Semigrupos

Producto Cartesiano de Grupos

Se va a hallar el producto G1 X G2 y definir la operación * de modo que (G1 x G2 ; *) sea grupo. G1 X G2 = { (0 ; a) , (0 ; b) , (1 ; a) , (1 ; b) , (2 ; a) , (2 ; b) } La operación * debe tener en cuenta que: (x , y) * (z , t) = (x *1 z , y ; *2 t) Por ejemplo: (1,a) * (2,b) = (1 *1 2, a *2 b) 47 Dra. Norka Bedregal Alpaca

Producto Cartesiano de Grupos

Semigrupos

Así se completa la tabla:

48 Dra. Norka Bedregal Alpaca

Sub-Grupo Definición:

Semigrupos

Sea (G ; *) un grupo y sea H no ϕ, H subconjunto de G. Si (H ; *) es grupo entonces H es subgrupo de G.

Observación: Un subgrupo es un conjunto no vacío, que está incluido en un grupo, y que en sí mismo es también grupo con la misma operación

Ejemplo: (Z ; +) es un subgrupo del grupo (R ; +), ya que cumple con la definición de subgrupo. 49 Dra. Norka Bedregal Alpaca

Sub-Grupo Ejemplo:

Semigrupos

Considere el conjunto P = { x ϵ Z / x = 2 k , k ϵ Z } Observar que el conjunto P es el de los enteros pares. Entonces: (P ; +) es subgrupo del grupo (Z ;+), pues cumple las condiciones: a.

No es vacío ;

b. Está incluido en Z c.

Al sumar números pares, se obtiene siempre un número par, la suma es asociativa, el elemento neutro de la suma es el cero que es par, y el opuesto de un número par también es par

d. (P ; +) es un grupo en sí mismo.

50 Dra. Norka Bedregal Alpaca

Sub-Grupo

Semigrupos

Ejemplo: Si (G ; *) es un grupo con neutro e , entonces ({e} ; *) es el subgrupo más pequeño que puede tener y se denomina subgrupo trivial de (G ; *)

Ejemplo: (G ; *) es el subgrupo más grande de (G ; *) y se denomina subgrupo impropio de (G ; *)

51 Dra. Norka Bedregal Alpaca

Sub-Grupo

Semigrupos

TEOREMA: CONDICIÓN NECESARIA Y SUFICIENTE para SUBGRUPOS Sea (G ; *) un grupo. H es subgrupo de G, si y solo si: 1.

H es no vacío

2.

H es subconjunto de G

3.

Para todo a, b ϵ H

=> a * b’ ϵ H

52 Dra. Norka Bedregal Alpaca

Sub-Grupo

Semigrupos

¿Cómo usar la condición suficiente? Dado un conjunto H y un grupo (G ; * ), si se prueba que H cumple las tres condiciones numeradas 1, 2 y 3, por este teorema ya se puede afirmar que H es un subgrupo del grupo dado.

¿Cómo usar la condición necesaria? Dado un conjunto H y un grupo (G ; * ) , si H no cumple con alguna de las 3 condiciones, se puede afirmar que H NO es subgrupo del grupo dado.

53 Dra. Norka Bedregal Alpaca

Semigrupos

FIN

54 Dra. Norka Bedregal Alpaca