Gates
The building blocks of all digital logic. Derive each gate from its truth table and build it from transistors (NOT, NAND, AND, NOR, OR, XOR), then minimise logic with Karnaugh maps.
NOTThe inverterThe simplest gate: output is always the opposite of the input. Two transistors, one PMOS and one NMOS, working in perfect opposition.NANDThe universal gate0 only when both inputs are 1. Every other gate can be built from it.ANDNAND, then invertedOutput is 1 only when both inputs are 1. Built by canceling the inversion of a NAND gate with a NOT gate from your library.NORNAND's mirror imageOutput is 1 only when both inputs are 0. Series PMOS pulls up, parallel NMOS pulls down: the exact complement of NAND's topology.ORNOR, then invertedOutput is 1 when at least one input is 1. Built by canceling the inversion of a NOR gate, mirroring exactly how AND is built from NAND.XORThe odd one outOutput is 1 exactly when the inputs differ. No single CMOS gate does this, so you combine NAND gates. XOR is also the core of binary addition.XNOR and the equality comparatorThe gate that tests for samenessXNOR outputs 1 exactly when its two inputs are equal, making it a one-bit equality detector. AND a row of XNORs together and you get a comparator that tells you whether two whole numbers are equal.Reading a multi-gate schematicFrom one gate to a blockA block is made by feeding one gate's output into another's input; reading a schematic means tracing each net from its source to the gates that consume it.Canonical forms: minterms and maxtermsThe two standard ways to write any truth table as gatesEvery truth table has two canonical expressions: a sum of minterms (OR the 1-rows) and a product of maxterms (AND the 0-rows). Each maps directly to a two-level gate circuit, and either becomes an all-NAND or all-NOR build.From a truth table to a real circuitThe recipe that turns a spec into gatesAny truth table becomes a circuit by writing one AND term per output-1 row and OR-ing those terms, connecting what it should do to what to build.The multiplexer as a universal logic elementAny function, read straight out of a muxA 2^n-to-1 multiplexer with the n input variables on its select lines can implement any n-variable boolean function: tie each data input to that row's truth-table output and the mux becomes a direct lookup table. Shannon expansion does the same job with a mux half the size.NOR is universal tooEvery gate from NOR aloneLike NAND, a NOR gate alone can build every other gate and therefore any logic function, and some historic machines (including the Apollo Guidance Computer) were built entirely from NOR.Karnaugh mapsReading the simplest circuit off a tableA Karnaugh map rearranges a truth table so adjacent cells differ in one bit. Grouping the 1s by sight gives the minimal AND-OR expression, fewer gates than the raw table.Hazards and glitchesThe momentary wrong answer a correct circuit can still produceUnequal gate delays can make a logically correct circuit flash the wrong value for an instant during an input change. A static-1 hazard is fixed by adding the redundant consensus term that bridges two non-overlapping K-map groups.The consensus theoremThe redundant term that kills a glitchThe consensus theorem says A·B + A'·C + B·C = A·B + A'·C, so the third term is logically redundant, yet adding it back is exactly the extra gate that removes a static-1 hazard.Quine-McCluskey minimizationThe algorithm that minimizes when a K-map cannotQuine-McCluskey is a tabular, exhaustive method for minimizing a boolean function. It combines minterms that differ in one bit to find every prime implicant, then uses a prime-implicant chart to pick a minimum cover, working where Karnaugh maps run out past five or six variables.