Home / Learn / Exam prep / IIT JAM Physics / Lesson 7.7
All lessons

Module 7: Solid state physics and electronics · Lesson 7.7 · about 45 min

Logic gates and Boolean algebra

Binary, hexadecimal, BCD, Gray code and two's complement; every logic gate and why NAND and NOR are universal; the laws of Boolean algebra and De Morgan; simplifying with Karnaugh maps; adders, multiplexers, flip-flops and counters.

Key points, meanings and formulas on one page: choose "Save as PDF" in the print box.

Module 7 · about 45 minutes. By the end you will be able to convert between binary, decimal, hexadecimal, BCD and Gray code, add and subtract in two’s complement and spot overflow, read and build any gate from NAND or NOR alone, simplify Boolean expressions algebraically and with Karnaugh maps, and explain adders, multiplexers, flip-flops and counters.

Digital circuits use only two values, 0 and 1, and a handful of rules for combining them; with those rules any calculation can be built from a single kind of gate.

1. Numbers in base 2

A transistor used as a switch (fully on or fully off, as in lesson 7.5) naturally stores one bit. A string of bits is a number in base 2, each place worth twice the one to its right:

(1011)2=1⋅23+0⋅22+1⋅21+1⋅20=11

To go from decimal to binary, divide by 2 repeatedly and read the remainders from the last one up: 45 gives remainders 1, 0, 1, 1, 0, 1, so 45=(101101)2.

Code Idea Example (decimal 59)
Hexadecimal groups of 4 bits, digits 0 to 9 and A to F (3B)16 = 00111011
Octal groups of 3 bits (73)8
BCD (8421) each DECIMAL digit in its own 4 bits 01011001
Gray code neighbours differ in one bit only binary 111011→100110

To get Gray code, keep the first bit and XOR each pair of neighbouring bits: gi=bi+1⊕︎bi. It is used in shaft encoders, where two bits changing at once could give a false reading.

2. Negative numbers: two’s complement

In an n-bit word, two’s complement gives the top bit a weight of −2n−1. To negate a number, invert every bit and add 1. For 8 bits:

  • +20=00010100; invert: 11101011; add 1: 11101100=−20 (as an unsigned number it is 256−20=236).
  • The range is −128 to +127; there is one zero.
  • Subtraction is addition of the negative: A−B=A+(B‾+1), and the carry out of the top bit is thrown away.

Overflow happens when the true answer is outside the range. It can only occur when both numbers have the same sign, and shows up as a result of the wrong sign.

Worked example. Work out 0110−1001 in 4-bit two’s complement (unsigned 6 − 9).

  1. Two’s complement of 1001: invert to 0110, add 1: 0111.
  2. Add: 0110+0111=1101 (no carry out).
  3. Top bit 1, so negative: invert 1101 to 0010, add 1: 0011=3. The answer is −3, as it should be.

3. The gates

Gate Expression Output is 1 when Truth table for AB = 00, 01, 10, 11
AND AB all inputs are 1 0, 0, 0, 1
OR A+B any input is 1 0, 1, 1, 1
NOT A‾ the input is 0 (one input)
NAND AB not all inputs are 1 1, 1, 1, 0
NOR A+B no input is 1 1, 0, 0, 0
XOR A⊕︎B=A‾B+AB‾ the inputs differ 0, 1, 1, 0
XNOR A⊕︎B the inputs are equal 1, 0, 0, 1
Pick a gate and tap A and B. The lit row of the truth table always matches the lamp. Try NAND with both inputs tied the same way (00 and 11): it behaves as NOT.

NAND and NOR are universal: each can build every other gate by itself.

  • NOT from NAND: tie the inputs together, AA=A‾.
  • AND from NAND: a NAND followed by a NAND-inverter.
  • OR from NAND: invert each input first, then NAND: A‾B‾=A+B.
  • XOR takes four NANDs: with N=AB, the output is AN⋅BN=A⊕︎B.

The same works for NOR with AND and OR swapped. Chips with only NAND gates were the workhorse of early computers.

4. Boolean algebra

Variables take only the values 0 and 1; + means OR, juxtaposition means AND, a bar means NOT.

