DeMorgan's Theorem

From Digital Logic Wiki
Jump to: navigation, search

Contents

Introduction

A mathematician named [Augustus DeMorgan] developed a [pair of important theorems] regarding the complementation of groups in Boolean algebra. DeMorgan found that an OR gate with all inputs inverted (a Negative-OR gate) behaves the same as a NAND gate with positive inputs; and an AND gate with all inputs inverted (a Negative-AND gate) behaves the same as a NOR gate with positive inputs. DeMorgan's theorem states that inverting the output of any gate is the same as using the opposite type of gate with inverted inputs. To put this in circuit terms, DeMorgan's theorem states that the AND gate with inverted output and the OR gate with inverted inputs in the following circuit are functionally equivalent.


Circuit Equivalent of DeMorgan's Theorem


Throughout this course, the NOT function is represented as an apostrophe because it is easy to type, like: (AB)' for "A AND B NOT." However, it is easiest to work with DeMorgan's theorem if NOT is represented by an overbar rather than an apostrophe. Thus, you would write LaTeX: \overline{AB} rather than LaTeX: (AB)'. Remember that an overbar is a grouping symbol (like parenthesis) and it means that everything under that bar would be complemented.

Applying DeMorgan's Theorem

Applying DeMorgan's theorem to a Boolean expression may be thought of in terms of "breaking the bar," or complementing. When applying DeMorgan's theorem to a Boolean expression:

  1. A complement bar is broken over a group of variables
  2. The operation (AND or OR) directly underneath the broken bar changes
  3. Pieces of the broken bar remain over the individual variables.

To illustrate:

LaTeX: \overline{A*B}\longleftrightarrow\overline{A}+\overline{B}

This formula shows how a two-input NAND gate is "broken" to form an OR gate with two complemented inputs.

LaTeX: \overline{A+B}\longleftrightarrow\overline{A}*\overline{B}

This formula shows how a two-input NOR gate is "broken" to form an AND gate with two complemented inputs.

Simple Example

When multiple "layers" of bars exist in an expression, only one bar is broken at a time, and the longest, or uppermost, bar is broken first. To illustrate, consider this circuit:


Circuit To Simplify with DeMorgan's Theorem


By writing the output at each gate (as illustrated), it is easy to determine the Boolean expression for the circuit:

LaTeX: \overline{A+\overline{BC}}

To simplify the circuit, break the bar covering the entire expression, and then simplify the resulting expression.

Expression Simplified
LaTeX: \overline{A+\overline{BC}} Original Expression
LaTeX: \overline{A}\overline{\overline{BC}} "Break" the longer bar and change to AND
LaTeX: \overline{A}BC Involution Property

As a result, the original circuit is reduced to a three-input AND gate with an inverter on one leg:


Simplified Circuit Using DeMorgan's Theorem

Incorrect Application of DeMorgan's Theorem

More than one bar is never broken in a single step, as illustrated by making that mistake with the previous problem:

Expression Simplified
LaTeX: \overline{A+\overline{BC}} Original Expression
LaTeX: \overline{A}\overline{\overline{B}}+\overline{\overline{C}} "Breaking" both the long and short bars at one time
LaTeX: \overline{A}B+C Incorrect solution due to breaking too many bars at one time

Thus, as tempting as it may be to take a shortcut and break more than one bar at a time, it often leads to an incorrect result. While it is possible to properly reduce an expression by breaking the short bar first; more steps are required so it is not recommended.

About Grouping

An important, but easily neglected, aspect of DeMorgan's theorem concerns grouping. Since a long bar functions as a grouping symbol, the variables formerly grouped by a broken bar must remain grouped or else proper precedence (order of operation) will be lost. Therefore, after simplifying a large grouping of variables, place them in parentheses in order to keep the order of operation the same.

Consider the following circuit:


Circuit Used to Illustrate Grouping with DeMorgan's Theorem


As always, the first step in simplifying this circuit is to generate the Boolean expression, which is done by writing the sub-expression at the output of each gate, as illustrated.

Grouping Example
LaTeX: \overline{\overline{A+BC}+\overline{A\overline{B}}} Original Expression
LaTeX: (\overline{\overline{A+BC}})(\overline{\overline{A\overline{B}}}) Breaking the longest bar but keep grouping
LaTeX: (A+BC)(A\overline{B}) Involution Property
LaTeX: (AA\overline{B})+(BCA\overline{B}) Distribute (A+BC)
LaTeX: (A\overline{B})+(BCA\overline{B}) Idempotence: AA=A
LaTeX: (A\overline{B})+0CA Complement: BB'=0
LaTeX: (A\overline{B})+0 Annihilator: A0=0
LaTeX: (A\overline{B}) Identity Element: A+0=A

The equivalent gate circuit for this much-simplified expression is as follows:


Circuit Simplified with DeMorgan's Theorem

Summary

Here are the important points to remember about DeMorgan's Theorem:

  • It describes the equivalence between gates with inverted inputs and gates with inverted outputs.
  • When "breaking" a complementation (or NOT) bar in a Boolean expression, the operation directly underneath the break (AND or OR) reverses and the broken bar pieces remain over the respective terms.
  • It is normally easiest to approach a problem by breaking the longest (uppermost) bar before breaking any bars under it.
  • Two complementation bars are never broken in one step.
  • Complementation bars function as grouping symbols. Therefore, when a bar is broken, the terms underneath it must remain grouped. Parentheses may be placed around these grouped terms as a help to avoid changing precedence.

Example Problems

The following examples use DeMorgan's Theorem to simplify a Boolean function.

Example DeMorgan Simplification
Original Function Simplified
LaTeX: (\overline{A + B})(\overline{ABC})(\overline{\overline{A}C}) LaTeX: \overline{A}\,\overline{B}\,\overline{C}
LaTeX: \overline{(AB + \overline{B}C)+(B\overline{C}+\overline{A}B)} LaTeX: \overline{B}\,\overline{C}
LaTeX: \overline{(AB+\overline{B}C)(AC+\overline{A}\,\overline{C})} LaTeX: \overline{A}+\overline{C}

Personal tools