Electronics Logic Gates: De Morgan’s Theorem

De Morgan’s Theorem was created by Augustus De Morgan, a 19th-century mathematician who developed many of the concepts that make Boolean logic work with electronics. Among De Morgan’s most important work are two related theorems that have to do with how NOT gates are used in conjunction with AND and OR gates:

  • An AND gate with inverted output behaves the same as an OR gate with inverted inputs.

  • An OR gate with inverted output behaves the same as an AND gate with inverted inputs.

An AND gate with inverted output is also called a NAND gate, of course, and an OR gate with inverted output is also called a NOR gate. Thus, De Morgan’s laws can also be stated like this:

  • A NAND gate behaves the same as an OR gate with inverted inputs.

  • A NOR gate behaves the same as an AND gate with inverted inputs.

An OR gate with inverted inputs is called a negative OR gate, and an AND gate with inverted inputs is called a negative AND gate.

In case you’re not persuaded, review for a moment the truth table for a NAND gate:

A B X
0 0 1
0 1 1
1 0 1
1 1 0

Now look at the truth table for an OR gate, with an extra set of columns added to show the inverted inputs:

A B NOT A NOT B X
0 0 1 1 1
0 1 1 0 1
1 0 0 1 1
1 1 0 0 0

Here, the A and B columns represent the inputs. The NOT A and NOT B columns are the inputs after they’ve been inverted. Finally, the X column represents an OR operation applied to the NOT A and NOT B values.

As you can see, the final output column of these truth tables is the same. Thus, a NAND gate is equivalent to a negative OR gate. Any time you see a NAND gate in a circuit diagram, you can substitute a negative OR gate.

Now take a look at the other side of De Morgan’s Theorem. Here’s a truth table for a NOR gate:

A B X
0 0 1
1 0 0
0 1 0
1 1 0

And here’s the output of a negative AND gate:

A B NOT A NOT B X
0 0 1 1 1
0 1 1 0 0
1 0 0 1 0
1 1 0 0 0

Again, you can see that these two truth tables give the same output.

Just as a circle is used on the output of a NAND or NOR gate to indicate that the output is inverted, you can use a circle on the inputs to an OR or AND gate to indicate that the inputs are inverted.

image0.jpg
  • Add a Comment
  • Print
  • Share
blog comments powered by Disqus
Advertisement

Inside Dummies.com