De Morgan's Laws
Date: 09/21/2000 at 19:40:51 From: Brandan Placke Subject: De Morgan's Law What is "De Morgan's Law"?
Date: 09/22/2000 at 09:41:34 From: Doctor Twe Subject: Re: De Morgan's Law Hi Brandan - thanks for writing to Dr. Math. DeMorgan's Laws (a.k.a. DeMorgan's Theorems) have several variations, depending on what branch of mathematics you're studying. They state a relation between the set operations intersection, union, and complement, or a relation between the logic operations AND, OR and NOT (or complement); or a relation between the digital electronics circuits AND gates, OR gates, NAND gates, NOR gates, and inverters. As Set Theorems, they state: ~(AUB) = ~A^~B ~(A^B) = ~AU~B where ~A means "the complement of A," A^B means "A intersect B," and AUB means "A union B." Similarly, as Logic Theorems, they state: ~(A+B) = ~A.~B ~(A.B) = ~A+~B where ~A means "not A," A.B means "A and B," and A+B means "A or B." This allows us to "distribute" the not function and get rid of the parenthesis (but note that the operation inside the parenthesis - the AND or OR - changes.) Essentially, we have just changed the complement function to the NOT function, intersection to AND, and union to OR. These are equivalent operations on different data types. Finally, in Digital Electronics, they define the equivalence for the NAND and NOR gates. (The Boolean expressions would be written as above.) The first one states that a NOR gate can be replaced with an AND gate with inverters on each input or vice-versa: ______ _____ A __\ \ A --o| \ B __ ) >o-- X = | )-- X /_____/ B --o|_____/ The second one states that a NAND gate can be replaced with an OR gate with inverters on each input or vice-versa: _____ ______ A __| \ A --o\ \ B __| )o-- X = ) >-- X |_____/ B --o/_____/ These are useful replacements, especially when simplifying a circuit design. I hope this helps. If you have any more questions, write back. - Doctor TWE, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.