7.8: Teoremas de DeMorgan

Un matemático llamado DeMorgan desarrolló un par de reglas importantes con respecto a la complementación de grupos en álgebra booleana. Por complementación grupal, me refiero al complemento de un grupo de términos, representado por una barra larga sobre más de una variable.

Debe recordar del capítulo sobre puertas lógicas que invertir todas las entradas a una puerta invierte la función esencial de esa puerta de AND a OR, o viceversa, y también invierte la salida. Entonces, una puerta OR con todas las entradas invertidas (una puerta Negativa-OR) se comporta igual que una puerta NAND, y una puerta AND con todas las entradas invertidas (una puerta Negativa-AND) se comporta igual que una puerta NOR. Los teoremas de DeMorgan establecen la misma equivalencia en forma “hacia atrás”: que invertir la salida de cualquier puerta da como resultado la misma función que el tipo opuesto de puerta (AND vs OR) con entradas invertidas:

Una barra larga que se extiende sobre el término AB actúa como un símbolo de agrupación, y como tal es completamente diferente del producto de A y B invertidos independientemente. Es decir, (AB) 'no es igual a A'B'. Debido a que el símbolo “primo” (') no puede estirarse sobre dos variables como puede una barra, nos vemos obligados a usar paréntesis para que se aplique a todo el término AB en la oración anterior. Una barra, sin embargo, actúa como su propio símbolo de agrupación cuando se estira sobre más de una variable. Esto tiene un profundo impacto en cómo se evalúan y reducen las expresiones booleanas, como veremos.

El teorema de DeMorgan puede pensarse en términos de romper un símbolo de barra larga. Cuando se rompe una barra larga, la operación directamente debajo de la rotura cambia de suma a multiplicación, o viceversa, y las piezas de barra rotas permanecen sobre las variables individuales. Para ilustrar:

Cuando existen múltiples “capas” de barras en una expresión, solo puede romper una barra a la vez, y generalmente es más fácil comenzar la simplificación rompiendo primero la barra más larga (superior). Para ilustrar, tomemos la expresión (A + (BC) ')' y la reduzcamos usando los teoremas de DeMorgan:

Siguiendo el consejo de romper primero la barra más larga (superior), comenzaré rompiendo la barra cubriendo toda la expresión como primer paso:

Como resultado, el circuito original se reduce a una puerta AND de tres entradas con la entrada A invertida:

Nunca debes romper más de una barra en un solo paso, como se ilustra aquí:

Por muy tentador que pueda ser conservar pasos y romper más de una barra a la vez, muchas veces conduce a un resultado incorrecto, ¡así que no lo hagas!

Es posible reducir adecuadamente esta expresión rompiendo primero la barra corta, en lugar de primero la barra larga:

El resultado final es el mismo, pero se requieren más pasos en comparación con usar el primer método, donde primero se rompió la barra más larga. Observe cómo en el tercer paso rompimos la barra larga en dos lugares. Esta es una operación matemática legítima, ¡y no lo mismo que romper dos barras en un solo paso! La prohibición de romper más de un listón en un solo paso no es una prohibición de romper una barra en más de un lugar. Romper en más de un lugar en un solo paso está bien; romper más de una barra en un solo paso no lo es.

Quizás se esté preguntando por qué se colocaron paréntesis alrededor de la subexpresión B' + C', considerando el hecho de que los acabo de quitar en el siguiente paso. Lo hice para enfatizar un aspecto importante pero fácilmente descuidado del teorema de DeMorgan. Dado que una barra larga funciona como un símbolo de agrupación, las variables anteriormente agrupadas por una barra rota deben permanecer agrupadas para que no se pierda la precedencia adecuada (orden de operación). En este ejemplo, realmente no importaría si olvidé poner paréntesis después de romper la barra corta, pero en otros casos podría ser. Considera este ejemplo, comenzando con una expresión diferente:

Como puede ver, mantener la agrupación implícita por las barras de complementación para esta expresión es crucial para obtener la respuesta correcta.

Apliquemos los principios de los teoremas de DeMorgan a la simplificación de un circuito de puerta:

Como siempre, nuestro primer paso para simplificar este circuito debe ser generar una expresión booleana equivalente. Podemos hacer esto colocando una etiqueta de subexpresión en la salida de cada puerta, a medida que se conozcan las entradas. Este es el primer paso en este proceso:

A continuación, podemos etiquetar las salidas de la primera puerta NOR y la puerta NAND. Al tratar con puertas de salida invertida, me resulta más fácil escribir una expresión para la salida de la puerta sin la inversión final, con una flecha apuntando justo antes de la burbuja de inversión. Entonces, en el cable que sale de la puerta (después de la burbuja), escribo la expresión completa, complementada. Esto ayuda a asegurar que no olvide una barra complementaria en la subexpresión, al obligarme a dividir la tarea de escritura de expresiones en dos pasos:

Finalmente, escribimos una expresión (o par de expresiones) para la última puerta NOR:

Ahora, reducimos esta expresión usando las identidades, propiedades, reglas y teoremas (DeMorgan) del álgebra booleana:

El circuito de puerta equivalente para esta expresión muy simplificada es el siguiente:

Revisar

• Los teoremas de DeMorgan describen la equivalencia entre puertas con entradas invertidas y puertas con salidas invertidas. En pocas palabras, una puerta NAND es equivalente a una puerta Negativo-OR, y una puerta NOR es equivalente a una puerta Negativa-AND.
• Al “romper” una barra de complementación en una expresión booleana, la operación directamente debajo de la ruptura (suma o multiplicación) se invierte, y las piezas de barra rotas permanecen sobre los términos respectivos.
• A menudo es más fácil abordar un problema rompiendo la barra más larga (superior) antes de romper cualquier barra debajo de ella. ¡Nunca debes intentar romper dos barras en un solo paso!
• Las barras de complementación funcionan como símbolos de agrupación. Por lo tanto, cuando se rompe una barra, los términos por debajo de ella deben permanecer agrupados. Se pueden colocar paréntesis alrededor de estos términos agrupados como una ayuda para evitar cambiar la precedencia.