PROBLEMAS RESUELTOS SOBRE ÁLGEBRA BOLEANA ( II )

PROBLEMA: En la familia lógica de circuitos conocida como TTL (Transistor Transistor Logic, véase el Suplemento # 1 para mayores detalles) el bloque fundamental es la función NAND. Obtener usando esta función como punto de partida las tres funciones lógicas básicas NOT, OR y AND.

Al igual que en el problema anterior, conectando todas las terminales de entrada de un NAND entre sí se puede obtener la función NOT:

NOT

Invirtiendo la salida de un NAND con un NOT así obtenido se puede lograr fácilmente la función AND:

AND

Por último, para obtener la función OR usando bloques NAND hay que relacionarla de alguna manera con el producto Boleano propio de la función NAND usando para ello una de las relaciones de DeMorgan. Buscamos dicha relación trabajando "a la inversa" (llevando a cabo pasos opuestos a los que normalmente tomaríamos para simplificar una expresión):

Vemos que basta invertir las entradas de un NAND para que este se convertierta en un OR. Por lo tanto, el circuito deseado es el siguiente:

OR

Puesto que, a partir de bloques NAND exclusivamente, podemos recuperar las tres funciones lógicas básicas, también al bloque NAND se le conoce también como una función universal.


PROBLEMA: Determinar si es más económico construír el siguiente circuito con bloques NOR o con bloques NAND. Usar los resultados de los dos problemas anteriores.

Este problema es representativo de una situación que ocurre frecuentemente en la práctica. En las familias de componente electrónicos utilizados para construír circuitos lógicos, es muy rara la ocasión (como lo es el caso de los relevadores electromecánicos) en la cual por la naturaleza propia del funcionamiento intrínseco de la familia los componente más sencillos no son el AND y el OR sino el NAND o el NOR, existiendo frecuentemente la opción de poder seleccionar entre estos dos últimos para construír un circuito lógico. Y también, con mucha frecuencia, habrá una diferencia en la cantidad de componentes requeridos al usar el bloque NOR y al usar el bloque NAND, lo cual puede constituírse en una razón para preferir un tipo de bloque sobre el otro. Y la razón principal no es ya tanto el factor costo, ya que el lograr que un diseño utilice 14 componentes en lugar de 16 no representa ya en estos tiempos un ahorro substancial de dinero; la razón principal es hoy la velocidad máxima bajo la cual puede funcionar un circuito lógico, entre menor sea la cantidad de componentes utilizados, menor será el tiempo que tarda una señal en llegar de un punto a otro dentro del circuito.

Comenzaremos el rediseño utilizando primero bloques NAND. Para ello, simplificaremos la representación del inversor NOT construído mediante un bloque NAND con sus dos entradas conectadas a un mismo punto. La representación esquemática es la siguiente:

Es importante tener siempre en mente que el bloque de la derecha no es un NAND de una sola entrada, todo NAND debe tener por lo menos dos entradas; se trata de un NAND que está actuando como un inversor lógico NOT por tener sus dos entradas conectadas a un mismo punto. Esto permite dar mayor claridad a los diagramas y es una práctica justificada en el trazado de los diagramas esquemáticos.

Usando únicamente bloques NAND y los resultados de uno de los problemas anteriores, el circuito toma el siguiente aspecto:

Del diagrama, podemos ver que el circuito se puede simplificar. Puesto que dos NOTs conectados en serie no alteran la señal a su entrada (debido a que el inverso del inverso de una variable Boleana es igual a la variable misma, o sea (A')' = A), estos se pueden reemplazar por una sola línea directa. Se han destacado dos de ellos de color rosa. Hay otros dos que se pueden eliminar en la parte inferior. De este modo, el circuito toma el siguiente aspecto:

Vemos que la construcción del circuito con bloques NAND requiere un mínimo de 5 bloques NAND.

Procedemos ahora a construír el circuito utilizando para ello bloques NOR. Así como simplificamos los esquemáticos utilizando un NAND de "una sola entrada", utilizaremos un NOR de "una sola entrada" actuando como inversor NOT, el cual se sobreentiende que ha derivado de un NOR de dos entradas con ambas entradas conectadas:

Usando únicamente bloques NOR y los resultados de uno de los problemas anteriores, el circuito toma el siguiente aspecto:

Del diagrama, podemos ver que el circuito se puede simplificar por las mismas razones expuestas en la simplificación anterior debido a que dos NOTs conectados en serie no alteran la señal a su entrada y se pueden reemplazar por una sola línea directa. En el diagrama se han destacado dos de ellos de color rosa. Hay otros dos en el circuito que también se pueden eliminar. De este modo, el circuito toma el siguiente aspecto:

Vemos que la construcción del circuito con bloques NOR requiere un mínimo de 6 bloques NOR. Puesto que se requiere un número menor (5) de bloques NAND que de bloques NOR (6) para construír el circuito propuesto, concluímos que es más económico construír el circuito con bloques NAND.


PROBLEMA: Demostrar los siguientes nueve teoremas básicos del álgebra Boleana:

(1) A + 1 = 1

(2) A • 1 = A

(3) A + 0 = 0

(4) A • 0 = 0

(5) A + A = A

(6) A • A = A

(7) ā = a

(8) A + A = 1

(9) A • A = 0

(1) Para llevar a cabo la demostración, consideramos los dos valores posibles que puede tomar la variable Boleana A, los cuales son 0 y 1:

A + 1 = 0 + 1 = 1

A+ 1 = 1 + 1 = 1

En ambos casos, obtenemos siempre 1. Se concluye que A + 1 = 1.

(2) Considerando los dos valores posibles, 0 y 1:

A • 1 = 0 • 1 = 0 = A

A • 1 = 1 • 1 = 1 = A

En ambos casos, recuperamos el valor original de A. Se concluye que A • 1 = A.

(3) Considerando los dos valores posibles, 0 y 1:

A + 0 = 0 + 0 = 0 = A

A + 1 = 1 + 0 = 1 = A

En ambos casos, recuperamos el valor original de A. Se concluye que A + 0 = A.

(4) Considerando los dos valores posibles, 0 y 1:

A • 0 = 0 • 0 = 0

A • 0 = 1 • 0 = 0

En ambos casos, obtenemos siempre 0. Se concluye que A • 0 = 0.

(5) Considerando los dos valores posibles, 0 y 1:

A + A = 0 + 0 = 0 = A

A + A = 1 + 1 = 1 = A

En ambos casos, recuperamos el valor original de A. Se concluye que A + A = A.

(6) Considerando los dos valores posibles, 0 y 1:

A • A = 0 • 0 = 0 = A

A • A = 1 • 1 = 1 = A

En ambos casos, recuperamos el valor original de A. Se concluye que A • A = A.

(7) Considerando los dos valores posibles, 0 y 1, para a=0 la primera inversión lógica de a convierte al 0 en un 1, o sea a'=1, y tras esto la segunda inversión convierte al 1 en el 0 que teníamos, o sea que (a')' = a para a=0. Por otro lado, para a=1 la primera inversión lógica de a convierte al 1 en un 0, o sea a'=0, y tras esto la segunda inversión convierte al 0 en el 1 que teníamos, o sea que (a')' = a para a=1. Siendo válida la operación de doble inversión tanto para a=0 como para a=1, la relación queda demostrada.

(8) Considerando los dos valores posibles, 0 y 1:

A + A = 0 + 1 = 1

A + A = 1 + 0 = 1

En ambos casos, obtenemos siempre 1. Se concluye que A + A = 1.

(9) Considerando los dos valores posibles 0 y 1:

A • A = 0 • 1 = 0

A • A = 1 • 0 = 0

En ambos casos, obtenemos siempre 0. Se concluye que A • A = 0.


PROBLEMA: Simplificar las siguientes expresiones:

1) A + AB

2) AB + AB

3) A(A + B)

4) (A+B)B

5) (A+B)(A+C)

6) (A+B)(A+B)

7) ABC + A·B·C + A·B·C + A·B·C

8) ABC + AC + C

En las simplificaciones de cada expresión se irán aplicando los teoremas que sirvan para la simplificación de las mismas.

1) A + AB = A(1 + B) = A•1 = A

2) AB + AB = A(B + B) = A•1 = A

3) A(A + B) = AA + AB = A + AB = A(1 + B) = A•1 = A

4) (A+B)B = AB + BB = AB + 0 = AB

5) (A+B)(A+C) = AA + AC + BA + BC = A + AC + AB + BC

= A(1 + C) + AB + BC

= A•1 + AB + BC

= A + AB + BC

= A(1 + B) + BC

= A•1 + BC

= A + BC

6) (A+B)(A+B) = AA + AB + BA + BB = A + AB + AB + BB

= A + AB + AB + 0

= A(1 + B) + AB

= A + AB

= A(1 + B)

= A

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

= AB+ A·C

8) ABC + AC + C = ABC + (A + 1)C = ABC + C = (AB + 1)C = C


PROBLEMA: Demostrar que:

A(B + C) = ABC + ABC + ABC

En este problema vamos de una expresión más sencilla a una expresión más compleja en la cual en la expresión final cada término consta de tres factores en lugar de los dos que normalmente produciría la expresión original. Una forma de resolver este problema es trabajar al revés, esto es, tomar la expresión de la derecha y simplificarla para obtener la expresión de la izquierda. Si esto hiciéramos, obtendríamos la siguiente secuencia de pasos que nos llevan de la expresión de la izquierda a la expresión de la derecha:

A(B + C) = AB + AC = AB•1 + AC•1

= AB(C + C) + AC(B + B)

= ABC + ABC + ABC + ABC

= (ABC + ABC) + ABC + ABC

= ABC + ABC + ABC

PROBLEMA: Demostrar que:

AB + AB + AB = A + B

En este caso, lo que se llevará a cabo será efectivamente una simplificación de la expresión en oposición a lo que se hizo en el problema anterior.

AB + AB + AB = AB + AB + AB + AB

= AB + AB + AB + AB

= B(A + A) + A(B + B)

= B + A

= A + B

PROBLEMA: Empezando con la expresión del lado izquierdo de la igualdad de la siguiente relación Boleana, demostrar que:

AB + BC + CA = ABC + ABC + ABC + A·B·C + ABC + A·B·C

y a continuación, usando el mismo principio de solución y empezando con la expresión del lado derecho de la siguiente relación Boleana, demuéstrese que:

AB + BC + CA = AB + BC + CA

Trabajando sobre la expresión del lado izquierdo de la primera relación Boleana proporcionada, tenemos que:

AB + BC + CA = AB•1 + BC•1 + CA•1

= AB•(C + C) + BC•(A + A) + CA•(B + B)

= ABC + AB·C + ABC + + ABC + ABC + A·B·C

= ABC + ABC + ABC + A·B·C + ABC + A·B·C

Siguiendo un procedimiento similar sobre la expresión del lado derecho de la segunda expresión Boleana proporcionada, tenemos que:

AB + BC + CA = AB•1 + BC•1 + CA•1

= AB•(C + C) + BC•(A + A) + CA•(B + B)

= ABC + ABC + ABC + A·B·C + ABC + A·B·C

= ABC + ABC + ABC + A·B·C + ABC + A·B·C

Comparando este último resultado con el anterior, y como sigue siendo válido en álgebra Boleana el principio de que dos cosas iguales a una tercera son iguales entre sí, vemos que:

AB + BC + CA = AB + BC + CA

PROBLEMA: Recurriendo a los resultados del problema anterior, demuéstrese que

(A + B + C) • A · B · C = AB + BC + CA

Podemos comenzar aplicando en el lado izquierdo de la ecuación Boleana el teorema de DeMorgan que nos dice que el complemento del producto de variables es igual a la suma de los complementos de las mismas, con lo cual tenemos:

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

Llevando a cabo la multiplicación para remover los paréntesis:

(A + B + C) • A·B·C = AA + AB + AC + AB + BB + BC + AC + BC + CC

Como los productos AA , BB y CC son todos iguales a cero, se cancelan dejando:

= AB + AC + AB + BC + AC + BC

Reagrupando los términos:

= (AB + BC + CA) + (AB + BC + CA)

Puesto que AB+BC+CA=AB+BC+CA de acuerdo con lo obtenido en el problema anterior, se deduce que las cantidades dentro de ambos paréntesis son iguales. Ya que uno de los teoremas Boleanos nos asegura que cantidades iguales sumadas dan la misma cantidad (A+A=A), podemos descartar todo el segundo paréntesis y así obtener:

(A + B + C) • A · B · C = AB + BC + CA

PROBLEMA: Demostrar, recurriendo al uso del álgebra Boleana, que el siguiente circuito no es un circuito útil para el procesamiento de información, por estar su salida "atorada en 1" todo el tiempo:

La salida Boleana de este circuito es igual a la suma Bolena de la entrada b, más el término a · b, siendo este último el producto resultante del pre-procesamiento llevado a cabo por el AND conectado al NOT:

Salida = a · b + b

Aplicando las leyes de DeMorgan, podemos "romper" el primer término en dos términos más sencillos:

Salida = a + b + b

Puesto que de acuerdo a uno de los teoremas ya demostrados, b + b = 1:

Salida = a + 1

Y nuevamente, aplicando otro de los teoremas ya demostrados, tenemos finalmente:

Salida = 1

Este problema es similar a unos que ya vimos en la sección de problemas resueltos correspondiente al Capítulo 2: Las Tres Funciones Lógicas Básicas, en donde también se preguntaba si ciertos circuitos lógicos eran útiles para el procesamiento de información, excepto que en en ese caso, sin el beneficio del álgebra Boleana, se tuvo que recurrir a utilizar todas las combinaciones posibles de "unos" y "ceros" para resolver dichos problemas, mientras que aquí con el álgebra Boleana a nuestra disposición la resolución del problema procede con mucha mayor rapidez.


PROBLEMA: Recurriendo al álgebra Boleana, simplificar el siguiente circuito lo más que se pueda:

El primer paso consiste en obtener la salida Boleana del circuito directamente a partir del diagrama del circuito. La salida del circuito, identificada como y, será igual a la suma Boleana de tres entradas. Una de dichas entradas, la que corresponde al AND superior, está dada por el producto Boleano ab. Otra de dichas entradas, la que corresponde al AND intermedio, está dada por el producto Boleano ab. Y la tercera entrada es la que corresponde al AND inferior, la cual está dada por el producto Boleano a · b. Entonces la expresión Boleana de salida será:

y = a · b + ab + ab

A continuación se presenta la simplificación Boleana de la expresión:

y = a · b + a · (b + b)

y = a · b + a · 1

y = a · b + a

y = a + b

La expresión simplificada nos indica que la terminal c es totalmente irrelevante, puesto que no aparece para nada en la expresión de salida. El circuito simplificado requiere únicamente de un inversor (para invertir lógicamente la entrada b) y de un OR (para sumar a y b).


PROBLEMA: Descríbase la salida del siguiente circuito escribiendo primero en el diagrama las expresiones Boleanas que corresponden a la salida de cada bloque lógico y tras esto la expresión Boleana que este produce, así como su Tabla de Verdad.

Las salidas explícitas de cada bloque son las que se muestran a continuación:

La salida del circuito es AB+AB.

La Tabla de Verdad para este circuito es la que se muestra a continuación:

Estudiando la Tabla de Verdad se observa que la salida es "1" únicamente cuando las dos entradas son diferentes. Este circuito desempeña funciones importantes en el diseño de sistemas digitales, y comúnmente se le designa como OR-EXCLUSIVO, siendo su símbolo el siguiente:

El concepto del OR-EXCLUSIVO se puede extender fácilmente hacia un bloque de esta naturaleza con más de dos entradas, utilizando el mismo principio: la salida será "1" si cualquiera de las entradas es diferente de las demás, y será cero si todas las entradas tienen un valor de "1" ó un valor de "0". Precisamente por esto al OR-EXCLUSIVO se le conoce también como comparador lógico, porque puede comparar dos o mas entradas entradas produciendo una salida de "1" si por lo menos una de las entradas es diferente a las demás.


