t = 0 gate delays stable

Truth table & Boolean expressions

Click a cell: 0 → 1 → X (don't care)

Logic levels and gates

Digital circuits represent information with two voltage levels: high (logic 1, e.g. near 3.3 V or 5 V) and low (logic 0, near 0 V). A gate computes a Boolean function of its inputs. In the editor, high wires glow green and low wires are dark.

Notation used on this page: $AB$ means A AND B, $A+B$ means A OR B (not ordinary addition), and a bar, $\overline{A}$, means NOT A. A truth table lists the output for every combination of inputs.

Boolean algebra

Write AND as a product $AB$, OR as a sum $A+B$, NOT as $\overline{A}$ and XOR as $A\oplus B$. For any variables:

LawAND formOR form
Identity$A\cdot 1 = A$$A + 0 = A$
Null (annihilator)$A\cdot 0 = 0$$A + 1 = 1$
Idempotent$AA = A$$A + A = A$
Complement$A\overline{A} = 0$$A + \overline{A} = 1$
Involution$\overline{\overline{A}} = A$
Commutative$AB = BA$$A+B = B+A$
Associative$(AB)C = A(BC)$$(A+B)+C = A+(B+C)$
Distributive$A(B+C) = AB + AC$$A + BC = (A+B)(A+C)$
Absorption$A(A+B) = A$$A + AB = A$
De Morgan$\overline{AB} = \overline{A} + \overline{B}$$\overline{A+B} = \overline{A}\,\overline{B}$

De Morgan's laws explain why a NAND is an OR with inverted inputs, and why NAND (or NOR) alone is functionally complete: $\overline{A} = \overline{AA}$, $AB = \overline{\overline{AB}}$, $A+B = \overline{\overline{A}\,\overline{B}}$.

Sum of products and Karnaugh maps

Any function can be written as the OR of its minterms, the input rows where it equals 1: $F = \sum m(\dots)$. Adjacent minterms that differ in one variable merge: $AB + A\overline{B} = A$. A Karnaugh map orders rows and columns in Gray code (00, 01, 11, 10) so logically adjacent cells are physically adjacent, including wrap-around at the edges. Group 1s in rectangles of 1, 2, 4, 8 or 16 cells; each group of $2^k$ cells eliminates $k$ variables. The largest possible groups are prime implicants; the minimal SOP picks the fewest of them that cover every 1. Don't-care cells (X) may be included in a group if it helps, but need not be covered. The lab uses the Quine–McCluskey method, which finds exactly the same prime implicants algorithmically.

Arithmetic: adders

$$\begin{gathered}\text{Half adder: } S = A\oplus B,\quad C = AB\\ \text{Full adder: } S = A\oplus B\oplus C_{in}\\ C_{out} = AB + C_{in}(A\oplus B)\end{gathered}$$

A $n$-bit ripple-carry adder chains $n$ full adders. The carry must ripple through every stage, and each stage adds about 2 gate delays to the carry path, so the worst-case delay grows as $O(n)$, roughly $2n$ gate delays. Carry-lookahead adders compute carries in parallel to reach $O(\log n)$.

Memory: latches and flip-flops

Feedback creates memory. Two cross-coupled NOR gates form an SR latch: $Q = \overline{R + \overline{Q}}$, $\overline{Q} = \overline{S + Q}$. With $S=R=0$ the latch holds its state; $S=1$ sets $Q=1$; $R=1$ resets it. $S=R=1$ forces both outputs to 0, which is not a valid memory state, and releasing both together causes a race. A gated D latch removes the forbidden input by deriving $S = D\cdot EN$ and $R = \overline{D}\cdot EN$; it is transparent while $EN = 1$. An edge-triggered D flip-flop samples $D$ only at the rising clock edge: $Q_{next} = D$. A JK flip-flop holds (00), resets (01), sets (10) or toggles (11) at each edge:

$$Q_{next} = J\overline{Q} + \overline{K}Q$$

A toggling flip-flop divides the clock frequency by 2, so $n$ cascaded toggles count from 0 to $2^n-1$.

About the simulator. It is event-driven: when a signal changes, every gate it feeds is re-evaluated and its new output is scheduled one gate delay later (blocks take 2). Delays differ by a few per cent between gates, and a pending change is cancelled if the input changes back first (an inertial delay). This is how real gates resolve races such as the power-up of an SR latch. Timing is in abstract gate delays, not nanoseconds, and analogue effects such as metastability are not modelled.

1. Simplify with a K-map

$F(A,B,C,D) = \sum m(0, 2, 5, 7, 8, 10, 13, 15)$. Press Example on the Karnaugh map tab to load it.

  1. The four corners $m_0, m_2, m_8, m_{10}$ are adjacent through wrap-around. In all four, $B=0$ and $D=0$, so they form $\overline{B}\,\overline{D}$.
  2. The centre square $m_5, m_7, m_{13}, m_{15}$ has $B=1, D=1$: the term $BD$.
  3. Both groups are essential, so $F = \overline{B}\,\overline{D} + BD = \overline{B \oplus D}$: an XNOR of $B$ and $D$. Eight minterms of 4 literals each (32 literals) collapse to 4 literals.

In hardware, eight 4-input AND gates and an 8-input OR shrink to a single XNOR gate, and $A$ and $C$ turn out not to matter at all. Build circuit from minimal SOP on the Karnaugh map tab gives the same two terms.

2. One row of a full adder

Load the Full adder preset and set $A=1$, $B=1$, $C_{in}=1$.

  • The full adder uses $S = A\oplus B\oplus C_{in}$ and $C_{out} = AB + C_{in}(A\oplus B)$. First XOR: $A\oplus B = 0$. Second XOR: $0 \oplus 1 = 1$, so $S = 1$.
  • $AB = 1$ and $C_{in}(A\oplus B) = 0$, so $C_{out} = 1 + 0 = 1$.

Check: $1+1+1 = 3 = 11_2$, so carry 1 and sum 1. The highlighted row of the truth table matches.

3. Four-bit addition

On the 4-bit ripple-carry adder, set $A = 0110_2 = 6$ (A2 and A1 on) and $B = 0111_2 = 7$ (B2, B1, B0 on).

BitABCinSCout
001010
111001
211111
300110

$S = 1101_2 = 13$ and the hex display shows d. Turn on slow motion and flip B0 to watch the carry ripple from stage 0 to stage 3.

4. XOR from four NANDs

Let $N = \overline{AB}$ (gate 1). Gates 2 and 3 give $\overline{A N} = \overline{A\,\overline{AB}}$ and $\overline{B N}$. Gate 4 NANDs these, and De Morgan's law $\overline{\overline{X}\cdot\overline{Y}} = X + Y$ gives

$$Y = \overline{\overline{AN}\cdot\overline{BN}} = AN + BN = (A+B)\,\overline{AB} = A\overline{B} + \overline{A}B = A\oplus B.$$

That is the NAND-only XOR challenge: 4 gates, the minimum possible.

5. Counter frequency

The 4-bit counter preset has a 2 Hz clock. Every JK flip-flop has $J=K=1$, so it toggles on each rising edge at its clock input. Stage 0 is clocked by the 2 Hz clock; each later stage is clocked by the previous stage's $\overline{Q}$, so it toggles when the previous $Q$ falls from 1 to 0, which makes the count go up (clocking from $Q$ instead would count down). Each stage halves the frequency: $Q_0$ runs at 1 Hz, $Q_1$ at 0.5 Hz, $Q_2$ at 0.25 Hz, $Q_3$ at 0.125 Hz. A full cycle of 16 counts (0 → F and back to 0) takes $16 / 2\,\text{Hz} = 8$ s, and the hex display changes every 0.5 s. This divide-by-two chain is how a digital watch turns a 32 768 Hz crystal into one tick per second: $2^{15} = 32\,768$, so 15 stages are needed.

Press Start to load a challenge into the builder. Inputs and outputs are placed for you and only the allowed parts are enabled. Your circuit is checked against the required truth table automatically as you wire it; press Check on the banner at any time to see how many rows are still wrong.

    Guided experiments

    1. Load SR latch from NOR gates. Pulse S on and off, then R. Note that the LEDs remember the last pulse. Now turn S and R on together and release them both: which state does the latch fall into? Expect both outputs to be 0 while S and R are both on, and then a race on release: the gate that switches first wins, so the final state depends on tiny differences in gate delay. This is why S = R = 1 is the forbidden input.
    2. Load Gated D latch. With EN = 1, toggle D: Q follows (transparent). Set EN = 0 and toggle D: Q holds.
    3. Load the 4-bit ripple-carry adder and set A = 1111, B = 0000. Turn on slow motion at 2 gate delays per second, then switch B0 on and count the delays until Cout lights. Expect about 8 gate delays on the t readout (each full adder block takes about 2), and every sum bit to flash briefly before settling to 0000; adding bits would lengthen the wait in proportion.
    4. Load the Ring oscillator. Why does a loop of three inverters never settle, while a loop of two (a latch) does? Expect each output to flip every 3 gate delays, a period of about 6: an odd number of inversions has no consistent state, while an even number does.
    5. Build any 3-input function, then open it in the Karnaugh map tab and press Build circuit from minimal SOP. Compare the gate count with your design. Expect the minimal SOP to need no more AND/OR gates than any other two-level design, though a design using XOR gates can sometimes be smaller still.

    Binary, hexadecimal and decimal

    A binary number $b_{n-1}\dots b_1 b_0$ has the value $\sum_i b_i 2^i$. Four bits make one hexadecimal digit (0–9, A–F), which is why the hex display takes four inputs weighted 1, 2, 4, 8.

    $$1101_2 = 1\cdot8 + 1\cdot4 + 0\cdot2 + 1\cdot1 = 13_{10} = \mathrm{D}_{16}$$

    Two's complement

    Signed integers are stored in two's complement: the most significant bit has weight $-2^{n-1}$. To negate, invert every bit and add 1. In 8 bits, $-5 = \overline{00000101} + 1 = 11111011_2$. The same adder hardware then performs both addition and subtraction ($A - B = A + \overline{B} + 1$, with $C_{in} = 1$).

    Click the bits above to toggle them.