# Functional equivalence

Recall that one of the gates for which we have defined a truth table
is called **nor**:

A |
B |
A nor B |

0 | 0 | 1 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 0 |

We can construct other circuits whose output column is the same as
that for **nor** For instance, consider the function

**not**

*A*)

**and**(

**not**

*B*)

We can derive its truth table as follows:

A |
B |
not A |
not B |
(not A) and
(not B) |

0 | 0 | 1 | 1 | 1 |

0 | 1 | 1 | 0 | 0 |

1 | 0 | 0 | 1 | 0 |

1 | 1 | 0 | 0 | 0 |

Notice the final column is the same as the **nor** table! We can
put them together in the same table to be extra clear about this:

↓ | ↓ | ||||

A |
B |
not A |
not B |
(not A) and
(not B) |
A nor B |

0 | 0 | 1 | 1 | 1 | 1 |

0 | 1 | 1 | 0 | 0 | 0 |

1 | 0 | 0 | 1 | 0 | 0 |

1 | 1 | 0 | 0 | 0 | 0 |

This is one way to conclusively show that two circuits are functionally equivalent. That is, the two expressions compute the same function: for any set of valid inputs, both expressions will produce exactly the same output. We sometimes use the symbol "⇔" to indicate that two expressions are equivalent:

*A* **nor**
*B*
⇔
(**not ***A*) **and
**(**not** *B*)

**nor**can be defined as a combination of

**not**with

**or**, and we can use our new notation to express this directly:

*A*

**nor**

*B*⇔

**not**(

*A*

**or**

*B*)

↓ | ↓ | |||

A |
B |
A nor B |
A or B |
not (A or B) |

0 | 0 | 1 | 0 | 1 |

0 | 1 | 0 | 1 | 0 |

1 | 0 | 0 | 1 | 0 |

1 | 1 | 0 | 1 | 0 |

Furthermore, since we've found two different expressions each
equivalent to
*A* **nor** *B*,
those two expressions are also functionally equivalent to each
other:

**not** (*A* **or**
*B*)
⇔
(**not ***A*) **and
**(**not** *B*)

We can determine whether *any* two logical functions are
equivalent by comparing their truth tables.
The functions are equivalent if and only if the truth values are the
same.

### Functional completeness

We have seen a total of six gates defined, but
for an electrical engineer trying to design hardware,
it isn't actually necessary to build all six gates. Some of them can be
written
as combinations
of others. For instance, we have already
seen that **nor** can be written as a combination of **not** and
**and**
gates:

*A*

**nor**

*B*⇔ (

**not**

*A*)

**and**(

**not**

*B*)

If we have two **not** gates and one
**and** gate, we can build a circuit that will
perform the **nor** function.

Similarly, we can write **nand**
and
**xor** as combinations of **and**,
**or**, and **not** gates (Exercises 9 and 11). This means that the set of gates {**and**,
**or,** **not**} is **functionally
complete**, because the other basic gates (and indeed, any logical circuit)
can be built from only these three gates.

Are there other functionally complete sets of gates? The answer is yes. Indeed, **and** can be written as a combination of **or** and **not**:

*A* **and**
*B*
⇔
**not** ((**not** *A*)
**or** (**not** *B*))
,

which you can verify using a truth
table. So {**not**,
**or**}
is functionally complete.

Similarly,
**or** can be written as a combination of **and** and **not**.

*A* **or**
*B*
⇔
**not** ((**not** *A*)
**and** (**not** *B*))
,

so
{**not**, **and**}
is functionally complete.

Surprisingly, {**nand**}
by itself is functionally complete!

**not**** ***A*
⇔
*A* **nand** *A*

*A* **and
***B*
⇔
(*A* **nand ***B*) **nand** (*A* **nand**
*B*) (Exercise
12)

*A* **or**
*B *
⇔
(*A* **nand** *A*) **nand** (*B* **nand*** B*) (Exercise
13)

Similarly, {**nor**}
is a functionally complete set. This
means that a computer engineer with a big supply of **nand** or **nor**
gates could theoretically build the most powerful computer in the world.

## Exercises

- Are the following circuits functionally equivalent?
- Are the following circuits functionally equivalent?
- Are the circuits
*x***and***x*and*x*functionally equivalent? - Are the circuits
*x***or**(*x***and***y*) and*x*functionally equivalent? - Are the circuits
**not**(*A***or***B*) and (**not***A*)**or**(**not***B*) functionally equivalent? - Are the circuits
**not**(*A***and***B*) and (**not***A*)**or**(**not***B*) functionally equivalent? - Are the circuits
*x***and**(**not***y*), and (**not***x*)**or***y*, functionally equivalent? - Are the circuits
(
**not***z*)**or**((**not***y*)**and***x*), and (*x***and**(**not***z*))**or**(**not**(*y***or***z*)), functionally equivalent? - Design a
circuit that is functionally equivalent to a
*NAND*gate using only*AND*,*OR*, and*NOT*gates*.* - Design a
circuit that is functionally equivalent to a
*NOR*gate using only*AND*,*OR*, and*NOT*gates*.* - Design a
circuit that is functionally equivalent to a
*XOR*gate using only*AND*,*OR*, and*NOT*gates*.* - Design a
circuit that is functionally equivalent to an
*AND*gate using only*NAND*gates*.* - Design a
circuit that is functionally equivalent to an
*OR*gate using only*NAND*gates.

## Credits and licensing

This article is by Robert P. Webber and Don Blaheta, licensed under a Creative Commons BY-SA 3.0 license.

Version 2016-Mar-23 01:00