NAND gate method to simplify boolean expressions

Table of contents

1. Introduction
2. Functional completeness
3. Simplification
   1. Step 1: Double negation
   2. Step 2: Applying De Morgan’s law
   3. Step 3: Construct the NAND circuit

Introduction

NAND Gates are universal gates. By the virtue of functional completeness, NAND Gates can be used to fully represent a given boolean expression. This simplifies the expression such that only one standard gate is used throughout.

Functional completeness

Functional completeness is a property pertaining to boolean logic, which states that a functionally complete boolean operator can express all possible truth tables by representing itself in a boolean expression. That is, any given boolean expression can be completely represented by using the a functionally complete boolean operator.

For example, NAND gates can be used to implement the NOT gate, the OR gate and the AND gate.

Simplification

To simplify any given boolean expression, first find the minimum number of NAND gates required. To do this, carry out the following steps.

Let’s find the minimum number of NAND gates required to simplify the logical expression:

F(A, B, C, D) = AB' + C'D

Step 1: Double negation

Since the NAND gate is a combination of a NOT gate and an AND gate, we first apply a double negation to the entire expression so that we are able to standardize it later on.

Adding a double negation does not alter the inherent value of the expression as a double negation always nullifies itself.

F = (F')' = ((AB' + C'D)')'

Step 2: Applying De Morgan’s law

We first apply De Morgan’s Law to the innermost bracket, such that we preserve the outermost negation at the time of expressing the F as a NAND expression.

Thus, by applying De Morgan’s Law:

F = ((AB' + C'D)')'
  = ((AB')' . (C'D)')' 

The boolean expression is now standardized such that it can completely be represented by a NAND gate at every input level.

Step 3: Construct the NAND circuit

Now that you have gotten the boolean expression to the required standard, you can implement it as a NAND circuit.

F = (A NAND B') NAND (C' NAND D)
F = (A NAND (B NAND B)) NAND ((C NAND C) NAND D)

Notice that there are input elements that are present in the negative form, namely B' and C'. You can represent them by using the NAND gate in order to realise the NOT gate.