Post on 25-Jan-2021
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
6. álgebra computacional
CONTENIDODefinición de álgebra [G8.1]. Estructuras
algebraicas: monoides, semigrupos, grupos, [G8.1], anillos, cuerpos [H10.1]. Subgrupos, isomorfismo entre grupos [G8.1]. Álgebras concretas y abstractas [H10.3]. Álgebras cocientes y homomorfismos canónicos [H10.5]. Álgebras de Boole [G7.1]. Circuitos digitales [H10.2].
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
bibliografía
GERSTING, JUDITH L. “Mathematical Structures for Computer Science: A Modern Approach to Discrete Mathematics”. W H Freeman & Co, 2006.
HEIN, JAMES. Discrete Structures, Logic and Computability. Jones and Bartlett Publishers. 1995 – 2001
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
álgebra
Un álgebra es una estructura consistente de un conjunto no vacío junto con una o mas operaciones definidas sobre dicho conjunto.
Ejemplos [R;+,- ,*,/][Q;+,-,*,/][R;+,- ,*,/,1,0][N;succ,0][℘(S); ∪, ∩][R[x];+,*,0,1]
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
álgebra
En la literatura se puede encontrar una definición más general de álgebra:
Un álgebra es una estructura consistente de uno o más conjuntos no vacíos junto con una o mas operaciones definidas sobre dichos conjuntos.
EjemploEl álgebra vectorial: [R,Rn;*,+] donde * se
define de R X Rn → Rn
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
estructuras algebraicas
Sea S un conjunto y sea • una operación binaria sobre S. La operación es asociativa si (∀x)(∀y)(∀z)[x • (y • z) = (x • y) • z]La operación es conmutativa si(∀x)(∀y)(x • y = y • x)[S, •] tiene elemento identidad si(∃i)(∀x)(x • i = i • x = x)Si [S, •] tiene un elemento identidad i,entonces se dice que cada elemento en S tiene un inverso con respecto a i si(∀x)(∃x−1)(x • x−1 = x−1 • x = i )
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
estructuras algebraicas
[S, •] es un grupo si S es un conjunto no vacío y • es una operación binaria sobre S tal que
1. • es asociativa2. existe un elemento identidad (en S)3. cada elemento en S tiene inverso (en S)
con respecto a •Un grupo en el cual la operación es
conmutativa se llama grupo conmutativo.
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
estructuras algebraicas
EjemploSea R+ el conjunto de los números
reales positivos y sea • la operación de multiplicación sobre reales positivos. Entonces [R+, •] es un grupo conmutativo:
La multiplicación es asociativa y conmutativa.El número real positivo 1 sirve de identidad x • 1 = 1 • x = x.Todo x en R+ tiene inverso en R+1/x, porque x • 1/x = 1/x • x = 1
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
estructuras algebraicas
[S, •] es un monoide si S es un conjunto no vacío y • es una operación binaria sobre S tal que
1. • es asociativa2. existe un elemento identidad (en S)
EjercicioMostar que el conjunto de cadenas
formadas por los símbolos a y b con la operación binaria de concatenación es un monoide.
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
estructuras algebraicas
[S, •] es un semigrupo si S es un conjunto no vacío y • es una operación binaria sobre S tal que
1. • es asociativaEjercicioMostar que el conjunto de los enteros
positivos pares con multiplicación es un semigrupo conmutativo. Mostrar que no es monoide.
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
resultados básicos sobre grupos
EjerciciosProbar las siguientes propiedades:1. En cualquier grupo (o monoide) [G, •], el
elemento identidad i es único.2. Para cada x en un grupo [G, •], x−1 es
único.3. Dados x e y miembros de un grupo [G, •],
(x • y) −1 = y−1 • x−1.
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
estructuras algebraicas
Un conjunto S con una operación binaria satisface la ley de cancelación a derecha si para x, y, z ∈ S, x • z = y •z implica x = y.
Satisface la ley de cancelación a izquierda si z • x = z • y implica x = y.
EjercicioProbar que todo grupo [G, •] satisface las
leyes de cancelación a izquierda y a derecha.
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
estructuras algebraicas
Un anillo es un álgebra [A;+, •] donde [A;+] es un grupo conmutativo, [A; •] es un monoide, yla operación • es distributiva (a izquierda y
a derecha) sobre +.Ejemplos
[Z;+,*][R[x];+,*][Mn(R); +,*]
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
estructuras algebraicas
Un cuerpo es un anillo [A;+, •] donde además se satisface que [A-{0}; •] es un grupo conmutativo, donde 0 es la identidad para [A,+].
Ejemplos[Q,+,*][N5,+5,*5]
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
subgrupos
Sea [G, •] un grupo y A ⊆ G. Entonces [A, •] es un subgrupo de [G, •] si [A, •] es un grupo.
Sea [G, •] un grupo con identidad i y A ⊆ G,[A, •] es un subgrupo de [G, •] si:
A es cerrado bajo •.i ∈ A.
Todo x ∈ A tiene inverso en A.
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
homomorfismos e isomorfismos
Sean [S, •] y [T, +] grupos. Un mapeo f: S → T es un homomorfismo
de [S, •] a [T, +] si para todo x, y ∈ S,f (x • y) =f (x) + f (y).
Sean [S, •] y [T, +] grupos. Un mapeo f: S → T es un isomorfismo de
[S, •] a [T, +] si1. la función f es una biyección.2. para todo x, y ∈ S, f (x • y)= f (x) + f (y).
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
álgebras de Boole
Un álgebra de Boole es un conjunto B sobre el cual están definidas dos operaciones binarias: + y •, una operación unaria ’, y se distinguen dos elementos 0 y 1 tal que las siguientes propiedades se verifican para todo x, y, z ∈ B:
x+y=y+x x • y=y • x conmutativa(x+y)+z=x+(y+z) (x • y) • z=x•(y • z) asociativax+(y•z)=(x+y)•(x+z) x•(y+z)=(x•y)+(x•z) distributivax+0=x x • 1=x identidadx+x’=1 x • x’=0 complemento
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
álgebras de Boole
La formalización de una estructura de álgebra de Boole nos ayuda a focalizarnos en las características esenciales comunes a todos los ejemplos de álgebras de Boole, permitiéndonos utilizar estas características para probar otras características.Denotaremos a las algebras de Boole [B, +, •,’, 0, 1].
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
álgebras de Boole
EjercicioConsidere los siguientes conjuntosS1 = {1,2,3,5,6,10,15,30}S2 = ℘({1,2,3})S3 = ℘({P1, P2, P3, P4}) donde las Pi ’s
son sentencias (proposiciones).Proponer operaciones binarias, unarias y
elementos 0 y 1 para definir álgebras de Boole en base a los conjuntos S1, S2y S3.
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
álgebras de Boole
EjerciciosProbar que la propiedad de idempotencia, es decir x + x = x, se verifica para toda álgebra de Boole.Para un elemento x de un álgebra de Boole el elemento x’ se denomina el complemento de x. El complemento dex satisface: x + x′ = 1 y x • x′ = 0.Probar que en un álgebra de Boole el complemento de x es único.
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
elementos lógicos básicos
Una compuerta lógica (logic gate) es un dispositivo electrónico que es la expresión física de un operador booleano.
compuerta OR compuerta AND
inversor
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
expresiones booleana
Una expresión booleana con n variables, x1, x2, ... , xn, es una cadena finita de símbolos formada aplicando las siguientes reglas:1. x1, x2, ... , xn son expresiones boolenas 2. Si P y Q son expresiones booleanas,
también lo son (P + Q), (P • Q), y (P′).
Ejemplosx3, (x1 + x2)′x3, (x1x3 + x′4)x2, y (x′1x2)′x1
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
redes y expresiones
Combinando compuertas AND, OR e inversores, podemos construir una red lógica que represente cualquier función.
EjemploRed lógica para la expresión Booleana x1x′2 + x3:
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
redes y expresiones
EjemploRed lógica para la expresión Booleana (x1x2 + x3)′ + x3
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
redes y expresiones
EjercicioDar la expresión Booleana para la
siguiente red lógica:
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
formas canónicas
Suma de productos
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
suma
Expresión para suma de dígitos binarios (s=suma, c= acarreo)
s = x′1x2 + x1x′2 (s = (x1 + x2)(x1x2)′)c = x1x2
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
half-adder
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
full-adder
Un full-adder está formado por dos half-adders y una compuerta OR adicional.
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
otros elementos lógicos
Compuerta NAND.
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
otros elementos lógicos
Las compuertas NAND son suficientes para expresar cualquier función de verdad
álgebracomputacional
LENGUAJESLENGUAJESFORMALES FORMALES
YYAUTAUTÓÓMATASMATAS
otros elementos lógicos
Compuerta NOR
EjercicioMostrar que las compuertas NOR son suficientes
para expresar cualquier función de verdad.