Chapter 19 · Electronic Devices

19.3 Logic Gates

A logic gate takes inputs that are either 0 or 1 and gives an output fixed by a simple rule: OR $Y=A+B$, AND $Y=A\cdot B$, NOT $Y=\overline{A}$, and their inverted forms NAND and NOR. With truth tables, waveforms and De Morgan's theorems you can name the gate hidden in any small circuit — and build every other gate from NAND or NOR alone.

Every photo on your phone, every song it streams and every JEE answer sheet scanned by an optical reader is stored and processed as long strings of just two symbols, 0 and 1. A modern processor handles billions of them every second, and it does so with circuits built from a handful of very simple decision-making blocks called logic gates. Each gate looks at one or two inputs, each of which is either "high" or "low", and sets its output high or low according to a fixed rule — "high if any input is high", "high only if all inputs are high", "the opposite of the input". Chain enough of these together and you get adders, memories, traffic-light controllers, lift interlocks and, eventually, a computer.

In Section 19.1 and Section 19.2 we met diodes, which conduct one way only — already a kind of switch. In this section we leave the device physics behind and study the logic: digital signals and binary numbers, the five gates on the JEE Main list (OR, AND, NOT, NAND and NOR) with their symbols, Boolean expressions and truth tables, reading inputs and outputs as waveforms, De Morgan's theorems, and why NAND and NOR are called universal gates. JEE Main asks one logic-gate question in most shifts — usually "which single gate is this circuit equivalent to?" or "what is the output waveform?" — and with the methods below it is one of the quickest four marks in the paper.

Digital signals and binary logic

The voltage from a microphone rises and falls smoothly with the pressure of the sound wave; it can take any value within its range. Such a signal is analogue. A digital signal, by contrast, is allowed only two levels. In a typical circuit powered from $5\ \text{V}$, any voltage close to $0\ \text{V}$ counts as one level and any voltage close to $5\ \text{V}$ as the other; the exact value does not matter as long as it is clearly in one band or the other. That is the great strength of digital electronics: a little noise picked up on the way changes an analogue signal for ever, but it leaves a digital signal readable, because a "nearly $5\ \text{V}$" is still unmistakably high.

📘 Definition 19.12 — Analogue and digital signals; positive logic

An analogue signal is a voltage (or current) that varies continuously and can take any value in a range. A digital signal takes only two discrete levels, high and low, written as the binary digits (bits) 1 and 0.

In positive logic — the convention used throughout this course and in JEE Main — the higher voltage level stands for 1 and the lower one (usually close to $0\ \text{V}$) for 0.

A quantity that can only be 0 or 1 is called a logical or Boolean variable, after George Boole, who in 1854 worked out an algebra for statements that are either true (1) or false (0). We write inputs as capital letters $A$, $B$, $C$, … and the output as $Y$.

📘 Definition 19.13 — Logic gate and truth table

A logic gate is a digital circuit with one or more inputs and one output, in which the output (0 or 1) is fixed by the present inputs according to a definite logical rule. The rule is written as a Boolean expression for $Y$, and listed in full in a truth table: a table with one row for every possible combination of the inputs and the output for each.

With $n$ inputs, each 0 or 1, there are $2^n$ combinations, so a truth table has $2^n$ rows: 2 rows for one input, 4 for two, 8 for three. The rows are listed in counting order of the binary number formed by the inputs ($00,01,10,11$ for $AB$).

Boolean algebra uses three operations, which we shall meet as gates in a moment: OR, written as a "sum" $A+B$; AND, written as a "product" $A\cdot B$ (or just $AB$); and NOT, written with a bar, $\overline{A}$. They look like ordinary arithmetic, but they are not: the variables can only be 0 or 1, and in particular $1+1=1$ in Boolean algebra ("true or true" is simply true). As in arithmetic, AND is done before OR unless brackets say otherwise: $A+B\cdot C$ means $A+(B\cdot C)$. The rules below follow from the truth tables and save a lot of work when simplifying a circuit.

📐 Result 19.9 — Rules of Boolean algebra

For Boolean variables $A$, $B$, $C$ (each equal to 0 or 1):

  • with 0 and 1: $\ A+0=A$, $\ A+1=1$, $\ A\cdot0=0$, $\ A\cdot1=A$;
  • with itself: $\ A+A=A$, $\ A\cdot A=A$, $\ A+\overline{A}=1$, $\ A\cdot\overline{A}=0$, $\ \overline{\overline{A}}=A$;
  • order and grouping do not matter: $\ A+B=B+A$, $\ A\cdot B=B\cdot A$, $\ (A+B)+C=A+(B+C)$, $\ (AB)C=A(BC)$;
  • distributive laws: $\ A\cdot(B+C)=A\cdot B+A\cdot C\ $ and also $\ A+B\cdot C=(A+B)\cdot(A+C)$;
  • absorption: $\ A+A\cdot B=A$, $\ A\cdot(A+B)=A$, $\ A+\overline{A}\cdot B=A+B$.

Each rule can be proved by checking every combination of the variables in a truth table (only 2, 4 or 8 cases). The second distributive law and the absorption rules have no counterpart in ordinary algebra.

For example, $A+\overline{A}\cdot B=A+B$: if $A=1$ both sides are 1; if $A=0$ the left side is $\overline{0}\cdot B=B$ and the right side is $B$. Two cases, done. This "split on one variable" trick is often the fastest proof in an exam.

A logic gate has three inputs $A$, $B$ and $C$. The number of rows in its complete truth table is

The basic gates: OR, AND and NOT

