How do you remember DeMorgan's theorems?

DeMorgan's theorems

DeMorgan's theorems

Chapter 7 - Boolean Algebra

A mathematician named DeMorgan developed a couple of important rules for group complementation in Boolean algebra. In group complementation, I am referring to the complement of a group of terms represented by a long bar over more than one variable.

You should remember the chapter on logic gates that inverting all the inputs of a gate reverses the essential function of that gate from AND to OR or vice versa, and also inverts the output. An OR gate with all inverted inputs (a negative OR gate) behaves exactly like a NAND gate, and an AND gate with all inverted inputs (a negative AND gate) behaves just like a NOR gate. DeMorgan's theorems state the same equivalence in "reverse" form: that inverting the output of any gate results in the same function as the opposite type of gate (AND vs. OR) with inverted inputs:

A long bar spanning the term AB acts as a grouping symbol and as such is inverted independently, completely different from the product of A and B. In other words, (AB) 'is not the same as A'B'. Since the "prime" symbol (') cannot stretch across two variables like a bar, we are forced to use parentheses to apply it to the entire AB expression in the previous sentence. However, a bar functions as its own grouping symbol when it is spread over several variables. This has a profound impact on how Boolean expressions are evaluated and reduced, as we shall see.

DeMorgan's theorem can be thought of in terms of breaking a long bar symbol. When a long bar is broken, the operation changes from addition to multiplication or vice versa just below the break, and the broken bar pieces remain above each variable. To illustrate:

When there are multiple "levels" of bars in a printout, you can only break one bar at a time, and it is generally easier to start simplifying by breaking the longest (top) bar first. To illustrate, we take the expression (A + (BC) ')' and reduce it using DeMorgan's theorems:

Following the advice of breaking the longest (top) bar first, as a first step I will start by breaking the bar for the entire printout:

As a result, the original circuit is reduced to a three-input AND gate with the A input inverted:

You should never break more than one bar in one step, as shown here:

As tempting as it is to save steps and break more than one bar at a time, it often leads to a wrong result, so don't do it!

It is possible to reduce this expression properly by breaking through the short bar first rather than the long bar first.

The end result is the same, but it takes more steps compared to the first method where the longest bar was broken first. Notice how in the third step we broke the long bar in two places. This is a legitimate math operation, and not the same thing as breaking two bars in one step! The prohibition on breaking more than one bolt in one step is not a prohibition on breaking a bolt in more than one place. It's okay to enter more than one location in a single step. breaking more than a bar in one step isn't.

You may be wondering why parentheses were put around the sub-expression B '+ C', considering the fact that I just removed them in the next step. I did this to emphasize an important, but slightly neglected, aspect of DeMorgan's theorem. Since a long bar acts as a grouping symbol, the variables previously grouped by a broken bar must remain grouped so that the correct priority (order of operations) is not lost. In this example, it really wouldn't mind if I forgot to put brackets after the short bar was broken, but in other cases it could be. Consider this example starting with another expression:

As you can see, maintaining the grouping implied by the complementation bars for this phrase is critical to getting the correct answer.

Let's apply the principles of DeMorgan's theorems to the simplification of a gate circuit:

As always, our first step in simplifying this circuit has to be to create an equivalent Boolean expression. We can do this by placing a sub-expression label at the output of each gate as soon as the inputs become known. Here is the first step in this process:

Next we can denote the outputs of the first NOR gate and the NAND gate. When it comes to gates with inverted output, I find it easier to write an expression for the output of the gate without the final inversion, with an arrow pointing right in front of the inversion bubble. Then I write the complete, complemented printout on the wire that leads out of the gate (after the bubble). This helps ensure I don't forget a complementing bar in the subexpression by forcing myself to split the expression writing task into two steps:

Finally, we write an expression (or a pair of expressions) for the last NOR gate:

Now we reduce this expression with the identities, properties, rules and theorems (DeMorgans) of Boolean algebra:

The equivalent gate circuit for this oversimplified expression is as follows:

  • DeMorgan's theorems describe the equivalence between gates with inverted inputs and gates with inverted outputs. Simply put, a NAND gate is equivalent to a negative OR gate and a NOR gate is equivalent to a negative AND gate.
  • When a complementary bar in a Boolean expression is "broken", the operation just below the fraction (addition or multiplication) is reversed and the broken bar pieces remain above the respective terms.
  • It is often easier to approach a problem by breaking the longest (top) bar before breaking any bars below it. You must never try to break two bars in one go!
  • Supplement bars function as grouping symbols. If a bar is broken, the terms below must therefore remain grouped. Parentheses can be put around these grouped terms in order to avoid a change in priority.