The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 

I hope this helps. If you have any more questions, write back.

- Doctor TWE, The Math Forum   
Associated Topics:
High School Logic

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.