Combinational logic — half adder, full adder, multiplexer, decoder

1. The core idea — WHY we need adders, muxes, decoders

WHY these four?

Half/Full adder → so the computer can do binary arithmetic (add numbers).
Multiplexer (MUX) → so we can select one signal out of many (routing data).
Decoder → so we can activate exactly one output line from a binary code (addressing memory, choosing instructions).

2. Half Adder — adding two single bits

Derive from the truth table (first principles):

$A$	$B$	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

WHY this table? Just count in binary: $1+1 = 10_2$ , so Sum $=0$ , Carry $=1$ .

HOW do we turn a truth table into gates? Find which rows give output $1$ .

Sum is $1$ when $A,B$ differ → that is exactly XOR: $\text{Sum} = A \oplus B = \bar{A}B + A\bar{B}$
Carry is $1$ only when both are $1$ → that is AND: $\text{Carry} = A \cdot B$

3. Full Adder — adding two bits plus a carry-in

Truth table (3 inputs):

$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

Derive Sum: Sum $=1$ when the number of $1$ s among $(A,B,C_{in})$ is odd. Odd-parity of three bits is exactly XOR chained: $\text{Sum} = A \oplus B \oplus C_{in}$

Derive Carry-out: $C_{out}=1$ when at least two inputs are $1$ (majority). From the table: $C_{out} = AB + AC_{in} + BC_{in}$

WHY this step? List the rows where $C_{out}=1$ : $\{011,101,110,111\}$ — each has a pair that is both $1$ , captured by one of the AND terms.

Figure — Combinational logic — half adder, full adder, multiplexer, decoder

4. Multiplexer (MUX) — the data selector

Derive a 2-to-1 MUX (1 select line $S$ ):

When $S=0$ → output $=I_0$ .
When $S=1$ → output $=I_1$ .

Turn that into Boolean: each input is "gated" by the select condition. $Y = \bar{S}\,I_0 + S\,I_1$

WHY this works: $\bar S I_0$ passes $I_0$ only when $S=0$ (the other term is $0$ ); $S I_1$ passes $I_1$ only when $S=1$ . Exactly one term is ever live.

5. Decoder — binary code → one-hot

Derive 2-to-4 decoder: each output $D_k$ should be $1$ iff inputs equal $k$ in binary. That's the minterm: $D_0=\bar A\bar B,\quad D_1=\bar A B,\quad D_2=A\bar B,\quad D_3=AB$

WHY: $D_2=A\bar B$ is true only when $A=1,B=0$ , i.e. input $=10_2=2$ . Each output is one AND of the inputs in true/complement form.

6. The 80/20 — what to truly remember

Flashcards

What defines a combinational circuit?

Output depends only on current inputs; no memory/state/clock.

Half adder Sum expression?

\text{Sum}=A\oplus B

Half adder Carry expression?

\text{Carry}=A\cdot B

Why is the half-adder Sum XOR and not OR?

OR wrongly outputs 1 when both inputs are 1; XOR excludes that case (it becomes a carry instead).

Full adder Sum expression?

A\oplus B\oplus C_{in}

(odd parity of the three bits).

Full adder Carry-out expression?

AB+AC_{in}+BC_{in}=AB+C_{in}(A\oplus B)

(majority function).

How many half adders + gates build a full adder?

Two half adders + one OR gate.

2-to-1 MUX output equation?

Y=\bar S I_0 + S I_1

What do select lines of a MUX control?

Which data input is routed to the single output (they don't appear in the output value).

What does a 2-to-4 decoder output for input 10?

One-hot 0100 (only

D_2

high).

General output of a decoder line

D_k

The

k

-th minterm of the inputs.

How do decoder + OR gates implement any Boolean function?

OR together the minterm outputs corresponding to the function's 1-rows.

Recall Feynman: explain to a 12-year-old

Imagine you're adding two LEGO-coin piles, but each spot can only hold ONE coin. Half adder: put two coins together; if both are there you'd have two, so you keep one as a "carry" to give to the next spot — that carry-keeping is the AND, and the "leftover here" is the XOR. Full adder: same, but now a friend also hands you a coin from the previous spot. Multiplexer: a TV remote that, depending on the channel number you press, lets ONE channel through. Decoder: you say a number out loud, and exactly ONE light bulb labeled with that number turns on.

Connections

Boolean Algebra and Logic Gates — minterms, De Morgan's laws.
Binary Number System — why carry exists at all.
Ripple Carry Adder and ALU — chaining full adders.
Sequential Logic and Flip-Flops — the "memory" contrast.
Memory Addressing — decoders selecting rows.
Karnaugh Maps — simplifying these expressions.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, combinational logic ka matlab hai aise circuits jinka output sirf abhi ke inputs par depend karta hai — koi memory nahi, koi clock nahi. Same input daalo, same output milega, har baar. Yahi cheez sequential logic se alag hai jahan flip-flop "yaad" rakhte hain.

Half adder: do single bits ko add karta hai. $1+1=10_2$ hota hai, isliye do output chahiye — Sum aur Carry. Sum tab $1$ hota hai jab dono bits alag hon — yeh exactly XOR hai. Carry tab $1$ jab dono $1$ hon — yeh AND hai. Common galti: log Sum ke liye OR laga dete hain, par OR dono-1 wale case mein galat 1 deta hai, isliye XOR sahi hai.

Full adder mein ek extra input aata hai — $C_{in}$ (pichli column ka carry). Sum ban jaata hai $A\oplus B\oplus C_{in}$ (odd parity), aur carry-out majority function $AB+AC_{in}+BC_{in}$ . Trick: do half adders + ek OR gate se poora full adder ban jaata hai.

MUX ek switch jaisa hai — kayi inputs mein se ek ko select line ke hisaab se output tak bhejta hai. Decoder ulta kaam karta hai — ek binary number ko leke us number wali ek hi line ko ON karta hai (one-hot). Yaad rakho: MUX chunta hai, Decoder jalata hai. Aur sabse bada point — har Boolean function minterms se banta hai, aur decoder + OR se kuch bhi banaya ja sakta hai. Yeh CPU ke ALU aur memory addressing ki foundation hai!

Test yourself — How Computers Work

Connections