Álgebra De Conmutación. Puertas Lógicas

Tema 3 Álgebra de Conmutación. Puertas Lógicas

3.1. Álgebra Booleana.

3.1.1. Postulados

3.1.2. Teoremas

3.2. Funciones Lógicas

3.3. Formas canónicas: Mintéminos y Maxtérminos

3.4. Optimización de Funciones Lógicas

3.4.1. Mapas de Karnaugh

3.4.2. Simplificación mediante mapas de Karnaugh.

3.4.3. Simplificación de funciones incompletamente específicadas.

3.5. Bases de Implementación: Puertas Lógicas. Estándares.

3.5.1. Funciones básicas.

3.5.2. Simbologías de representación

3.5.3. Suficiencia de los operadores NAND y NOR

3. 1. Álgebra Booleana.

El álgebra de Boole es una estructura matemática que resulta muy adecuada para el diseño de los Sistemas Digitales.

La forma más simple de definir un álgebra de Boole es a partir de un conjunto de postulados básicos o axiomas. Estos axiomas no tienen demostración y además han de ser independientes unos de otros y no pueden contradecirse.

3.1.1. Postulados

El matemático Huntington propuso el siguiente conjunto de postulados independientes y consistentes para definir un álgebra de Boole.

POSTULADO 1:

Se define un conjunto de elementos C={a,b,c,d…}, donde tales elementos pueden estar sujetos a relaciones de equivalencia (a=b). Este conjunto debe tener al menos dos elementos distintos.

POSTULADO 2:

Se definen dos leyes o reglas de composición interna denotadas por “+” y “•” tales que:

POSTULADO 3:

Existen en el conjunto C dos elementos distintos 0 y 1 llamados neutros tales que:

POSTULADO 4

Las leyes de composición interna “+” y “•” son ambas conmutativas es decir:

POSTULADO 5

Cada una de estas leyes de composición interna es distributiva respecto de la otra, es decir:

POSTULADO 6

Para cualquier elemento de C existe un único elemento simétrico (complementario o inverso) que también pertenece a C, es decir:

Este conjunto de axiomas no es el único para definir el álgebra de Boole. Existen muchos conjuntos que pueden verificar estas propiedades, por ejemplo dado un conjunto cualquiera A, un álgebra de Boole se podría definir sobre el conjunto de partes de A, las operaciones de unión e intersección y sería un álgebra de Boole.

El conjunto C que nosotros utilizaremos tendrá como elementos variables binarias que solo pueden tomar valores 0 y 1. Esto da lugar a un caso particular de un álgebra de Boole, denominada álgebra de Conmutación.

Puede observarse que entre los postulados del álgebra de Boole, que hemos establecido, no se incluye la propiedad asociativa, el motivo es que puede demostrarse a partir de ellos y por tanto no pueden incluirse entre ellos porque dejarían de ser independientes.

Entre los postulados existe una cierta simetría o dualidad entre las dos leyes de composición interna, en efecto, las dos afirmaciones que se hacen en cada postulado son idénticas si sustituimos el 0 por el 1 y la operación “+” por “•”.

3.1.1. Teoremas

Vamos a exponer una serie de propiedades o teoremas que se deducen de los postulados planteados anteriormente. En dichos teoremas también se verifica esa propiedad de dualidad.

TEOREMA 1

Dualmente

Demostración:

Dualmente:

TEOREMA 2: Idempotencia

Dualmente

Demostración:

Dualmente:

TEOREMA 3: Absorción

Dualmente

Demostración:

Dualmente

TEOREMA 4: Involución

Demostración:

TEOREMA 5:

Dualmente

Demostración:

Dualmente

TEOREMA 6: Asociativa

Dualmente

Demostración:

}

Por tanto

La demostración de la parte dual sería análoga, basta con intercambiar las operaciones “+” y “•”.

TEOREMA 7: Leyes de D’Morgan

Demostración:

Sabemos que

Por tanto

La demostración de la parte dual sería análoga, basta con intercambiar las operaciones “+” y “•”.

3.2. Funciones Lógicas

Se define una variable booleana (o variable de Boole) como una variable matemática que puede asumir sólo dos valores el 0 y el 1.

