Lógica y Matemática Computacional

Licenciatura en Sistemas de Información

Estructuras
Algebraicas Finitas

Ing. JULIO C. ACOSTA

Facultad de Ciencias Exactas y Naturales y Agrimensura - UNNE

2019 1
 Leyes de composición interna
¿qué es una ley de composición interna?

Sea K = {0, 1} y las siguientes tablas, diga en cada

caso si (K, +) es LCI

+ 0 1 + 0 1 + 0 1
0 0 1 0 2 0 0 0 0
1 1 0 1 0 1 1 0 1

2019 2
 ¿Cuántas LCI pueden establecerse en el conjunto A ={0, 1}?

+ 0 1
0 0 1
1 1 0

(0,0,0,0); (1,1,1,1)

(0,0,0,1); (0,0,1,0); (0,1,0,0); (1,0,0,0)

(1,1,1,0); (1,1,0,1); (1,0,1,1); (0,1,1,1)

(0,0,1,1); (0,1,1,0); (1,1,0,0); (1,0,0,1); (0,1,0,1); (1,0,1,0)

¿Cuántas LCI pueden establecerse en el conjunto A ={0, 1, 2}?

2019 3
 Propiedad Asociativa

Ejemplo:

Si A = { x / x = 2k, k  Z } ; + es el producto ordinario

2k + (2t + 2s) = 2k · (2t · 2s) = 2k · 2(t + s) = 2k + ( t + s)

= 2( k + t ) + s = 2( k + t ) · 2s = (2 k · 2 t ) · 2s = (2 k + 2 t ) + 2s

2k + (2t + 2s) = (2 k + 2 t ) + 2s
2019 4
 Elemento neutro

Ejemplos

Si A = { x / x = 2k, k  Z } ; + es el producto ordinario

Para cada 2k debe existir 2t = e con t  Z

2 k · e = 2 k · 2 t = 2(k+t) = 2 k

 k+t=k entonces t=0 0Z

Proponga ejemplos de conjuntos y operaciones donde

existe elemento neutro y donde no existe elemento neutro
2019 5
 Elemento simétrico (o inverso)

Ejemplo:

Si A={x/xZ}; + es la adición

Asumimos que existe e = 0 (neutro) en A,

a+b=e si b=-a

Proponga ejemplos de conjuntos y operaciones donde

existe elemento inverso y donde no existe elemento inverso
2019 6
 Propiedad conmutativa

Diga en cada caso si se verifica la propiedad

conmutativa para el par (A,+)

Si A={x/xN}; + es la suma ordinaria

Si A={x/xN}; + es el producto ordinario

Si A={x/xZ}; + es el cociente

2019 7
 Monoide

Monoide es todo par (A,+)

A es un conjunto no vacío

+ es una ley de composición interna definida en A

(N, +) ; +: suma aditiva
(N, +) ; +: producto ordinario
(N, +) ; +: diferencia
(P(gr(n)), +) ; +: suma de polinomios

2019 8
 Resuelva las siguientes operacipnes de matrices
Sea M el conjunto de matrices de clase 2x3 donde sus
elementos son 0 y/o 1, que representan valores de verdad del
algebra proposicional; y sea + una operación proposicional
determinada; diga si son monoides:
Ejemplos

(M, +) ; +: disyunción

(M, +) ; +: conjunción

2019 9
 Propiedades

Sea: A un conjunto no vacío

+: A x A  A una función

1) Si existe un neutro en A para +, éste es único

2) Sea +: A x A  A asociativa y e pertenece al conjunto

A
Si a poseee inverso en A, este inverso es único

2019 10
 Semigrupo
(A, +) es semigrupo si:
1) Monoide (L.C.I.) A2  A + es una LCI
2) +: es Asociativo en A
interna en A
a,b,c : a, b, c  A  (a + b) + c = a + (b + c)

(N, +) + es suma aditiva

(Z, +) + es suma aditiva

(P(x), +) + intersección de conjuntos

(P(x), +) + unión de
2019 conjuntos 11
 Semigrupo con Unidad
(A, +) es semigrupo con unidad si:
1) Monoide (L.C.I.) A2  A + es una LCI
2) +: es Asociativo en A
interna en A
a,b,c : a, b, c  A  (a + b) + c = a + (b + c)
3) Existe Elemento Neutro: Definida una operación +
si en el conjunto A existe al menos un elemento “ e”,
que al operarlo con cualquier otro elemento “ a” de A
resulta el mismo elemento “

e  A / a : a  A  a * e = e * a = a
2019 12
 (N0, +) + es suma aditiva
A2  A + es una LCI interna en A
a,b,c : a, b, c  A  (a + b) + c = a + (b + c)

e=0  A / a : a  A  a * e = e * a = a