Think of a lamp $Y$ and two switches $A$ and $B$, where a closed switch means 1 and a glowing lamp means 1. If the switches are in parallel, the lamp glows when $A$ or $B$ (or both) is closed. If they are in series, it glows only when $A$ and $B$ are both closed. If a single switch is wired so that closing it short-circuits the lamp, the lamp glows only when the switch is not closed. These three behaviours are the three basic gates.

📘 Definition 19.14 — OR, AND and NOT gates
  • OR gate (two or more inputs): the output is 1 if at least one input is 1; it is 0 only when every input is 0. Boolean expression $\ Y=A+B$ (read "$A$ OR $B$").
  • AND gate (two or more inputs): the output is 1 only if every input is 1; it is 0 if any input is 0. Boolean expression $\ Y=A\cdot B$ (read "$A$ AND $B$").
  • NOT gate or inverter (exactly one input): the output is the complement of the input, $1\to0$ and $0\to1$. Boolean expression $\ Y=\overline{A}$ (read "NOT $A$" or "$A$ bar").

The circuit symbols are shown in the figure below: the OR gate has a curved back and a pointed front, the AND gate a flat back and a round front, the NOT gate is a triangle with a small circle (the "bubble") at its output. A bubble anywhere on a symbol means "invert here".

$A$$B$$A+B$
000
011
101
111
OR
$A$$B$$A\cdot B$
000
010
100
111
AND
$A$$\overline{A}$
01
10
NOT
The five gates of the JEE Main syllabus. A bubble at the output means the output is inverted: NAND = AND + NOT, NOR = OR + NOT.

How real gates are made. The OR and AND gates can be built from the diodes of Section 19.2 and a resistor. For a diode OR gate, connect each input to the p-side of its own diode, join the n-sides at the output and connect the output to earth through a resistor. If any input is at $5\ \text{V}$, its diode is forward biased and the output rises to about $5-0.7=4.3\ \text{V}$ — high; only when both inputs are at $0\ \text{V}$ does no current flow, leaving the output at $0\ \text{V}$. For a diode AND gate, reverse the diodes and connect the output to $+5\ \text{V}$ through the resistor: if any input is at $0\ \text{V}$, its diode conducts and drags the output down to about $0.7\ \text{V}$ — low; only when both inputs are high is the output high. A NOT gate cannot be made from diodes and resistors alone (it must make the output high precisely when the input is low, which needs an active switching device such as a transistor); in practice all gates are made from transistors on a chip. For JEE Main only the logic matters, not the circuit inside.

Gates with more inputs follow the same wording: a three-input AND gate gives $Y=A\cdot B\cdot C$, which is 1 in just one of its 8 rows ($111$); a three-input OR gate gives $Y=A+B+C$, which is 0 in just one row ($000$).

Waveforms (timing diagrams). In practice the inputs change with time, and JEE Main often draws them as square waveforms: a line that sits at the high level while the input is 1 and at the low level while it is 0. Because a gate's output depends only on the present inputs, the output waveform is found one time interval at a time.

🧭 Problem-solving strategy — Output waveform of a gate
  1. Draw vertical lines through every instant at which any input changes. Between two neighbouring lines, all inputs are constant.
  2. In each interval, read the inputs as bits and write them down, e.g. $A=1$, $B=0$.
  3. Apply the gate's truth table to each interval and write the output bit.
  4. Join the output bits into a waveform. Check one easy feature: an AND output is never high when either input is low; an OR output is never low when either input is high; a NAND/NOR output is exactly the AND/OR output turned upside down.
✏️ Example 1 — A three-input expression
A circuit has three inputs and output $Y=(A+B)\cdot\overline{C}$. (a) Say which gates are needed to build it. (b) Write its complete truth table. (c) In how many rows is $Y=1$? (d) Find $Y$ when all three inputs are 1.
(a) An OR gate for $A+B$, a NOT gate for $\overline{C}$, and an AND gate combining the two results.
(b) Three inputs: $2^3=8$ rows, in counting order of $ABC$.
$A$$B$$C$$A+B$$\overline{C}$$Y$
000010
001000
010111
011100
100111
101100
110111
111100
(c) $Y=1$ in 3 rows: $ABC=010$, $100$ and $110$.
(d) $Y=(1+1)\cdot\overline{1}=1\cdot0=0$.
⏱ Shortcut Count without the table: $Y=1$ needs $C=0$ (half the rows, 4) and $A+B=1$, which fails only for $AB=00$. So $4-1=3$ rows.
✏️ Example 2 — Reading waveforms
The waveforms $A$ and $B$ below are applied to the two inputs of a gate; each interval lasts $1\ \text{ms}$. Find the output waveform, written as a string of bits, and the total time for which the output is high, if the gate is (a) AND, (b) OR, (c) NAND, (d) NOR.
Read Interval by interval: $A=$ 1 1 0 0 1 0, $\ B=$ 1 0 1 0 1 1.
(a) AND, 1 only when both are 1: 1 0 0 0 1 0 — high for $2\ \text{ms}$.
(b) OR, 0 only when both are 0: 1 1 1 0 1 1 — high for $5\ \text{ms}$.
(c) NAND, the AND output inverted: 0 1 1 1 0 1 — high for $4\ \text{ms}$.
(d) NOR, the OR output inverted: 0 0 0 1 0 0 — high for $1\ \text{ms}$.
Check AND and NAND are complements, so their high times add up to the full $6\ \text{ms}$: $2+4=6$ ✓; likewise OR and NOR: $5+1=6$ ✓.

In Interactive 1 choose the NOR gate and let the timing diagram play. Out of the 8 time slots, in how many is the output $Y$ high?

