Logic Gates: NOT, AND, OR

Two levels, 0 and 1

A signal that can take any value, like the output of a microphone, is an analogue signal. A digital signal takes only two values. In the circuits of this lesson a voltage near \(0\,\text{V}\) is the level \(0\), or low. A voltage near \(5\,\text{V}\) is the level \(1\), or high. The exact voltage does not matter, only which of the two ranges it lies in. That makes digital circuits very tolerant of noise.

With two levels, numbers are written in binary, with the digits \(0\) and \(1\) only. Each place is worth twice the place to its right: \(1, 2, 4, 8, \dots\). So \(7\) is \(111\), \(5\) is \(101\), and \(12\) is \(1100\). A calculator works on numbers in this form.

Each input has two possible levels. So a gate with two inputs has \(2 \times 2 = 4\) input combinations, one with three inputs has \(8\), and one with \(n\) inputs has \(2^n\). Write them in the order of counting in binary, \(00, 01, 10, 11\), so that none is missed.

The three basic gates

The NOT gate has one input and gives the opposite level: \(0\) becomes \(1\), and \(1\) becomes \(0\). Its output is written \(Y = \bar A\), read "A bar" or "not A". The AND gate gives \(1\) only when all its inputs are \(1\); its output is written \(Y = A \cdot B\). The OR gate gives \(1\) when any input is \(1\), or more than one; its output is written \(Y = A + B\).

The symbols in Fig 5.1 are the standard ones. NOT is a triangle with a small circle, the inversion bubble, at its output. AND has a flat back and a round front. OR has a curved back and a pointed front. The expressions \(A \cdot B\) and \(A + B\) are the notation of Boolean algebra. The dot is read "and", and the plus is read "or"; they are not ordinary multiplication and addition.

The three truth tables fit side by side: \[ \begin{array}{cc|c|c|c} A & B & \bar A & A \cdot B & A + B \\ \hline 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 1 \end{array} \] Read down each column. AND has a single \(1\), in the last row. OR has a single \(0\), in the first row.

Series and parallel switches

Two switches and a lamp show the same two rules. Let a closed switch be \(1\) and a lit lamp be \(1\). With the switches in series, current flows only if both are closed: the circuit is an AND gate. With the switches in parallel, current flows if either is closed: the circuit is an OR gate.

A few rules of Boolean algebra

Since every quantity is \(0\) or \(1\), a few rules follow straight from the tables. Check each against the truth tables: \[ A + 0 = A, \quad A + 1 = 1, \quad A \cdot 0 = 0, \quad A \cdot 1 = A \] \[ A + A = A, \quad A \cdot A = A, \quad A + \bar A = 1, \quad A \cdot \bar A = 0, \quad \bar{\bar A} = A \] The last three say three things. A statement and its opposite are never both true. One of them always is. Inverting twice changes nothing.

Gates made of diodes

A gate is a circuit, and the simplest ones need only diodes and a resistor. Take the inputs as \(0\,\text{V}\) or \(5\,\text{V}\), and ignore the small drop across a conducting diode. In the diode OR gate, each input feeds the anode of a diode, and the cathodes meet at the output \(Y\). A resistor joins \(Y\) to \(0\,\text{V}\).

In the OR gate of Fig 5.2, suppose \(A\) is at \(5\,\text{V}\) and \(B\) at \(0\,\text{V}\). The upper diode has \(5\,\text{V}\) on its anode, so it conducts and lifts \(Y\) to \(5\,\text{V}\). The lower diode now has \(0\,\text{V}\) on its anode and \(5\,\text{V}\) on its cathode. It is reverse-biased and off. If both inputs are at \(0\,\text{V}\), neither diode conducts, and the resistor holds \(Y\) at \(0\,\text{V}\). One high input is enough: an OR gate.

Turn both diodes round and join the resistor to \(+5\,\text{V}\) instead. Now a low input makes its diode conduct and pulls \(Y\) down to \(0\,\text{V}\). Only when both inputs are at \(5\,\text{V}\) does no diode conduct, so the resistor holds \(Y\) at \(5\,\text{V}\). That is the AND gate on the right of the figure.

A NOT gate from a transistor

Diodes alone cannot invert, but a transistor can. The input drives the base through a resistor, and a resistor joins the collector to the \(5\,\text{V}\) supply; the output is taken at the collector. A high input sends current into the base and turns the transistor fully on, pulling the collector nearly to \(0\,\text{V}\). A low input leaves it off, so no current flows in the collector resistor and the collector stays at \(5\,\text{V}\). Lesson 4 follows this switch in detail.

Adding two binary digits

Now return to the calculator. Adding two one-digit binary numbers \(A\) and \(B\) gives a sum digit \(S\) and a carry digit \(C\). In binary, \(1 + 1 = 10\): sum \(0\), carry \(1\). The four cases are: \[ \begin{array}{cc|cc} A & B & C & S \\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array} \] The carry column is AND: \(C = A \cdot B\). The sum column is \(1\) only when the inputs differ.

The sum is written \(S = A \cdot \bar B + \bar A \cdot B\): "A and not B, or not A and B". It is built from two NOT gates, two AND gates and one OR gate. This combination is so useful that it has its own name and symbol, the XOR gate, exclusive OR, written \(S = A \oplus B\). An XOR gate and an AND gate together make a half adder. A calculator chains such adders, one for each binary place, and \(7 + 5\) becomes \(111 + 101 = 1100\), twelve.