Logic Gates

The Puzzle of the Staircase Light

Most homes in India with a staircase have a small electrical mystery built into the wall: two switches, one at the bottom of the stairs and one at the top, that both control the same bulb. Flip the bottom switch up, the light turns on. Walk up the stairs, flip the top switch, and the light turns off — even though you didn't touch the bottom switch again. Flip the top switch again and the light comes back on. Neither switch is the "real" on/off switch and neither is a dummy. Both are equally in charge, and yet there is only one bulb.

This feels like magic the first time you notice it, but it is not magic — it is one of the simplest and most elegant pieces of digital logic in your house, and by the end of this chapter you will be able to say exactly why it works, using the same mathematical tool that engineers use to design every calculator, traffic-light controller, and processor: the logic gate.

From Voltages to Bits

Inside any digital circuit, a wire is not allowed to carry "a little bit of electricity" or "kind of on." Engineers deliberately design the circuit so that a wire is read as one of exactly two states: a high voltage, which we label 1, or a low voltage (close to zero), which we label 0. This 0/1 labelling is called a bit (binary digit).

Why only two states, when the real world has a continuous range of voltages? Because two states are easy to tell apart reliably. If "on" is officially anywhere above 3.5 volts and "off" is anywhere below 1 volt, then a little bit of electrical noise — a nearby motor switching on, a long wire picking up interference — can wobble the voltage without ever confusing a circuit about whether the bit is a 0 or a 1. A system that tried to distinguish, say, 100 different voltage levels to represent 100 different symbols would get confused by the same amount of noise. Two-state (binary) design is what makes digital electronics dependable.

A logic gate is a circuit that takes one or more bits as input and produces exactly one bit as output, according to a fixed rule. The staircase bulb is a real, physical example: its two switches are the inputs (each is either "up" or "down," i.e. 1 or 0), and the bulb is the output (lit or unlit, 1 or 0).

The Truth Table: A Complete Rulebook

Because a bit can only be 0 or 1, and a logic gate has a small, fixed number of inputs, we can write down every single input combination the gate will ever see, along with the output for each one. This complete list is called a truth table.

If a gate has n inputs, each of which can independently be 0 or 1, the number of possible input combinations is 2 × 2 × ... (n times), written 2n. A gate with 1 input has 2 rows. A gate with 2 inputs has 4 rows. A gate with 3 inputs has 8 rows. This is not a rule someone invented for logic gates specifically — it is just basic counting: two independent choices for the first input, times two independent choices for the second, and so on.

For our staircase bulb, there are 2 switches, so 22 = 4 possible situations. We will build that exact truth table once we have the vocabulary to describe it precisely. First, let's meet the basic gates one at a time, each with a rule you already use in everyday reasoning — you just haven't seen it written as a table before.

NOT: The One-Input Gate

The simplest gate has only one input. It is called NOT, or an inverter, and its rule is: flip whatever you're given. If the input is 0, the output is 1. If the input is 1, the output is 0.

A car's interior light often works this way in reverse logic: the light is ON when the door sensor reads "door is NOT closed." If the sensor bit for "door closed" is 0 (not closed), the lamp-control bit is 1 (lamp on). If the sensor reads 1 (closed), the lamp-control bit is 0 (lamp off). The lamp circuit is quite literally computing NOT(door closed).

In Boolean notation (the algebra of 0s and 1s, named after the mathematician George Boole), we write NOT A as A' or ̄A (a bar drawn over the letter). Its truth table has 21 = 2 rows:

AND: Everyone Must Agree

The AND gate takes two (or more) inputs and outputs 1 only when every single input is 1. If even one input is 0, the output is 0.

Think about how a cash machine decides whether to release money. It checks two conditions: is the card genuine, and is the PIN correct? Only when both checks pass does the machine dispense cash. If the PIN is right but the card is a photocopy, no cash. If the card is genuine but the PIN is wrong, no cash. Both conditions must be true simultaneously — that is exactly the AND rule, and it's why the AND symbol in the gate diagram above has a truth table with a single 1, sitting in the one row where both inputs are 1.