With NOR selected the readouts show "rows with $Y=1$: 1 of 4" and "slots with $Y=1$: 2 of 8". The input pattern is $A=$ 0 0 1 1 0 1 1 0, $B=$ 0 1 0 1 1 1 0 0; NOR is high only when both inputs are 0, which happens in the first and the last slot. Every input combination occurs twice in this pattern, so each gate is high in twice as many slots as it has 1-rows in its truth table (6 slots would be OR or NAND).
Interactive 1 — Gate Explorer: Symbol, Truth Table and Timing Diagram

Choose a gate. Press Play to run the input waveforms $A$ and $B$ through it: the cursor moves along the timing diagram, the wires on the symbol light up green when they carry a 1, and the matching truth-table row is highlighted. Pause and use the A and B buttons to set the inputs yourself — the shaded slots of the timing diagram are the ones with the same inputs, and so the same output.

Boolean expression—
output $Y$ now—
rows with $Y=1$—
slots with $Y=1$—

A lamp is connected to a battery through two switches $A$ and $B$ placed in series (closed switch = 1, lamp on = 1). The lamp behaves as the output of

NAND and NOR gates, De Morgan's theorems and universal gates

Put a NOT gate after an AND gate and you get a new gate whose output is 1 except when all the inputs are 1. Put a NOT gate after an OR gate and the output is 1 only when all the inputs are 0. These two combinations are so useful that they are made as single gates, drawn with the AND or OR symbol and a bubble on the output.

📘 Definition 19.15 — NAND and NOR gates
  • NAND gate (NOT-AND): $\ Y=\overline{A\cdot B}$. The output is 0 only when every input is 1; otherwise it is 1.
  • NOR gate (NOT-OR): $\ Y=\overline{A+B}$. The output is 1 only when every input is 0; otherwise it is 0.

The bar covers the whole expression: $\overline{A\cdot B}$ is not the same as $\overline{A}\cdot\overline{B}$.

$A$$B$$\overline{A\cdot B}$
001
011
101
110
NAND
$A$$B$$\overline{A+B}$
001
010
100
110
NOR
$A$$B$$\overline{A}$$\overline{B}$$\overline{A}+\overline{B}$$\overline{A}\cdot\overline{B}$
001111
011010
100110
110000
inverted inputs

Compare the columns. The NAND column $1,1,1,0$ is exactly the column of $\overline{A}+\overline{B}$, and the NOR column $1,0,0,0$ is exactly the column of $\overline{A}\cdot\overline{B}$. These two identities are De Morgan's theorems — the most useful tool for identifying a combination of gates.

📐 Theorem 19.10 — De Morgan's theorems

For any Boolean variables $A$ and $B$:

$$\overline{A+B}=\overline{A}\cdot\overline{B},$$ $$\overline{A\cdot B}=\overline{A}+\overline{B}.$$

In words: break the bar and change the sign — the complement of an OR is the AND of the complements, and the complement of an AND is the OR of the complements. Both extend to any number of variables, e.g. $\overline{A+B+C}=\overline{A}\cdot\overline{B}\cdot\overline{C}$. Proof: the truth tables above agree in every one of the four rows.

Bubbles on the inputs. De Morgan's theorems say that a gate can be redrawn by swapping AND $\leftrightarrow$ OR and moving the bubbles from the output to the inputs (or back). So an AND gate whose two inputs are first inverted, $\overline{A}\cdot\overline{B}$, is a NOR gate, and an OR gate with inverted inputs, $\overline{A}+\overline{B}$, is a NAND gate. Two bubbles on the same line cancel, since $\overline{\overline{A}}=A$. JEE Main loves exactly these disguises.

📐 Result 19.11 — NAND and NOR are universal gates

Every logic function — in particular NOT, AND and OR — can be built using NAND gates only, or using NOR gates only. For two-input gates:

  • NOT: one NAND (or one NOR) with its inputs joined: $\overline{A\cdot A}=\overline{A}$, $\ \overline{A+A}=\overline{A}$.
  • AND from NAND: a NAND followed by a NAND used as NOT (2 gates): $\overline{\overline{A\cdot B}}=A\cdot B$.
    OR from NOR: a NOR followed by a NOR used as NOT (2 gates): $\overline{\overline{A+B}}=A+B$.
  • OR from NAND: invert each input with a NAND, then NAND the results (3 gates): $\overline{\overline{A}\cdot\overline{B}}=\overline{\overline{A}}+\overline{\overline{B}}=A+B$.
    AND from NOR: invert each input with a NOR, then NOR the results (3 gates): $\overline{\overline{A}+\overline{B}}=\overline{\overline{A}}\cdot\overline{\overline{B}}=A\cdot B$.

Since NOT, AND and OR together can build any truth table, so can NAND alone or NOR alone. (The other inputs-joined option also works: a NAND with one input held at 1 is a NOT gate, $\overline{A\cdot1}=\overline{A}$; a NOR with one input held at 0 is a NOT gate, $\overline{A+0}=\overline{A}$.)

This is why chip makers love NAND gates: a factory that makes one kind of gate very well can make anything. A whole computer — the guidance computer that took Apollo astronauts to the Moon — was built from about 5600 identical three-input NOR gates and nothing else.

