Skip to content
Tutorials Center
My learning

Topics

Lesson 57 of 57 ยท Practice and Review

Digital Logic Cheat Sheet

A one-page digital logic reference: gate truth tables, Boolean laws, flip-flop equations, adder and counter formulas, code tables and timing rules, all verified.

This page collects the facts you reach for most while designing or revising digital circuits. It is a summary, not a lesson: each section links to the lesson that explains the idea. Two small programs at the end check the gate table, the laws and the flip-flop equations by brute force, so you can trust what is written here.

What is on this page

Gates and laws Truth tables and Boolean identities.
Flip-flops Characteristic and excitation tables.
Arithmetic Adders, lookahead, comparators.
Timing and codes Clock limits, counters, number codes.
1 / 2

Gates

A B AND OR NAND NOR XOR XNOR
0 0 0 0 1 1 0 1
0 1 0 1 1 0 1 0
1 0 0 1 1 0 1 0
1 1 1 1 0 0 0 1

NOT flips its input. XOR is 1 when the number of 1s is odd (parity); XNOR is 1 when the inputs are equal. NAND and NOR are universal. See AND, OR and NOT, NAND, NOR, XOR and XNOR and Universal Gates.

Boolean algebra

Law AND form OR form
Identity Aยท1 = A A + 0 = A
Null Aยท0 = 0 A + 1 = 1
Idempotent AยทA = A A + A = A
Complement AยทA' = 0 A + A' = 1
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 (AB)' = A' + B' (A + B)' = A'B'
Useful extras A(A' + B) = AB A + A'B = A + B
Consensus (A+B)(A'+C)(B+C) = (A+B)(A'+C) AB + A'C + BC = AB + A'C

Every law has a dual: swap AND with OR and 0 with 1. Double complement: (A')' = A. XOR: A โŠ• B = AB' + A'B, and A โŠ• 0 = A, A โŠ• 1 = A', A โŠ• A = 0. More in Boolean Algebra Laws and De Morgan's Theorems.

Canonical forms. A minterm is an AND of all variables (each true or complemented) that is 1 on exactly one row; ฮฃm(...) lists the rows where the function is 1. A maxterm is an OR that is 0 on exactly one row; ฮ M(...) lists the rows where the function is 0. The minterm number i and the maxterm number i are complements of each other. See Sum of Products and Product of Sums.

K-map rules. Group 1s (or 0s for POS) in rectangles of size 1, 2, 4, 8 or 16. Groups may wrap around the edges. Use the largest groups, the fewest groups, and cover every 1. Don't-cares may join a group but need not be covered. A group of 2^k cells removes k variables. See Karnaugh Maps.

Combinational building blocks

Block Formula
Half adder S = A โŠ• B, C = AยทB
Full adder S = A โŠ• B โŠ• Cin, Cout = AB + Cin(A โŠ• B)
Generate / propagate g = AB, p = A โŠ• B
Lookahead carries c1 = g0 + p0c0, c2 = g1 + p1g0 + p1p0c0
Subtraction A - B = A + B' + 1
Signed overflow V = c(n-1) โŠ• c(n) (carry into the top bit XOR carry out)
1-bit comparator A>B = AยทB', A=B = A โŠ™ B, A<B = A'ยทB
2^n : 1 mux Y = ฮฃ (minterm_i ยท D_i), n select lines
n : 2^n decoder output i is minterm i, with an optional enable
Parity even parity bit = XOR of all data bits
Hamming code r parity bits where 2^r >= m + r + 1 for m data bits

See adders, fast adders, subtractors and comparators, multiplexers, decoders and encoders and parity and error detection.

Flip-flops

Type Characteristic equation Behavior
D Q+ = D copies D at the clock edge
T Q+ = T โŠ• Q toggles when T = 1
SR Q+ = S + R'Q (with SR = 0) set, reset, hold; S = R = 1 forbidden
JK Q+ = JQ' + K'Q hold, reset, set, toggle

Excitation table (what inputs give a wanted transition; X is a don't-care):

Q โ†’ Q+ D T S R J K
0 โ†’ 0 0 0 0 X 0 X
0 โ†’ 1 1 1 1 0 1 X
1 โ†’ 0 0 1 0 1 X 1
1 โ†’ 1 1 0 X 0 X 0

Conversions: to build a T flip-flop from a D flip-flop use D = T โŠ• Q; to build a D flip-flop from a T flip-flop use T = D โŠ• Q. From a JK flip-flop, tie J = K = T for T behavior, or use J = D, K = D' for D behavior. A latch is level-sensitive, a flip-flop is edge-triggered. See SR latches, D flip-flops and JK and T flip-flops.

Registers, counters and state machines

Item Rule
Binary counter n flip-flops, 2^n states, counts 0 to 2^n - 1
Mod-N counter โŒˆlog2 NโŒ‰ flip-flops, f_out = f_clk / N
Ring counter n flip-flops, n states (one hot bit circulates)
Johnson counter n flip-flops, 2n states (inverted feedback)
Ripple counter delay up to n ยท tpd to settle
Moore machine output = f(state)
Mealy machine output = f(state, input)
State encoding n flip-flops encode at most 2^n states; one-hot uses 1 flip-flop per state

See Registers and Shift Registers, Counters and Finite State Machines.

Timing

Check Formula
Setup (clock period) T >= tcq + tlogic(max) + tsu + skew
Maximum frequency fmax = 1 / T_min
Hold tcq(min) + tlogic(min) >= thold + skew
Synchronizer MTBF e^(tr/ฯ„) / (T0 ยท f_clk ยท f_data)

Setup is fixed by slowing the clock; hold is fixed by adding delay and is independent of the period. See Timing, Clock Skew and Metastability.

Number systems and codes

Decimal Binary / BCD Hex Gray Excess-3
0 0000 0 0000 0011
1 0001 1 0001 0100
2 0010 2 0011 0101
3 0011 3 0010 0110
4 0100 4 0110 0111
5 0101 5 0111 1000
6 0110 6 0101 1001
7 0111 7 0100 1010
8 1000 8 1100 1011
9 1001 9 1101 1100
  • Gray from binary: g = b ^ (b >> 1).
  • Two's complement: negate by inverting and adding one; the n-bit range is -2^(n-1) to 2^(n-1) - 1.
  • Sign extension: copy the sign bit into the new upper bits.
  • Conversions: one hex digit is 4 bits; one octal digit is 3 bits.
  • BCD addition: add as binary, then add 6 to any digit that exceeds 9 or produced a carry.

See Binary, Octal and Hexadecimal, Signed Numbers and BCD, Gray Code and ASCII.

Verify the tables

The first program regenerates the gate table and brute-force checks eight laws from the table above.

Python Gate table and Boolean laws, checked

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second one checks the flip-flop equations against their behavior, the adder and lookahead formulas against ripple addition, and prints the counter and Hamming rules.

Python Flip-flop, adder and counter formulas, checked

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which flip-flop equation is Q+ = JยทQ' + K'ยทQ?

    J sets, K resets, both together toggle, neither holds. That behavior gives the JK equation.
  2. 2. How many flip-flops are needed for a Johnson counter with 10 states?

    A Johnson counter has 2n states for n flip-flops, so 10 states need 5.
  3. 3. A 4-input K-map group of 8 cells removes how many variables?

    A group of 2^k cells removes k variables, and 8 = 2^3, so three variables disappear and the term has one literal.
  4. 4. Which formula describes the hold requirement?

    Hold compares the shortest path with the hold time plus skew. It does not involve the clock period.

Summary

  • Gates: NAND and NOR are universal, XOR is parity, XNOR is equality.
  • Laws come in AND/OR dual pairs; De Morgan, absorption and consensus do most of the simplification work.
  • Flip-flop equations: D: Q+ = D, T: Q+ = T โŠ• Q, SR: Q+ = S + R'Q, JK: Q+ = JQ' + K'Q.
  • Full adder: S = A โŠ• B โŠ• Cin, Cout = AB + Cin(A โŠ• B); lookahead uses g = AB and p = A โŠ• B.
  • Setup limits the clock period; hold does not depend on it.

This is the end of the Digital Logic course. To keep going, build something with these ideas: revisit Designing an ALU and the tiny CPU, or start again from Digital vs Analog Signals.