Transistors, logic gates and Boolean algebra

The bottom floor of a computer is the transistor. Gates are built from transistors, circuits from gates. On this page you see the two lowest levels (devices and logic circuits). The question types from this part on the midterm are well known: read a circuit diagram and produce the truth table, write an expression from a table, simplify an expression with Boolean algebra, take its complement with DeMorgan, write it using only NAND.

The MOS transistor

A MOS transistor is an electrical switch. It has three terminals: gate, source and drain. The voltage applied to the gate decides whether current passes between the other two terminals.

In CMOS (complementary MOS) circuits both types are used together in every gate. The p-types connect the output to +V (logical 1), the n-types to GND (logical 0). In a correctly designed CMOS gate, for every input exactly one of these two paths is open.

CMOS NOT, NAND, NOR

NOT (inverter): one p, one n. Input 0 → p conducts → output 1. Input 1 → n conducts → output 0.

NAND: the p-types are in parallel (between +V and the output), the n-types are in series (between the output and GND). For the output to be 0, the whole series path must conduct, that is A = B = 1. In every other case one of the parallel p’s pulls the output to 1.

NOR: the exact opposite. The p-types are in series, the n-types in parallel. The output is 1 only when A = B = 0.

AND and OR gates are not built directly in CMOS. AND = NAND + NOT, OR = NOR + NOT. That is why the “cheapest” gates in circuits are NAND and NOR.

TIP · Series = AND, parallel = OR. With switches in series, all of them must be closed for current to pass (AND). In parallel, one is enough (OR). Since the n-types of a NAND are in series, it says “if A AND B, connect to GND”.

Logic gates

In diagrams: the D shape with a flat back is AND, the curved-back shape with a pointed tip is OR, anything with a small circle (bubble) at its tip is the complement of that gate (NAND, NOR), and a triangle ending in a circle is NOT. XOR carries a second curve behind the OR shape.

Notation: $A'$ (or $\overline{A}$) = NOT A, writing side by side $AB$ = AND, $+$ = OR, $\oplus$ = XOR. Order of operations: NOT > AND > OR.

Truth table → expression

Minterm and SOP

The table of a function with $n$ inputs has $2^n$ rows. The rows are numbered from 0 to $2^n - 1$ (ABC = 101 → row 5).

A minterm is the AND term that is 1 in a single row. The rule: if the bit is 1 the letter itself, if the bit is 0 its complement. $m_5 = AB'C$.

The canonical SOP (sum of products) form of a function: write the minterm of every row where F = 1 and OR them all. The short notation is $\Sigma m(\ldots)$.

A B C | F
0 0 0 | 1   ← m0 = A'B'C'
0 0 1 | 1   ← m1 = A'B'C
0 1 0 | 0
0 1 1 | 0
1 0 0 | 0
1 0 1 | 1   ← m5 = AB'C
1 1 0 | 0
1 1 1 | 0

F = Σm(0,1,5) = A'B'C' + A'B'C + AB'C

This expression turns directly into a circuit: one AND gate for each term, a single OR gate at the end. This means: every truth table can be built with AND, OR and NOT. This property is called logical completeness.

Maxterm and ΠM

A maxterm is the OR term that is 0 in a single row. The rule is the opposite of the minterm: bit 0 → the letter itself, bit 1 → its complement. $M_5 = (A' + B + C')$.

$F = \Sigma m(\text{rows with F}=1) = \Pi M(\text{rows with F}=0) \qquad F' = \Sigma m(\text{rows with F}=0)$

In the example above, $F = \Pi M(2,3,4,6,7)$ and $F' = \Sigma m(2,3,4,6,7)$.

PITFALL · mixing up the letter rule of minterms and maxterms. m5 = 101 → $AB'C$ (plain if 1). M5 = 101 → $(A' + B + C')$ (complemented if 1). The opposite operation, the opposite rule.

Boolean algebra

One more that is used a lot: $X + X'Y = X + Y$.

Simplification recipe

1. Find two minterms that differ in only one variable.
2. Factor out the common factor: $AB'C' + AB'C = AB'(C' + C)$.
3. $C' + C = 1$, leaving $AB'$.
4. If you need to use a term in two pairings, copy it first ($X = X + X$).
5. Check the result against the table: which rows does each term cover?

Worked example: the $F = A'B'C' + A'B'C + AB'C$ above.

F = A'B'C' + A'B'C + AB'C
  = A'B'C' + A'B'C + A'B'C + AB'C      idempotent: A'B'C was copied
  = A'B'(C' + C) + B'C(A' + A)         distributive
  = A'B'·1 + B'C·1                     complement
  = A'B' + B'C                         identity
check: A'B' → 000, 001 (m0, m1) · B'C → 001, 101 (m1, m5) ✓

Taking the complement with DeMorgan

If $F = A'B' + B'C$:

F' = (A'B' + B'C)'
   = (A'B')' · (B'C)'          DeMorgan (complement of a sum)
   = (A + B) · (B + C')        DeMorgan (complement of a product), involution
   = AB + AC' + BB + BC'       distributive
   = AB + AC' + B + BC'        idempotent BB = B
   = B + AC'                   absorption: B + AB = B, B + BC' = B

Check: the rows where $F'$ = 1: B = 1 (2, 3, 6, 7) and AC’ (4, 6). The union is {2, 3, 4, 6, 7}. Combined with the set {0, 1, 5} of F it gives {0..7}, with no common element.

Circuit reading

In the exam a diagram is given and you are asked: recognize each gate, name the intermediate outputs, fill in the table, write the expression, simplify, answer the “which operation?” question.

Example: Gate 1 is a NOR (inputs A, B), its output is X. Gate 2 is an AND (inputs B, C), its output is Y. Gate 3 is an OR (inputs X, Y), its output is F.

A B C | X=(A+B)' | Y=BC | F=X+Y
0 0 0 |    1     |  0   |  1
0 0 1 |    1     |  0   |  1
0 1 0 |    0     |  0   |  0
0 1 1 |    0     |  1   |  1
1 0 0 |    0     |  0   |  0
1 0 1 |    0     |  0   |  0
1 1 0 |    0     |  0   |  0
1 1 1 |    0     |  1   |  1

F = (A+B)' + BC = A'B' + BC = Σm(0, 1, 3, 7)

Recognize the patterns: $A'B + AB'$ is XOR, $A'B' + AB$ is XNOR, $S'A + SB$ is a 2-to-1 mux, $AB + AC + BC$ is majority.

Using only NAND (or NOR)

NAND alone is complete (logically complete): AND, OR and NOT can all be written with NAND.

Recipe: write the SOP expression, complement it twice, apply DeMorgan to the inner one.

$F = AB + CD = ((AB + CD)')' = ((AB)' \cdot (CD)')'$

Result: make every gate in the AND-OR circuit a NAND, and the circuit stays the same. For NOR the same idea works with the POS (product of sums) expression.

Common mistakes