✏️ Example 3 — Building gates from NOR gates only
Using two-input NOR gates only, show how to make (a) a NOT gate, (b) an OR gate and (c) an AND gate. In each case state how many NOR gates are used and prove that the circuit works with a truth table or with De Morgan's theorems.
(a) One NOR with both inputs connected to $A$: $Y=\overline{A+A}=\overline{A}$ (since $A+A=A$). Table: $A=0\Rightarrow\overline{0+0}=1$; $A=1\Rightarrow\overline{1+1}=0$ ✓. 1 gate.
(b) First NOR: $P=\overline{A+B}$. Feed $P$ to both inputs of a second NOR: $Y=\overline{P}=\overline{\overline{A+B}}=A+B$. 2 gates.
(c) NOR 1 (inputs joined) gives $P=\overline{A}$; NOR 2 gives $Q=\overline{B}$; NOR 3 combines them: $Y=\overline{P+Q}=\overline{\overline{A}+\overline{B}}$. By De Morgan, $\overline{\overline{A}+\overline{B}}=\overline{\overline{A}}\cdot\overline{\overline{B}}=A\cdot B$. 3 gates.
Check (c) row by row: $AB=00$: $P=Q=1$, $Y=\overline{1+1}=0$; $01$: $P=1,Q=0$, $Y=0$; $10$: $Y=0$; $11$: $P=Q=0$, $Y=\overline{0+0}=1$. Output column $0,0,0,1$ — AND ✓.
⏱ Shortcut "Same family is quick, cross family needs three": NAND→AND and NOR→OR take 2 gates; NAND→OR and NOR→AND take 3.
✏️ Example 4 — Bubbles on the inputs
The inputs $A$ and $B$ each pass through a NOT gate, and the two inverted signals then enter a single gate $G$. Name the single gate the whole circuit is equivalent to when $G$ is (a) AND, (b) OR, (c) NAND, (d) NOR. For case (b), in how many of the four rows of the truth table is the output 1?
Find the number of rows with output 1 in case (b) before you open the solution:
(a) $Y=\overline{A}\cdot\overline{B}=\overline{A+B}$ (De Morgan): a NOR gate.
(b) $Y=\overline{A}+\overline{B}=\overline{A\cdot B}$: a NAND gate. Its output is 1 in 3 rows (all except $AB=11$).
(c) $Y=\overline{\overline{A}\cdot\overline{B}}=\overline{\overline{A}}+\overline{\overline{B}}=A+B$: an OR gate.
(d) $Y=\overline{\overline{A}+\overline{B}}=\overline{\overline{A}}\cdot\overline{\overline{B}}=A\cdot B$: an AND gate.
⏱ Shortcut Inverting both inputs swaps AND $\leftrightarrow$ OR and toggles the output bubble: AND→NOR, OR→NAND, NAND→OR, NOR→AND. Learn this little table — it answers a whole family of JEE questions in seconds.

By De Morgan's theorem, the output of a NAND gate, $\overline{A\cdot B}$, is equal to

Combinations of gates: finding the overall gate

A typical JEE Main question shows three or four gates wired together and asks which single gate the combination is equivalent to, or what its output is for given inputs or waveforms. There are two reliable methods, and a good candidate uses one to check the other.

🧭 Problem-solving strategy — Identifying a combination of gates
  1. Label every intermediate wire ($P$, $Q$, …) from the inputs towards the output.
  2. Truth-table method: list all input combinations (4 rows for two inputs) and fill in $P$, $Q$, …, $Y$ row by row. Compare the $Y$ column with the five known columns: AND $0001$, OR $0111$, NAND $1110$, NOR $1000$ (rows in the order $AB=00,01,10,11$).
  3. Algebra method: write $Y$ as a Boolean expression, then simplify with De Morgan's theorems and the rules of Result 19.9 (watch for double bars, $\overline{\overline{X}}=X$, and for absorption).
  4. For a quick check, the number of rows with $Y=1$ already narrows the choice: one row → AND or NOR; three rows → OR or NAND.

A combination that is not one of the five. Some useful combinations do not reduce to a single basic gate. The most famous takes $A$ and $B$ into an OR gate and a NAND gate at the same time and feeds both outputs to an AND gate: $Y=(A+B)\cdot\overline{A\cdot B}$. Its output is 1 when exactly one input is 1 — that is, when the inputs differ — with column $0110$. (Engineers call it "exclusive OR"; it is the heart of the circuit that adds binary digits. For JEE Main treat it simply as a combination of the gates you know and work it out row by row.) An inverter on its output gives a circuit that is 1 when the inputs are equal, column $1001$.

✏️ Example 5 — Which single gate is this?
The inputs $A$ and $B$ are both connected to a NOR gate (output $P$) and to a NAND gate (output $Q$). $P$ and $Q$ are the inputs of a second NOR gate, whose output is $Y$. (a) Make the truth table and identify the single gate equivalent to the circuit. (b) Confirm the result with Boolean algebra. (c) In how many rows of the truth table is $Y=1$?
Find the number of rows with $Y=1$ first:
(a)
$A$$B$$P=\overline{A+B}$$Q=\overline{A\cdot B}$$Y=\overline{P+Q}$
00110
01010
10010
11001
The column $0001$ is that of an AND gate.
(b) $Y=\overline{P+Q}=\overline{P}\cdot\overline{Q}$ (De Morgan) $=\overline{\overline{A+B}}\cdot\overline{\overline{A\cdot B}}=(A+B)\cdot(A\cdot B)$. By absorption, $(A+B)\cdot AB=AB$ — so $Y=A\cdot B$ ✓.
(c) Only for $A=B=1$: 1 row.
⏱ Shortcut A final NOR is 1 only when all its inputs are 0. $Q$ (a NAND) is 0 only for $AB=11$, and there $P=0$ too. One row, $AB=11$: AND.
✏️ Example 6 — Waveforms through a combination
The waveforms $A$ and $B$ below, made of intervals of $2\ \mu\text{s}$ each, are fed to the circuit $Y=(A+B)\cdot\overline{A\cdot B}$ (an OR gate and a NAND gate, both driven by $A$ and $B$, feeding an AND gate). (a) Find the output as a string of bits. (b) For how long in total is $Y$ high? (c) Describe in words when $Y$ is high.
Find the total time for which $Y$ is high:
Read $A=$ 0 1 1 0 1 0 1 1, $\ B=$ 0 0 1 1 1 0 0 1.
(a) OR: 0 1 1 1 1 0 1 1; NAND: 1 1 0 1 0 1 1 0; AND of the two: $Y=$ 0 1 0 1 0 0 1 0.
(b) $Y$ is high in 3 intervals: $3\times2=6\ \mu\text{s}$.
(c) $Y=1$ exactly when the inputs differ: OR needs at least one 1, NAND forbids two 1s, so exactly one input must be 1.
⏱ Shortcut Recognise the combination, then just compare the two input strings: mark the intervals where they disagree (2nd, 4th, 7th).