PROBLEMA: Un diseñista desea utilizar un NOR de 7 entradas cuando cuenta para ello con un bloque NOR de 8 entradas proporcionadas por el circuito integrado CD4078. ¿Qué es lo que se debe de hacer para poder utilizar el NOR de ocho entradas como uno de siete? El mismo diseñista desea utilizar únicamente 3 entradas de un NAND de 4 entradas proporcionadas por el circuito integrado CD4012. ¿Qué es lo que se debe de hacer para poder utilizar el NAND de cuatro entradas como uno de tres?

(1) La salida de un NOR de 8 entradas que llamaremos A, B, C, D, E, F, G y H, cualesquiera que sea la tecnología con la cual haya sido fabricado, está dada por la siguiente expresión:

Salida = A + B + C + D + E+ F +G + H

De esta expresión vemos que basta con poner un "0" permanentemente en cualquiera de las entradas para convertir un NOR de ocho entradas en uno de siete. Por ejemplo, podemos poner un "0" todo el tiempo en la entrada H:

Salida = A + B + C + D + E+ F +G + 0

Salida = A + B + C + D + E+ F +G

(2) La salida de un NAND de 4 entradas A, B, C y D, cualesquiera que sea la tecnología con la cual haya sido fabricado, está dada por la siguiente expresión:

Salida = A · B · C · D

De esta expresión vemos que basta con poner un "1" permanentemente en cualquiera de las entradas para convertir un NAND de cuatro entradas en uno de tres. Por ejemplo, podemos poner un "0" todo el tiempo en la entrada D:

Salida = A · B · C · 1

Salida = A · B · C

Por ningún motivo y bajo ninguna circunstancia se debe dejar terminal de entrada alguna a un circuito lógico sin conexión a ninguna parte. Todas las entradas no utilizadas deben ser conectadas siempre a un "0" ó a un "1" lógico, según sea el caso.


PROBLEMA: Demuéstrese con algebra Boleana que el circuito mostrado a continuación es equivalente a un OR-EXCLUSIVO.

"Rastreando las señales" Boleanas a través del circuito tal y como se llevó a cabo en el problema anterior, tenemos lo siguiente:

La salida del circuito es (A+B)A · B. Aplicando las leyes de DeMorgan podemos llevar a cabo una simplificación mediante el álgebra Boleana:

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

= AA + AB + AB + BB

= AB + AB

en donde las entradas AA y BB se eliminan por uno de los teoremas ya demostrado

Como lo vimos en el problema anterior, esta es la salida de un OR-EXCLUSIVO. Y esto lo pudimos verificar sin necesidad de tener que construír una Tabla de Verdad para el circuito, lo cual evidencia las ventajas de llevar a cabo el análisis mediante el álgebra Boleana.


PROBLEMA: Demostrar que el siguiente circuito es un OR-EXCLUSIVO.

Para resolver el problema, determinamos primero la expresión Boleana producida a la salida del circuito. El OR superior es alimentado con los complementos (inversos) de las variables A y B, o sea con A y B, razón por la cual su salida será A+B. Por su parte, el OR inferior es alimentado directamente con las variables A y B, razón por la cual su salida será A+B. Al ser alimentado el AND con las salidas de los OR, la salida del AND será:

(A+B)(A+B)

Pero esta es la misma expresión intermedia que se obtiene en la resolución del problema anterior, la cual se simplifica a AB + AB. Por lo tanto, el circuito dado es también una implementación de OR-EXCLUSIVO.


PROBLEMA: Como lo vimos en uno de los problemas anteriores, sabiendo que la salida de un OR-EXCLUSIVO de dos entradas puede estar dada por la expresión (A+B)A · B, extender este concepto para encontrar la salida de un OR-EXCLUSIVO de tres entradas A, B y C, poniendo la expresión como una "suma de productos" Boleanos. Constrúyase asimismo una Tabla de Verdad para la expresión obtenida y comprobar así que efectivamente se tiene un OR-EXCLUSIVO de tres entradas. ¿Cuál sería el símbolo para esta función?

