Digital Systems

A. Number systems

Number Systems and Codes

Convert between binary, octal, and hex; represent signed numbers with two's complement; do binary arithmetic with overflow detection; and read BCD, Gray, and ASCII codes.

Unlocks with an access pass — one-time payment, no auto-renew. View passes

Pass holders

B. Boolean logic

Boolean Algebra and Logic Gates

Master the Boolean axioms, De Morgan's theorems, the seven core gates, and the SOP/POS forms that turn any truth table into a circuit.

Boolean algebra is the grammar of every digital circuit you will see on the FE: combinational logic, decoders, multiplexers, and the next-state equations of sequential machines all reduce to manipulating expressions in two-valued algebra. The handbook (Logic Operations and Boolean Algebra) supplies the three primitive operators, the gate truth tables, and De Morgan's theorems — but the points come from fluency: simplifying an expression by hand, reading a truth table into a sum-of-products form, and knowing that one universal gate can build the whole circuit. This concept builds that fluency from the axioms up so the manipulations become automatic.

The three primitive operations

All of Boolean logic is built from AND (written

\cdot

or by juxtaposition), OR (written

+

), and NOT (an overbar or prime). AND returns

1

only when every input is

1

; OR returns

1

when any input is

1

; NOT inverts. These are not ordinary arithmetic:

1+1 = 1

, not

2

. The handbook lists their truth tables together with XOR, and from these three you can express any logic function whatsoever.

A\cdot B,\qquad A + B,\qquad \overline{A}

Axioms and single-variable theorems

A small set of identities collapses almost every exam expression. Each comes in a dual pair: swap AND with OR and swap

0

with

1

, and a true identity stays true. The identity laws (

A\cdot 1 = A

,

A+0 = A

), null laws (

A\cdot 0 = 0

,

A+1 = 1

), idempotent laws (

A\cdot A = A

,

A+A = A

), and complement laws (

A\cdot \overline{A}=0

,

A+\overline{A}=1

) are the workhorses. Add involution,

\overline{\overline{A}} = A

, and you can reduce most expressions without a truth table.

A + 0 = A,\quad A\cdot 1 = A,\quad A + \overline{A} = 1,\quad A\cdot\overline{A} = 0

Algebraic laws and absorption

Boolean AND and OR are commutative and associative, and each distributes over the other — including the form

A + B\cdot C = (A+B)(A+C)

that has no arithmetic analog. The high-value simplifiers are absorption,

A + A\cdot B = A

, and its companion

A + \overline{A}\cdot B = A + B

, which delete redundant terms on sight. The consensus theorem,

A\cdot B + \overline{A}\cdot C + B\cdot C = A\cdot B + \overline{A}\cdot C

, removes the redundant

B\cdot C

term whenever you see a variable and its complement across two products. Recognizing these patterns is faster than any truth table.

A + AB = A,\qquad A + \overline{A}B = A + B,\qquad AB + \overline{A}C + BC = AB + \overline{A}C

De Morgan's theorems

De Morgan's theorems are the bridge between AND/OR and their inverted gates, and they are the most-tested identity in this area. The complement of a product is the sum of the complements, and the complement of a sum is the product of the complements. Practically, to invert any expression you flip every AND to OR (and vice versa) and complement each variable. These two relations are exactly what define the NAND and NOR gates the handbook draws.

\overline{A\cdot B} = \overline{A} + \overline{B},\qquad \overline{A + B} = \overline{A}\cdot\overline{B}

The seven gates and XOR

The exam's gate vocabulary is AND, OR, NOT (the inverter), NAND, NOR, XOR, and XNOR. NAND and NOR are AND/OR followed by inversion — the bubble on the symbol's output. XOR outputs

1

when its inputs differ; XNOR (its complement) outputs

1

when they match, making it an equality detector. XOR is also modulo-2 addition, which is why it appears in adders, parity, and Gray-code logic. Keep the bubble convention in mind: a bubble means 'invert,' on either an input or an output.

A \oplus B = A\overline{B} + \overline{A}B,\qquad \overline{A \oplus B} = AB + \overline{A}\,\overline{B}

Truth tables, SOP, and POS

Any function is fully specified by its truth table. To build a sum-of-products (SOP) expression, write one minterm — a product in which every variable appears, complemented where its input is

0

— for each row that outputs

1

, then OR them. For a product-of-sums (POS), write one maxterm — a sum complemented where the input is

1

— for each row that outputs

0

, then AND them. SOP is canonical when it lists every minterm; the same function in POS lists every maxterm. Both describe the identical function; you choose whichever yields the cheaper circuit after simplification.

F = \sum m(\dots) \;\text{(OR of minterms)},\qquad F = \prod M(\dots)\;\text{(AND of maxterms)}

Universal gates

NAND and NOR are each universal: any Boolean function can be built from copies of one of them alone, which is why real logic families are dominated by NAND. The trick is to synthesize the three primitives. A NAND with both inputs tied together is an inverter,

\overline{A\cdot A} = \overline{A}

; two NANDs make an AND (NAND then invert); and De Morgan turns the OR into NANDs of inverted inputs. Recognizing that a two-level AND-OR (SOP) network maps directly to a two-level all-NAND network is a frequent exam shortcut.

\overline{A\cdot A} = \overline{A},\qquad A + B = \overline{\overline{A}\cdot\overline{B}} = \overline{A}\ \text{NAND}\ \overline{B}

Exam strategy

Reach for absorption (

A+AB=A

),

A+\overline{A}B = A+B

, and consensus first — they erase terms instantly. When you must invert a whole expression, apply De Morgan mechanically: swap every AND/OR and complement each literal, working from the outermost bar inward. Build SOP from the

1

-rows and POS from the

0

-rows, and remember the two are equal functions. If a problem restricts you to NAND-only or NOR-only gates, convert your SOP to all-NAND (or POS to all-NOR) by inserting double inversions and applying De Morgan — do not redesign from scratch.

Key equations

Identity laws

A + 0 = A,\quad A\cdot 1 = A

OR with 0 and AND with 1 leave a variable unchanged. The starting point for most simplifications.

Null (dominance) laws

A + 1 = 1,\quad A\cdot 0 = 0

OR with 1 forces 1; AND with 0 forces 0. Use to collapse a term to a constant.

Complement laws

A + \overline{A} = 1,\quad A\cdot\overline{A} = 0

A variable ORed with its complement is 1; ANDed with its complement is 0. Key to eliminating variables.

Idempotent and involution

A + A = A,\quad A\cdot A = A,\quad \overline{\overline{A}} = A

Repeated operands collapse; double inversion cancels. Lets you duplicate or remove terms freely.

Distributive laws

A(B+C) = AB + AC,\quad A + BC = (A+B)(A+C)

Both AND-over-OR and OR-over-AND hold. The second form has no arithmetic analog — used to convert between SOP and POS.

Absorption

A + AB = A,\quad A(A+B) = A

Deletes a term subsumed by a simpler one. The single most useful simplification on the exam.

Redundancy / simplification

A + \overline{A}B = A + B,\quad A(\overline{A}+B) = AB

Removes a complemented literal that adds nothing. Easy to miss; check whenever a variable and its complement coexist.

Consensus theorem

AB + \overline{A}C + BC = AB + \overline{A}C

The consensus term $BC$ is redundant when $A$ appears true in one product and complemented in another. Drop it.

De Morgan's theorems

\overline{A\cdot B} = \overline{A} + \overline{B},\quad \overline{A+B} = \overline{A}\cdot\overline{B}

Complement of a product/sum. Use to invert expressions and to map between AND/OR and NAND/NOR.

XOR and XNOR

A\oplus B = A\overline{B} + \overline{A}B,\quad \overline{A\oplus B} = AB + \overline{A}\,\overline{B}

XOR is true when inputs differ (mod-2 sum); XNOR is the equality/coincidence detector.

Canonical SOP / POS

F = \textstyle\sum m_i = \prod M_j

Sum of minterms for the 1-rows of the truth table, or product of maxterms for the 0-rows. Both specify the same function.

NAND as inverter

\overline{A\cdot A} = \overline{A}

Tie both NAND inputs together to make a NOT. Foundation of NAND-universal logic.

Worked examples

Algebraic simplification with consensus

Problem. Simplify $F = AB + \overline{A}C + BC$ to minimum sum-of-products and confirm by truth table.

Solution. The three-term expression has

A

true in the first product and complemented in the second, with the remaining variables

B

and

C

forming the third product — exactly the consensus pattern. By the consensus theorem the term

BC

is redundant:

F = AB + \overline{A}C

. To confirm, build both truth tables over

A,B,C

. In the original the three products cover

AB

at rows

\{6,7\}

,

\overline{A}C

at rows

\{1,3\}

, and

BC

at rows

\{3,7\}

, whose union is the 1-row set

\{1,3,6,7\}

. The reduced form

AB+\overline{A}C

gives

AB

at

\{6,7\}

and

\overline{A}C

at

\{1,3\}

, i.e. rows

\{1,3,6,7\}

— identical. (Independently verified by exhaustive check.) Answer:

\mathbf{F = AB + \overline{A}C}

.

AB + \overline{A}C + BC = AB + \overline{A}C

Truth table to SOP, then NAND realization

Problem. A function $F(A,B,C)$ is $1$ exactly for the input rows where an odd number of inputs are $1$ : minterms $1, 2, 4, 7$ . Write the canonical SOP and identify the function.

Solution. Write one minterm per 1-row, complementing each variable whose input is

0

: row 1 (

001

)

= \overline{A}\,\overline{B}C

; row 2 (

010

)

= \overline{A}B\overline{C}

; row 4 (

100

)

= A\overline{B}\,\overline{C}

; row 7 (

111

)

= ABC

. OR them:

F = \overline{A}\,\overline{B}C + \overline{A}B\overline{C} + A\overline{B}\,\overline{C} + ABC

. This is the odd-parity function, which equals

A\oplus B\oplus C

(verified by exhaustive truth-table check: the XOR of three inputs is 1 exactly at minterms 1, 2, 4, 7). To realize the SOP with NAND-only logic, feed each product term through a NAND (AND-then-invert) and combine them with a final NAND; by De Morgan the two-level AND-OR maps directly to two levels of NAND. Answer:

\mathbf{F = A\oplus B\oplus C}

(3-input odd parity).

F = \sum m(1,2,4,7) = A\oplus B\oplus C

Applying De Morgan to invert an expression

Problem. Find the complement $\overline{F}$ of $F = A\overline{B} + \overline{A}C$ and express it in product-of-sums form.

Solution. Apply De Morgan to the whole sum:

\overline{F} = \overline{A\overline{B} + \overline{A}C} = \overline{(A\overline{B})}\cdot\overline{(\overline{A}C)}

. Invert each product into a sum (De Morgan again, with involution on the doubly-barred literals):

\overline{A\overline{B}} = \overline{A} + B

and

\overline{\overline{A}C} = A + \overline{C}

. Therefore

\overline{F} = (\overline{A}+B)(A+\overline{C})

, already in POS form. Sanity check at

A{=}1,B{=}0,C{=}1

:

F = 1\cdot1 + 0 = 1

, so

\overline{F}

should be

0

; the POS gives

(\,0+0)(1+0) = 0\cdot1 = 0

. Consistent. Answer:

\mathbf{\overline{F} = (\overline{A}+B)(A+\overline{C})}

.

\overline{A\overline{B} + \overline{A}C} = (\overline{A}+B)(A+\overline{C})

Common pitfalls

•Treating $+$ as arithmetic addition. In Boolean algebra $1+1 = 1$ ; there is no carry. Likewise $A+A = A$ , not $2A$ .
•Applying De Morgan to only one operator. You must swap EVERY AND/OR and complement EVERY literal under the bar — a half-applied De Morgan is the most common wrong answer.
•Building SOP from the 0-rows or POS from the 1-rows. SOP minterms come from output-1 rows; POS maxterms come from output-0 rows.
•Writing a maxterm with the wrong polarity. In a maxterm, complement the variable where its input is 1 (the opposite of the minterm rule).
•Forgetting the OR-distributive law $A+BC = (A+B)(A+C)$ . It is valid in Boolean algebra even though it looks wrong by arithmetic intuition.
•Assuming a NAND with one input is an inverter. Tie BOTH inputs together (or tie the unused input HIGH) to get $\overline{A}$ ; a floating input is not defined.
•Confusing XOR with OR. XOR is 0 when both inputs are 1; only OR is 1 there. XNOR, not XOR, is the equality detector.

References

NCEES FE Reference Handbook — Electrical and Computer Engineering: Logic Operations and Boolean Algebra
NCEES FE Reference Handbook — Electrical and Computer Engineering: De Morgan's Theorems — Gives the NAND/NOR-defining forms used here.
IEEE Std 91/91a — Graphic Symbols for Logic Functions — Standard gate symbols and the bubble (inversion) convention.
Mano & Ciletti, Digital Design — Boolean axioms, canonical forms, and universal-gate synthesis.

D. Logic minimization

Logic Minimization with K-Maps

Use Karnaugh maps to read a minimal SOP or POS directly off a truth table — grouping prime implicants, exploiting don't-cares, and knowing when to reach for Quine-McCluskey.

Unlocks with an access pass — one-time payment, no auto-renew. View passes

Pass holders

E. Flip-flops and counters

Flip-Flops, Counters, and Timing

Latches versus flip-flops, the SR/D/JK/T characteristic and excitation tables, ripple versus synchronous counters, and the setup/hold timing that bounds clock speed.

Unlocks with an access pass — one-time payment, no auto-renew. View passes

Pass holders

G. State machine design

State Machines and Programmable Logic

Mealy versus Moore machines, building a state diagram and table, encoding states and next-state logic, and the PLA/PAL/PLD/FPGA fabrics that implement them.

Unlocks with an access pass — one-time payment, no auto-renew. View passes

Pass holders