In Interactive 2 select OR from three NAND gates, pause, and set $A=0$, $B=1$. What are the intermediate outputs $P$, $Q$ and the output $Y$, and which single gate does the circuit act as?

With $A=0$, $B=1$ the readouts show $P=1$, $Q=0$, $Y=1$ and "acts as: OR gate". Each first-stage NAND has its inputs joined, so it is a NOT gate: $P=\overline{A}=1$, $Q=\overline{B}=0$. The last NAND gives $\overline{1\cdot0}=1$. Let it play through all four rows: the $Y$ column is $0,1,1,1$ — the OR column, as De Morgan predicts: $\overline{\overline{A}\cdot\overline{B}}=A+B$. (A NAND gate would also give 1 in this row; it differs only in the row $A=B=1$.)
Interactive 2 — Combination Lab: Universal Gates and Disguised Gates

Pick a circuit. Press Play to step through every row of its truth table, or pause and set the inputs with the A and B buttons. Every wire is labelled with its value and turns green when it carries a 1; the table fills in the intermediate outputs $P$, $Q$ and the output $Y$, and the last readout names the single gate the whole circuit is equivalent to.

inputs—
intermediate $P,\ Q$—
output $Y$—
acts as—
⚠️ JEE Main traps

1. The long bar versus two short bars. $\overline{A\cdot B}$ (NAND) is not $\overline{A}\cdot\overline{B}$ (which is NOR), and $\overline{A+B}$ (NOR) is not $\overline{A}+\overline{B}$ (which is NAND). Break the bar and change the sign.

2. Boolean "addition" is not arithmetic. $1+1=1$ and $A+A=A$; there is no "carry". Likewise $A\cdot A=A$, not $A^2$.

3. Joined inputs. A NAND or NOR with its two inputs tied together is a NOT gate — but an AND or OR with tied inputs just passes the signal through ($A\cdot A=A$, $A+A=A$). Look carefully for the bubble.

4. Missing a row or an interval. Two inputs need all four rows; three inputs need eight. In waveform questions, mark every instant at which either input changes — an interval in which only one input changes is easy to skip.

5. Gate counts. NAND → AND and NOR → OR need 2 gates; NAND → OR and NOR → AND need 3; NOT needs 1. Mixing these up is the commonest wrong answer to "minimum number of gates".

The output of an AND gate (inputs $A$, $B$) is connected to both inputs of a NOR gate. The whole circuit is equivalent to

Exercises

Positive logic is used throughout: 1 = high, 0 = low. Truth-table rows are listed in counting order ($AB=00,01,10,11$). Enter outputs as 0 or 1 and counts as whole numbers.

I
Digital signals, truth tables and the basic gates.
  • 1 How many rows are there in the complete truth table of a gate with (a) 3 inputs, (b) 5 inputs?
  • 2 Write the Boolean expression for a three-input OR gate. In how many rows of its truth table is the output 1?
  • 3 Write the Boolean expression for a three-input AND gate. In how many rows of its truth table is the output 1, and which?
  • 4 Find $Y=A+B\cdot C$ for (a) $A=0$, $B=1$, $C=1$; (b) $A=0$, $B=1$, $C=0$.
  • 5 Find $Y=\overline{A}\cdot(B+C)$ for (a) $A=0$, $B=0$, $C=1$; (b) $A=1$, $B=1$, $C=1$.
  • 6 A lamp $Y$ is lit through two switches $A$ and $B$ in parallel, the pair being in series with a third switch $C$ (closed = 1). Write $Y$ in Boolean form. In how many of the 8 switch settings is the lamp lit?
  • 7 A digital circuit works with $0\ \text{V}$ and $5\ \text{V}$ levels. Explain what positive logic means here, and why a signal of $4.6\ \text{V}$ picked up with a little noise is still read correctly.
  • 8 Use the rules of Boolean algebra to simplify (a) $A+A\cdot B$; (b) $A\cdot(A+B)$; (c) $A+\overline{A}\cdot B$; (d) $(A+B)\cdot(A+\overline{B})$.
