Teorema de DeMorgan

Com hem vist anteriorment, l'Àlgebra Boolean utilitza un conjunt de lleis i regles per definir el funcionament d'un circuit lògic digital amb "0's" i "1's" que s'utilitzen per representar una condició d'entrada o sortida digital. L'Àlgebra Boolean utilitza aquests zeros i els per crear taules de veritat i expressions matemàtiques per definir el funcionament digital d'una lògica i, O i NO (o inversió), així com maneres d'expressar altres operacions lògiques com la funció XOR (Exclusive-OR)

Mentre que el conjunt de lleis i normes de George Boole ens permet analiar i simplificar un circuit digital, hi ha dues lleis dins del seu conjunt que s'atribueixen a Augustus DeMorgan (un matemàtic anglès del segle XIX) que veu les operacions lògiques NAND i NOR com a funcions separades NO I NO I NO O respectivament.

Però abans de mirar la teoria de DeMorgan amb més detall, recordem-nos les operacions lògiques bàsiques on A i B són variables binàries d'entrada lògiques (o booleanes), i els valors només poden ser"0"o"1" produintquatre combinacions d'entrada possibles, 00, 01, 10i 11.

Taula de veritat per a cada operació lògica

Variable d'entrada		Condicions de sortida
Un	B	I	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

La taula següent dóna una llista de les funcions lògiques comunes i la seva notació booleana equivalent on un "." (un punt) significa una operació AND (producte), un "+" (signe més) significa una operació OR (suma), i el complement o invers d'una variable s'indica per una barra sobre la variable.

Funció lògica	Notació booleana
I	A.B
O	A+B (A+B)
No	Un
Nand	Un. B
Ni	A+B (A+B)

La teoria de DeMorgan

Els teorems de DeMorgan són bàsicament dos conjunts de regles o lleis desenvolupades a partir de les expressions booleanes per and, O no utilitzant dues variables d'entrada, A i B. Aquestes dues regles o teorems permeten negar i convertir les variables d'entrada d'una forma d'una funció booleana en una forma oposada.

El primer teorema de DeMorgan afirma que dues (o més) variables NOR'ed junts són les mateixes que les dues variables invertida (Complement) i AND'ed, mentre que el segon teorema afirma que dues (o més) variables nand'ed junts és la mateixa que els dos termes invertits (Complement) i OR'ed. És a dir, substituir tots els operadors OR per operadors AND, o tots els operadors and per un operador OR.

El primer teorema de DeMorgan

El primer teorema de DeMorgan demostra que quan dues (o més) variables d'entrada són and'ed i negades, són equivalents a l'OR dels complements de les variables individuals. Així, l'equivalent a la funció NAND serà una funció negativa-OR, demostrant que A.B = A+B. Podem mostrar aquesta operació utilitzant la taula següent.

Verificació del primer teorema de DeMorgan utilitzant la taula de la veritat

Aportacions		Sortida de la taula de veritat per a cada terme
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

També podem demostrar que A.B = A+ B utilitzantportes lògiques com es mostra.

Primera aplicació de la llei de DeMorgan utilitzant Logic Gates

La disposició de la porta lògica superior de: A.B es pot implementar utilitzant una porta NAND estàndard amb entrades A i B. La disposició de la porta lògica inferior inverteix primer les dues entrades que produeixen A i B. Aquests es converteixen en les entrades a la porta OR. Per tant, la sortida des de la porta OR es converteix en: A+B

A continuació, podem veure aquí que una funció estàndard o porta amb inversors (no portes) en cadascuna de les seves entrades equival a una funció de porta NAND. Així que una porta NAND individual es pot representar d'aquesta manera, ja que l'equivalència d'una porta NAND és un negatiu-OR.

Segon Teorema de DeMorgan

El segon teorema de DeMorgan demostra que quan dues (o més) variables d'entrada són OR'ed i negades, són equivalents a l'AND dels complements de les variables individuals. Així, l'equivalent de la funció NOR és una funció negativa-AND que demostra que A+B = A. B, i una altra vegada podem mostrar operació això utilitzant la taula de veritat següent.

Verificació del segon teorema de DeMorgan utilitzant la taula de la veritat

Aportacions		Sortida de la taula de veritat per a cada terme
B	Un	A+B (A+B)	A+B (A+B)	Un	B	A . B (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

També podem demostrar que A+B = A. B utilitzant l'exemple de portes lògiques següents.

La segona aplicació de la llei de DeMorgan utilitzant Logic Gates

La disposició de la porta lògica superior de: A + B es pot implementar utilitzant una funció estàndard de porta NOR utilitzant les entrades A i B. La disposició de la porta lògica inferior inverteix primer les dues entrades, produint així A i B. Així doncs, convertir-se en les entrades a la porta and. Per tant, la sortida des de la porta and es converteix en: A. B (B)

A continuació podem veure que una funció estàndard i de porta amb inversors (NO portes) en cadascuna de les seves entrades produeix una condició de sortida equivalent a una funció estàndard nor gate, i una porta NOR individual es pot representar d'aquesta manera com l'equivalència d'una porta NOR és un negatiu-I.

Tot i que hem utilitzat els teorems de DeMorgan amb només dues variables d'entrada A i B,són igualment vàlides per al seu ús amb tres, quatre o més expressions variables d'entrada, per exemple:

Per a una entrada de 3 variables

A.B.C = A+B+C

i també

A+B+C = A. B. C Des del

For a 4-variable input

A.B.C.D = A+B+C+D

i també

A+B+C+D = A. B. C. D (D)

i així successivament.

Les portes equivalents de DeMorgan

Hem vist aquí que mitjançant l'ús dels Teorems de DeMorgan podem substituir tots els operadors and (.) per un OR (+) i viceversa, i després complementa cada un dels termes o variables en l'expressió invertint-lo, és a dir, de 0 a 1 i 1 a 0 abans d'invertir tota la funció.

Així, per obtenir l'equivalent de DeMorgan per a una porta AND, NAND, OR o NOR, simplement afegim inversors (NO-portes) a totes les entrades i sortides i canviem un símbol AND a un símbol OR o canviem un símbol OR a un símbol AND tal com es mostra a la taula següent.

Les portes equivalents de DeMorgan

Porta lògica estàndard	Porta equivalent de DeMorgan

A continuació, hem vist en aquest tutorial sobre Thereom de DeMorgan que el complement de dues (o més) variables d'entrada and'ed equival a l'OR dels complements d'aquestes variables, i que el complement de dues (o més) variables OR'ed equival a l'I dels complements de les variables tal com defineix DeMorgan.