¡Aumenta Tu Popularidad!

ALGEBRA DE BOOLE

En 1854 George Boole introdujo una notación simbólica para el tratamiento de variables cuyo valor podría ser verdadero o falso (variables binarias) Así el álgebra de Boole nos permite manipular relaciones proposicionales y cantidades binarias. Aplicada a las técnicas digitales se utiliza para la descripción y diseño de circuitos mas económicos. Las expresiones booleanas serán una representación de la función que realiza un circuito digital. En estas expresiones booleanas se utilizarán las tres operaciones básicas ( AND, OR NOT ) para construir expresiones matemáticas en las cuales estos operadores manejan variables booleanas (lo que quiere decir variables binarias).

Elementos del álgebra de Boole

No es objeto de este curso un análisis profundo y formal de los postulados y teoremas del Algebra de Boole.

Los símbolos elementales son:

• 0: representativo de FALSO

• 1: representativo de VERDADERO

Las operaciones fundamentales son:

• Conjunción u operación AND (se representa con • )

• Disyunción u operación OR (se representa con + )

• Complementación, Negación u operación NOT ( se representa con una barra sobre la variable, )

Las variables son las proposiciones, que se representan o simbolizan por letras

Postulados:

Los postulados para las tres operaciones básicas, AND, OR Y NOT, son suficientes para deducir cualquier relación bolean.

OR AND NOT

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1 0 • 0 = 0

0 • 1 = 0

1 • 0 = 0

1 • 1 = 1

Teoremas:

1. Regla del cero y la unidad

a) X + 0 = X

b) X + 1 = 1 c) X • 1 = X

d) X • 0 = 0

2. Idempotencia o potencias iguales

a) X + X = X b) X • X = X

3. Complementación

a) X + = 1 b) X • = 0

4. Involución

5. Conmutatividad

a) conmutatividad del +

X + Y = Y + X b) conmutatividad del •

X • Y = Y • X

6. Asociatividad

a) asociatividad del +

X + (Y + Z) = (X + Y) + Z b) asociatividad del •

X • (Y • Z) = (X • Y) • Z

7. Distribuitividad

a) distribuitividad del +

X + (Y • Z) = (X + Y) • (X + Z) b) distribuitividad del •

X • (Y + Z) = (X • Y) + (X • Z)

8. Leyes de absorción

a) X • (X + Y)= X

b) X • ( + Y)= X•Y

c) • (X + Y)= •Y

d) (X + Y) • (X + )= X e) X + X•Y = X

f) X + •Y = X + Y

g) + X•Y = + Y

h) X•Y + X• = X

9. Teoremas de DeMorgan

a)

b) c)

d)

10. Teoremas generalizados de DeMorgan

a) b)

Dualidad

Los postulados y teoremas presentados anteriormente están representados en pares. La razón es que cada teorema posee lo que llamamos un dual. El dual de una expresión se obtiene intercambiando las ocurrencias de OR por AND, 0 por 1 y viceversa.. Si un teorema es valido, también lo será su dual, En efecto siguiendo el dual de la demostración del teorema, se obtiene la demostración del dual del teorema.

Por ejemplo dado el postulado 0+0 = 0 se obtiene el dual haciendo 1•1 = 1

Problemas

1. Demuestre las 8 leyes de absorción utilizando algebra de Boole

2. Demuestre los 4 Teoremas de De Morgan utilizando tablas de verdad

ver respuesta

ver respuesta

En clase se utilizaran los postulados y teoremas del álgebra de Boole para minimizar funciones booleanas. La simplificación de estas funciones con el uso de álgebra de Boole es un "arte". No existe un algoritmo que uno pueda seguir para garantizar que el resultado llegue a dar la forma mas simple de expresión mínima. Como en el juego del ajedrez, con la practica se va aprendiendo a reconocer patrones que nos guían hacia la solución.

Una pregunta importante que tenemos que hacernos es la de ¿que es simplificación? ¿Una expresión con menos literales? ¿una expresión con menos operaciones? La respuesta depende de lo que deseamos optimizar, ¿velocidad? ¿numero de interconexiones entre compuertas? ¿numero de componentes?

Antes de proceder a detallar la forma de minimizar expresiones estudiaremos las diferentes representaciones de las funciones booleanas.

Representación de funciones booleanas

Existen infinitas

...