Skip to content Skip to navigation

Connexions

You are here: Home » Content » An algorithm to implement a boolean function using only NAND's or only NOR's.

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

      A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

      What is in a lens?

      Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

      Who can create a lens?

      Any individual Connexions member, a community, or a respected organization.

      What are tags? tag icon

      Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

    • External bookmarks
  • E-mail the author
  • Rate this module (How does the rating system work?)

    Rating system

    Ratings

    Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

    How to rate a module

    Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

    		(0 ratings)

Recently Viewed

This feature requires Javascript to be enabled.

An algorithm to implement a boolean function using only NAND's or only NOR's.

Module by: Katherine Fletcher

Summary: An algorithm to implement a boolean function as a gate network using only NAND's or only NOR's is presented. Any boolean function can be implemented straightforwardly using AND's, OR's, and NOT gates. Using DeMorgan's Law in different forms gates in the network can be successively converted to use only NAND's or only NOR's.

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

NAND's and NOR's are the most common basic logic circuit element in use because they are simpler to build than AND and OR gates, and because each is logically complete . Many logical functions are expressed using AND's, OR's, and Inverters (NOT), however, because an implementing circuit can be constructed straightforwardly from the truth table expression of a logical function and because Karnaugh Map's can be used to minimize AND, OR, INVERTER networks.

This document is adapted, with permission, from algorithms and examples given in Dr. Jump's Elec326 course notes.

Below a simple algorithm is given for converting a network with AND gates, OR gates and INVERTERS to one with NAND gates or NOR gates exclusively. First the boolean function is represented using AND's, OR's, and NOT gates. Then, using DeMorgan's Law in various forms, the AND, OR, INVERTER network is converted step-by-step to use only NAND gates or only NOR gates.

Table 1: DeMorgan's Law using Boolean Algebra
OR to NAND AND to NOR
a∨b≡¬(¬a∧¬b)a∨b≡¬(¬a∧¬b) a∧b≡¬(¬a∨¬b)a∧b≡¬(¬a∨¬b)

Figure 1: The figure is adapted with permission from Dr. Robert Jump's Elec326 lecture notes . The first two rows of the figure above illustrate DeMorgan's Law using gates. The third row illustrates how to eliminate any inverters with either NAND or NOR gates.
DeMorgan's Laws Illustrated Using Logic Gates
DeMorgan's Laws Illustrated Using Logic Gates (demorgans.jpg)

Conversion Algorithm

  1. Draw AND, OR, INVERTER implementation. First draw out an implementation of the boolean function using AND gates, OR gates and INVERTERS. Any implementation that uses only those three gate types will work. One way to implement a boolean function using AND's, OR's and INVERTERS is to build the Disjunctive Normal Form of the boolean function from the truth table that describes the function. Disjunctive Normal Form, is also called Sum of Products form. Propositional Logic: Normal Forms gives a succinct treatment of normal forms and of how to go from a truth table to Disjunctive Normal Form.
  2. Apply DeMorgan's Law. Apply DeMorgan's Law to the circuit by using the equivalences in the first two rows of the Figure above. To create a NAND only circuit, use the transforms in the left box, and for a NOR only circuit use the transforms in the right-hand box.
  3. Remove redundant inverters: Any time that two inverters are in series (an inverted output goes directly in to an inverted input), remove both of them, since they cancel each other out.
  4. Replace remaining inverters. Replace any remaining inverters with the equivalent NAND or NOR implementation (the third row of the Figure).

Example 1

Figure 2: Example conversion to a NAND only network.
Conversion Example
Conversion Example (conversion.png)

Note that in step c. the final elimination of inverters isn't quite done since B and D are inverted into one of the NAND's.

Glossary

Karnaugh Map:
A visual map of the truth table of a boolean expression and an algorithm for removing redundant elements to realize a minimized boolean expression.
logically complete:
A set of circuit gates or logical elements is logically complete if any boolean function representable by a truth table can be realized using only gates or elements from that set.

Example:

AND, OR, and NOT is a logically complete set. NAND is logically complete. NOR is logically complete.

References

  1. Robert Jump. (2004). NAND/NOR Networks. Rice University, Department of Electrical and Computer Engineering, Houston TX 77251: Unpublished course notes from Elec 326.

Comments, questions, feedback, criticisms?

Send feedback