Logic Gates & Boolean Basics

Every digital device is a city of logic gates. A modern processor wires tens of billions of transistors into gates, each doing exactly what this article describes — reading two-valued inputs, forcing a two-valued output — a few billion times a second. Adders built from XOR and AND gates do the arithmetic; latches and flip-flops built from cross-coupled NAND or NOR gates hold the bits of memory. Because NAND is universal and cheap to fabricate, whole chips are laid down as uniform NAND arrays and personalised by their wiring — and NAND flash memory, the storage in every phone and SSD, takes its name from the gate structure of its cells. The very idea that a machine can reason — that "if this and not that, then act" can be a voltage — is Shannon's, and it now underlies not just computers but every controller in a car, a pacemaker, or a spacecraft. The next article is the numerical gym where these truth tables meet the band-gap, mass-action and rectifier numbers of the whole chapter.

Digital electronics makes one radical decision: it throws away all voltages except two. Inside a logic chip a wire is not allowed to loiter at $2.7\ \text{V}$ or $3.9\ \text{V}$; the circuit forces it either near the supply rail (HIGH) or near ground (LOW), and reads everything in between as noise to be squeezed out. We label the HIGH state 1 and the LOW state 0 — but the labels are a convention, not a measurement. In classic TTL (transistor–transistor logic) chips the rail is $+5\ \text{V}$, so $1\approx 5\ \text{V}$ and $0\approx 0\ \text{V}$; modern low-power chips use $3.3\ \text{V}$ or less. What matters is only that there are exactly two allowed states, because two states is the minimum you need to say yes or no, true or false — one bit of information. Once a wire carries a truth value, a circuit that combines wires is doing logic. Recall the transistor of the previous article as a switch: driven hard into saturation it is ON (a closed switch, output pulled LOW), starved into cutoff it is OFF (an open switch, output floats HIGH). Recall the diode as a one-way valve. A logic gate is nothing more than a small, deliberate arrangement of these switches and valves whose output voltage is HIGH or LOW according to a fixed rule applied to its input voltages. Shannon's discovery was that these rules are precisely Boole's AND, OR and NOT — so a circuit designer can reason about hardware with pencil-and-paper algebra instead of a voltmeter.

A gate's behaviour is completely fixed once you list its output for every possible set of inputs. That list is the truth table, and it is the single most important object in this chapter — draw it correctly and every question falls out of it. Because each input is a bit that can be $0$ or $1$, a gate with $n$ inputs has

rows in its truth table. where: $n$ is the number of inputs and $N$ is the number of distinct input combinations. The physical reading: two inputs give $2^{2}=4$ rows, three inputs give $2^{3}=8$ rows, and the count doubles with every wire you add — which is exactly why circuits with many inputs grow complicated so fast. (A related count worth knowing: with two inputs there are $2^{4}=16$ different truth tables you could fill in, so there are exactly sixteen possible two-input gates — but only a few have names.)

The OR gate answers "is at least one input true?" Its Boolean expression is $Y=A+B$, read "A OR B," where the $+$ sign is logical OR, not ordinary addition (so $1+1=1$, not $2$). It outputs $0$ only when every input is $0$.

The AND gate answers "are all inputs true?" Its expression is $Y=A\cdot B$, read "A AND B," where the dot is logical AND (which happens to agree with ordinary multiplication for single bits: $1\cdot 1=1$, $1\cdot 0=0$). It outputs $1$ only when every input is $1$.

The NOT gate (also called an inverter) takes a single input and flips it: $Y=\bar A$, read "NOT A" or "A bar." It is the only basic gate with one input, and its truth table has just $2^{1}=2$ rows.

These three are functionally complete: any logic function whatsoever can be written with OR, AND and NOT alone. That is why a Boolean expression like $Y = A\cdot\bar B + \bar A\cdot B$ (which, you can check, is the "exactly one input is 1" or XOR rule) is a perfectly good recipe for a circuit — it says "build two AND gates, two inverters, and an OR gate, and wire them thus."

