📟 ISC CS · Topic 2

Computer
Hardware

Logic gates, adders, encoders, decoders, multiplexers & universal gates — complete ISC theory for 100/100.

NOT AND OR
NAND NOR XOR XNOR
Half/Full Adder
Encoder/Decoder
Multiplexer
Universal Gates
TOPIC 2A
Elementary Logic Gates
NOT · AND · OR · NAND · NOR · XOR · XNOR

A logic gate is a basic electronic circuit that implements a Boolean function. It takes one or more binary inputs (0 or 1) and produces a single binary output.

A Y
NOT Gate
Y = Ā
Inverter. Outputs the complement of the input. Single input only.
A B Y
AND Gate
Y = A · B
Output is 1 only when ALL inputs are 1. Like multiplication in Boolean.
A B Y
OR Gate
Y = A + B
Output is 1 when AT LEAST ONE input is 1. Like addition in Boolean.
A B Y
NAND Gate
Y = ̄(A · B)
NOT-AND. Output is 0 only when ALL inputs are 1. Universal gate.
A B Y
NOR Gate
Y = ̄(A + B)
NOT-OR. Output is 1 only when ALL inputs are 0. Universal gate.
A B Y
XOR Gate
Y = A ⊕ B
Exclusive OR. Output is 1 when inputs are DIFFERENT. Used in adders.
A B Y
XNOR Gate
Y = ̄(A ⊕ B)
Exclusive NOR. Output is 1 when inputs are SAME. Equality detector.
Complete Truth Tables — All 7 Gates
ABNOT AA AND BA OR BA NAND BA NOR BA XOR BA XNOR B
001001101
011011010
100011010
110110001
⭐ Memory Tricks

AND: All must be 1 → output is 1
OR: Any one is 1 → output is 1
NAND: Opposite of AND (bubble on output)
NOR: Opposite of OR (bubble on output)
XOR: "eXclusive OR" — different inputs → 1
XNOR: Same inputs → 1 (equality checker)

XOR and XNOR — Extended Expressions

XOR (A ⊕ B)

Y = A⊕B = Ā·B + A·B̄

Output is 1 when an odd number of inputs are 1. Used in arithmetic (half adder sum), parity generation and checking.

XNOR ̄(A ⊕ B)

Y = ̄(A⊕B) = A·B + Ā·B̄

Output is 1 when an even number of inputs are 1 (including zero). Used as an equality comparator.

TOPIC 2B
Half Adder & Full Adder
Boolean expressions, truth tables, gate implementations
Half Adder
Definition

A half adder adds two single-bit binary numbers A and B, producing a Sum (S) and Carry (C). It cannot accommodate a carry from a previous addition (no carry-in).

Half Adder Truth Table

ABSum (S)Carry (C)
0000
0110
1010
1101

Boolean Expressions

Sum (S) — XOR gate:
S = A ⊕ B = Ā·B + A·B̄
Carry (C) — AND gate:
C = A · B
Gates needed

1 XOR gate (for Sum) + 1 AND gate (for Carry) = 2 gates total

Half Adder Circuit Diagram
A B S (Sum) C (Carry) XOR AND
Full Adder
Definition

A full adder adds three bits: A, B, and Carry-in (Cᵢₙ), producing a Sum (S) and Carry-out (Cₒᵤₜ). It can be cascaded to add multi-bit binary numbers (ripple carry adder).

Full Adder Truth Table

ABCᵢₙSum (S)Carry-out (Cₒᵤₜ)Minterms
00000m₀
00110m₁ →S
01010m₂ →S
01101m₃ →Cout
10010m₄ →S
10101m₅ →Cout
11001m₆ →Cout
11111m₇ →S,Cout

Boolean Expressions (SOP)

Sum = ∑m(1,2,4,7):
S = A⊕B⊕Cᵢₙ
Carry-out = ∑m(3,5,6,7):
Cₒᵤₜ = A·B + B·Cᵢₙ + A·Cᵢₙ
= A·B + Cᵢₙ·(A⊕B)

Implementation using 2 Half Adders

1
Half Adder 1
S₁ = A ⊕ B    C₁ = A · B
2
Half Adder 2
S = S₁ ⊕ Cᵢₙ    C₂ = S₁ · Cᵢₙ
3
Final Carry
Cₒᵤₜ = C₁ + C₂ (OR gate)
TOPIC 2C
Encoder
Converts 2ⁿ inputs → n-bit binary code
Definition

An encoder is a combinational circuit that converts one of 2ⁿ input lines into an n-bit binary output code. At any given time, exactly ONE input line is active (HIGH). It is the reverse of a decoder.

⭐ Key Point — Assumption

Only ONE input is 1 at a time (mutually exclusive). If multiple inputs are 1 simultaneously, a priority encoder is needed (not in ISC syllabus).