(N0, +) es Semigrupo con Unidad

(N, +) + es suma aditiva
A2  A + es una LCI interna en A
a,b,c : a, b, c  A  (a + b) + c = a + (b + c)

e=0 NO pertenece al conjunto A – NO HAY NEUTRO

(N, +) NO es Semigrupo2019con Unidad 13
 Grupo
(A, +) es semigrupo con unidad si:
1) Monoide (L.C.I.) A2  A + es una LCI

2) +: es Asociativo en A
a,b,c : a, b, c  A  (a + b) + cinterna en+Ac)
= a + (b

3) Existe Elemento Neutro

e  A / a : a  A  a + e = e + a = a
4) Existe Elemento Inverso: Definida + si para cada
elemento de A existe al menos un elemento a´que
al operar con a dá como resultado el neutro e
a : a  A, a´  A / a + a´ = a´ + a = e
2019 14
 Grupo Abeliano
Grupo Abeliano es un Grupo conmutativo
1) Monoide (L.C.I.)
2) +: es Asociativo en A
a,b,c : a, b, c  A  (a + b) + c = a + (b + c)
3) Existe Elemento Neutro
e  A / a : a  A  a + e = e + a = a
4) Existe Elemento Inverso
a : a  A, a´  A / a + a´ = a´ + a = e
5) Propiedad conmutativa
a,b : a, b  A 2019
a+b=b+a 15
 Si A = { 1; -1 } ; + es el producto ordinario
1)
1·1=1A -1 · 1 = -1  A Se verifica que + es
-1 · -1 = 1  A 1 · -1 = -1  A L.C.I. en A

2) Podemos admitir que la Asociatividad “se hereda”

de la asociatividad del producto entre elementos del
conjunto de los números enteros

3) Sabemos que para el producto existe neutro en Z,

pero debemos verificar que ese neutro  A
-1 · e = -1  e=1 1A
1·e= 1  e=1 Existe neutro
2019 16
4) Analizamos si cada elemento de A admite
inverso en A
1·x=e=1  x=1 Los elementos
de A admiten
-1 · x = e = 1  x = -1 inverso

5) Podemos admitir que la Conmutatividad “se

hereda” de la conmutatividad del producto entre
elementos del conjunto de los números enteros

El par (A, +) ES grupo abeliano

Si A = { 1; -1 } ; + es el producto ordinario

2019 17
 Repaso

(A, +) A es un conjunto no vacío

+ es un operador de una operación
binaria definida en A

L.C.I en A Semi-
grupo Semigrupo
+ es Asociativo en A
con unidad
Hay elemento neutro en A para + Grupo
Grupo
Hay elemento inverso en A para + Abeliano
+ es Conmutativa en A
2019 18
Analice (G, +) donde:

G = R - {0}

G=R

G = R - { -1 }

2018 19
 Grupos Finitos

Sea (G, +) un grupo finito, G es un conjunto finito.

Orden de G es el número de elementos de G

G={e} + e
e e
G = { e, a }
+ e a
Si llenamos el casillero con a, no
se cumple la unicidad del neutro, e e a
por tanto debe ser llenado con e a a e
No se deben repetir elementos en la misma línea para no
perder la unicidad
2018
del neutro... 20
+ e a b G = { e, a, b }
e e a b
a a
b b

+ e a b
e e a b No se deben repetir elementos
a a b e en las filas ni en las columnas
porque no se cumpliría la
b b e a unicidad del neutro

2018 21
G = { e, a, b, c }

+ e a b c + e a b c
e e a b c e e a b c
a a e c b a a e c b
b b c e a b b c a e
c c b a e c c b e a

+ e a b c + e a b c
e e a b c e e a b c
a a b c e a a c e b
b b c e a b b e c a
c c e a b c c b a e

2018 22
 Analice la Estructura algebraica del par (A,+) donde:
1) A es el conjunto de las matrices cuadradas de clase n x n
+ es la suma de matrices
( Knxn, + )
2) A es el conjunto de las matrices cuadradas de clase 2 x 2
+ es la suma de matrices
( K2x2, + )
3) A es el conjunto de las matrices cuadradas de clase 2 x 2

del tipo:

+ es el producto ordinario de matrices

( K2x2 - {[0]2x2}, + )
2019 23
 Es regular o simplificado si:

2018 24
 Propiedades
Sea (G,+) grupo, entonces:

1) El neutro es único. El inverso de cada elemento es único

2) Los elementos de G son regulares

3) Las ecuaciones
admiten solución única en G

4)

5)

2018 25
 Subgrupos

Sea (A, +) Un conjunto no vacío S es subgrupo de A

cuando S es grupo con el operador +

Sea (A, +) un Grupo, y S incluido en A, S no vacío