Symbols and tables are the logic; the previous two articles gave us the hardware to make them real. A diode passes current one way and blocks the other; a transistor, driven hard, snaps between a closed switch (saturation) and an open one (cutoff). Combine them and the abstract gates become circuits you could solder. The NOT gate is a single transistor in common-emitter, exactly the "transistor as a switch" of the last article. Tie the output through a load resistor to the supply $V_{CC}=5\ \text{V}$ and feed the input to the base through a resistor. When the input is HIGH ($5\ \text{V}$), base current drives the transistor into saturation; it conducts hard and pulls the output down to the saturation voltage $V_{CE(\text{sat})}\approx 0.2\ \text{V}$ — a LOW. When the input is LOW ($0\ \text{V}$), no base current flows, the transistor is in cutoff (open switch), and the output floats up to $V_{CC}=5\ \text{V}$ — a HIGH. HIGH in gives LOW out, LOW in gives HIGH out: that is $Y=\bar A$, and it is why the common-emitter stage's built-in $180^\circ$ inversion is the NOT gate. The OR and AND gates can be made from two diodes. In diode OR, the two inputs feed the anodes of two diodes whose cathodes join at the output, which is tied to ground through a resistor. If either input is HIGH, its diode conducts and lifts the output to one diode-drop below the input, $5-0.7=4.3\ \text{V}$ — comfortably a HIGH; only if both inputs are LOW does the output stay at $0\ \text{V}$. In diode AND, the inputs feed the cathodes and the common anode is pulled up to $+5\ \text{V}$ through a resistor. If either input is LOW, its diode conducts and clamps the output down to $0+0.7=0.7\ \text{V}$ — a LOW; only when both inputs are HIGH does no diode conduct and the output rise to $+5\ \text{V}$, a HIGH.

Put an inverter on the output of an OR gate and you get NOR ("NOT-OR"): $Y=\overline{A+B}$. Put one on the output of an AND gate and you get NAND ("NOT-AND"): $Y=\overline{A\cdot B}$. On the symbols this inversion is drawn as a small bubble at the output, so a NOR is the OR shield with a bubble and a NAND is the AND D-shape with a bubble. Their truth tables are just the OR and AND tables with every output flipped.

NOR outputs $1$ only when both inputs are $0$; NAND outputs $0$ only when both inputs are $1$. These inverted gates are tied to the basic ones by De Morgan's theorems, the two most useful identities in all of Boolean algebra. The first says the complement of an OR is the AND of the complements:

where: the bar is logical NOT, $+$ is OR and $\cdot$ is AND. The physical reading: "not (A or B)" means "neither A nor B," i.e. both must be false — which is exactly the word "nor." The second theorem is its mirror image, the complement of an AND being the OR of the complements:

Read aloud: "not (A and B)" means "A is false or B is false." De Morgan lets you push a bar through a bracket by flipping the operation and inverting each term — the single algebraic move that most exam simplifications turn on. You can prove both theorems in one breath by building the truth tables of the two sides and checking they match row for row, which we do in the verification script. Now the punchline of the whole chapter. NAND and NOR are universal gates: with copies of just one of them — nothing else — you can build NOT, AND and OR, and therefore every logic circuit that exists. This is not a mere convenience; it is why a real silicon chip is manufactured as a vast, uniform field of one gate type. One mask, one transistor pattern repeated millions of times, wired into whatever function is wanted.

Boolean algebra is the arithmetic of true and false, and a handful of its laws let you shrink a tangle of gates into a clean expression before you draw a circuit. The variables are $0$ and $1$; the operations are $+$ (OR), $\cdot$ (AND) and the bar (NOT). Many rules look like ordinary algebra, but a few are startling because there are only two values. The basic identities every exam expects:

The two that have no arithmetic analogue are $A+A=A$ (an OR of a signal with itself is just the signal) and $A+1=1$ (OR-ing anything with a constant true is always true). Add the distributive law $A\cdot(B+C)=A\cdot B+A\cdot C$, the absorption law $A+A\cdot B=A$, and the identity $A+\bar A\cdot B=A+B$, and you have enough to simplify almost every school circuit. For instance $Y=A\cdot B+A\cdot\bar B$ factors to $A\cdot(B+\bar B)=A\cdot 1=A$: two gates and an inverter collapse to a plain wire. De Morgan's theorems (2) and (3) complete the toolkit, letting you trade NANDs and NORs for AND/OR/NOT and back. The goal is always the same — fewest gates, cheapest chip.

Board level — output of a two-gate combination (CBSE and ICSE pattern)

In the circuit, inputs A and B go to a NAND gate; its output and input B go to a second NAND gate, whose output is Y. Build the truth table for Y and name the single gate it is equivalent to.

Step 1. First NAND: $P=\overline{A\cdot B}$. Tabulate $P$ for the four input rows: $(0,0)\to1$, $(0,1)\to1$, $(1,0)\to1$, $(1,1)\to0$.

Step 2. Second NAND takes $P$ and $B$: $Y=\overline{P\cdot B}$. Row by row: $(P,B)=(1,0)\to1$; $(1,1)\to0$; $(1,0)\to1$; $(0,1)\to1$.

Step 3. Collect $Y$ against the original $A,B$: $(0,0)\to1$, $(0,1)\to0$, $(1,0)\to1$, $(1,1)\to1$.

Step 4. Compare with the named gates. $Y$ is $0$ only in the row $A=0,B=1$; it is $1$ everywhere else. That is the rule $Y=A+\bar B$ — HIGH unless B alone is HIGH. So the two-NAND network is equivalent to an OR of A with NOT-B. The lesson: chase the signal gate by gate, writing the intermediate column, and only compare to named gates at the end.

Board level — simplify a Boolean expression and count the gates saved (CBSE and JEE pattern)

Simplify $Y=A\cdot B+A\cdot\bar B+\bar A\cdot B$ using Boolean algebra, and state how many gates the simplified form needs.

Step 1. Group the first two terms and factor $A$: $A\cdot B+A\cdot\bar B=A\cdot(B+\bar B)$. By the complement law $B+\bar B=1$, so this is $A\cdot 1=A$.

Step 2. The expression is now $Y=A+\bar A\cdot B$. Apply the identity $A+\bar A\cdot B=A+B$ (or expand: $A+\bar A B=(A+\bar A)(A+B)=1\cdot(A+B)=A+B$).

Step 3. So $Y=A+B$ — a single OR gate. The unsimplified form needed two inverters, three AND gates and one OR (six gates); the simplified form needs one. Confirm by truth table: the original is $1$ for every row except $A=0,B=0$, which is exactly the OR table. The moral for exams: always simplify before drawing — marks (and, in industry, silicon) are won by the shorter expression.

Competitive level — build a half adder and read off its two gates (JEE Main and Advanced pattern)

A half adder adds two single bits A and B and produces a sum bit S and a carry bit C, so that the two-bit binary number $C\,S$ equals $A+B$ in ordinary arithmetic. Work out the truth table for S and C, and identify which gate produces each.

Step 1. Do the binary arithmetic for all four input pairs. $0+0=0$ (so $C=0,S=0$); $0+1=1$ ($C=0,S=1$); $1+0=1$ ($C=0,S=1$); $1+1=10_2$, i.e. two ($C=1,S=0$).

Step 2. Read the S column against $A,B$: $S=0,1,1,0$. That is $1$ when the inputs differ — the XOR rule, $S=A\oplus B=A\bar B+\bar A B$.

Step 3. Read the C column: $C=0,0,0,1$, which is $1$ only when both inputs are $1$ — the AND rule, $C=A\cdot B$.

Step 4. So a half adder is just one XOR gate for the sum and one AND gate for the carry. Sanity check the encoding: in the $1+1$ row, $C\,S=10_2=2$, matching $1+1=2$ — the carry is the "tens" (here "twos") digit, the sum is the "units." This tiny circuit, chained with a carry-in, becomes the full adder that does all the arithmetic in a processor. Timing note: under a minute. The whole item is one line of binary addition per row; the instant you see $S=0110$ down the column, write "XOR," and $C=0001$ is "AND" on sight. Do not derive XOR from scratch — recognise the "outputs 1 when inputs differ" pattern and name it.

Competitive level — count the NAND gates for a target function (JEE Advanced pattern)

Using only 2-input NAND gates, how many are needed to build (a) an inverter, (b) an AND gate, (c) an OR gate, and (d) an XOR gate? Assume inputs and their use as many times as needed.

Step 1. Inverter: tie both inputs of one NAND together, $\text{NAND}(A,A)=\bar A$. One gate.

Step 2. AND: a NAND followed by an inverting NAND, $\overline{\overline{A\cdot B}}=A\cdot B$. That is $1$ (the NAND) $+\,1$ (the inverter) $=$ two gates.

Step 3. OR: by De Morgan, $A+B=\overline{\bar A\cdot\bar B}$ — invert each input (two NANDs) then NAND them (one more). Three gates.

Step 4. XOR: the standard construction is $Y=\overline{\,\overline{A\cdot\overline{AB}}\cdot\overline{B\cdot\overline{AB}}\,}$, which lays out as one NAND for $\overline{AB}$, two NANDs combining it with A and with B, and a final NAND — four gates. So the tally is $1,2,3,4$. The exam point: the more a target gate differs from NAND's own AND-then-invert shape, the more NANDs it costs, and XOR — needing a "differ" test — is the priciest of the common gates. Timing note: about ninety seconds if you have the four counts memorised as $1$–$2$–$3$–$4$ for NOT–AND–OR–XOR. Deriving the four-NAND XOR live under exam pressure is a time sink; recall the count, and if a circuit is given, just verify one or two rows rather than the whole table.