1 $2^n$ rows: (a) $2^3=8$; (b) $2^5=32$.
2 $Y=A+B+C$. It is 0 only for $000$, so it is 1 in $8-1=7$ rows.
3 $Y=A\cdot B\cdot C$. It is 1 only in the single row $ABC=111$.
4 AND before OR: (a) $Y=0+1\cdot1=0+1=1$; (b) $Y=0+1\cdot0=0+0=0$.
5 (a) $Y=\overline{0}\cdot(0+1)=1\cdot1=1$; (b) $Y=\overline{1}\cdot(1+1)=0\cdot1=0$.
6 Parallel = OR, series = AND: $Y=(A+B)\cdot C$. $C=1$ in 4 settings, and $A+B=1$ in 3 of them: lamp lit in 3 settings ($ABC=011,101,111$).
7 In positive logic the higher level, $5\ \text{V}$, stands for 1 and $0\ \text{V}$ for 0. A gate accepts any voltage in a band near $5\ \text{V}$ as 1 and any voltage in a band near $0\ \text{V}$ as 0, so $4.6\ \text{V}$ is still a clear 1; the gate's output is then restored to a clean high level, so noise does not build up from stage to stage as it would for an analogue signal.
8 (a) $A+AB=A(1+B)=A\cdot1=A$. (b) $A(A+B)=AA+AB=A+AB=A$. (c) $A+\overline{A}B=A+B$ (split on $A$: $A=1$ gives $1=1$; $A=0$ gives $B=B$). (d) $(A+B)(A+\overline{B})=A+B\overline{B}=A+0=A$ (second distributive law).
II
NAND and NOR gates, De Morgan's theorems and universal gates.
  • 1 Write the truth tables of two-input NAND and NOR gates. In how many rows of the truth table of a three-input NAND gate is the output 1?
  • 2 Show, with truth tables, that a NAND gate and a NOR gate each act as a NOT gate when their two inputs are joined.
  • 3 Draw an AND gate made from NAND gates only. How many NAND gates are needed?
  • 4 Draw an OR gate made from NOR gates only, and prove that it works.
  • 5 How many two-input NOR gates are needed to build an AND gate? Draw the circuit.
  • 6 Prove De Morgan's theorem $\overline{A\cdot B}=\overline{A}+\overline{B}$ with a truth table.
  • 7 Simplify $Y=\overline{\overline{A}+\overline{B}}$ and name the single gate it represents.
  • 8 One input of a NAND gate is held at 1 and the other is $A$. What is the output? What is the output if the fixed input is held at 0 instead?
  • 9 Show that a NAND gate with inputs $A$ and $\overline{A}$ always gives 1, and a NOR gate with inputs $A$ and $\overline{A}$ always gives 0.
1 NAND: $1,1,1,0$; NOR: $1,0,0,0$ (rows $00,01,10,11$). A three-input NAND is 0 only for $111$, so it is 1 in $8-1=7$ rows.
2 NAND with $B=A$: $A=0\Rightarrow\overline{0\cdot0}=1$, $A=1\Rightarrow\overline{1\cdot1}=0$. NOR with $B=A$: $A=0\Rightarrow\overline{0+0}=1$, $A=1\Rightarrow\overline{1+1}=0$. Both give $Y=\overline{A}$.
3 NAND($A$, $B$) followed by a NAND with joined inputs: $Y=\overline{\overline{AB}}=AB$. 2 gates.
4 NOR($A$, $B$) gives $P=\overline{A+B}$; a NOR with both inputs $P$ gives $\overline{P}=A+B$. Table: $Y=0,1,1,1$ ✓. 2 gates.
5 NOR($A$,$A$) $=\overline{A}$, NOR($B$,$B$) $=\overline{B}$, then NOR: $\overline{\overline{A}+\overline{B}}=AB$. 3 gates.
6 Rows $00,01,10,11$: $AB=0,0,0,1$ so $\overline{AB}=1,1,1,0$; $\overline{A}=1,1,0,0$, $\overline{B}=1,0,1,0$, so $\overline{A}+\overline{B}=1,1,1,0$. Equal in every row ✓.
7 De Morgan: $\overline{\overline{A}+\overline{B}}=\overline{\overline{A}}\cdot\overline{\overline{B}}=A\cdot B$ — an AND gate.
8 $\overline{A\cdot1}=\overline{A}$: a NOT gate. With the fixed input at 0, $\overline{A\cdot0}=\overline{0}=1$ whatever $A$ is: the output is stuck at 1.
9 $A\cdot\overline{A}=0$ always, so $\overline{A\cdot\overline{A}}=1$; $A+\overline{A}=1$ always, so $\overline{A+\overline{A}}=0$.
III
Waveforms and timing diagrams. Parts 1–5 use the waveforms below, each interval lasting $1\ \mu\text{s}$.
  • 1 Find the output of an AND gate as a bit string. For how many microseconds is it high?
  • 2 Repeat for an OR gate.
  • 3 Repeat for a NAND gate, and check your answer against part 1.
  • 4 Repeat for a NOR gate.
  • 5 The waveforms are fed to the combination $Y=(A+B)\cdot\overline{A\cdot B}$. For how many microseconds is $Y$ high?
  • 6 $A$ is a square wave of period $2\ \text{ms}$ and $B$ a square wave of period $4\ \text{ms}$; both start high at $t=0$ and are high for the first half of each period. They are fed to an AND gate. For how many milliseconds between $t=0$ and $t=12\ \text{ms}$ is the output high, and what is the frequency of the output?
  • 7 An unknown two-input gate gives $Y=$ 1 0 0 0 for $A=$ 0 0 1 1, $B=$ 0 1 0 1. Name it. Which gate would give $Y=$ 1 1 1 0?
  • 8 Input $A$ of a NOR gate is held at 0 while $B$ is a $1\ \text{kHz}$ square wave. Describe the output. What happens if $A$ is held at 1 instead?