Una función Booleana (o función lógica) es una expresión formada por un conjunto de variables booleanas relacionadas entre sí por las operaciones definidas en el álgebra de Boole. Dicha función sólo podrá tomar el valor lógico 0 o 1, por tanto puede también ser considerada como una variable booleana.

TEOREMA 8

Dada una función booleana de n variables dicha función es posible descomponerla como:

O bien como:

DEMOSTRACIÓN

Sabemos que por ser una variable de Boole necesariamente se ha de verificar que ó por tanto ó .

Si

y

Sumando ambas ecuaciones miembro a miembro tendremos:

Si

y

Sumando ambas ecuaciones miembro a miembro tendremos:

Por tanto se verifica para cualquier valor de la variable

Otra forma de demostrarlo sería:

Multiplicamos (1) por y (2) por

Sumando miembro a miembro las dos igualdades:

La parte dual también quedaría demostrada.

3.3. Formas canónicas

Se denominan términos canónicos ( o formas canónicas) a expresiones algebraicas en las cuales solo aparece una de las dos operaciones del Álgebra de Boole.

Una función de Boole de n variables puede descomponerse en una expresión de 2n términos canónicos. La función booleana podrá expresarse como una suma de productos canónicos o bien como un producto de sumas canónicas.

Supongamos que n=3, aplicando el teorema 8 repetidas veces tendremos que:

Por lo tanto:

Operando llegamos a que:

A los productos se les llama términos canónicos producto o mintérminos y se denotan por:

Así pues:

En general una función f de n variables puede expresarse como:

La función puede descomponerse también en suma de productos canónicos o maxtérminos. Para ellos utilizamos el dual del teorema 8.

Por lo tanto, sustituyendo y operando llegaríamos a:

A los términos canónicos en los que aparece solo la operación suma se les denomina maxtérminos:

Así:

En general:

Usando el teorema de D’Morgan podemos obtener la equivalencia entre mintérminos y maxtérminos como sigue. Tomemos como ejemplo el mintérmino m2 función de 3 variables y obtengamos su complemento:

Lo anterior se cumple para cualquier mintérmino, es decir, en general el complemento de un mintérmino es el maxtérmino correspondiente: mi = Mi

Partiendo de una función booleana cualquiera se puede obtener la expresión de dicha función como suma de mintérminos o producto de maxtérminos mediante el siguiente procedimiento:

• Si la función está expresada como suma de productos:

o Cada término producto multiplicarlo por 1 en términos de la variable que falte. Hacer esto tantas veces como variables falten en el término producto.

o Aplicar la función distributiva sobre la suma

o Aplicar la idempotencia

Así por ejemplo si

• Si la función está expresada como producto de sumas:

o A cada término suma sumarle 0 en términos de la variable que falte. Hacer esto tantas veces como variables falten en el término suma.

o Aplicar la función distributiva sobre el producto

o Aplicar la idempotencia

Así por ejemplo si

3.4. Optimización de Funciones Lógicas

Se pueden simplificar funciones lógicas aplicando postulados y teoremas del álgebra de Boole, pero a la hora de obtener una función mínima este proceso puede ser muy laborioso ya que no existe ninguna regla que indique cual es el teorema adecuado que se ha de aplicar en cada momento. Se han ideado otros métodos para la simplificación de funciones lógicas, entre ellos el método de Karnaugh y el método de Quine-McCluskey. Nos centraremos en el primero.

3.4.1. Mapas de Karnaugh

Este método se fundamenta en dibujar la función de Boole mediante un diagrama llamado mapa de Karnaugh. Tal mapa es una figura geométrica compuesta de un conjunto de cuadros a los que se les asigna un coeficiente de la función booleana.

La forma de representar tales funciones es sombrear aquellos cuadros para los cuales la función vale 1, a este tipo de función se le denomina Diagrama de Venn. Por ejemplo la función se representaría como:

El paso de un diagrama de Venn a uno de Karnaugh es inmediato consiste en anotar un 1 en aquellos cuadros que aparezcan sombreados en el diagrama de Venn.

La función

...