Writing $1+1=2$ in a Boolean line. The $+$ is OR, so $1+1=1$. Every stray "$2$" (or a carry that should not exist) in a truth table costs the row. Keep arithmetic addition and logical OR in separate mental boxes; the half-adder question above is the one place binary addition is intended, and even there the carry is handled by a gate, not by the OR symbol.

Confusing OR with XOR on the $1,1$ row. Plain OR is inclusive: $1+1=1$. The gate that gives $0$ for two $1$s is XOR, a different gate. If a truth table has $0$ in the both-inputs-high row and $1$ in the two mixed rows, it is XOR, not OR.

Forgetting the bubble means invert. A NAND is not an AND, and a NOR is not an OR; the output bubble flips every output. Students who copy the AND table for a NAND lose the whole question. Bubble on the symbol, bar on the expression, flip in the table — all three say the same thing.

Mangling De Morgan. Pushing a bar across a bracket must flip the operation and invert every term: $\overline{A+B}=\bar A\cdot\bar B$, not $\bar A+\bar B$. Writing $\overline{A+B}=\bar A+\bar B$ is the single most common Boolean error on JEE and A-Level papers.

Naming the wrong universal gates. NAND and NOR are the universal ones; AND, OR and NOT individually are not (you cannot build a NOT from AND gates alone, for example). And "universal" means "can build any circuit," not "used most often" — though in practice they are that too.

Board scope. Logic gates, their symbols and truth tables, NAND/NOR as universal gates, and basic Boolean simplification are core on CBSE (Ch. 14), ICSE (ISC), JEE Main, JEE Advanced, and NEET. IGCSE 0625 carries the qualitative gate story — the symbols and truth tables of AND, OR, NOT, NAND, NOR (and often XOR) — but not Boolean-algebra simplification or the universal-gate proofs; an IGCSE answer completes truth tables, it does not manipulate expressions. Note: semiconductor electronics, and therefore logic gates, is not on AP Physics 2, and IB Physics has moved electronics out of its core — do not cite either board for this topic.

Texts. NCERT Physics Class 12, Chapter 14 ("Semiconductor Electronics"), the logic-gates section · H. C. Verma, Concepts of Physics Vol. 2, "Semiconductors and Devices" · Morris Mano, Digital Design, for Boolean algebra and gate minimisation done properly · Floyd, Digital Fundamentals, for the diode/transistor gate circuits.

Provenance. All logic values are exact (Boolean), verified by full truth tables. Recompute: truth tables of OR, AND, NOT, NAND, NOR and XOR; row count $N=2^{n}$ ($2^{2}=4$, $2^{3}=8$); number of distinct 2-input functions $2^{2^{2}}=16$; both De Morgan laws over all four input rows; NAND-built NOT/AND/OR reproducing the basic tables; four-NAND XOR matching $A\oplus B$; NOR universality; Boolean simplifications $A B+A\bar B=A$ and $AB+A\bar B+\bar A B=A+B$; half-adder $S=A\oplus B$, $C=A\cdot B$ with $2C+S=A+B$; gate counts NOT/AND/OR/XOR $=1/2/3/4$ from NAND; and the circuit voltages $V_{CC}=5\ \text{V}$, $V_{CE(\text{sat})}=0.2\ \text{V}$, diode drop $0.7\ \text{V}$, diode-OR HIGH $=5-0.7=4.3\ \text{V}$, diode-AND LOW $=0.7\ \text{V}$, midpoint $2.5\ \text{V}$ — all in verify_hs2-logic-gates.py.

Prerequisites. The Junction Diode & its I–V Curve supplies the one-way valve that steers current in the diode OR and AND gates, and The Bipolar Junction Transistor supplies the saturation/cutoff switch that makes the NOT gate — this article assumes both. Leads to. Semiconductor & Logic Numericals, the chapter's archetype problem set, where these truth tables are worked alongside band-gap, mass-action, rectifier and current-gain sums. For the university seam, digital-design courses take Boolean minimisation (Karnaugh maps, Quine–McCluskey) and sequential logic (flip-flops, state machines) far beyond this page — enrichment only, never an exam dependency here.