El Grupo (S, +) es SubGrupo de (A, +) si:

S contiene el elemento identidad de A

+ es cerrada en S

S contiene los simétricos

2019 26
Propiedades de los Subgrupos
1) Todo Grupo A, tiene al menos dos sub grupos

2) Transitividad de los subgrupos

Sean S1 , S2 y S3 subgrupos de A
Si S1 es subgrupo de S2 y S2 es subgrupo de S3

entonces: S1 es subgrupo de S3
3) La intersección de dos subgrupos es un subgrupo
Sean S y S` dos subgrupos de A

2019 27
 Ejemplos
1) Sea el Grupo (A, +) donde A = Z ; + es la suma aditiva
Proponga subgrupos de A y analice como se cumplen
las propiedades
2) Sea el Grupo (A, +)

Si A = { x / x = 2k, k  Z } ; + es el producto ordinario

Proponga subgrupos de A y analice como se cumplen
las propiedades

3) Muestre algunos subgrupos posibles del Grupo (Σ3, +).

Si Σ={0,1} ; Σ3={000,001,010,100,011,101,110,111}

+ Se define: (x1x2x2)+(y1y2y3) = (x1+y1, x2+y2, x3+y3)

2018 28
 000 001 010 100 011 101 110 111
000 000 001 010 100 011 101 110 111
001 001 000 011 101 010 100 111 110
010 010 011 000 110 001 111 100 101
100 100 101 110 000 111 001 010 011
011 011 010 001 111 000 110 101 100
101 101 100 111 001 110 000 011 010
110 110 111 100 010 101 011 000 001
111 111 110 101 011 100 010 001 000

Los invito a programar para nxn

Los invito al mismo ejemplo pero cambiando el operador

Los invito a programar para nxn y para cualquier operador….

2019 29
4) Consideremos en Σ = {0, 1} las siguientes leyes de
composición interna representadas con + y .

+ 0 1 . 0 1
0 0 1 0 0 0
1 1 0 1 0 1

y una función inyectiva e: Σ2  Σ5 / e(x) = x M

x pertenece a Σ2

x M es el producto matricial de x por la matriz M

2018 30
2018 31
2018 32
 Anillo
Sea una estructura algebraica definida en un conjunto G con
dos leyes de composición + y 
(A, +  ) es Anillo
1) (A, +) es Grupo abeliano
2) (A, ) es semi Grupo
3)  es distributivo a izquierda y derecha
respecto de +
a, b, c  G : a  (b + c) = (a  b) + (a  c)
(b + c)  a = (b  a) + (c  a)

Si la segunda ley de composición es conmutativa,

(A, +  ) es Anillo Conmutativo
2019 33
Sea la estructura (A, +, )

Donde A=Z
+ es la suma aditiva
 es el producto ordinario

(A, +) es Grupo Abeliano

(A, ) es Grupo semigrupo
 es doblemente distributivo respecto de +
(A, +, ) es anillo

(A, ) además es conmutativo

(A, +, ) es anillo conmutativo

2019 34
 Si (A, +,  ) es Anillo

Y además posee elemento neutro respecto de 

(A, +,  ) es Anillo con Unidad

Un Anillo con unidad cuyos elementos no nulos son inversibles

se llama Anillo con división

(A, +) es Grupo Abeliano

(A – {0}, ) es Grupo
 es doblemente distributivo respecto de +

Ejercicio: Analice (Z, + ) donde + es la adición (suma) y 

es el producto ordinario
2019 35
 Ejercicio: Analice el Anillo de las matrices cuadradas
(A, +, ) con los operadores suma y producto
respectivamente

Si un Anillo con división es conmutativo, se llama Cuerpo

1) (A, +) es Grupo abeliano
2) (A – {0}, ) es Grupo abeliano
3)  es distributivo respecto de +
Ejemplo: (Z, * ) donde * es la adición (suma) y  es el
producto ordinario
No es cuerpo,
cuerpo pues los únicos elementos no nulos que
admiten inverso multiplicativo son 1 y - 1
(R, * ) donde * es la adición y  es el producto ordinario
Es Cuerpo
2019 36
 Anillos Finitos
G={e}
+ e  e
(G, +, *)
Anillo e e e e

G = { e, a } + e a  e a
e e a e e e
a a e a e e

+ e a  e a
e e a e e e
a a e a e a

2018 37
G = { e, a, b }

+ e a b  e a b
e e a b e e e e
a a b e a e e e
b b e a b e e e

+ e a b  e a b
e e a b e e e e
a a b e a e a b
b b e a b e b a

+ e a b  e a b
e e a b e e e e
a a b e a e b a
b b e a 2018 b e a a 38
FIN

2019 39