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.