Law OR form AND form
Identity A+0=A A⋅1=A
Null A+1=1 A⋅0=0
Idempotent A+A=A AA=A
Complement A+A‾=1 AA‾=0
Absorption A+AB=A A(A+B)=A
Distributive A+BC=(A+B)(A+C) A(B+C)=AB+AC
De Morgan A+B=A‾B‾ AB=A‾+B‾
Useful extras A+A‾B=A+B consensus: AB+A‾C+BC=AB+A‾C

Every law has a dual: swap + with ⋅ and 0 with 1. Notice the laws ordinary algebra does not have: A+1=1, A+A=A, and OR distributing over AND.

A + B
OR: true if at least one is true (not an arithmetic sum: 1 + 1 = 1)
AB
AND: true only if both are true
Ā
NOT: the opposite value
De Morgan
"break the bar, change the sign": a NOR is an AND of inverted inputs, a NAND an OR of inverted inputs
Physical meaning
Each law says two circuits give the same output for every input. Simplifying an expression means building the same behaviour with fewer gates, less power and less delay.

Worked example. Simplify Y=(A+B)(A+B‾)(A‾+C).

  1. (A+B)(A+B‾)=A+BB‾=A+0=A (OR distributes over AND).
  2. Y=A(A‾+C)=AA‾+AC=AC.
  3. Check one row: A=1,B=0,C=1 gives (1)(1)(1)=1 and AC=1.

“The complement of AB is Ā·B̄.” No: putting a bar over each letter is not the same as putting one long bar over the product. AB=A‾+B‾ (NAND), while A‾B‾=A+B (NOR). They differ when exactly one input is 1: A=1,B=0 gives AB=1 but A‾B‾=0. When you break a bar, the operation underneath must flip.

5. Minterms and Karnaugh maps

Any function can be written straight from its truth table as a sum of products (SOP): one AND term (minterm) for each row where the output is 1. With A as the most significant bit, row 5 is 101, the minterm AB‾C, written m5. The product of sums (POS) uses one OR term (maxterm) for each 0 row. So f=∑m(3,5,6,7)=∏M(0,1,2,4) (this is the majority function AB+BC+CA).

A Karnaugh map lays the truth table out so that neighbouring cells differ in one variable (rows and columns run in Gray-code order 00, 01, 11, 10, and the edges wrap round). Simplifying then becomes drawing loops:

Fill the map. Put a 1 in the cell of every minterm. Cells marked X are "don't cares": use them only if they help.

Loop the 1s in blocks of 1, 2, 4, 8 or 16. Blocks must be rectangles (wrapping round the edges is allowed) and their sizes powers of two.

Make each loop as big as possible. A loop of 2ᵏ cells removes k variables: inside it those variables take every value, so they drop out.

Use as few loops as possible to cover every 1. Overlapping loops are fine.

Read off each loop as the AND of the variables that stay constant inside it, and OR the loops together.

Worked example. Simplify f(A,B,C,D)=∑m(0,1,2,3,4,6,8,9,10,11,12,14).

  1. There are 12 ones and only 4 zeros, at m5,m7,m13,m15 = 0101,0111,1101,1111.
  2. The zeros are exactly the cells with B=1 and D=1, so f‾=BD.
  3. By De Morgan f=B‾+D‾: two loops of eight. Looking at the zeros first was much faster than looping twelve ones.

A function with no two neighbouring 1s, like A⊕︎B⊕︎C (a checkerboard), cannot be simplified at all. To check your loops on any function, the logic simplifier gives the minimal SOP and POS and draws the Karnaugh map.

6. Circuits that combine

  • Half adder: sum S=A⊕︎B, carry C=AB.
  • Full adder (with carry-in Ci): S=A⊕︎B⊕︎Ci (odd parity), Co=AB+Ci(A⊕︎B)=AB+BCi+CiA (majority). Chained, n full adders add two n-bit numbers (a ripple-carry adder).
  • Multiplexer (data selector): n select lines pick one of 2n inputs. A 4-to-1 MUX gives Y=S‾1S‾0I0+S‾1S0I1+S1S‾0I2+S1S0I3, so tying its inputs to 0s and 1s makes any function of the select lines.
  • Decoder: n inputs light exactly one of 2n outputs; a demultiplexer sends one input to the chosen output.

