Custom Search

De Morgan's Theorem or Rules

A mathematician named DeMorgan developed a pair of important rules regarding group complementation in Boolean algebra.

Group complementation is the complement (NOT version) of a group of terms. It is represented by a long bar over more than one input.

This is (for my way of thinking as a physicist) best thought of in terms of logic gates.

Inverting all inputs to a gate reverses that gate's essential function from AND to OR, or vice versa, and also inverts the output. So, an OR gate with all its inputs inverted (a Negative-OR gate) behaves the same as a NAND gate, and an AND gate with all its inputs inverted (a Negative-AND gate) behaves the same as a NOR gate.

Let's look at the truth tables for that:

.
+
+
.
0
0
1
1
0
1
1
0
1
1
0
1
1
0
0
1
1
1
0
0
1
0
0
1
0
1
1
1
0
0
1
1
0
0
1
0
0
1
0
0

=

=

 

De Morgan's rules are very useful for circuit simplification. They allow you to break a long bar over an expression. When the long bar is broken, the operation directly underneath the break changes from OR to AND, or vice versa, and the broken bar pieces remain over the individual variables.

When learning to use these expressions at college I always had to write them out at the start of an examination - make myself an equation sheet - in those days we were not given such things!! Swap the dot and cross and split the top bar - simples!

= +

see above
= .

see above

When using De Morgan's Laws:

  • break one bar at a time - don't try to do it all in one line - you will make a mistake!
  • it doesn't matter which bar you break first, but I usually break the longest first.

Example Question

Simplify the expression

First of all break the big bar and change the 'plus sign' to a 'dot'.I have put the B and C expression into a bracket so that I do not get confused!

We now have a double bar - a double negative cancels out - let's do that before we continue.

We can then tidy up and remove the brackets.

-------------------------------------------

We can now try doing this by breaking the short bar first:

It is a good idea to put the B and C part of the expression into a bracket:

Now we have to break the big bar - the bracket we put in reminds us that the breaking bar will be between A and the A and B expression.

We now have the bar above the A and B expression to deal with:

The double bars can be erased.

We can then tidy up and remove the brackets.

So you can see that it doesn't matter which way you do this. You get to the same answer in the end. BUT is is important that you write out each step and that you bracket together sections that you are treating as one item.