Boolean Algebra

The equivalence between NAND gates and Negative-OR gates is something easily verified by an examination of these two gates’ respective truth tables, and is often a starting-point for learning about DeMorgan’s Theorem:

A lesser-known fact is how the equivalence between NAND and Negative-OR gates may be transformed to express an equivalence between two other types of gates, shown here:

Another example is shown here:

Explain how the first equivalence (between the NAND and the Negative-OR gate) was transformed into the latter two equivalences, both in terms of the gate symbols and their respective Boolean expressions. In other words, explain how we can derive the last two examples by manipulating the first example.

Suppose we wished to have an AND gate for some logic purpose, but did not have any AND gates on hand. Instead, we only had NOR gates in our parts collection. Draw a diagram whereby multiple NOR gates are connected together to form an AND gate.

NAND and NOR gates both have the interesting property of universality. That is, it is possible to create any logic function at all, using nothing but multiple gates of either type. The key to doing this is DeMorgan’s Theorem, because it shows us how properly applied inversion is able to convert between the two fundamental logic gate types (from AND to OR, and visa-versa).

Using this principle, convert the following gate circuit diagram into one built exclusively of NAND gates (no Boolean simplification, please). Then, do the same using nothing but NOR gates: