Boolean Algebra & Gates

Logic Gates: The Whole of Digital Built From Three Operations

A logic gate maps one or more binary inputs to a binary output by a fixed rule. There are only three operations that matter - AND, OR and NOT - and everything else is a combination of them, which is a genuinely surprising fact: every arithmetic unit, every processor, every memory controller reduces to those three. In practice NAND and NOR matter more than any of them, because either one alone can build all three, and because CMOS makes an inverting gate cheaper than a non-inverting one.

How it is built

• A truth table is the complete specification of a gate. With n inputs there are 2^n rows, and any assignment of outputs to those rows is a valid function - so there are 2^(2^n) possible n-input functions, sixteen of them for two inputs.
• AND outputs 1 only when every input is 1; OR outputs 1 when any input is 1; NOT inverts. NAND and NOR are those first two followed by an inversion, and each is functionally complete on its own.
• XOR outputs 1 when the inputs differ, which makes it the parity and difference detector. It is the gate behind adders, comparators, checksums and error detection, and it is the only common gate whose output changes for every input change.
• Functional completeness is why NAND matters industrially. Any circuit can be built from NAND alone, so a fabrication process only has to make one gate well - and in CMOS a NAND is four transistors while an AND is six, because the AND is a NAND with an inverter bolted on.
• Real gates are not instantaneous. Propagation delay is the time from an input edge to the output responding, and it differs between a rising and a falling output. Every timing constraint in a synchronous design is ultimately a sum of these delays.
• Fan-out is how many inputs one output can drive. Each input presents capacitance, so driving more of them slows the edge, and past the specified fan-out the timing no longer holds.

Design procedure

1. Write the truth table first. It is the specification, and going straight to gates without it is how a design ends up implementing something subtly different from what was wanted.
2. Identify whether the function is naturally a sum of products - true for a few input combinations - or a product of sums. That choice decides which implementation is smaller.
3. Convert to NAND-only or NOR-only if the target technology prefers it. Applying De Morgan's laws mechanically turns any AND-OR network into NAND-NAND.
4. Count the levels of logic between registers, because that count times the per-gate delay is what the clock period must accommodate.
5. Check fan-out on any signal that drives many loads, and insert a buffer tree rather than letting one gate drive twenty inputs.
6. Simulate the truth table exhaustively for small designs. With four inputs there are only sixteen cases, and checking all of them is faster than reasoning about which ones matter.

Key terms

Truth table

Complete specification: one row per input combination. 2^n rows for n inputs.

Functional completeness

A set of gates that can build any function. NAND alone is complete; so is NOR.

De Morgan's laws

NOT(A AND B) = NOT A OR NOT B, and the dual. How AND-OR becomes NAND-NAND.

XOR

Output 1 when inputs differ. The parity, difference and comparison gate.

Propagation delay

Input edge to output response. Different for rising and falling outputs.

Fan-out

How many inputs one output can drive before the edge rate fails.

Levels of logic

Gates in series between registers. Their delays add into the clock period.

Worked example

A two-input multiplexer - pick A when S is 0, B when S is 1 - has the expression Y = (A AND NOT S) OR (B AND S). That is three gate types and four gates. Applying De Morgan twice turns it into four NANDs, which in CMOS is sixteen transistors rather than twenty-two, and every one of them is the same cell the process already characterises. This is why a standard-cell library is mostly inverting gates, and why a schematic full of ANDs and ORs is not what ends up on the die.

Common pitfalls

Boolean Algebra: Making a Circuit Smaller Without Changing It

Boolean algebra is the set of rules for rewriting a logic expression into an equivalent one. That matters because the first expression anybody writes is almost never the smallest, and every gate removed is area, power and delay saved. The rules look like ordinary algebra in places and diverge sharply in others - there is no subtraction, no division, and both AND and OR distribute over each other, which is the one identity that catches people used to arithmetic.

How it is built

• The basic identities do most of the work: A AND 1 = A, A AND 0 = 0, A OR 0 = A, A OR 1 = 1, A AND A = A, A OR NOT A = 1. Idempotence and complementation together eliminate most redundancy.
• The distributive laws are dual: AND distributes over OR as in arithmetic, and OR also distributes over AND, which has no arithmetic equivalent and is the source of most simplification.
• De Morgan's laws convert between AND and OR through inversion. They are what allow any circuit to be rebuilt in NAND-only or NOR-only form, and they explain why an active-low signal's logic looks inverted.
• The consensus theorem removes a term that is already implied by two others - AB + A'C + BC reduces to AB + A'C. It is the rule a Karnaugh map applies visually, and it is easy to miss algebraically.
• Sum of products maps directly onto two levels of gates: AND then OR. Product of sums maps onto OR then AND. Both are two levels of logic, so the choice is about gate count rather than depth.
• Canonical forms - minterms and maxterms - give every function a unique expression. They are large and never used for implementation, but they make two expressions comparable, which is how equivalence is proved.

Design procedure

1. Write the function as a sum of products from the truth table, one term per row where the output is 1.
2. Apply complementation and idempotence first, since those eliminate whole terms rather than shortening them.
3. Look for pairs of terms differing in exactly one variable, and combine them - that variable drops out. This is the algebraic form of what a Karnaugh map does by adjacency.
4. Check for consensus terms, which are redundant and removable and are the ones algebra most often misses.
5. Compare the sum-of-products result against the product-of-sums form, built from the rows where the output is 0. One of the two is usually noticeably smaller.
6. Verify by exhaustive truth-table comparison. Simplification is exactly the kind of manipulation where a sign error produces a plausible wrong answer.

Key terms

Minterm

A product term true for exactly one input combination.

Maxterm

A sum term false for exactly one input combination.

Sum of products (SOP)

OR of ANDs. Two levels: AND then OR.

Product of sums (POS)

AND of ORs. Two levels: OR then AND.

De Morgan

NOT(A AND B) = NOT A OR NOT B. Converts between gate types.

Consensus theorem

AB + A'C + BC = AB + A'C. The redundant term algebra tends to miss.

Duality

Swap AND with OR and 0 with 1 and any identity remains true.

Worked example

F = A'BC + AB'C + ABC' + ABC looks like four terms and eleven gate inputs. Combining the last two on C gives AB, combining the first and last on A gives BC, and combining the second and last on B gives AC - so F = AB + BC + AC, the majority function. Three terms, six inputs, and the structure is now obvious: the output is 1 when at least two inputs are. The original expression contained that fact and did not show it, which is the real argument for simplification.

Common pitfalls

Karnaugh Maps: Simplification You Can See

A Karnaugh map is a truth table redrawn so that physically adjacent cells differ in exactly one variable. That single property turns algebraic simplification into a visual one: any two adjacent 1s can be combined and the variable that changes between them drops out. It works up to about four variables, beyond which the adjacency becomes impossible to see and the job belongs to a computer - but those four variables cover most hand design, and the intuition it builds outlasts the technique.

How it is built

• The rows and columns are labelled in Gray code - 00, 01, 11, 10 - rather than binary order. That is the whole trick: consecutive labels differ in one bit, so neighbouring cells differ in one variable.
• The map wraps around. The leftmost column is adjacent to the rightmost and the top row to the bottom, because their labels also differ in one bit. Groups spanning the edges are legal and easy to miss.
• Groups must be rectangular and a power of two in size: 1, 2, 4, 8. A group of size 2^k eliminates k variables, so bigger groups are always better.
• Groups may overlap, and often must. A cell already covered can be included again to make another group larger, and refusing to overlap produces a larger expression.
• Don't-care conditions - input combinations that cannot occur - can be treated as either 0 or 1, whichever makes groups bigger. They are free simplification and are routinely left unused.
• A prime implicant is a group that cannot be made larger. An essential prime implicant is one covering a 1 that no other group covers, and those must all be in the answer - which is where a minimal cover starts.

Design procedure

1. Fill the map from the truth table, using Gray-code ordering on both axes. Getting the ordering wrong makes every subsequent step wrong in a way that looks plausible.
2. Mark don't-cares distinctly rather than assigning them a value up front, so they stay available to enlarge groups.
3. Find all prime implicants: for each 1, make the largest legal group containing it, remembering wraparound.
4. Identify essential prime implicants - those covering a 1 that appears in no other prime implicant - and include all of them.
5. Cover any remaining 1s with the fewest additional prime implicants. This is a choice, and different valid answers of the same size exist.
6. Read the expression off the groups: each group contributes one product term made of the variables that do not change across it.

Key terms

Gray code ordering

00, 01, 11, 10. Adjacent labels differ in one bit, which is what makes the map work.

Wraparound

Edges are adjacent. Groups spanning them are legal and frequently missed.

Implicant

A group of 1s that can be combined into one product term.

Prime implicant

A group that cannot be enlarged.

Essential prime implicant

Covers a 1 that no other group covers. Must appear in the answer.

Don't care (X)

An input combination that cannot occur. Free to treat as whichever value helps.

Group size

Must be a power of two. A group of 2^k removes k variables.

Worked example

A BCD digit uses only 0 through 9, so inputs 1010 through 1111 are don't-cares - six of sixteen cells. A function detecting 'digit is 5 or more' with those cells forced to 0 needs four terms. Treating them as don't-cares lets the groups extend into the unused region, and the result collapses to A + BC + BD: three terms and a much smaller circuit that behaves identically for every input that can actually occur. Ignoring don't-cares is the single most common way to leave simplification on the table.

Common pitfalls

Boolean algebra: the rules that let you rewrite a circuit

Boolean algebra is the arithmetic of two-valued logic, and its practical use is that it lets you transform an expression into a different expression with identical behaviour. That is what makes minimisation possible: you are not guessing at a smaller circuit, you are applying identities that provably preserve the truth table. Every gate-level optimisation a synthesis tool performs is an application of these rules.

How it is built

• The three operators are AND (conjunction), OR (disjunction) and NOT (complement); everything else is built from them.
• The identities come in dual pairs: whatever holds for AND over OR holds for OR over AND with 0 and 1 exchanged.
• De Morgan's laws are the two that matter most in practice: NOT(A AND B) = NOT A OR NOT B, and NOT(A OR B) = NOT A AND NOT B.
• Absorption, A + AB = A, is where most of the reduction in a hand-minimised expression comes from.
• The consensus theorem, AB + A'C + BC = AB + A'C, removes a redundant term that is nevertheless needed to avoid a hazard - a case where the smallest circuit is not the correct one.

Design procedure

1. Write the truth table first. It is the specification; the expression is one of many implementations of it.
2. Extract a sum of products by taking one product term per row that outputs 1.
3. Apply absorption and combining wherever two terms differ in exactly one variable.
4. Use De Morgan's laws to convert the result into whatever gate family you actually have.
5. Check the reduced expression against the original truth table row by row before trusting it.

Key terms

Sum of products

An OR of ANDs. The canonical form taken directly from the rows where the output is 1.

Product of sums

An AND of ORs. The dual form, taken from the rows where the output is 0.

De Morgan's laws

The pair that lets you push a complement through a gate, exchanging AND for OR.

Absorption

A + AB = A. The identity behind most hand minimisation.

Consensus term

A redundant product that is logically unnecessary and can still be required to prevent a hazard.

Worked example

The same function, three ways:

  truth table                A B | Y
                             0 0 | 0
                             0 1 | 1
                             1 0 | 1
                             1 1 | 1

  canonical SOP    Y = A'B + AB' + AB
  absorption       Y = A'B + A(B' + B)
                     = A'B + A
                     = A + B                (absorption again)

  Three product terms and two gate levels became one OR gate. The
  truth table is unchanged, which is the only thing that had to be
  preserved.

And De Morgan turning that into the gates you actually stock:

  Y = A + B
    = NOT(NOT(A + B))
    = NOT(A' · B')          <- one NAND with inverted inputs,
                               or three NANDs if that is all you have

Common pitfalls

Functional completeness: why everything is built from NAND

A set of operators is functionally complete if every possible Boolean function can be expressed using only those operators. AND, OR and NOT together are complete, which is unsurprising. What matters industrially is that NAND alone is complete, and so is NOR alone - so an entire logic family can be manufactured from one repeated cell, which is exactly what happens in silicon.

How it is built

• NAND is complete: NOT A is A NAND A, AND is the NAND of a NAND, and OR follows from De Morgan.
• NOR is complete by the dual argument, and was the basis of several early logic families.
• AND and OR together are NOT complete: with no complement available, no combination of them produces an inverting function.
• XOR is not complete alone, but XOR with AND is - which is why arithmetic circuits are built from that pair.
• In CMOS, NAND is cheaper than AND: AND is literally a NAND followed by an inverter, so the inverting form is the primitive and the non-inverting one costs extra.

Design procedure

1. When targeting a specific family, convert the minimised expression into that family's primitive using De Morgan.
2. Prefer inverting gates in CMOS designs; a design expressed in NAND and NOR is usually smaller and faster than the same logic in AND and OR.
3. Count gate levels after conversion, since a NAND-only implementation of a wide OR can be deeper than expected.
4. Use a bubble-pushing diagram to convert visually rather than algebraically when the expression is large.
5. Check fan-in limits: a 6-input NAND may not exist in the library, forcing a tree and an extra level of delay.

Key terms

Functional completeness

The property that every Boolean function can be built from a given operator set.

NAND-only logic

An implementation using nothing but NAND gates. Possible for any function.

Bubble pushing

Moving inversion bubbles through a schematic using De Morgan, to convert between gate types visually.

Fan-in

The number of inputs a gate accepts. Physically limited, which forces wide functions into trees.

Universal gate

A gate that is functionally complete on its own: NAND or NOR.

Worked example

Building the full basis from NAND alone:

  NOT A     = A NAND A
  A AND B   = (A NAND B) NAND (A NAND B)
  A OR B    = (A NAND A) NAND (B NAND B)

Which is why the transistor count works out the way it does in CMOS:

  NAND2   4 transistors
  AND2    6 transistors   (a NAND2 plus an inverter)
  NOR2    4 transistors
  OR2     6 transistors

The inverting gates are the primitives and the non-inverting ones are built
from them, which is the opposite of how the logic is usually taught. The
transistor-level reason is in the CMOS section; here it is enough to know that
expressing a design in NAND and NOR generally makes it smaller.

Common pitfalls

Karnaugh maps, and what to do beyond four variables

A Karnaugh map is a truth table redrawn so that adjacent cells differ in exactly one variable, which turns algebraic combining into a visual operation: any rectangular group of adjacent 1s whose size is a power of two corresponds to a product term with the varying variables eliminated. It is the fastest hand method for up to four variables, awkward at five, and impractical beyond six - at which point the honest answer is to let a tool do it.

How it is built

• Rows and columns are labelled in Gray code order, so horizontally or vertically adjacent cells differ in one bit.
• The map wraps: the leftmost and rightmost columns are adjacent, as are the top and bottom rows.
• A group of 2^n adjacent 1s eliminates n variables from the product term covering it.
• Groups may overlap, and larger groups are always better because they eliminate more variables.
• Don't-care cells may be included in a group when it helps, or excluded when it does not - they cost nothing either way.

Design procedure

1. Fill the map from the truth table, placing each output in the cell its input combination names.
2. Circle the largest legal groups first, remembering the wraparound at every edge.
3. Continue until every 1 is covered by at least one group; overlapping is fine and often necessary.
4. Read each group as a product of the variables that do not change across it.
5. Above four variables, use the Quine-McCluskey method or a synthesis tool; the visual adjacency stops being visual.

Key terms

Gray code ordering

Labelling in which consecutive entries differ in one bit. What makes map adjacency mean algebraic adjacency.

Implicant

A product term that implies the function. A prime implicant is one that cannot be made larger.

Essential prime implicant

A prime implicant covering at least one 1 that no other prime implicant covers. It must appear in the solution.

Don't care

An input combination that cannot occur or whose output is irrelevant, usable as either value.

Quine-McCluskey

The tabular minimisation algorithm, mechanical rather than visual, and what tools actually implement.

Worked example

A four-variable map, and the wraparound people miss:

           CD
        00  01  11  10
  AB 00  1   0   0   1
     01  0   0   0   0
     11  0   0   0   0
     10  1   0   0   1

  The four corner cells are ALL adjacent to each other, because the
  map wraps both ways. They form one group of four:

     A=0,D=0 / A=0,D=0 ... varying A and C, fixed B'=1 and D'=1
     Y = B'D'

  Read as four separate 1s it is four product terms. Read as the
  group it actually is, it is one term with two literals.

And where don't-cares earn their keep:

  a BCD digit uses 0-9; inputs 1010 through 1111 cannot occur
  marking those six cells as X lets them join groups freely,
  frequently halving the term count for no cost at all

Common pitfalls

More in Digital Electronics

• Combinational BlocksEvery combinational building block in one place: multiplexers and demultiplexers, encoders and priority encoders, decoders and address decoding, and the arithmetic circuits from half adder through carry-lookahead. Each with a live explorer and the propagation-delay cost that decides which one you use.
• Sequential DesignStorage and state: latches against flip-flops, the D/T/JK families and how they convert, counters and clock dividers, shift registers and serial conversion, and the Moore/Mealy state machine encodings, with a live stepper for each.
• Timing, Hazards & MetastabilityWhat breaks when logic meets a clock: setup and hold windows, propagation delay and clock skew, static and dynamic hazards, metastability and the synchroniser chain, switch debouncing, and arbitration between requesters that can collide.
• Logic Levels & InterfacingThe electrical contract under the logic: threshold voltages and noise margins across TTL, CMOS and LVCMOS families, level shifting and open-drain interfacing, fan-out and drive strength, and where dynamic and static power actually goes.
• Digital ElectronicsGates, Boolean algebra, K-maps, muxes, encoders, decoders, flip-flops, arithmetic circuits, counters and debouncing.