1 $A=$ 1 0 1 1 0 0 1 0, $B=$ 1 1 0 1 0 1 0 0. AND: 1 0 0 1 0 0 0 0 — high for $2\ \mu\text{s}$.
2 OR: 1 1 1 1 0 1 1 0 — high for $6\ \mu\text{s}$.
3 NAND: 0 1 1 0 1 1 1 1 — high for $6\ \mu\text{s}$; $2+6=8\ \mu\text{s}$, the whole time ✓.
4 NOR: 0 0 0 0 1 0 0 1 — high for $2\ \mu\text{s}$.
5 High where the inputs differ: 0 1 1 0 0 1 1 0 — $4\ \mu\text{s}$. (Check: it is OR AND NAND, interval by interval.)
6 $A$ is high in $[0,1)$, $[2,3)$, $[4,5)$, …; $B$ in $[0,2)$, $[4,6)$, $[8,10)$ ms. Both high in $[0,1)$, $[4,5)$, $[8,9)$: $3\ \text{ms}$. The output repeats every $4\ \text{ms}$, so its frequency is $1/(4\ \text{ms})=250\ \text{Hz}$.
7 $1000$ is 1 only when both inputs are 0: a NOR gate. $1110$ is 0 only when both are 1: a NAND gate.
8 $\overline{0+B}=\overline{B}$: the output is the inverted square wave, still $1\ \text{kHz}$. With $A=1$, $\overline{1+B}=0$: the output stays low.
IV
Combinations of gates — JEE Main level.
  • 1 The output of a NOR gate (inputs $A$, $B$) passes through a NOT gate. Name the single equivalent gate.
  • 2 $A$ passes through a NOT gate; $\overline{A}$ and $B$ are the inputs of a NAND gate. Find $Y$ in simplest form, and its value for $A=0$, $B=1$.
  • 3 $A$ and $B$ feed both a NAND gate and an OR gate, whose outputs feed an AND gate. In how many rows of the truth table is $Y=1$?
  • 4 $P$ is the output of a NAND gate with inputs $A$ and $B$; $Y$ is the output of a second NAND gate with inputs $A$ and $P$. Show that $Y=\overline{A}+B$ and find the number of rows in which $Y=1$.
  • 5 The output of a NOR gate (inputs $A$, $B$) and a third input $C$ are the inputs of an AND gate. In how many of the 8 rows is $Y=1$?
  • 6 For $Y=A\cdot B+\overline{C}$, find the number of rows (out of 8) in which $Y=1$.
  • 7 What is the least number of two-input NAND gates needed to make $Y=A\cdot B+C$? Draw the circuit.
  • 8 (Model) A car's warning buzzer $Y$ must sound when the ignition is on ($I=1$) and either a door is open ($D=1$) or the driver's seat belt is not fastened ($S=0$). Write $Y$ in Boolean form and find in how many of the 8 combinations of $I$, $D$, $S$ the buzzer sounds.
1 $\overline{\overline{A+B}}=A+B$: an OR gate.
2 $Y=\overline{\overline{A}\cdot B}=\overline{\overline{A}}+\overline{B}=A+\overline{B}$. For $A=0$, $B=1$: $Y=0+0=0$.
3 $Y=\overline{AB}\cdot(A+B)$: column $0,1,1,0$ — 1 when the inputs differ, in 2 rows.
4 $Y=\overline{A\cdot\overline{AB}}=\overline{A}+\overline{\overline{AB}}=\overline{A}+AB=\overline{A}+B$ (absorption). It is 0 only for $A=1$, $B=0$: 1 in 3 rows.
5 $Y=\overline{A+B}\cdot C=\overline{A}\cdot\overline{B}\cdot C$: only $ABC=001$, 1 row.
6 $\overline{C}=1$ in 4 rows; $AB=1$ in 2 rows ($110$, $111$), one of which ($110$) is already counted: $4+2-1=5$.
7 By De Morgan, $AB+C=\overline{\overline{AB}\cdot\overline{C}}$: NAND($A$,$B$), NAND($C$,$C$) $=\overline{C}$, and a NAND of the two. 3 gates (one gate cannot do it, and two leave one input inverted).
8 $Y=I\cdot(D+\overline{S})$. Need $I=1$ (4 combinations of $D$, $S$), and $D+\overline{S}=1$, which fails only for $D=0$, $S=1$: buzzer sounds in 3 combinations.
🎯 Exam corner JEE Main · MCQJEE Main · Numerical

E1. JEE Main · MCQ Inputs $A$ and $B$ are applied to a NOR gate, and its output is connected to both inputs of a second NOR gate. The combination is equivalent to (A) an AND gate (B) a NAND gate (C) an OR gate (D) a NOR gate

Idea A NOR with joined inputs is a NOT gate, so the second gate inverts $\overline{A+B}$.
Algebra $Y=\overline{\overline{A+B}}=A+B$.
Answer (C).
⏱ Shortcut Two inversions in a row cancel: NOR + NOT = OR. (D) forgets that the second gate inverts.

E2. JEE Main · Numerical Inputs $A$ and $B$ feed an AND gate. Its output and a third input $C$ feed a NOR gate, whose output is $Y$. For how many of the 8 possible combinations of $A$, $B$, $C$ is $Y=1$? Give the answer to the nearest integer.

Expression $Y=\overline{A\cdot B+C}=\overline{AB}\cdot\overline{C}$.
Count Need $C=0$ (4 combinations) and $AB=0$, which fails only for $AB=11$: $4-1=3$.
Answer $3$.
⏱ Shortcut A NOR output is 1 only when all its inputs are 0: $C=0$ and $AB\neq11$.

E3. JEE Main · MCQ Over six equal time intervals the inputs of a NAND gate are $A=$ 0 0 1 1 0 1 and $B=$ 0 1 0 1 1 1. The output over the same intervals is (A) 0 0 0 1 0 1 (B) 0 1 1 1 1 1 (C) 1 0 0 0 0 0 (D) 1 1 1 0 1 0

AND first $A\cdot B=$ 0 0 0 1 0 1 (both 1 only in the 4th and 6th intervals).
Invert NAND $=$ 1 1 1 0 1 0.
Answer (D).
⏱ Shortcut The NAND output is low only where both inputs are high. (A) is AND, (B) is OR and (C) is NOR — every option is one of the other gates.

