Teorema de DeMorgan
El teorema y las leyes de DeMorgan se pueden utilizar para encontrar la equivalencia de las puertas NAND y NOR
Como hemos visto anteriormente, El 脕lgebra Booleano utiliza un conjunto de leyes y reglas para definir el funcionamiento de un circuito l贸gico digital con "0" y "1" que se utilizan para representar una condici贸n de entrada o salida digital. 脕lgebra booleana utiliza estos ceros y otros para crear tablas de verdad聽 y expresiones matem谩ticas para definir el funcionamiento digital de una l贸gica聽y no (o inversi贸n), as铆 como formas de expresar otras operaciones l贸gicas como la funci贸n聽XOR (Exclusive-OR).
Si bien el conjunto de leyes y reglas de George Boole nos permite analizar y simplificar un circuito digital, hay dos leyes dentro de su conjunto que se atribuyen a聽Augustus DeMorgan (un matem谩tico ingl茅s del siglo XIX) que ve las operaciones l贸gicas聽de NAND y聽NOR como funciones separadas DE聽NOT Y NOT OR respectivamente.
Pero antes de mirar la聽Teor铆a de DeMorgan con m谩s detalle, recordemos las operaciones l贸gicas b谩sicas donde聽A y聽B son variables binarias de entrada l贸gica (o booleana), y cuyos valores s贸lo pueden ser "0" o "1" produciendo cuatro combinaciones de entrada posibles,聽00,聽01, 10y聽11.
Tabla de la verdad para cada operaci贸n l贸gica
| Variable de entrada | Condiciones de salida | ||||||
| Un | B | Y | Nand | O | Ni | ||
| 0 | 0 | 0 | 1 | 0 | 1 | ||
| 0 | 1 | 0 | 1 | 1 | 0 | ||
| 1 | 0 | 0 | 1 | 1 | 0 | ||
| 1 | 1 | 1 | 0 | 1 | 0 | ||
En la tabla siguiente se ofrece una lista de las funciones l贸gicas comunes y su notaci贸n booleana equivalente donde un "." (un punto) significa una operaci贸n聽AND (producto), un "+" (signo m谩s) significa una operaci贸n聽OR (suma), y el complemento o inversa de una variable se indica mediante una barra sobre la variable.
| Funci贸n l贸gica | Notaci贸n booleana |
| Y | A.b |
| O | A+B |
| No | Un |
| Nand | Un. B |
| Ni | A+B |
La teor铆a de DeMorgan
Theorems de DeMorgan son b谩sicamente dos conjuntos de reglas o leyes desarrolladas a partir de las expresiones booleanas para聽AND,聽O NO utilizando dos variables de entrada,聽A y聽B. Estas dos reglas o te贸ricos permiten que las variables de entrada se nieguen y se conviertan de una forma de una funci贸n booleana en una forma opuesta.
El primer teorema de DeMorgan afirma que dos (o m谩s) variables NOR'ed juntas son las mismas que las dos variables invertidas (Complement) y AND'ed, mientras que el segundo teorema afirma que dos (o m谩s) variables NAND'ed juntas es la misma que los dos t茅rminos invertidos (Complement) y OR'ed. Esto es sustituir a todos los operadores OR por operadores AND, o todos los operadores AND por operadores OR.
Primer teorema de DeMorgan
El primer teorema de DeMorgan demuestra que cuando dos (o m谩s) variables de entrada son聽AND'ed y negadas, son equivalentes al聽quir贸fano de los complementos de las variables individuales. Por lo tanto, el equivalente de la funci贸n聽NAND ser谩 una funci贸n negativo-OR, lo que demuestra que聽A.B =聽A+B. Podemos mostrar esta operaci贸n utilizando la siguiente tabla.
Verifican primer teorema de DeMorgan usando tabla de la verdad
| Entradas | Resultados de la tabla de la verdad para cada t茅rmino | ||||||
| B | Un | A.b | A.b | Un | B | A +聽B | |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | |
Tambi茅n podemos mostrar que聽A.B =聽A+B usando puertas l贸gicas como se muestra.
La primera implementaci贸n de la ley de DeMorgan usando Logic Gates
La disposici贸n de la puerta l贸gica superior de:聽A.B se puede implementar utilizando una puerta聽NAND est谩ndar con entradas聽A y聽B. La disposici贸n de compuerta l贸gica inferior invierte primero las dos entradas que producen聽A y聽B. Estos luego se convierten en las entradas a la puerta聽de quir贸fano. Por lo tanto, la salida de la puerta聽OR se convierte en:聽A+B
Entonces podemos ver aqu铆 que una funci贸n est谩ndar聽o puerta de embarque con inversores (PUERTAS NO) en cada una de sus entradas es equivalente a una funci贸n de compuerta聽NAND. As铆 que una puerta聽NAND individual se puede representar de esta manera como la equivalencia de una puerta聽NAND es un negative-OR.
Segundo teorema de DeMorgan
El segundo teorema de DeMorgan demuestra que cuando dos (o m谩s) variables de entrada son聽OR'ed y negadas, son equivalentes al聽AND de los complementos de las variables individuales. Por lo tanto, el equivalente de la funci贸n聽NOR es una funci贸n negative-AND que demuestra que聽A+B =聽A.聽B, y de nuevo podemos mostrar la operaci贸n de esto utilizando la siguiente tabla de la verdad.
Verifican segundo teorema de DeMorgan usando tabla de la verdad
| Entradas | Resultados de la tabla de la verdad para cada t茅rmino | ||||||
| B | Un | A+B | A+B | Un | B | A .聽B | |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 | |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | |
Tambi茅n podemos mostrar que聽A +B =聽A.聽B con el siguiente ejemplo de puertas l贸gicas.
La segunda implementaci贸n de la ley de DeMorgan usando Logic Gates
La disposici贸n de compuerta l贸gica superior de:聽A+B se puede implementar utilizando una funci贸n de compuerta聽NOR est谩ndar utilizando las entradas聽A y聽B. La disposici贸n de compuerta l贸gica inferior invierte primero las dos entradas, produciendo as铆聽A y聽B. As铆, entonces convi茅rtase en las entradas a la puerta聽AND. Por lo tanto, la salida de la puerta聽AND se convierte en:聽A.聽B
Entonces podemos ver que una funci贸n est谩ndar聽y de compuerta con inversores (NO puertas) en cada una de sus entradas produce una condici贸n de salida equivalente a una funci贸n est谩ndar聽nor gate, y una puerta聽NOR individual se puede representar de esta manera, ya que la equivalencia de una puerta聽NOR es un NEGATIVO-AND.
Aunque hemos utilizado los te贸ricos de DeMorgan con solo dos variables de entrada聽A y聽B,son igualmente v谩lidos para su uso con tres, cuatro o m谩s expresiones de variable de entrada, por ejemplo:
Para una entrada de 3 variables
A.B.C =聽A+B+C
y tambi茅n
A+B+C =聽A.聽B.聽C
Para una entrada de 4 variables
A.B.C.D =聽A+B+C+D
y tambi茅n
A+B+C+D =聽A.聽B.聽C.聽D
y as铆 sucesivamente.
Puertas equivalentes de DeMorgan
Hemos visto aqu铆 que mediante el uso de Theorems de DeMorgan podemos reemplazar a todos los operadores聽AND (.) por un聽QUIR脫FANO (+) y viceversa, y luego complementa cada uno de los t茅rminos o variables de la expresi贸n invirtiendo, es decir, de 0 a 1 y 1 a 0 antes de invertir toda la funci贸n.
Por lo tanto, para obtener el equivalente de DeMorgan para una puerta聽AND,聽NAND, OR o聽NOR, simplemente agregamos inversores (PUERTAS NO) a todas las entradas y salidas y cambiamos un s铆mbolo聽AND a un s铆mbolo聽OR o cambiamos un s铆mbolo聽OR a un s铆mbolo聽AND como se muestra en la tabla siguiente.
Puertas equivalentes de DeMorgan
| Puerta l贸gica est谩ndar | La puerta equivalente de DeMorgan |
 |
 |
 |
 |
 |
 |
 |
 |
Luego hemos visto en este tutorial sobre Thereom de DeMorgan que el complemento de dos (o m谩s) variables de entrada聽AND'ed es equivalente al聽quir贸fano de los complementos de estas variables, y que el complemento de dos (o m谩s) variables聽OR'ed es equivalente al聽AND de los complementos de las variables definidos por聽DeMorgan.