Boolean algebra — AND, OR, NOT, XOR, NAND, NOR operations

WHAT each operation is

WHY these symbols ( $+$ and $\cdot$ )?

Because they behave like arithmetic. $A \cdot B$ acts like multiplication: $0\cdot0=0,\ 1\cdot1=1$ . $A+B$ acts like addition except $1+1=1$ (it saturates, it can't overflow past 1). This analogy is the whole reason it's called algebra.

HOW to read every gate — the truth tables

A truth table lists the output for every possible input combination. With $n$ inputs there are $2^n$ rows.

$A$	$B$	AND	OR	XOR	NAND	NOR
0	0	0	0	0	1	1
0	1	0	1	1	1	0
1	0	0	1	1	1	0
1	1	1	1	0	0	0

NOT (one input): $\lnot 0 = 1$ , $\lnot 1 = 0$ .

Figure — Boolean algebra — AND, OR, NOT, XOR, NAND, NOR operations

Deriving the formulas from scratch

You don't memorize XOR's formula — you build it. "When do the inputs differ?" Either ( $A=1, B=0$ ) or ( $A=0, B=1$ ). Translate each English word into algebra:

" $A=1$ and $B=0$ " $\Rightarrow A\cdot\bar B$
" $A=0$ and $B=1$ " $\Rightarrow \bar A\cdot B$
"either...or" $\Rightarrow +$

$\boxed{A \oplus B = A\bar B + \bar A B}$

Why this step? Each row of a truth table where output = 1 becomes one AND-term (a minterm); we OR all those terms together. This is called Sum of Products (SOP) and it lets you derive a formula for any truth table.

Worked examples

Worked example 2. Show XOR built from NAND only

Goal: a famous result. $A \oplus B$ using NAND ( $\,\uparrow\,$ ). Let $g = A \uparrow B = \overline{AB}$ . Then $A\oplus B = \big(A \uparrow g\big) \uparrow \big(g \uparrow B\big)$ . Why this step? Expanding: $A\uparrow g = \overline{A\,\overline{AB}} = \overline{A(\bar A+\bar B)} = \overline{A\bar B} = \bar A + B$ . Similarly $g\uparrow B = \bar B + A$ . NAND those: $\overline{(\bar A+B)(A+\bar B)} = \overline{\bar A A + \bar A\bar B + AB + B\bar B} = \overline{\bar A \bar B + AB} = (A+B)(\bar A+\bar B) = A\bar B + \bar A B = A\oplus B.$ ✓

Recall Feynman: explain to a 12-year-old

Imagine light switches. AND is two switches in a row — the bulb glows only if both are on. OR is two switches side by side — either one lights the bulb. NOT is a backwards switch: push it and the light goes off. XOR is the trick hallway light — flick either switch and it changes, so it's on only when the switches disagree. NAND/NOR are just the "opposite-day" versions of AND/OR. Wire enough of these toy switches together and you've literally built a computer's brain.

Flashcards

When is A AND B equal to 1?

Only when both A and B are 1.

When is A OR B equal to 1?

When at least one input is 1 (inclusive OR; 1+1=1).

What does XOR output 1 for?

When the two inputs differ (A≠B).

Formula for XOR in terms of AND/OR/NOT?

A\oplus B = A\bar B + \bar A B

State De Morgan's laws.

\overline{A\cdot B}=\bar A+\bar B

and

\overline{A+B}=\bar A\cdot\bar B

How do you make NOT from a single NAND?

Tie both inputs together:

\overline{A\cdot A}=\bar A

Why is NAND called a "universal" gate?

It alone can build NOT, AND, OR — hence any circuit.

Difference between OR and XOR at inputs 1,1?

OR gives 1, XOR gives 0.

What is NAND of A and B?

\overline{A\cdot B}

— AND first, then NOT.

Simplify

A+\bar A B

A+B

How many rows in a truth table with n inputs?

2^n

Connections

Logic Gates and Transistors — how these operations become physical circuits.
Binary Number System — the 0/1 values these gates act on.
Half Adder and Full Adder — XOR + AND build binary addition.
Karnaugh Maps — visual tool for simplifying Boolean expressions.
Sum of Products and Minterms — deriving a formula from any truth table.
De Morgan's Laws — the bridge between AND and OR.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, computer ke andar sirf do hi cheezein hoti hain: 0 aur 1 (off ya on, low ya high voltage). Boolean algebra inhi do values ki maths hai. Jaise normal maths mein plus aur multiply hote hain, waise hi yahan AND, OR, NOT, XOR, NAND, NOR operations hote hain. AND tab 1 deta hai jab dono inputs 1 hon (sabki haan zaroori). OR tab 1 jab koi ek bhi 1 ho (ek haan kaafi hai). NOT simply bit ko ulta kar deta hai. XOR tab 1 jab dono inputs alag hon (disagreement detector). NAND aur NOR bas AND/OR ke ulte (negated) versions hain.

Sabse important trick hai De Morgan's law: $\overline{A\cdot B}=\bar A+\bar B$ aur $\overline{A+B}=\bar A\cdot\bar B$ . Yaad rakho — "bar ko todo, sign badlo" (AND ban jaata OR, OR ban jaata AND). Ye law itna powerful hai ki sirf NAND gate se hi pura computer ban sakta hai, isliye factory mein bas NAND banao aur kaam chal jaata hai.

Sabse common galti: students sochte hain OR mein $1+1=0$ hota hai (kyunki English mein "ya to chai ya coffee" matlab ek). Galat! Boolean OR inclusive hai, $1+1=1$ . "Exactly one" wala matlab XOR ka hai. Doosri galti: De Morgan lagate waqt sirf bar laga dete hain par operator (AND/OR) badalna bhool jaate hain.

Padhne ka tareeka: truth table ko dhakk ke khud se dobara likho (active recall), phir XOR ka formula $A\bar B+\bar A B$ truth table se khud derive karo, ratta mat maaro. Yeh 6 gates digital electronics ki ABCD hain — inhe samajh liya to adder, memory, processor sab samajh aa jayega.

Test yourself — How Computers Work

Connections