Departamento de Ciencias e Ingenierı́a de la Computación
Lenguajes Formales y Autómatas
Segundo Cuatrimestre de 2023
Trabajo Práctico N◦ 5
Álgebra Computacional
Un álgebra es una estructura consistente de uno o más conjuntos junto con una o más
operaciones sobre esos conjuntos. Por ejemplo: ⟨N; +, 1, 0⟩ es un álgebra donde el conjunto de
los naturales N es el conjunto (asumimos que 0 ∈ N), + es una operación binaria sobre N, y
por último 1 y 0 son operaciones 0-arias sobre N (i.e constantes).
Otro ejemplo, es el álgebra de vectores de n dimensiones, con componentes reales positivas
que se puede describir como: ⟨R, Rn ; ∗, +⟩. Los dos conjuntos (carriers) son: el conjunto de
los números reales R, y el conjunto Rn (vectores de reales). Las operaciones definidas son: el
producto (∗) de un real por un vector, y la suma de vectores (+).
1. Operadores binarios
Dado un conjunto C y un operador binario •,
• un elemento z en C se denomina cero si verifica que z • x = x • z = z
• un elemento u en C se denomina identidad si verifica que u • x = x • u = x
• un elemento y en C se denomina inverso de x si verifica que y • x = x • y = u
Dados los siguientes conjuntos, y considerando las definiciones anteriores, determinar si
existen elementos cero e identidad para los operadores mencionados.
(a) Sea S un conjunto cualquiera. Considere el conjunto C = power(S), y los operadores
binarios de intersección (∩) y unión (∪) entre elementos de C.
Obs: power(S) es el conjunto de partes de S.
(b) Sea C = {0, 1, 2, . . . , n} para algún n fijo, y sea max la función binaria (operador)
que retorna el máximo de dos enteros. Ejemplo: max(3, 6) = 6, max(4, 4) = 4.
(c) Sea C = {true, f alse}, y los operadores binarios ∧, ∨, y →
2. Álgebras con un conjunto y una operación binaria
Sea A = {a, b}. Para cada uno de los siguientes incisos, definir a través de una tabla, la
operación binaria • sobre A que verifique las condiciones dadas.
IMPORTANTE: Para poder resolver este ejercicio, necesita, tener a mano las defini-
ciones de grupo, monoide, semigrupo (Ver teóricas o libro de referencia); además de
recordar la definición de operación binaria.
(a) ⟨A, •⟩ es un grupo.
(b) ⟨A, •⟩ es un monoide pero no un grupo.
(c) ⟨A, •⟩ es un semigrupo pero no un monoide.
3. Propiedades de álgebras con una operación binaria
Probar que:
(a) Cualquier operación binaria tiene a lo sumo un elemento identidad.
(b) En cualquier grupo o monoide el elemento identidad es único.
(c) Si un elemento en un monoide ⟨M ; •, u⟩ tiene inverso entonces ese inverso es único.
(d) Sea ⟨G; •⟩ un grupo. Todo elemento x ∈ G tiene un único inverso (denotado usual-
mente x−1
(e) Sea ⟨G; •⟩ un grupo. Si x e y pertenecen a G, entonces (x • y)−1 = y −1 • x−1
(f) Si ⟨G; •⟩ es un grupo, entonces satisface las leyes de cancelación a izquierda y a
derecha. (Enuncie estas leyes antes de realizar la prueba).
4. (a) Mostrar que el conjunto de cadenas formadas por los sı́mbolos a y b con la operación
binaria de concatenación (·) es un monoide. Esto es; probar que ⟨{a, b}∗ ; ·⟩ es un
monoide.
(b) Sea Zp = {2n | n ≥ 0}, mostrar que ⟨Zp ; ×⟩ (i.e. el conjunto de los enteros positivos
pares, con la operación de multiplicación) es un semigrupo conmutativo. Mostrar
además que no es un monoide.
5. Álgebras con un conjunto y varias operaciones
(a) ¿Qué propiedades debe cumplir un álgebra ⟨A; +, ∗⟩ para ser un anillo (ring)? ¿Y
qué propiedades para ser un cuerpo (field )?
(b) Probar que:
• ⟨Z; +, ∗⟩ es un anillo.
• ⟨N5 ; +5 , ∗5 ⟩ es un cuerpo.
Donde N5 = {0, 1, 2, 3, 4} y los operadores +5 y ∗5 se definen como:
x +5 y = (x + y) mod 5 x ∗5 y = (x ∗ y) mod 5
6. Grupos: homomorfismos e isomorfismos
Sea N5 = {0, 1, 2, 3, 4} y E5 = {[0], [1], [2], [3], [4]}, donde cada [k] es la clase de equivalen-
cia definida sobre N, bajo la relación R definida como: xRy sı́ y solo si (x − y) mod 5 = 0.
Esto es;
[0] = {0, 5, 10, 15, 20, 25, . . .}
[1] = {1, 6, 11, 16, 21, 26, . . .}
[2] = {2, 7, 12, 17, 22, 27, . . .}
[3] = {3, 8, 13, 18, 23, 28, . . .}
[4] = {4, 9, 14, 19, 24, 29, . . .}
(a) Mostrar que ⟨E5 ; +⟩ es un grupo conmutativo, donde la operación + se define como:
[x] + [y] = [x + y].
Por ejemplo, [3] + [4] = [3 + 4] = [7] = [2].
Recordamos que una clase de equivalencia puede referenciarse por cualquiera de sus
elementos. Por lo tanto hablar de la clase de equivalencia de 7, es lo mismo que
hablar de la clase de equivalencia de 2.
(b) Probar que ⟨N5 ; +5 ⟩ es isomórfico al grupo ⟨E5 ; +⟩.
7. Álgebras de Boole
Recordamos que una estructura ⟨B; +, ·,′ , 0, 1⟩ es un álgebra de Boole si cumple:
• ⟨B; +, 0⟩ y ⟨B; ·, 1⟩ son monoides conmutativos.
En otras palabras, se verifica para todo x, y, z ∈ B:
(x + y) + z = x + (y + z) (x · y) · z = x · (y · z)
x+y =y+x x·y =y·x
x+0=x x·1=x
• los operadores + y · son distributivos uno sobre el otro.
Esto es:
x · (y + z) = (x · y) + (x · z)
x + (y · z) = (x + y) · (x + z)
• x + x′ = 1 y x · x′ = 0 para todos los elementos x ∈ B
El elemento x′ se denomina complemento de x o negación de x
(a) Probar que en toda álgebra de Boole se verifica que x + x = x (Idempotencia)
(b) Probar que en un álgebra de Boole el complemento de un elemento x es único.
8. Para los siguientes conjuntos B, dar una definición para los operadores +, ·,′ , 1 y 0, de
forma tal que la estructura ⟨B; +, ·,′ , 0, 1⟩ sea un álgebra de Boole.
(a) B = {0, 1}.
(b) B es el conjunto de todas las fórmulas bien formadas de la lógica proposicional.
(c) B es el conjunto de partes de S, para algún conjunto S.
(d) B = {1, 2, 3, 5, 6, 10, 15, 30}.
