Teoremas de DeMorgan

Un matemático llamado DeMorgan desarrolló un par de reglas importantes con respecto a la complementación de grupos en el álgebra de Boole.

Por grupo complementación, 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 la inversión de todas las entradas a una puerta invierte la función esencial de esa puerta de Y a O, o viceversa, y también invierte la salida.

Entonces, una puerta OR con todas las entradas invertidas (una puerta O negativa) se comporta igual que una puerta NAND, y una puerta Y con todas las entradas invertidas (una puerta Y negativa) 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 (Y contra O) 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.

En otras palabras, (AB) "no es igual a A’B". Debido a que el símbolo "primo" (’) no puede extenderse sobre dos variables como lo hace una barra, nos vemos obligados a usar paréntesis para que se aplique a todo el término AB en la oración anterior.

Sin embargo, una barra actúa como su propio símbolo de agrupación cuando se extiende sobre más de una variable.

Esto tiene un impacto profundo en cómo se evalúan y reducen las expresiones booleanas, como veremos.

Teorema de DeMorgan

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 ruptura cambia de suma a multiplicación, o viceversa, y las piezas de la barra rota permanecen sobre las variables individuales. Para ilustrar:

Cuando existen varias "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 reduzcamos usando los Teoremas de DeMorgan:

Siguiendo el consejo de romper primero la barra más larga (superior), comenzaré rompiendo la barra que cubre 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:

Deberías nunca romper más de una barra en un solo paso, como se ilustra aquí:

Por muy tentador que sea conservar pasos y romper más de un compás a la vez, a menudo conduce a un resultado incorrecto, ¡así que no lo haga!

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

El resultado final es el mismo, pero se requieren más pasos en comparación con el primer método, donde la barra más larga se rompió primero.

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 es lo mismo que romper dos barras en un solo paso!

La prohibición de romper más de una barra en un paso no una prohibición de romper una barra en más de un lugar.

Irrumpir 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 pregunte por qué se colocaron paréntesis alrededor de la subexpresión B ’+ C’, considerando el hecho de que los eliminé en el siguiente paso.

Hice esto 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 me olvidara de poner paréntesis después de romper la barra corta, pero en otros casos sí podría hacerlo.

Considere este ejemplo, comenzando con una expresión diferente:

Como puede ver, mantener la agrupación que implican 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 conocen las entradas. Este es el primer paso de este proceso:

A continuación, podemos etiquetar las salidas de la primera puerta NOR y la puerta NAND.

Cuando se trata de puertas de salida invertidas, 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.

Luego, en el cable que sale de la puerta (después de la burbuja), escribo la expresión completa complementada.

Esto ayuda a asegurarme de que no me olvido de 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 un par de expresiones) para la última puerta NOR:

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

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 O negativa, y una puerta NOR es equivalente a una puerta Y negativa.
• 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 partes de la barra rota 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. Debe nunca ¡Intente 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 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.

HOJAS DE TRABAJO RELACIONADAS:

• Hoja de trabajo de álgebra booleana