Logic circuits

Wiring gates into circuits

A logic circuit is a network of gates that carries out a Boolean expression.
You must move freely between four forms: problem → expression → circuit → truth table.
Let's practise each direction.

Draw one gate per operator and wire them up.
For $X = (A \cdot B) + \overline{C}$: an AND on $A, B$; a NOT on $C$; an OR combining the two results.

Practice

For $X = (A \cdot B) + \overline{C}$ with $A=1, B=1, C=1$, what is $X$?

For $n$ inputs there are $2^n$ rows — list every input combination.
For each row, work out each gate's output in turn until you reach the final output.
e.g. 2 inputs → 4 rows; 3 inputs → 8 rows.

Practice

How many rows does a truth table have for a circuit with 3 inputs?

Practice

How many rows for 4 inputs?

For each row that outputs 1, write an AND of the inputs (put NOT on any input that is 0 in that row).
OR those terms together.
Example: a table that is 1 only on $(A{=}0,B{=}1)$ and $(A{=}1,B{=}0)$ gives $\overline{A}B + A\overline{B}$ — which is $A \text{ XOR } B$.

Practice

In the sum-of-products method, for each row whose output is 1 you write:

Turn the English into Boolean first:
"A and B" → $A \cdot B$ · "A or B (or both)" → $A + B$
"exactly one of A and B" → $A \text{ XOR } B$
"neither A nor B" → $A \text{ NOR } B$ · "not both" → $A \text{ NAND } B$

Practice

"Output 1 when exactly one of A and B is 1" is which gate?

Practice

"Output 1 only when neither A nor B is 1" is which gate?

Key idea

a circuit = one gate per operator, wired up (expression ↔ circuit)
a truth table has $2^n$ rows for $n$ inputs
sum of products: OR together an AND-term for each output-1 row (NOT the 0 inputs)
problem → Boolean: exactly one = XOR, neither = NOR, not both = NAND