Digital Electronics

ACSL digital electronics problems give you a circuit diagram made of logic gates and ask you to find the output, simplify the circuit, or determine which inputs produce a given output. This is Boolean algebra made physical - the same rules apply, but now you’re reading a diagram instead of an equation.

The gates

Every gate takes one or more binary inputs (0 or 1) and produces one binary output.

NOT gate (inverter)

One input, one output. Flips the bit.

Input ─▷○─ Output

AND gate

Output is 1 only when all inputs are 1.

A ─┐
   AND ── Output
B ─┘

OR gate

Output is 1 when any input is 1.

A ─┐
   OR ── Output
B ─┘

NAND gate (NOT AND)

The opposite of AND. Output is 0 only when all inputs are 1.

A ─┐
   AND─○── Output
B ─┘

The small circle (○) after the gate means “invert the output.”

Key fact: NAND is a universal gate - you can build any other gate using only NAND gates.

NOR gate (NOT OR)

The opposite of OR. Output is 1 only when all inputs are 0.

Key fact: NOR is also a universal gate.

XOR gate

Output is 1 when inputs differ.

XNOR gate (NOT XOR)

Output is 1 when inputs are the same.

Reading a circuit diagram

Work left to right (inputs to output), evaluating one gate at a time.

Example:

A ──┐
    AND──┐
B ──┘    OR── Output
C ───────┘

Step 1: AND gate takes A and B. Output $=AB$. Step 2: OR gate takes $AB$ and C. Output $=AB+C$.

If $A=1$, $B=0$, $C=1$:

• AND: $1\text{ AND }0=0$
• OR: $0\text{ OR }1=1$

Output = 1

Multi-layer circuits

For deeper circuits with several layers of gates, label intermediate wires.

Example:

A ──┐
    AND── W1 ──┐
B ──┘          OR── W3 ──▷○── Output
C ──┐          │
    OR── W2 ───┘
D ──┘

W1 = A AND B = $AB$ W2 = C OR D = $C+D$ W3 = W1 OR W2 = $AB+C+D$ Output = NOT W3 = $(AB+C+D{)}^{\prime }$

Speed tip: Label each gate’s output as you go. Don’t try to hold everything in your head.

From circuit to Boolean expression

Trace from inputs to output, writing the expression for each gate:

1. Start at the final output gate
2. Write what that gate does to its inputs
3. Replace each input with its sub-expression
4. Simplify using Boolean algebra laws

Example:

A ─▷○── NOT_A ──┐
                 AND── Output
B ───────────────┘

Output $=A^{\prime }B$

From Boolean expression to circuit

Go the other direction - break the expression into gates:

For $(A+B)C^{\prime }$:

1. OR gate: inputs A and B, output $=A+B$
2. NOT gate: input C, output $=C^{\prime }$
3. AND gate: inputs $(A+B)$ and $C^{\prime }$, output $=(A+B)C^{\prime }$

Truth table from circuit

For problems asking “find all inputs that produce output 1,” build a truth table.

Example: Circuit implements $AB+A^{\prime }C$

Output is 1 for inputs: (0,0,1), (0,1,1), (1,1,0), (1,1,1).

Reasoning backward (faster method)

For circuits with many inputs, truth tables get large (4 inputs = 16 rows). Instead, reason backward from the output gate.

Example: Find all inputs $(A,B,C)$ that make this circuit FALSE:

A ──┐
    NAND──┐
B ──┘      OR── Output
C ─────────┘

The circuit is $\overline{AB}+C$. For this to be FALSE, the OR gate must output 0, which means both its inputs must be 0:

• $C=0$ (one input to OR must be 0)
• $\overline{AB}=0$, which means $AB=1$, so $A=1$ and $B=1$

Only one answer: (1, 1, 0)

This took 3 lines of reasoning instead of an 8-row truth table.

NAND/NOR-only circuits

ACSL sometimes asks you to convert a circuit to use only NAND or only NOR gates. Key identities:

Using only NAND:

$\begin{array}{rl}& \text{NOT }A=A\text{ NAND }A\\ & A\text{ AND }B=(A\text{ NAND }B)\text{ NAND }(A\text{ NAND }B)\\ & A\text{ OR }B=(A\text{ NAND }A)\text{ NAND }(B\text{ NAND }B)\end{array}$

Using only NOR:

$\begin{array}{rl}& \text{NOT }A=A\text{ NOR }A\\ & A\text{ OR }B=(A\text{ NOR }B)\text{ NOR }(A\text{ NOR }B)\\ & A\text{ AND }B=(A\text{ NOR }A)\text{ NOR }(B\text{ NOR }B)\end{array}$

Shortcut: To convert, first write the Boolean expression, apply DeMorgan’s to get it into the right form, then map to gates.

Circuit simplification

If a circuit is complex, write the Boolean expression, simplify using Boolean algebra (see the Boolean Algebra lesson), then redraw.

Example: A circuit implements $A^{\prime }B+A{B}^{\prime }+AB$.

Simplify:

$\begin{array}{rlrl}& A^{\prime }B+A{B}^{\prime }+AB& & \\ & =A^{\prime }B+A(B^{\prime }+B)& & \text{(factor }A\text{)}\\ & =A^{\prime }B+A& & \text{(complement: }{B}^{\prime }+B=1\text{)}\\ & =A+A^{\prime }B& & \\ & =A+B& & \text{(absorption)}\end{array}$

The simplified circuit is just an OR gate with inputs A and B.

Half-adder and full-adder

These come up occasionally.

Half-adder adds two 1-bit numbers:

• Sum $=A\oplus B$
• Carry $=AB$

Full-adder adds two 1-bit numbers plus a carry-in:

• Sum $=A\oplus B\oplus C_{in}$
• Carry $=AB+C_{in}(A\oplus B)$

Common mistakes

1. Forgetting the inversion bubble. The small circle on NAND/NOR/NOT gates flips the output. Missing it changes everything.
2. Wrong gate read. AND vs OR confusion under time pressure. Double-check each gate symbol.
3. Evaluating gates in wrong order. Always work from inputs toward output, layer by layer.
4. DeMorgan’s in circuits. A NAND gate is $\text{NOT}(AB)=A^{\prime }+B^{\prime }$, not $A^{\prime }{B}^{\prime }$.
5. Assuming left-to-right is top-to-bottom. Read the actual wire connections, not the visual position.

Contest strategy

• Label every intermediate wire with its value (when evaluating) or expression (when deriving)
• For “find the output” problems: plug in values left to right, gate by gate (~30 seconds)
• For “write the expression” problems: trace from output back to inputs (~45 seconds)
• For “simplify” problems: get the expression first, then use Boolean algebra laws (~60-90 seconds)
• For truth table problems with 2 variables, just enumerate all 4 cases. With 3 variables, all 8 cases.
• Typical time: 45-90 seconds depending on problem type