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
design.

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

- Doctor TWE, The Math Forum
http://mathforum.org/dr.math/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search