Worked example. Make S1⊕︎S0 from a 4-to-1 MUX.

  1. XOR is 1 for select values 01 and 10.
  2. So set I0=0, I1=1, I2=1, I3=0.
  3. The MUX copies the truth table column straight to its output.

7. Circuits that remember

Feed a gate’s output back to its input and the circuit can store a bit.

  • SR latch (two cross-coupled NOR gates): S = 1 sets Q = 1, R = 1 resets Q = 0, S = R = 0 holds. S = R = 1 forces both outputs to 0 and leaves the next state unpredictable: forbidden. (With NAND gates the inputs are active-low and the forbidden state forces both outputs to 1.)
  • D flip-flop: at the clock edge Q copies D. The basic memory cell of registers.
  • JK flip-flop: like SR, but J = K = 1 toggles Q. Its characteristic equation is Qn+1=JQ‾n+K‾Qn. A level-triggered JK latch with J = K = 1 can toggle many times while the clock is high (race-around); edge triggering or a master-slave design fixes this.
  • T flip-flop: T = 1 toggles at every edge, so it divides the clock frequency by 2.

Counters. A chain of n toggling flip-flops, each clocked by the previous one, is a ripple counter: it counts 0 to 2n−1, and the last output is the clock divided by 2n. A mod-N counter needs ⌈log2⁡N⌉ flip-flops and a gate that clears them all when the count reaches N (e.g. clear at 1010 for a decade counter). A Johnson counter (a shift register with its inverted last output fed back to the start) runs through 2n states with n flip-flops; a ring counter (one circulating 1) runs through n.

Worked example. Three D flip-flops are clocked together with D2=Q1, D1=Q0, D0=Q‾2. Starting at 000, list the states.

  1. Each clock shifts left and brings in Q‾2 at the right: 000→001→011→111→110→100→000.
  2. Six states: a 3-bit Johnson counter, 2n=6.
  3. The two missing states, 010 and 101, form a separate loop of their own; a careful design makes sure the counter cannot get stuck there after power-up.

To play with gates, NAND-only circuits and chained gates, use the logic gates tool.

  • Binary place values are powers of 2; hex groups 4 bits; BCD codes each decimal digit separately; Gray code changes one bit at a time (gi=bi+1⊕︎bi).
  • Two’s complement: invert and add 1; n bits hold −2n−1 to 2n−1−1; overflow means the result has the wrong sign.
  • NAND and NOR are universal. XOR is 1 when inputs differ; XOR needs four NANDs.
  • Boolean laws: A+1=1, A+A=A, A+AB=A, A+A‾B=A+B, A+BC=(A+B)(A+C), De Morgan, consensus.
  • K-maps: Gray-code order, loops of 2k cells remove k variables; largest and fewest loops; look at the 0s when there are fewer of them.
  • Full adder: sum = parity, carry = majority. MUX: n select lines for 2n inputs.
  • Flip-flops: D copies, JK with J = K = 1 toggles, SR forbids S = R = 1. Ripple counters divide by 2n; Johnson counters have 2n states.

Practise: exam questions on this lesson

They start easy and climb to top-rank level. Check each answer, then read the full solution. There are more on the logic gates and Boolean algebra practice page.

Next: this completes the electronics module, with transistors and op-amps before it, and module 8 begins with the JAM paper. The GATE Physics course goes on to combinational design, flip-flops, counters and registers in detail.

Check yourself

1What does De Morgan's theorem give for the complement of (A + B)?
2How many select lines does a multiplexer with 16 data inputs need?
3The 8-bit two's complement numbers for +100 and +50 are added. What does the 8-bit result read as?

Sources

  • M. M. Mano and M. D. Ciletti, Digital Design, 6th ed. (2018), chapters 1 to 6
  • A. P. Malvino and D. P. Leach, Digital Principles and Applications, 8th ed. (2014)
  • P. Horowitz and W. Hill, The Art of Electronics, 3rd ed. (2015), chapter 10: digital logic
  • IIT JAM Physics syllabus (Solid State Physics, Devices and Electronics section), published by the organising IIT each year

Your ticks stay in this browser. Save them as a file on the course home.

Updated 2026-11-22. Not affiliated with IIT or the JAM organising institute. Exam pattern as published for recent years: always check the official JAM website before the exam. All questions are original.