Logic gates and truth tables

Yes or no

A smoke alarm asks one question: is there smoke? A lift asks two: is the door closed, and has a floor been chosen? The answers are yes or no, which we write as $1$ and $0$. A circuit that takes such answers and gives an answer is a logic gate. A computer is a very large collection of gates.

In a digital circuit a voltage has only two meanings. A high voltage, such as $5$ V, is $1$. A low voltage, near $0$ V, is $0$. A small noise does not change the meaning, so digital signals are copied and stored without loss. The lesson on the transistor switch showed how one gate, the NOT gate, is made.

The basic gates

A truth table lists the output $Y$ for every combination of the inputs. With $n$ inputs there are $2^n$ rows.

• NOT has one input. $Y = \overline{A}$. The output is the opposite of the input.
• OR gives $1$ if at least one input is $1$. $Y = A + B$.
• AND gives $1$ only if both inputs are $1$. $Y = A \cdot B$.
• NAND is AND followed by NOT. $Y = \overline{A \cdot B}$. It gives $0$ only when both inputs are $1$.
• NOR is OR followed by NOT. $Y = \overline{A + B}$. It gives $1$ only when both inputs are $0$.
• XOR (exclusive OR) gives $1$ when the two inputs are different. $Y = A \oplus B$. XNOR is the opposite: it gives $1$ when they are the same.

Read the four rows in the order $(A, B) = (0,0)$, $(0,1)$, $(1,0)$, $(1,1)$. The outputs are:

• OR: $0, 1, 1, 1$
• AND: $0, 0, 0, 1$
• NAND: $1, 1, 1, 0$
• NOR: $1, 0, 0, 0$
• XOR: $0, 1, 1, 0$

Notation. The signs are $+$ for OR, a dot for AND and a bar over a letter for NOT. Do not read $+$ as addition: $1 + 1 = 1$ in this algebra. The shapes of the symbols above are the ones in most Indian textbooks. Some courses abroad use boxes instead (the IEC symbols), with $\geq 1$ for OR, $\&$ for AND and a small circle for NOT. The syllabus of the latest NCERT book has OR, AND, NOT, NAND and NOR. XOR is common in other courses, so we include it.

Rules for working with gates

De Morgan's rules let us change AND into OR:

To find the output of a circuit, work from the inputs towards the output, and write the value on every wire. To find the whole truth table, do it for every row.

Universal gates

A universal gate can make every other gate. NAND is universal.

• NOT: tie the two inputs of a NAND gate together. $\overline{A \cdot A} = \overline{A}$.
• AND: a NAND gate followed by a NOT made from a NAND gate. Two gates.
• OR: a NOT on each input, then a NAND gate. $\overline{\overline{A} \cdot \overline{B}} = A + B$ by De Morgan's rule. Three gates.

NOR is universal too, by the same pattern. This matters in practice: a factory can make one kind of gate in millions and build any circuit from it.

A worked example. A circuit has three gates. Gate 1 is an AND gate for $A$ and $B$. Gate 2 is a NOT gate for $C$. Gate 3 is an OR gate for the outputs of gates 1 and 2. Find $Y$ for $A = 1$, $B = 0$, $C = 1$.

1. Gate 1. $A \cdot B = 1 \cdot 0 = 0$.
2. Gate 2. $\overline{C} = \overline{1} = 0$.
3. Gate 3. $0 + 0 = 0$. So $Y = 0$.

For all eight rows, $Y = A \cdot B + \overline{C}$ is $0$ only when $C = 1$ and $A \cdot B = 0$.

Choose gate 5 (XOR). Which rows have a big circle? Then choose gate 6 (XNOR). Do the big circles and the small circles swap places?

Practise with new numbers

Try it in Python

The program builds NOT, AND, OR, NOR and XOR from NAND gates only, and compares each one with its definition for all four rows.

Common mistakes

• Reading $+$ as addition. In logic, $1 + 1 = 1$.
• Mixing up NAND and NOR. NAND is $0$ only for $1, 1$. NOR is $1$ only for $0, 0$.
• Forgetting the bubble. A small circle at the output of a symbol means NOT.
• Calling XOR the same as OR. The two differ for $1, 1$. OR gives $1$, XOR gives $0$.
• Counting the rows wrongly. $n$ inputs give $2^n$ rows, not $2n$.
• Mixing up the two forms of De Morgan's rule. The bar over the whole expression changes AND into OR and OR into AND.

Remember these

• NOT: $\overline{A}$. OR: $A + B$. AND: $A \cdot B$. NAND: $\overline{A \cdot B}$. NOR: $\overline{A + B}$. XOR: $A \oplus B$.
• $n$ inputs give $2^n$ rows. XOR gives $1$ when its inputs differ, XNOR when they are the same.
• De Morgan: $\overline{A + B} = \overline{A} \cdot \overline{B}$ and $\overline{A \cdot B} = \overline{A} + \overline{B}$.
• NAND and NOR are universal gates.

References

• NCERT Physics Class 12, Semiconductor Electronics, the section on digital electronics and logic gates.
• Horowitz and Hill, The Art of Electronics, third edition, Chapter 10, Digital logic.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. Which gate gives $1$ only when both inputs are $0$?

2. What is the output of an XOR gate for $A = 1$ and $B = 1$?

3. How many NAND gates are needed to make a NOT gate? To make an AND gate?

4. Use De Morgan's rule to write $\overline{A + B}$ with ANDs and NOTs.