E4. JEE Main · Numerical Let $a$ be the least number of two-input NAND gates needed to make an AND gate, $b$ the least number of two-input NOR gates needed to make an AND gate, and $c$ the least number of NAND gates needed to make a NOT gate. Find $a+b+c$. Give the answer to the nearest integer.

a NAND then NAND-as-NOT: $\overline{\overline{AB}}=AB$, so $a=2$.
b Invert each input with a NOR, then NOR: $\overline{\overline{A}+\overline{B}}=AB$, so $b=3$.
c One NAND with joined inputs: $c=1$.
Answer $a+b+c=2+3+1=6$.
⏱ Shortcut Same family (NAND→AND) is 2 gates, cross family (NOR→AND) is 3, NOT is 1.

E5. JEE Main · MCQ Input $A$ passes through a NOT gate, and $\overline{A}$ and $B$ are then the inputs of a NOR gate. The output is (A) $Y=A\cdot\overline{B}$ (B) $Y=\overline{A}+B$ (C) $Y=\overline{A}\cdot B$ (D) $Y=A+\overline{B}$

De Morgan $Y=\overline{\overline{A}+B}=\overline{\overline{A}}\cdot\overline{B}=A\cdot\overline{B}$.
Check $Y=1$ needs both NOR inputs 0: $\overline{A}=0$ and $B=0$, i.e. $A=1$, $B=0$ — and $A\cdot\overline{B}$ is 1 only there ✓.
Answer (A).
⏱ Shortcut (B) is the input of the NOR before inversion; (C) and (D) invert the wrong variable. Test one row ($A=1$, $B=0$) to separate them.

E6. JEE Main · Numerical Two square waves, $A$ of frequency $125\ \text{Hz}$ and $B$ of frequency $250\ \text{Hz}$, are applied to a NAND gate. Both waves are high for the first half of each of their periods, starting together at $t=0$. For how many milliseconds between $t=0$ and $t=16\ \text{ms}$ is the output high? Give the answer to the nearest integer.

Periods $T_A=8\ \text{ms}$ (high $0$–$4$, $8$–$12$ ms); $T_B=4\ \text{ms}$ (high $0$–$2$, $4$–$6$, $8$–$10$, $12$–$14$ ms).
Low output NAND is low only when both are high: $0$–$2$ ms and $8$–$10$ ms, a total of $4\ \text{ms}$.
Answer High for $16-4=12$ ms: $12$.
⏱ Shortcut Both high for a quarter of the time (half × half, the waves being in step), so NAND is high $\tfrac34$ of $16\ \text{ms}$.
🔬 Research–Teaching NexusResearch-tutored · optional, about 60 minutes

Research question. Can a complete safety interlock be built from one kind of gate only — and at what input voltage does a real gate decide that a "0" has become a "1"?

Why it matters. Lifts, metro-train doors, industrial presses, microwave ovens and car ignition systems all use interlocks: logic that allows a dangerous action only when every safety condition is met. Engineers routinely build them from a single gate type (Result 19.11) because one chip type is cheaper to stock and test. And a gate is only useful because it treats a whole band of voltages as 1 and another band as 0 (Definition 19.12) — the gap between the bands is what protects a factory controller or an aircraft's flight computer from electrical noise.

What to do.

  1. Choose an interlock, e.g. "a lift moves ($Y=1$) only if the door is shut ($D=1$) and either the call button is pressed ($C=1$) or the lift is already moving ($M=1$)". Write its truth table and its Boolean expression.
  2. Rewrite the expression using NAND only (De Morgan's theorems), and count the gates.
  3. Build it on a breadboard with a quad two-input NAND chip (four gates in one package, a 5 V supply), using switches for the inputs and an LED with a series resistor for the output — or in a free online logic simulator if no kit is available. Check every row of your truth table.
  4. Connect one input of a single NAND to a potentiometer and the other to 5 V. Raise the input voltage slowly from 0 V and record, with a multimeter, the input voltage at which the output switches from high to low, and back again as you lower it.
  5. Repeat step 4 two or three times and with a second gate on the same chip.

Tools: NAND gate chip, breadboard, 5 V supply or USB power bank module, switches, LEDs, resistors (330 Ω, 10 kΩ potentiometer), multimeter; or an online logic-circuit simulator.

Hand in: The truth table, the NAND-only circuit diagram with the gate count, a photo or screenshot of the working circuit, and a table of switching voltages with a sentence on how much noise the gate could tolerate.

Going further. Rebuild the same interlock with NOR gates only. Which version needs fewer gates? Is there a pattern — expressions that are "OR of ANDs" suit NAND, "AND of ORs" suit NOR?

Instructor note: common 5 V CMOS NAND chips switch at roughly half the supply, about 2.2–2.8 V, often with a little hysteresis between rising and falling inputs; TTL-compatible chips switch nearer 1.4 V. Unused inputs must be tied to 0 V or 5 V — a floating input gives erratic results and is itself a good lesson in why digital levels must be well defined. The lift example converted directly, $D\cdot(C+M)$, needs five NAND gates; expanded first to $D\cdot C+D\cdot M=\overline{\overline{DC}\cdot\overline{DM}}$ it needs only three — a nice reward for students who look for the minimum.

🧪 Self-check quiz

0/5 correct

Q1. The output of a two-input NOR gate is 1 when

Q2. The complete truth table of a logic circuit with four inputs has

Q3. The Boolean expression $\overline{A+B}$ is equal to

Q4. A NAND gate whose two inputs are joined together acts as

Q5. Which gate gives an output 0 only when all of its inputs are 1?