Harvard chart method

From Wikiversity
Jump to navigation Jump to search
Progress-1000.svg Completion status: this resource is considered to be complete.
Nuvola apps edu mathematics-p.svg Subject classification: this is a mathematics resource.
Gnome-fs-client.svg Subject classification: this is an information technology resource.
Books-aj.svg aj ashton 01b.svg Educational level: this is a secondary education resource.
Applications-games.svg Type classification: this is a game resource.

Harvard Chart Method of Logical Equation Reduction[1][2] was developed in response to the need to automate the process of logical equation reduction in the early days of computer hardware and switching circuit development. Large scale production of computer circuitry entailed many more variables than could be reasonably handled by hand using Boolean logic. Logical equation reduction was necessary to minimize logic circuits and thereby reduce the number of logic gates which used vacuum tubes as switches due to their relatively high cost and excessive thermal emission. Logical equations with five of more variables can be reduce to minimum form using Boolean logic but as the number of variables grows the number of operations expands exponentially placing practical limits on doing logical equation reduction by hand. The Harvard Chart Method was developed to solve this problem and to automate the process of logical reduction. The method thus represents one of the first instances of computers being used to design the very circuits of which they are made. Application of this method is limited only by the logical speed and size of the computer (or computer network) on which it is run.


Logical Equation Reduction, Simplification or Minimization[edit]

(note this chart uses upper case to represent the logic state of "TRUE" and lower case to represent the logic state of "FALSE")

Lets simplify the following equation:

f = ABc + ABC + aBC + aBc + AbC


The Harvard Chart (style 1)[edit]

Harvard Chart.PNG

The Harvard Chart (style 2)[edit]

The Harvard Chart
1 2 3 4 5 6 7
A B C AB AC BC ABC
a b c ab ac bc abc Row1
a b C ab aC bC abC Row2
a B c aB ac Bc aBc Row3
a B C aB aC BC aBC Row4
A b c Ab Ac bc Abc Row5
A b C Ab AC bC AbC Row6
A B c AB Ac Bc ABc Row7
A B C AB AC BC ABC Row8

The Reduction Steps[edit]

According to William Hunter, to complete the example above a number of distinct steps need to be followed:[3]

  1. Strike out any row which contains items that do not occur in the expression that is to be simplified. In the above example, row 1 contains a, b, c, ab, ac, bc and abc, none of which occur in the expression. Accordingly, row 1 can be discounted, as can rows 2 and 5.
  2. The focus now moves to the columns. Starting from the left, remove any item that was removed from the rows that were discounted in step 1. In this case, you would remove "a", as it occurs in both rows 1 and 2, and "A" (as it occurs in row 5).
  3. Moving to the second column, "b" has to be removed, as it occurs in all three rows that were struck out. However, that means that "B" remains. Hunter recommends highlighting the B's.
  4. For each row that contains a B in the second column, you now remove all items that already contain the symbol. For example, row 3 contains aB, Bc and aBc - all three need to be struck out.
  5. Repeating the exercise with the third column, both "c" and "C" need to be removed.
  6. For the fourth column, "Ab" is the only element remaining, and it was removed from rows 1 and 2. So it should also be struck out.
  7. When the fifth column is reached, aC and Ac are removed, but this leaves AC. As with step 4, in rows containing AC, any element which incorporates AC should be removed. This will result in the removal of AbC in row 6.
  8. The sixth column is only one element unstruck: bC. This was removed in row 2, so it needs to be struck out now.
  9. All elements in the seventh column have been discounted. Therefore, looking back over the rows, only B and AC remain.
  10. Accordingly, the answer is f = B + AC.

See also[edit]

A Method for Simulating the Process of Logical Human Thought
See w:table of logic symbols for explanations of symbols used in logic.

Notes and References[edit]

  1. *Hunter, William L. [10-1975]. Chapter 4, "The Laws of Logic, Boolean Equation Simplification - The Harvard Chart". Digital/Logic electronics Handbook(in English), pp.112-113, Blue Ridge summit, PA 17214: Tab Books / No. 774, 1975. ISBN 0-8306-5774-6, ISBN 0-8306-4774-0
  2. Moved from original location in Wikipedia w:Harvard Chart Method of Logical Equation Reduction to Wikibooks by "author request, no substantial contributions by anyone else"
  3. Hunter, William L. [10-1975]. Chapter 4, "The Laws of Logic, Boolean Equation Simplification - The Harvard Chart". Digital/Logic electronics Handbook(in English), pp.112-113, Blue Ridge summit, PA 17214: Tab Books / No. 774, 1975. ISBN 0-8306-5774-6, ISBN 0-8306-4774-0