Si (A+B)A · B es la salida de un OR-EXCLUSIVO de dos entradas, entonces la salida de un OR-EXCLUSIVO de tres entradas será:

(A+B+C)A · B · C

Simplificando la expresión recurriendo para ello a las leyes de DeMorgan aplicadas a tres variables en vez de dos:

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

= AA + AB + AC + BA + BB + BC + CA + CB + CC

= AB + AC + BA + BC + CA + CB

Construyendo a continuación la Tabla de Verdad para todas las combinaciones posibles de "unos" y "ceros", vemos que efectivamente, cuando todas las entradas son iguales la salida es "0", y cuando no son todas iguales entre sí, entonces la salida es "1":

El símbolo usado será el siguiente:

PROBLEMA: ¿Se puede convertir un OR-EXCLUSIVO de tres entradas en un OR-EXCLUSIVO de dos entradas? Justificar la respuesta.

La salida del OR-EXCLUSIVO de tres entradas, según se vió en el problema anterior, está dada por:

Salida = AB + AC + BA + BC + CA + CB

Queremos convertir esto a un circuito cuya salida sea:

Salida = AB + BA

Esto no lo podemos lograr poniendo una de las entradas permanentemente a un "0" lógico, por ejemplo haciendo C=0 en el OR-EXCLUSIVO de tres entradas:

Salida = AB + A•0 + BA + B•0 + 0•A + 0•B

Salida = AB + A•1 + BA + B•1

Salida = AB + A + BA + B

Salida = A(B + 1) + B(A + 1)

Salida = A + B

Poner un "0" lógico permanentemente en cualquiera de las entradas de un OR-EXCLUSIVO lo convierte simplemente en un OR, no en un OR-EXCLUSIVO de dos entradas. Tampoco lo podemos lograr poniendo una de las entradas permanentemente a un "1" lógico, por ejemplo haciendo C=1 en el OR-EXCLUSIVO de tres entradas:

Salida = AB + A•1 + BA + B•1 + 1•A + 1•B

Salida = AB + A•0 + BA + B•0 + A + B

Salida = AB + BA + A + B

Salida = (A + 1)B + (B + 1)A

Salida = A + B

Salida = A · B

Poner un "1" lógico permanentemente en cualquiera de las entradas de un OR-EXCLUSIVO lo convierte simplemente en un NAND, no en un OR-EXCLUSIVO de dos entradas. Sin embargo, lo podemos lograr conectando dos de las entradas en una sola, lo cual equivaldría por ejemplo a hacer C=B en el OR-EXCLUSIVO de tres entradas:

Salida = AB + AC + BA + BC + CA + CB

Salida = AB + AB + BA + BB + BA + BB

Salida = AB + AB + BA + 0 + BA + 0

Salida = AB + AB

Esta es la salida de un OR-EXCLUSIVO de dos entradas. Y esto resuelve el problema.

Habríamos obtenido un resultado similar si hubieramos conectado las entras A y B (haciendo B=A) ó las entradas A y C (haciendo C=A).


PROBLEMA: La Tabla de Verdad para un circuito lógico es la siguiente:

¿Cuál es el diagrama para el circuito de acuerdo con esta Tabla de Verdad? Simplificar el circuito lo más que se pueda.

En este caso, puesto que hay menos ceros que unos, es más conveniente diseñar alrededor de los ceros, o sea usando maxterms. Obtenemos primero de la Tabla de Verdad los maxterms requeridos:

La salida está dada por:

Salida = f₁f₇

Salida = (A + B + C) • (A + B + C)

Simplificando:

Salida = AA + AB + AC + BA + BB + BC + CA + CB + CC

Puesto que AA = 0 y BB = 0, podemos borrar dichos términos y continuar con la simplificación:

Salida = AB + AC + AC + BA + BC + BC + C

Factorizando:

Salida = AB + C(A + A) + BA + C(B + B) + C

Puesto que:

A + A= 1

B + B = 1

La simplificación conduce a:

Salida = AB + C + BA + C + C

Y como C+C = C, la expresión final simplificada será:

Salida = AB + AB + C

El diagrama del circuito correspondiente es como se muestra a continuación: