02. Leyes del álgebra de Boole

INTRODUCCION

Debido a que los computadores trabajan con información binaria, la herramienta matemática adecuada para el análisis y diseño de su funcionamiento es el Algebra de Boole. El Algebra de Boole fue desarrollada inicialmente para el estudio de la lógica. Ha sido a partir de 1938, fecha en que C.E. Shanon publicó un libro llamado "Análisis simbólico de circuitos con relés", estableciendo los primeros conceptos de la actual teoría de la conmutación, cuando se ha producido un aumento considerable en el número de trabajos de aplicación del Algebra de Boole a los computadores digitales. Hoy en día, esta herramienta resulta fundamental para el desarrollo de los computadores ya que, con su ayuda, el análisis y síntesis de combinaciones complejas de circuitos lógicos puede realizarse con rapidez y eficacia.

Definiciones básicas

Se comenzará el estudio del Algebra de Boole introduciendo el concepto de clase. Se define como clase el total de los elementos que cumplen las características definidas por un criterio de pertenencia. En general, una subclase S de una clase dada C, es una clase cuyos elementos pertenecen a la clase C. A su vez, la clase C podría ser una subclase de una clase más amplia que contuviera todos los elementos de C juntos con otros elementos distintos. E inversamente, la clase S puede contener sus propias subclases. Una clase especialmente importante es la denominada clase de referencia o clase universal, que es aquella que comprende a todos los elementos bajo estudio. Una vez definida la clase universal, se puede definir la clase complementaria de una clase cualquiera A perteneciente a la universal, como la clase que encierra a todos los elementos de la clase universal excepto aquellos que están contenidos en la clase A. Finalmente, se definir  la clase vacía como la clase complementaria de la clase universal. De acuerdo con la definición de clase universal, la clase vacía es aquella que no contiene ningún elemento.

Diagramas de Venn

Los diagramas de Venn constituyen un sistema para representar gráficamente las clases. Sus reglas básicas son las siguientes:

La clase universal U se representa por un rect ngulo.

Una clase cualquiera A, perteneciente a la clase universal, se representa mediante la superficie definida por una curva cerrada, dibujada en el interior del rectángulo.

Un elemento e de la clase A se representa por un punto dibujado en el interior de la curva cerrada.

La clase complementaria A' de la clase A se representa por la superficie diferencia entre la de la clase universal U y la de la clase A.

La clase vacía no tiene representación por medio de los diagramas de Venn.

La representación de varias clases pertenecientes a la misma clase universal se realiza de la misma forma, es decir, dibujando en el interior del rectángulo tantos círculos como clases distintas se deseen representar.

Las clases que tienen elementos comunes se representan mediante círculos que se cortan entre sí. El área común define el subconjunto formado por los elementos comunes a ambas clases. Si dos clases no tienen ningún elemento en común, no habrá ningún punto de corte entre sus dos diagramas.

La representación de subclases de una clase dada se realiza dibujando círculos en el interior de la clase.

OPERACIONES

En esta sección se definirán las operaciones básicas del Algebra de Boole, describiéndose a continuación su aplicación a los circuitos lógicos.

Unión o adición

La unión de dos clases A y B se define como la clase formada por todos los elementos de la clase A, todos los elementos de la clase B, y ningún otro elemento. La clase unión se representa mediante la simbología matemática:

   A O B

Intersección o producto

La intersección de dos clases A y B se define como la clase formada por todos los elementos que pertenecen simultáneamente a las clases A y B. La clase intersección se puede representar mediante los símbolos:

   A Y B

Complementación

La clase complementaria de una dada ya ha sido definida. Las notaciones simbólicas empleadas para representar el complementario de A son: A' o bien NO A. Aquí se mencionarán dos propiedades importantes de la complementación, que se pueden comprobar fácilmente:

A + A' =U (clase universal)

A + A' = 0 (clase vacía)

APLICACION A CIRCUITOS LOGICOS

Dado que los elementos de los circuitos utilizados en los computadores sólo admiten dos estados, las clases y operaciones básicas del Algebra de Boole deberán particularizarse para este caso. Por tanto, habrá que aplicar un Algebra de Boole de tipo binario, donde sólo existirán dos clases: la universal que se representará por 1, y la vacía que se representará por 0. El estado de un elemento del circuito lógico viene representado por una variable que sólo puede tomar valores 0 o 1, que se corresponden con las dos clases posibles en un Algebra de Boole binaria.

En el caso de un álgebra binaria, las operaciones básicas del Algebra de Boole pueden describirse mediante las denominadas tablas de verdad, que agrupan en forma tabulada todas las combinaciones posibles de operandos, con sus correspondientes resultados.

Adición

A   B      A + B

=============

0   0            0

0   1            1

1   0            1

1   1            1

Equivale a un circuito en paralelo con un interruptor en cada hilo, donde al conectar cualquiera de ellos hay conducción en el circuito.

Producto

A   B      A · B

=============

0   0            0

0   1            0

1   0            0

1   1            1

Equivale a un circuito en serie donde existe dos interruptores en el mismo hilo, de tal forma que sólo hay conducción cuando están cerrados ambos interruptores.

Complementación

A     A'

======

0       1

1       0

Se representa bajo la forma de contactos complementarios de un mismo interruptor, de modo que si uno está cerrado el complementario estará abierto, y viceversa.

LEYES FUNDAMENTALES

Teoremas

El resultado de aplicar cualquiera de las tres operaciones definidas a variables del sistema booleano resulta en otra variable del sistema, y este resultado es único.

Ley de idempotencia:   A + A = A   |   A · A = A

Ley de involución:   (A')' = A

Ley conmutativa:   A + B = B + A   |   A · B = B · A

Ley asociativa:   A + (B + C) = (A + B) + C   |   A · (B · C) = (A · B) · C

Ley distributiva:   A + B · C = (A + B) · (A + C)   |   A · (B + C) = A · B + A · C

Ley de absorción:   A + A · B = A   |   A · (A + B) = A

Ley de De Morgan:   (A + B)' = A' · B'   |   (A · B)' = A' + B'

Principio de dualidad

El concepto de dualidad permite formalizar este hecho: a toda relación o ley lógica le corresponderá su dual, formada mediante el intercambio de los operadores unión con los de intersección, y de los 1 con los 0.

#      ADICION                                    PRODUCTO  

===============================================

1     A + A' = 1                                    A · A' = 0

2     A + 0 = A                                     A · 1 = A

3     A + 1 = 1                                      A · 0 = 0

4     A + A = A                                    A · A = A

5     A + B = B + A                              A · B = B . A

6     A + (B + C) = (A + B) + C           A · (B · C) = (A · B) · C

7     A + B · C = (A + B) · (A + C)      A · (B + C) = A · B + A · C

8     A + A · B = A                               A · (A + B) = A

9     (A + B)' = A' · B'                          (A · B)' = A' + B'