In Number Systems & Binary Codes we learned to write any data as bits. Now we need circuits that do something with those bits: compare them, combine them, add them. The smallest such circuit is the logic gate. Everything from a calculator to a GPU is built by connecting millions or billions of these simple blocks.
A logic gate is an electronic circuit with one or more binary inputs and one binary output, where the output is a fixed Boolean function of the present inputs.
A gate has no memory: give it the same inputs and (after a tiny propagation delay) you always get the same output. So every gate is a tiny combinational circuit. In this chapter we study the seven standard gates (NOT, AND, OR, NAND, NOR, XOR, XNOR) plus the buffer, their symbols, truth tables and expressions, and learn to analyse a small circuit and read a timing diagram.
Notation Used in This Tutorial
Operation | Written as | Also seen as | Read as |
|---|---|---|---|
NOT | A′ | Ā (bar over A), ¬A, ~A | "A bar", "A complement", "not A" |
AND | A·B or AB | A ∧ B, A & B | "A and B" |
OR | A + B | A ∨ B, A | B | "A or B" |
XOR | A ⊕ B | A ^ B | "A ex-or B" |
XNOR | A ⊙ B or (A ⊕ B)′ | A ≡ B | "A ex-nor B" |
The "+" here is not arithmetic addition: in Boolean logic 1 + 1 = 1. Precedence is NOT first, then AND, then OR, just like powers, multiplication and addition in ordinary algebra. So AB + C′ means (A·B) + (C′).
The Basic Gates
NOT Gate (Inverter)
One input; the output is the opposite of the input. The small circle (the bubble) on any symbol means inversion.
┌──╲
A ────┤ ╲o──── Y = A′ A | Y
│ ╱ --+--
└──╱ 0 | 1
1 | 0
Two inverters in series give back the original signal: (A′)′ = A. Without the bubble, the triangle is a buffer (Y = A). A buffer does not change the logic value; it is used to boost the drive strength so one output can feed many inputs, or to add a small delay.
AND Gate
The output is 1 only when all inputs are 1. Think of two switches in series: the bulb lights only if both are closed.
┌────╮
A ────┤ ╲
│ )──── Y = A·B A B | Y
B ────┤ ╱ ----+--
└────╯ 0 0 | 0
0 1 | 0
1 0 | 0
1 1 | 1
OR Gate
The output is 1 when at least one input is 1. Think of two switches in parallel: either one lights the bulb.
─────╮
A ────╲ ╲
) )──── Y = A + B A B | Y
B ────╱ ╱ ----+--
─────╯ 0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1
This is "inclusive OR": the case where both inputs are 1 also gives 1.
NAND Gate (NOT-AND)
An AND followed by a NOT. The output is 0 only when all inputs are 1.
┌────╮
A ────┤ ╲
│ )o──── Y = (A·B)′ A B | Y
B ────┤ ╱ ----+--
└────╯ 0 0 | 1
0 1 | 1
1 0 | 1
1 1 | 0
NOR Gate (NOT-OR)
An OR followed by a NOT. The output is 1 only when all inputs are 0.
─────╮
A ────╲ ╲
) )o──── Y = (A + B)′ A B | Y
B ────╱ ╱ ----+--
─────╯ 0 0 | 1
0 1 | 0
1 0 | 0
1 1 | 0
NAND and NOR are special: each one alone can build every other gate. They are called universal gates and get their own chapter, Universal Gates: NAND & NOR.
XOR Gate (Exclusive-OR)
The output is 1 when the inputs are different. Think of a staircase light with a switch at the top and bottom: flipping either switch changes the light.
─────╮
A ───╲╲ ╲
)) )──── Y = A ⊕ B = A′B + AB′ A B | Y
B ───╱╱ ╱ ----+--
─────╯ 0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0
XNOR Gate (Exclusive-NOR, Equivalence)
The output is 1 when the inputs are equal. It is a 1-bit equality checker, the heart of the comparators we build in Magnitude Comparators.
─────╮
A ───╲╲ ╲
)) )o──── Y = (A ⊕ B)′ = AB + A′B′ A B | Y
B ───╱╱ ╱ ----+--
─────╯ 0 0 | 1
0 1 | 0
1 0 | 0
1 1 | 1
All Gates at a Glance
Gate | Expression | Output is 1 when ... | Output is 0 when ... | IEEE rectangular symbol mark |
|---|---|---|---|---|
NOT | A′ | input is 0 | input is 1 | 1 (with output bubble/triangle) |
AND | AB | all inputs are 1 | any input is 0 | & |
OR | A + B | any input is 1 | all inputs are 0 | ≥1 |
NAND | (AB)′ | any input is 0 | all inputs are 1 | & with bubble |
NOR | (A + B)′ | all inputs are 0 | any input is 1 | ≥1 with bubble |
XOR | A ⊕ B | odd number of 1s | even number of 1s | =1 |
XNOR | (A ⊕ B)′ | inputs equal (2-input) | inputs differ | =1 with bubble (or =) |
The curved symbols shown above are the "distinctive shape" symbols that most Indian textbooks and exams use. IEEE/IEC standards also define the rectangular style, where a box contains the mark in the last column.
Gates with More Than Two Inputs
AND, OR, NAND, NOR and XOR extend naturally to n inputs. A gate with n inputs has a truth table of 2n rows.
n-input AND: 1 only when all n inputs are 1 (only 1 row out of 2n).
n-input OR: 0 only when all n inputs are 0.
n-input NAND = (A·B·C ...)′ and n-input NOR = (A + B + C ...)′.
n-input XOR = A ⊕ B ⊕ C ...: 1 when an odd number of inputs are 1. This makes it the natural parity generator.
AND, OR and XOR are associative, so a 3-input AND can be built as two 2-input ANDs: ABC = (AB)C. NAND and NOR are not associative: ((AB)′C)′ is not the same as (ABC)′. We prove this in Universal Gates: NAND & NOR.
A Note on Multi-Input XNOR
For two inputs, XNOR means "equal". For more inputs, there are two possible meanings, and they differ: a chain of 2-input XNOR gates, or the complement of the n-input XOR. For three inputs, the chain XNOR(XNOR(A, B), C) actually equals A ⊕ B ⊕ C, not its complement (the two inversions cancel). In this tutorial, an "n-input XNOR" means (A ⊕ B ⊕ C ...)′, which is 1 for an even number of 1s.
Gates as Controlled Switches (Enable/Disable)
A very useful way to think about a 2-input gate: treat one input as data and the other as control. This viewpoint explains how multiplexers, decoders and clock gating work.
Gate | Control = 0 | Control = 1 | Use |
|---|---|---|---|
AND | Output forced to 0 (blocked) | Output = data (passes) | Enable/gate a signal |
OR | Output = data (passes) | Output forced to 1 | Force a signal HIGH |
NAND | Output forced to 1 | Output = data′ | Gated inverter |
NOR | Output = data′ | Output forced to 0 | Gated inverter |
XOR | Output = data | Output = data′ | Controlled inverter (used in adder/subtractor circuits) |
These come straight from the identities A·0 = 0, A·1 = A, A + 0 = A, A + 1 = 1, A ⊕ 0 = A and A ⊕ 1 = A′, which we list formally in Boolean Algebra Laws.
Useful XOR Properties
A ⊕ 0 = A A ⊕ 1 = A′
A ⊕ A = 0 A ⊕ A′ = 1
A ⊕ B = B ⊕ A (commutative)
(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C) (associative)
If A ⊕ B = C then A ⊕ C = B (XOR "undoes" itself: basis of simple encryption and RAID parity)
(A ⊕ B)′ = A′ ⊕ B = A ⊕ B′
Analysing a Gate Circuit
To analyse a circuit, label every internal wire, write the expression at each gate's output working from inputs to output, and then fill in the truth table.
Example 1: Find the Output Expression and Truth Table
A ───────────────┐
AND ── P = AB ──────┐
B ──┬────────────┘ OR ──── F
│ │
└── NOT ── B′ ──┐ │
AND ── Q = B′C ──┘
C ──────────────────┘
F = P + Q = AB + B′C
A | B | C | P = AB | Q = B′C | F = P + Q |
|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 | 1 | 1 |
0 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 | 0 | 1 |
1 | 1 | 1 | 1 | 0 | 1 |
Read it in words: "if B is 1, F follows A; if B is 0, F follows C". That is a 2-to-1 multiplexer with B as the select line, a block we study in Multiplexers. Analysing small circuits like this often reveals a familiar function.
Example 2: Reading a Timing Diagram
In the lab you see gates on an oscilloscope or logic analyser as waveforms. To find an output waveform, just apply the truth table in each time slot.
time slot: t0 t1 t2 t3 t4 t5 t6 t7
A 0 1 1 0 1 1 0 0
B 0 0 1 1 1 0 1 0
─────────────────────────────────────────
A·B 0 0 1 0 1 0 0 0
A + B 0 1 1 1 1 1 1 0
A ⊕ B 0 1 0 1 0 1 1 0
t0 t1 t2 t3 t4 t5 t6 t7
A ____‾‾‾‾‾‾‾‾____‾‾‾‾‾‾‾‾________
B ________‾‾‾‾‾‾‾‾‾‾‾‾____‾‾‾‾____
AND ________‾‾‾‾____‾‾‾‾____________
OR ____‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾____
XOR ____‾‾‾‾____‾‾‾‾____‾‾‾‾‾‾‾‾____
(Real outputs change slightly after the inputs because of propagation delay; ideal timing diagrams ignore it.)
Gates in Real Hardware
For lab work you will use the 74-series ICs. Most come in a 14-pin package with VCC on pin 14 and GND on pin 7. The same part numbers exist in TTL (74LS) and CMOS (74HC, 74HCT) versions.
IC | Contents |
|---|---|
7400 | Quad 2-input NAND |
7402 | Quad 2-input NOR (note: its pinout differs from the 7400; outputs come first) |
7404 | Hex inverter (six NOT gates) |
7408 | Quad 2-input AND |
7410 | Triple 3-input NAND |
7420 | Dual 4-input NAND |
7432 | Quad 2-input OR |
7486 | Quad 2-input XOR |
Inside a CMOS chip, the simplest gates are actually NAND, NOR and NOT (they need the fewest transistors: 4 for a 2-input NAND or NOR, 2 for NOT). An AND gate is a NAND followed by an inverter, which is why it uses 6 transistors and is slightly slower. Details are in Logic Families: TTL & CMOS.
Tri-State Buffer
A tri-state (three-state) buffer has a data input A, an enable input E and an output that can be 0, 1, or high impedance (Z), which means "electrically disconnected".
E
│
┌─┴╲
A ───┤ ╲──── Y E A | Y
│ ╱ ----+---
└──╱ 0 x | Z (disconnected)
1 0 | 0
1 1 | 1
Many devices can share one wire (a bus) if only one of them is enabled at a time. This is how a CPU, memory and I/O chips share the data bus.
Simulating the Gates in Python
A quick way to check truth tables is to model each gate as a function on 0/1 values. The program below prints all 2-input gates and shows that 3-input XOR is 1 exactly when the count of 1s is odd.
from itertools import product
gates = {
"AND": lambda a, b: a & b,
"OR": lambda a, b: a | b,
"NAND": lambda a, b: 1 - (a & b),
"NOR": lambda a, b: 1 - (a | b),
"XOR": lambda a, b: a ^ b,
"XNOR": lambda a, b: 1 - (a ^ b),
}
print("A B | " + " ".join(f"{name:>4}" for name in gates))
print("----+" + "-" * 30)
for a, b in product([0, 1], repeat=2):
print(f"{a} {b} | " + " ".join(f"{g(a, b):>4}" for g in gates.values()))
# 3-input XOR is 1 when an odd number of inputs are 1
print("\nA B C | XOR3 count of 1s")
for a, b, c in product([0, 1], repeat=3):
print(f"{a} {b} {c} | {a ^ b ^ c} {a + b + c}")
Output:
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
A B C | XOR3 count of 1s
0 0 0 | 0 0
0 0 1 | 1 1
0 1 0 | 1 1
0 1 1 | 0 2
1 0 0 | 1 1
1 0 1 | 0 2
1 1 0 | 0 2
1 1 1 | 1 3
How Many Different Gates Could Exist?
A 2-input gate is completely defined by its 4-row truth table, and each row's output can be 0 or 1. So there are 24 = 16 possible 2-input functions. They include the six named gates above, the two constants (always 0, always 1), A, B, A′, B′, and four others such as A′B ("inhibition") and A′ + B ("implication", A → B). In general there are 22n Boolean functions of n variables, which is 256 for n = 3.
Common Mistakes
Treating "+" as arithmetic. In logic, 1 + 1 = 1 (OR), not 10.
Reading (AB)′ as A′B′. NAND is (AB)′ = A′ + B′, which is 1 in three rows; A′B′ is NOR. The bar over the whole product is not the same as bars over each letter (see De Morgan's Theorems).
Thinking XOR means "exactly one input is 1" for 3 or more inputs. 3-input XOR is 1 for an odd count, so 1 ⊕ 1 ⊕ 1 = 1.
Building a 3-input NAND from two 2-input NANDs in a chain. NAND is not associative; you need an AND first, then the NAND.
Leaving unused TTL/CMOS inputs unconnected in the lab. Floating CMOS inputs pick up noise; tie unused AND/NAND inputs to 1 and unused OR/NOR inputs to 0 (or tie them to a used input).
Forgetting the bubble when reading a symbol: a bubble anywhere means inversion at that point.
GATE and Interview Questions
Q1. Which 2-input gate gives output 1 only when the inputs are different? Which gives 1 only when both inputs are 0?
XOR gives 1 when inputs differ. NOR gives 1 only when both inputs are 0.
Q2. What is the output of a 4-input XOR gate for inputs 1, 0, 1, 1?
Three inputs are 1 (odd count), so the output is 1: 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1.
Q3. How can an XOR gate be used as a NOT gate? As a buffer?
Tie one input to 1: A ⊕ 1 = A′ (NOT). Tie one input to 0: A ⊕ 0 = A (buffer). This "controlled inverter" behaviour is used to switch an adder into a subtractor.
Q4. How many rows does the truth table of a 5-input AND gate have, and in how many is the output 1?
25 = 32 rows; output is 1 in exactly 1 row (all inputs 1). For a 5-input OR, the output is 1 in 31 rows.
Q5. What is X ⊕ X ⊕ X ⊕ ... (X repeated 7 times)?
Pairs cancel (X ⊕ X = 0), leaving 3 pairs and one X, so the result is X. With an even number of X's it would be 0.
Q6. Show that XNOR(XNOR(A, B), C) = A ⊕ B ⊕ C.
XNOR(P, C) = (P ⊕ C)′ = P′ ⊕ C. With P = (A ⊕ B)′ we get P′ = A ⊕ B, so the result is A ⊕ B ⊕ C. Checking all 8 rows confirms it: the output is 1 for inputs 001, 010, 100, 111 (odd number of 1s).
Q7. Two switches in series control a lamp. Which gate does this model? Two switches in parallel?
Series = AND (both must be closed); parallel = OR (either one is enough). This analogy is exactly how Shannon connected relay circuits to Boolean algebra.
Summary
A gate computes a fixed Boolean function of its present inputs. Basic gates: NOT, AND (all 1s), OR (any 1).
Derived gates: NAND (0 only if all 1s), NOR (1 only if all 0s), XOR (inputs differ / odd number of 1s), XNOR (inputs equal).
An n-input gate has 2n truth-table rows; there are 22n functions of n variables (16 for two inputs).
AND/OR/XOR are associative; NAND/NOR are not.
Viewed as switches: AND enables, OR forces 1, XOR is a controlled inverter.
Analyse circuits by labelling wires and building the truth table; read timing diagrams slot by slot.
Next, Universal Gates: NAND & NOR shows how any circuit can be built from just one gate type.