Logic Gates and Circuits

Logic gates are the basic building blocks of digital circuits. Each gate takes one or more binary inputs (0 or 1) and produces a single binary output according to a fixed logical rule.

Six fundamental gates — you must know their truth tables and ANSI/IEEE symbols:

NOT (Inverter)

A	NOT A
0	1
1	0

Boolean: $\bar{A}$ or $\neg A$. Flips the input.

AND

A	B	A AND B
0	0	0
0	1	0
1	0	0
1	1	1

Boolean: $A\cdot B$. Output is 1 only when both inputs are 1.

OR

A	B	A OR B
0	0	0
0	1	1
1	0	1
1	1	1

Boolean: $A+B$. Output is 1 when at least one input is 1.

XOR (Exclusive OR)

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

Boolean: $A\oplus B$. Output is 1 when inputs are different.

NAND (NOT AND)

A	B	A NAND B
0	0	1
0	1	1
1	0	1
1	1	0

Boolean: $\overline{A\cdot B}$. AND followed by NOT. Output is 0 only when both inputs are 1.

NOR (NOT OR)

A	B	A NOR B
0	0	1
0	1	0
1	0	0
1	1	0

Boolean: $\overline{A+B}$. OR followed by NOT. Output is 1 only when both inputs are 0.

Logic gates are connected in circuits to implement more complex Boolean functions. Each gate's output can feed into another gate's input.

Example circuit — two gates in sequence:

A ──┐
    AND ──── NOT ──── Output X
B ──┘

Boolean expression: $X=\overline{A\cdot B}$ — this is a NAND.

Completing a truth table for a circuit:

Circuit: $X=(A\cdot B)+C$

A	B	C	A AND B	X = (A AND B) OR C
0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	0	1
1	0	0	0	0
1	0	1	0	1
1	1	0	1	1
1	1	1	1	1

Method: add intermediate columns for each gate's output, working left to right through the circuit. Never try to evaluate the whole expression in one column.

A half adder adds two single bits (A and B) and produces two outputs: a Sum bit and a Carry bit.

$\text{Sum}=A\oplus B\text{Carry}=A\cdot B$

A	B	Sum (A XOR B)	Carry (A AND B)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Circuit: one XOR gate (Sum) and one AND gate (Carry), both taking A and B as inputs.

Why "half"? It has no carry-in input. It can add two bits but cannot chain together to add multi-bit numbers without modification.

A full adder adds two bits (A and B) plus a carry-in ($C_{in}$) — allowing it to be chained for multi-bit addition. It produces a Sum and a carry-out ($C_{out}$).

A	B	$C_{in}$	Sum	$C_{out}$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

$\text{Sum}=A\oplus B\oplus C_{in}$ $C_{out}=(A\cdot B)+(C_{in}\cdot (A\oplus B))$

A full adder is built from two half adders and an OR gate. Chain $n$ full adders together to add two $n$-bit binary numbers.

A D-type flip-flop is a simple memory element — it stores one bit. Unlike combinational logic (which depends only on current inputs), a flip-flop has state that persists until changed.

Behaviour:

• Has a Data input (D) and a Clock input (CLK)
• Output Q changes only on a rising edge (low→high transition) of the clock signal
• At the rising clock edge: Q takes the value of D at that moment
• Between clock edges: Q holds its previous value regardless of D

CLK edge	D	Q (after edge)
Rising ↑	0	0
Rising ↑	1	1
No edge	any	Q unchanged

Why it matters: flip-flops are the fundamental building block of sequential circuits — registers, counters, memory cells. They allow circuits to remember and store information between clock cycles.

1. Confusing XOR and OR

OR outputs 1 when at least one input is 1 (including when both are 1). XOR outputs 1 only when inputs are different — so XOR(1,1) = 0, not 1. For the half adder Sum, it is XOR, not OR.

2. Forgetting intermediate columns in circuit truth tables

For a three-gate circuit, you need at least one intermediate column. Trying to evaluate the whole expression in one step leads to errors — show your working gate by gate.

3. Confusing NAND and NOR

NAND = AND then NOT (output is 0 only when all inputs are 1). NOR = OR then NOT (output is 1 only when all inputs are 0). Remember: NAND's all-ones input gives 0; NOR's all-zeros input gives 1.

4. Confusing the half adder's Sum and Carry gates

Sum = XOR (adds the bits modulo 2). Carry = AND (set only when 1+1 overflows). The exam regularly asks you to state the Boolean expressions — memorise both.