4-to-2 Encoder (4 inputs → 2-bit output)

Truth Table

I₃I₂I₁I₀Y₁Y₀
000100
001001
010010
100011

Boolean Expressions

Output bit Y₁ (MSB):
Y₁ = I₂ + I₃
Output bit Y₀ (LSB):
Y₀ = I₁ + I₃

Each output bit is simply the OR of the input lines where that output bit is 1 in the truth table.

Implementation

Only 2 OR gates needed (one per output bit).

8-to-3 Encoder (Octal to Binary)

Truth Table

I₇I₆I₅I₄I₃I₂I₁I₀Y₂Y₁Y₀
00000001000
00000010001
00000100010
00001000011
00010000100
00100000101
01000000110
10000000111
Y₂ = I₄ + I₅ + I₆ + I₇
Y₁ = I₂ + I₃ + I₆ + I₇
Y₀ = I₁ + I₃ + I₅ + I₇
Each Yᵢ = OR of all inputs where bit i of their binary encoding is 1
TOPIC 2D
Decoder
Converts n-bit binary code → 2ⁿ output lines
Definition

A decoder is a combinational circuit that converts an n-bit binary input into one of 2ⁿ output lines. Exactly ONE output is active (HIGH) for each unique binary input combination. It is the reverse of an encoder.

2-to-4 Decoder (2-bit input → 4 outputs)

Truth Table

ABD₀D₁D₂D₃
001000
010100
100010
110001

Boolean Expressions

D₀ = Ā · B̄
D₁ = Ā · B
D₂ = A · B̄
D₃ = A · B

Each output is a minterm of the inputs. D₀ = m₀, D₁ = m₁, D₂ = m₂, D₃ = m₃.

Implementation

2 NOT gates + 4 AND gates. Each AND gate generates one minterm.

3-to-8 Decoder (Binary to Octal)

Boolean Expressions — 3-to-8 Decoder

D₀ = Ā·B̄·C̄   (minterm 0)
D₁ = Ā·B̄·C   (minterm 1)
D₂ = Ā·B·C̄   (minterm 2)
D₃ = Ā·B·C   (minterm 3)
D₄ = A·B̄·C̄   (minterm 4)
D₅ = A·B̄·C   (minterm 5)
D₆ = A·B·C̄   (minterm 6)
D₇ = A·B·C   (minterm 7)

A decoder generates ALL minterms of n variables. It can therefore implement ANY Boolean function by connecting relevant outputs to an OR gate.

⭐ EXAM KEY — Decoder Implementing Boolean Functions

Any n-variable Boolean function in SOP form can be realized using an n-to-2ⁿ decoder and an external OR gate. The decoder generates all minterms; the OR gate selects the required ones.

Example: f(A,B,C) = ∑m(1,3,5,7) — connect D₁, D₃, D₅, D₇ to an OR gate.

TOPIC 2E
Multiplexer (MUX)
Many-to-one data selector — 2ⁿ inputs, n select lines, 1 output
Definition

A multiplexer (MUX) is a combinational circuit that selects ONE of several input data lines and routes it to a single output, based on a set of selection (control) lines. It acts as a data selector.

Inputs

2ⁿ

Data input lines

Select Lines

n

Control/select lines

Output

1

Single output line

2:1 Multiplexer (2 inputs, 1 select line)

Truth Table

S (Select)Output Y
0I₀ (selects input I₀)
1I₁ (selects input I₁)

Boolean Expression

Y = S̄·I₀ + S·I₁

When S=0: Y = I₀. When S=1: Y = I₁. Needs 1 NOT, 2 AND, 1 OR gate.

4:1 Multiplexer (4 inputs, 2 select lines)

Truth Table

S₁S₀Output Y
00I₀
01I₁
10I₂
11I₃

Boolean Expression

Y = S̄₁·S̄₀·I₀ + S̄₁·S₀·I₁ + S₁·S̄₀·I₂ + S₁·S₀·I₃

Each term enables exactly one input based on the select line combination.

⭐ MUX as a Universal Logic Circuit

A 2ⁿ:1 MUX can implement any n-variable Boolean function by connecting the data inputs (I₀ to I₂ⁿ⁻¹) to 0 or 1 based on the function's truth table, and using the n variables as select lines.

Example: To implement f(A,B) = A XOR B using a 4:1 MUX with A,B as select lines:
S₁S₀=00 (A=0,B=0): f=0 → I₀=0    S₁S₀=01 (A=0,B=1): f=1 → I₁=1
S₁S₀=10 (A=1,B=0): f=1 → I₂=1    S₁S₀=11 (A=1,B=1): f=0 → I₃=0

TOPIC 2F
NAND & NOR as Universal Gates
Proving universality by implementing NOT, AND, OR using only NAND or NOR
What is a Universal Gate?