A common mistake students make here is reading "A AND B" as "either A or B is enough." It is not. Everyday English is loose about this ("bring an umbrella and a raincoat" doesn't strictly require both), but in Boolean logic AND is strict: all inputs must be 1, with no exceptions. The gate that says "one is enough" is a different gate, described next.

OR: One Is Enough

The OR gate outputs 1 if at least one input is 1. The only way to get a 0 output is if every input is 0.

A home burglar alarm typically wires several sensors — a door sensor, a window sensor, a motion sensor — into an OR gate. The siren should sound if the door sensor detects intrusion, OR the window sensor does, OR the motion sensor does. It doesn't need all three to trigger; any single one is sufficient. Look again at the OR truth table above: three of the four rows output 1, and the only 0 is the all-zero row.

Notice something important: when both A and B are 1, OR still outputs 1. This is called an inclusive OR, and it is the standard meaning of OR in digital logic. This is different from how we sometimes use "or" in spoken language — "you can have tea or coffee" usually implies you pick exactly one, not both. Logic-gate OR makes no such restriction. The gate that behaves like the "pick exactly one" version of "or" is called XOR, and we are about to meet it properly — because it is exactly the rule your staircase light follows.

Solving the Staircase Puzzle: XOR

Let's finally write down the truth table for the two staircase switches. Say a switch pushed "up" reads as 1, and pushed "down" reads as 0. Watching a real staircase circuit carefully (or wiring one on a lab board), you'll find the bulb lights up exactly when the two switches are in different positions, and goes dark when they are in the same position:

• S1 down (0), S2 down (0) → same position → bulb OFF (0)
• S1 down (0), S2 up (1) → different → bulb ON (1)
• S1 up (1), S2 down (0) → different → bulb ON (1)
• S1 up (1), S2 up (1) → same position → bulb OFF (0)

Compare this to the XOR ("exclusive OR") truth table drawn earlier: 0,1,1,0. It's an exact match. The staircase light is a physical, everyday implementation of an XOR gate, built entirely out of wires and mechanical switches, with no microchip involved at all. That's why flipping either switch always toggles the bulb: changing just one input from 0 to 1 (or 1 to 0) necessarily changes whether the two inputs match, which necessarily flips the output.

XOR is written A ⊕ B, and unlike AND, OR, and NOT, it isn't considered one of the three fundamental gate types — it's built by combining them: A ⊕ B = A·B' + A'·B (in words: "A is 1 and B is 0" OR "A is 0 and B is 1"). You can check this against the truth table row by row and confirm it produces 0,1,1,0.

The Inverted Cousins: NAND, NOR, XNOR

Every gate we've met can be followed by a NOT to produce its "inverted" version. In circuit diagrams this is drawn as a small bubble at the gate's output — the same bubble you saw on the NOT symbol.

• NAND = NOT(AND). Output is 0 only when every input is 1; otherwise 1. Truth table: 1,1,1,0.
• NOR = NOT(OR). Output is 1 only when every input is 0; otherwise 0. Truth table: 1,0,0,0.
• XNOR = NOT(XOR). Output is 1 when the inputs are the same; 0 when they differ. Truth table: 1,0,0,1. (This is precisely what you'd want if you wired the staircase light the opposite way — bulb on when switches match.)

NAND and NOR have a special reputation among engineers: each one, on its own, is enough to build every other gate. You can build an AND, OR, NOT, XOR — any Boolean function at all — using nothing but NAND gates wired together in different patterns. Because of this, NAND is often called a universal gate, and real chips are frequently built almost entirely from repeated NAND (or NOR) units, since manufacturing one gate design over and over is simpler and cheaper than manufacturing many different gate shapes.

Combining Gates: Reading a Boolean Expression

Real circuits chain gates together, and we describe the result using Boolean algebra notation: · for AND, + for OR, and a prime (') or bar for NOT. Let's carefully build the truth table for a three-input expression:

Y = A·B + C'

Read aloud, this says: "Y is 1 if (A AND B) is 1, OR if (NOT C) is 1." With 3 inputs, there are 23 = 8 rows. Let's work through every row methodically, computing the two pieces (A·B and C') before combining them with OR:

A B C | A·B | C' | Y = A·B + C'
0 0 0 |  0   | 1  |  1
0 0 1 |  0   | 0  |  0
0 1 0 |  0   | 1  |  1
0 1 1 |  0   | 0  |  0
1 0 0 |  0   | 1  |  1
1 0 1 |  0   | 0  |  0
1 1 0 |  1   | 1  |  1
1 1 1 |  1   | 0  |  1

Walk through the last row as a check: A=1, B=1, C=1. A·B = 1·1 = 1. C' = 1' = 0. Then Y = 1 + 0, and since OR only needs one 1, Y = 1. Every other row follows the same two-step process: compute the AND term, compute the NOT term, then OR them together. This step-by-step method — build each sub-expression as its own column before combining — is exactly how you should approach any Boolean expression, no matter how many gates it chains together.

Logic Gates as Arithmetic: Building an Adder

Here is where logic gates stop being an abstract puzzle and become the reason your calculator can add numbers. Suppose you want to add two single binary digits, A and B. There are four possible sums:

0 + 0 = 0   (binary 00)
0 + 1 = 1   (binary 01)
1 + 0 = 1   (binary 01)
1 + 1 = 2   (binary 10)

Every result needs two output bits: a Sum bit and a Carry bit (the same "carry the 1" you learned in Class 3 for decimal addition, just with only two digits, 0 and 1, instead of ten). Look closely at the Sum column across all four rows: 0, 1, 1, 0. That is exactly the XOR truth table. And the Carry column: 0, 0, 0, 1 — exactly the AND truth table.

So a circuit made of just one XOR gate and one AND gate, both fed the same two inputs A and B, computes:

Sum   = A ⊕ B
Carry = A · B

This tiny two-gate circuit is called a half adder, and it is the literal starting block of every binary adder circuit inside every processor, including the one in your phone. Chain enough of these together (with a small addition to also accept an incoming carry, called a full adder), and you can add binary numbers of any length. Two logic gates, wired correctly, are doing arithmetic.

Gates as Code: Verifying the Rules in Python

Because AND, OR, and NOT are just rules mapping 0s and 1s to 0s and 1s, you can also write them as ordinary arithmetic, which is a good way to double check you've really understood the rule rather than memorised a table:

def AND(a, b):
    return a * b              # 1 only if both a and b are 1

def OR(a, b):
    return 1 if (a + b) >= 1 else 0

def NOT(a):
    return 1 - a

def XOR(a, b):
    return (a + b) % 2        # remainder after dividing by 2

for a in (0, 1):
    for b in (0, 1):
        print(a, b, AND(a, b), OR(a, b), NOT(a), XOR(a, b))

Trace it by hand before running it. AND uses multiplication, since 0×anything = 0 and 1×1 = 1 — multiplication naturally gives 1 only when both factors are 1. XOR uses "remainder after dividing by 2": 0+0=0, remainder 0; 0+1=1, remainder 1; 1+0=1, remainder 1; 1+1=2, remainder 0 — matching the XOR table exactly, because a sum of two 0-or-1 numbers is only even (remainder 0) when the two numbers were equal. Running the loop for all four combinations of (a, b) prints:

0 0 0 0 1 0
0 1 0 1 1 1
1 0 0 1 0 1
1 1 1 1 0 0

Compare each printed row to the truth tables built earlier — every column (AND, OR, NOT-of-A, XOR) matches exactly.

Common Misconceptions, Named and Corrected

• "AND means either one." No — that is OR. AND requires all inputs to be 1 simultaneously; it is the strictest of the basic gates.
• "OR means exactly one, not both." No — that is XOR. The digital-logic OR is inclusive: if both inputs are 1, OR still outputs 1. Only XOR excludes the both-1 case.
• "NOT takes two inputs like the other gates." No — NOT is the only gate on this page with a single input. It has one job: flip it.
• "XOR is a basic building-block gate like AND/OR/NOT." Not quite — while manufacturers do sell ready-made XOR chips for convenience, XOR is logically built out of AND, OR, and NOT (A·B' + A'·B), the same way the half-adder is built from XOR and AND.

Summary

A logic gate is a circuit rule that turns one or more input bits (0 or 1) into a single output bit. Because inputs are limited to 0 and 1, we can list every possible case in a truth table, with 2n rows for n inputs. NOT flips a single bit. AND needs every input to be 1. OR needs at least one input to be 1. XOR needs the inputs to differ — the exact rule your two-way staircase light switch follows, wired entirely from mechanical switches with no chip at all. NAND, NOR, and XNOR are their inverted counterparts, and NAND alone is powerful enough to build every other gate, which is why real chips lean on it heavily. Chaining gates lets you evaluate any Boolean expression, one sub-term at a time, and chaining just an XOR gate with an AND gate gives you a half adder — the first working piece of the arithmetic hardware inside every calculator and computer.

Practice: Active Recall

1. Without looking back at the tables, write the full 4-row truth table for OR.
2. A smart plug turns a room heater ON only when "temperature sensor reads LOW" is 1 and "someone is present" is 1. Which gate is this, and why not OR?
3. Build the truth table for Y = (A + B)·C' (all 8 rows, showing your working column by column, the way we did for A·B + C').
4. A half adder computes Sum and Carry for A=1, B=0. What are Sum and Carry, and what decimal number do they represent together?
5. Explain, in one sentence, why flipping just one staircase switch always toggles the bulb, using the word "XOR."

Answers: (1) 0,0→0; 0,1→1; 1,0→1; 1,1→1. (2) AND — the heater should only run when both conditions hold at once; OR would also switch it on when only one condition is true, wasting electricity or missing the point of the sensor. (3) Rows (A,B,C): 000→A+B=0,C'=1,Y=0·1=0; 001→A+B=0,C'=0,Y=0; 010→A+B=1,C'=1,Y=1; 011→A+B=1,C'=0,Y=0; 100→A+B=1,C'=1,Y=1; 101→A+B=1,C'=0,Y=0; 110→A+B=1,C'=1,Y=1; 111→A+B=1,C'=0,Y=0. (4) Sum = 1⊕0 = 1, Carry = 1·0 = 0. Reading Carry-then-Sum as a 2-bit binary number gives "01", which is decimal 1 — matching A+B = 1+0 = 1. (5) Toggling one switch always changes whether the two switch positions match, and since the bulb state is the XOR of the two positions, a change in "do they match" always flips the XOR output.