An inverted AND and an inverted OR
Put a NOT gate after an AND gate, and the pair becomes a single NAND gate, short for NOT AND. Its output is the opposite of AND's in every row: it is \(0\) only when all inputs are \(1\). In the same way a NOT after an OR makes a NOR gate, NOT OR, which is \(1\) only when all inputs are \(0\). The symbols are those of AND and OR with the inversion bubble at the output.
The two tables are the AND and OR columns turned upside down: \[ \begin{array}{cc|c|c} A & B & \overline{A \cdot B} & \overline{A + B} \\ \hline 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \end{array} \] NAND has a single \(0\), in the last row. NOR has a single \(1\), in the first row.
Both inputs of a NAND gate are at \(1\). What is its output, and what would an AND gate give?
One gate that makes all the others
Join the two inputs of a NAND gate, so that both receive \(A\). Its output is \(\overline{A \cdot A} = \bar A\), because \(A \cdot A = A\). One NAND with joined inputs is a NOT gate. Put such a NOT after a NAND, and the two inversions cancel, \(\overline{\overline{A \cdot B}} = A \cdot B\): two NANDs make an AND gate.
The OR gate at the bottom of Fig 6.1 needs three NANDs. Two of them, with joined inputs, invert \(A\) and \(B\), and the third NANDs the results: \(Y = \overline{\bar A \cdot \bar B}\). Try the chips: \(Y\) is \(0\) only when \(A\) and \(B\) are both \(0\), which is exactly OR. The theorem later in this lesson proves it in one line.
Every logic function, however complicated, can be written with NOT, AND and OR alone. Since NAND gates alone make all three, NAND gates alone can build any logic circuit. The same is true of NOR gates, and so NAND and NOR are called universal gates. A factory that makes only one kind of gate can build a whole computer.
With NOR the roles swap. One NOR with joined inputs gives \(\overline{A + A} = \bar A\), a NOT. A NOR followed by a NOR-as-NOT gives \(\overline{\overline{A + B}} = A + B\), an OR, from two gates. Inverting both inputs and then NORing them gives \(\overline{\bar A + \bar B} = A \cdot B\), an AND, from three gates.
How many NOR gates are needed to build a two-input AND gate?
The output of a NAND gate is fed to both inputs of a second NAND gate. What does the pair do?
Break the bar, change the sign
NOR says "not (A or B)". In words, that is the same as "not A, and not B": neither is true. NAND says "not (A and B)", which is the same as "not A, or not B": at least one is false. These two facts are De Morgan's theorems. To invert a whole expression, invert each part and swap \(+\) with \(\cdot\).
For any logic levels \(A\) and \(B\): \(\overline{A + B} = \bar A \cdot \bar B\), and \(\overline{A \cdot B} = \bar A + \bar B\).
A theorem about two inputs can be proved by trying all four rows. For the first theorem: \[ \begin{array}{cc|c|cc|c} A & B & \overline{A + B} & \bar A & \bar B & \bar A \cdot \bar B \\ \hline 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \end{array} \] The third and last columns agree in every row, so the two sides are equal. The second theorem checks the same way.
\[ Y = \overline{\bar A \cdot \bar B} \]
Why. the output of the three-NAND circuit: two NANDs invert \(A\) and \(B\), and the third NANDs the results.
?
Your turn. De Morgan's second theorem, applied with \(\bar A\) and \(\bar B\) as the two inputs. Which line is it?
\[ Y = A + B \]
Read it. inverting twice changes nothing, \(\bar{\bar A} = A\).
Simplifying a gate circuit
The rules of Boolean algebra and De Morgan's theorems often shrink a circuit. Two useful results come from taking out a common factor, just as in ordinary algebra. First, \(A + A \cdot B = A(1 + B) = A \cdot 1 = A\): if \(A\) is \(1\), \(B\) does not matter. Second, \(A \cdot B + A \cdot \bar B = A(B + \bar B) = A \cdot 1 = A\). Each looked like it needed two or three gates, yet the output is simply \(A\).
A third result is easiest to prove with a table: \(A + \bar A \cdot B = A + B\). If \(A = 1\), both sides are \(1\). If \(A = 0\), then \(\bar A = 1\) and both sides equal \(B\). The two sides agree in all four rows, so they are equal. In words: when \(A\) is already true, \(B\) does not matter; when \(A\) is false, the result is just \(B\).
An AND gate takes \(A\) and \(B\), a NOT gate takes \(C\), and an OR gate combines their two outputs into \(Y\). Write \(Y\), and find for how many of the eight input combinations \(Y = 0\). Then simplify \(Z = \overline{\overline{A \cdot B} \cdot \bar C}\).
\(Y = A \cdot B + \bar C\).
If \(C = 0\), then \(\bar C = 1\) and \(Y = 1\), whatever \(A\) and \(B\) are: four rows. If \(C = 1\), \(Y = A \cdot B\), which is \(1\) only for \(A = B = 1\). So \(Y = 0\) in three rows: \(001\), \(011\) and \(101\).
By De Morgan, \(Z = \overline{\overline{A \cdot B}} + \bar{\bar C} = A \cdot B + C\). The inverted NAND of two signals is the OR of the signals themselves.
Values used: logic \(0\) and \(1\) only.
Simplify \(\overline{A + \bar B}\).
Gates on changing inputs
In a real circuit the inputs change with time. A timing diagram draws each input as a wave that is high or low, and the output below them. To draw the output, cut the time axis at every moment when any input changes. Within each piece every input is steady, so the truth table gives the output directly.
In Fig 6.2 each second holds one row of the truth table. So AND is high only from \(3\) to \(4\,\text{s}\) and from \(7\) to \(8\,\text{s}\), in the rows \(11\). OR is low only from \(0\) to \(1\,\text{s}\) and from \(4\) to \(5\,\text{s}\). NAND and NOR are the upside-down copies of AND and OR. XOR is high from \(1\) to \(3\,\text{s}\) and from \(5\) to \(7\,\text{s}\), where the inputs differ.
Over \(8\,\text{s}\), input \(A\) is high from \(0\) to \(4\,\text{s}\), and input \(B\) is high from \(2\) to \(6\,\text{s}\). When is the output high for a NAND gate, a NOR gate and an XOR gate?
The edges at \(2\), \(4\) and \(6\,\text{s}\) cut the time into four pieces. In them \(AB\) is \(10\), \(11\), \(01\) and \(00\), in that order.
NAND is \(0\) only in the piece \(11\): it is high from \(0\) to \(2\,\text{s}\) and from \(4\) to \(8\,\text{s}\).
NOR is \(1\) only in the piece \(00\): it is high from \(6\) to \(8\,\text{s}\).
XOR is \(1\) where the inputs differ: from \(0\) to \(2\,\text{s}\) and from \(4\) to \(6\,\text{s}\).
Input \(A\) is high from \(1\) to \(3\,\text{s}\) and input \(B\) from \(2\) to \(5\,\text{s}\), over \(6\,\text{s}\). When is the output of a NOR gate high?
Why are NAND and NOR called universal gates?
Every logic function can be written using only NOT, AND and OR. Each of these three can be built from NAND gates alone, and also from NOR gates alone. So any logic circuit whatever can be built from one type of gate, NAND or NOR.
Augustus De Morgan was born in 1806 in Madurai, where his father served in the army of the East India Company. He went to England as a baby and became the first professor of mathematics at University College London. He worked on the logic of classes and wrote the rules that carry his name. His friend George Boole built the algebra of the previous lesson on work like his.
The computer that guided the Apollo spacecraft to the Moon in 1969 was built almost entirely from one kind of chip, each holding NOR gates. Its designers chose a universal gate so that only one chip had to be made and tested. Today the memory that stores the photos in a phone is called NAND flash. Its cells are wired in strings, like the inputs of a NAND gate.
- Breaking the bar without changing the sign.\(\overline{A + B} = \bar A \cdot \bar B\), not \(\bar A + \bar B\). Break the bar and change the sign together.
- Taking \(\overline{A \cdot B}\) to mean \(\bar A \cdot \bar B\).A long bar inverts the whole result. \(\overline{A \cdot B}\) is NAND, which equals \(\bar A + \bar B\).
- Reading a timing diagram only at the edges of one input.Cut the time axis at every edge of every input; the output can change at any of them.