contenidocs.uns.edu.ar/~td/lfya2013/downloads/teoricas/t06.2013... · 2013. 11. 17. · estructuras...

á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].




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




á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]




á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




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 )





[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.





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





[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.





[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.




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.





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.





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); +,*]





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]




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.




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).




á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




á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].




á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.




á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.




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




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




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:




redes y expresiones

EjemploRed lógica para la expresión Booleana (x1x2 + x3)′ + x3




redes y expresiones

EjercicioDar la expresión Booleana para la

siguiente red lógica:




formas canónicas

Suma de productos




suma

Expresión para suma de dígitos binarios (s=suma, c= acarreo)

s = x′1x2 + x1x′2 (s = (x1 + x2)(x1x2)′)c = x1x2




half-adder




full-adder

Un full-adder está formado por dos half-adders y una compuerta OR adicional.




otros elementos lógicos

Compuerta NAND.





Las compuertas NAND son suficientes para expresar cualquier función de verdad





Compuerta NOR

EjercicioMostrar que las compuertas NOR son suficientes

para expresar cualquier función de verdad.

contenidocs.uns.edu.ar/~td/lfya2013/downloads/teoricas/t06.2013... · 2013. 11. 17. · estructuras...

Documents