A gate is called a universal gate if it can be used to implement any Boolean function — i.e., any combination of NOT, AND, and OR gates can be replaced by using only that gate. NAND and NOR are the two universal gates.

NAND Gate: Y = ̄(A·B)

1. NOT using NAND
NOT A = Ā → NAND(A, A) = ̄(A·A) = Ā ✓
A Ā (NOT A) Both inputs = A

Proof: NAND(A,A) = ̄(A·A) = ̄(A) = Ā ✓ (idempotent law A·A=A)

2. AND using NAND
A AND B = A · B → NOT[NAND(A,B)] = NOT[̄(A·B)] = A·B ✓

Proof: NAND gives ̄(A·B). Apply NOT (which is NAND with itself): ̄[̄(A·B)] = A·B ✓

AND(A,B) = NAND(NAND(A,B), NAND(A,B))
3. OR using NAND
A OR B = A + B → NAND(Ā, B̄) = ̄(Ā·B̄) = A+B ✓ (De Morgan)
Step 1: Get Ā using NAND(A,A)
Step 2: Get B̄ using NAND(B,B)
Step 3: OR(A,B) = NAND(Ā, B̄) = NAND(NAND(A,A), NAND(B,B))
NAND Summary — Gates needed

NOT: 1 NAND gate | AND: 2 NAND gates | OR: 3 NAND gates

Converting any circuit to NAND-only — Method

1
Write the Boolean expression
Get the expression from the circuit or truth table.
2
Convert to SOP (Sum of Products)
All expressions can be written in AND-OR form.
3
Double negate the entire expression
̄̄f = f. Apply De Morgan to the outer NOT to get NAND form.
4
Replace each operation with NAND
Each AND with bubble = NAND gate. NOT = self-connected NAND.
⭐ Key Rule for SOP → NAND-NAND

A two-level AND-OR circuit implementing SOP form can be directly converted to a two-level NAND-NAND circuit. Replace each AND gate and the final OR gate with NAND gates. This works because: ̄(Ā·B̄·...) = A+B+... by De Morgan's, and ̄[̄(AB)+̄(CD)+...] = AB+CD+... ✓

NOR Gate: Y = ̄(A+B)

1. NOT using NOR
NOT A = Ā → NOR(A, A) = ̄(A+A) = Ā ✓

Proof: NOR(A,A) = ̄(A+A) = ̄(A) = Ā ✓ (idempotent law A+A=A)

2. OR using NOR
A OR B = A + B → NOT[NOR(A,B)] = NOT[̄(A+B)] = A+B ✓
OR(A,B) = NOR(NOR(A,B), NOR(A,B))
3. AND using NOR
A AND B = A · B → NOR(Ā, B̄) = ̄(Ā+B̄) = A·B ✓ (De Morgan)
Step 1: Get Ā using NOR(A,A)
Step 2: Get B̄ using NOR(B,B)
Step 3: AND(A,B) = NOR(Ā, B̄) = NOR(NOR(A,A), NOR(B,B))
NOR Summary — Gates needed

NOT: 1 NOR gate | OR: 2 NOR gates | AND: 3 NOR gates

POS → NOR-NOR Conversion

Just as SOP maps to NAND-NAND, POS (Product of Sums) maps to NOR-NOR:

⭐ Key Rule for POS → NOR-NOR

A two-level OR-AND circuit implementing POS form can be converted to a two-level NOR-NOR circuit. Replace each OR gate and the final AND gate with NOR gates.

Example: f = (A+B)·(C+D)
Step 1: Apply double NOT: f = ̄[̄((A+B)·(C+D))]
Step 2: De Morgan inner: = ̄[̄(A+B) + ̄(C+D)]
= NOR(NOR(A,B), NOR(C,D)) ← two-level NOR-NOR ✓
Comparison: NAND vs NOR as Universal Gates
FunctionUsing NAND onlyUsing NOR only
NOT ANAND(A,A)NOR(A,A)
A AND BNAND(NAND(A,B), NAND(A,B))NOR(NOR(A,A), NOR(B,B))
A OR BNAND(NAND(A,A), NAND(B,B))NOR(NOR(A,B), NOR(A,B))
Best forSOP (Sum of Products)POS (Product of Sums)
2-level formNAND-NAND (≡ AND-OR)NOR-NOR (≡ OR-AND)
⭐⭐ Conversion Example — Half Adder to NAND only

Half Adder: S = A⊕B = Ā·B + A·B̄    C = A·B

Carry using NAND:
C = A·B = NAND(NAND(A,B), NAND(A,B))

Sum using NAND (5 gates):
Let P = NAND(A,B) = ̄(A·B)
Let Q = NAND(A,P) = ̄(A·̄(AB)) = Ā + AB = A+̄AB... (simplifies to A⊕B via NAND construction)
Full NAND implementation: S = NAND(NAND(A, NAND(A,B)), NAND(B, NAND(A,B)))

Verification: NAND(A,B)=P; NAND(A,P)=̄(A·̄(AB)); NAND(B,P)=̄(B·̄(AB)); S=NAND(these two)=A⊕B ✓

INTERACTIVE
Gate Simulator
Toggle inputs and see live gate output
Select a gate and toggle inputs:
0
0
→
NOT
Y = Ā
→
Output Y
0
PRACTICE
Quick Quiz
ISC exam-level questions on Computer Hardware
Your Score 0 / 0
Q1. Which gate outputs 1 ONLY when both inputs are 0?
NOR gate: Y = ̄(A+B). Output is 1 only when A=0 AND B=0 (0+0=0, NOT 0 = 1). All other input combos give 0.
Q2. To implement NOT gate using NAND, what do you do?
NAND(A,A) = ̄(A·A) = ̄A (because A·A = A by idempotent law). This gives NOT A using a single NAND gate.
Q3. A 4-to-1 MUX has how many select lines?
A 4:1 MUX has 4 = 2² data inputs, so it needs n=2 select lines. Generally: 2ⁿ:1 MUX needs n select lines.
Q4. What are the Boolean expressions for a 2-to-4 decoder outputs?
A 2-to-4 decoder generates all 4 minterms of 2 variables: D₀=m₀=Ā·B̄, D₁=m₁=Ā·B, D₂=m₂=A·B̄, D₃=m₃=A·B. Exactly one is HIGH for each input combination.
Q5. OR gate using only NOR gates requires:
OR(A,B) = NOT[NOR(A,B)]. NOT using NOR needs 1 NOR gate. So: NOR gate #1 = NOR(A,B); then NOR gate #2 = NOR(output₁, output₁) = NOT(output₁) = A+B. Total: 2 NOR gates.
Q6. In an 8-to-3 encoder, which expression is correct for Y₀ (LSB)?
Y₀ (LSB) is 1 for inputs 1,3,5,7 (odd numbers in binary have LSB=1). So Y₀ = I₁+I₃+I₅+I₇. Y₁ = I₂+I₃+I₆+I₇ (bit 1 is 1 for 2,3,6,7). Y₂ = I₄+I₅+I₆+I₇ (bit 2 is 1 for 4,5,6,7).
Q7. Which two-level NAND-NAND circuit is equivalent to?
Two-level NAND-NAND is equivalent to AND-OR (SOP). This is because: first level NAND does AND then inverts; second level NAND inverts the previous inversions and ORs them, giving the same result as AND-OR. Similarly, NOR-NOR ≡ OR-AND (POS).
QUICK REF
Master Cheat Sheet
All key formulas — Computer Hardware Topic 2
NOT
Y = Ā
Output is complement of input
AND
Y = A · B
1 only when ALL inputs = 1
OR
Y = A + B
1 when ANY input = 1
NAND
Y = ̄(A·B)
0 only when ALL inputs = 1
NOR
Y = ̄(A+B)
1 only when ALL inputs = 0
XOR
Y = A⊕B
1 when inputs are DIFFERENT
XNOR
Y = ̄(A⊕B)
1 when inputs are SAME
Half Adder S
S = A ⊕ B
XOR gate
Half Adder C
C = A · B
AND gate
Full Adder S
S = A⊕B⊕Cᵢₙ
Two XOR gates
Full Adder Cout
Cout = AB+BCin+ACin
Majority function
4:1 MUX
Y = S̄₁S̄₀I₀+S̄₁S₀I₁+...
2 select lines, 4 inputs
NOT via NAND
NAND(A,A)
Tie both inputs together
AND via NAND
NAND(NAND(A,B),NAND(A,B))
2 NAND gates
OR via NAND
NAND(NAND(A,A),NAND(B,B))
3 NAND gates
NOT via NOR
NOR(A,A)
Tie both inputs together
OR via NOR
NOR(NOR(A,B),NOR(A,B))
2 NOR gates
AND via NOR
NOR(NOR(A,A),NOR(B,B))
3 NOR gates
Encoder
2ⁿ → n lines
Each output = OR of inputs
Decoder
n → 2ⁿ lines
Each output = a minterm
🎯 Top ISC Exam Questions for Topic 2

1. Draw and explain the logic circuit and truth table of a Half Adder / Full Adder
2. Show how NAND gate is a universal gate by implementing NOT, AND, OR
3. Show how NOR gate is a universal gate by implementing NOT, OR, AND
4. Write Boolean expressions for a 2-to-4 decoder
5. Convert an AND-OR circuit to NAND-NAND equivalent
6. Write the Boolean expression for a 4:1 MUX
7. Find the output of a given logic circuit for specific inputs
8. Draw the logic diagram for the SOP expression of a given truth table