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.
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.
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:
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 .
| Code | Idea | Example (decimal 59) |
|---|---|---|
| Hexadecimal | groups of 4 bits, digits 0 to 9 and A to F | = |
| Octal | groups of 3 bits | |
| BCD (8421) | each DECIMAL digit in its own 4 bits | |
| Gray code | neighbours differ in one bit only | binary |
To get Gray code, keep the first bit and XOR each pair of neighbouring bits: . 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 -bit word, two’s complement gives the top bit a weight of . To negate a number, invert every bit and add 1. For 8 bits:
- ; invert: ; add 1: (as an unsigned number it is ).
- The range is to ; there is one zero.
- Subtraction is addition of the negative: , 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 in 4-bit two’s complement (unsigned 6 − 9).
- Two’s complement of : invert to , add 1: .
- Add: (no carry out).
- Top bit 1, so negative: invert to , add 1: . The answer is , as it should be.
3. The gates
| Gate | Expression | Output is 1 when | Truth table for AB = 00, 01, 10, 11 |
|---|---|---|---|
| AND | all inputs are 1 | 0, 0, 0, 1 | |
| OR | any input is 1 | 0, 1, 1, 1 | |
| NOT | the input is 0 | (one input) | |
| NAND | not all inputs are 1 | 1, 1, 1, 0 | |
| NOR | no input is 1 | 1, 0, 0, 0 | |
| XOR | the inputs differ | 0, 1, 1, 0 | |
| XNOR | the inputs are equal | 1, 0, 0, 1 |
NAND and NOR are universal: each can build every other gate by itself.
- NOT from NAND: tie the inputs together, .
- AND from NAND: a NAND followed by a NAND-inverter.
- OR from NAND: invert each input first, then NAND: .
- XOR takes four NANDs: with , the output is .
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 | ||
| Null | ||
| Idempotent | ||
| Complement | ||
| Absorption | ||
| Distributive | ||
| De Morgan | ||
| Useful extras | consensus: |
Every law has a dual: swap with and 0 with 1. Notice the laws ordinary algebra does not have: , , 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 .
- (OR distributes over AND).
- .
- Check one row: gives and .
“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. (NAND), while (NOR). They differ when exactly one input is 1: gives but . 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 as the most significant bit, row 5 is , the minterm , written . The product of sums (POS) uses one OR term (maxterm) for each 0 row. So (this is the majority function ).
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 .
- There are 12 ones and only 4 zeros, at = .
- The zeros are exactly the cells with and , so .
- By De Morgan : 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 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 , carry .
- Full adder (with carry-in ): (odd parity), (majority). Chained, full adders add two -bit numbers (a ripple-carry adder).
- Multiplexer (data selector): select lines pick one of inputs. A 4-to-1 MUX gives , so tying its inputs to 0s and 1s makes any function of the select lines.
- Decoder: inputs light exactly one of outputs; a demultiplexer sends one input to the chosen output.
Worked example. Make from a 4-to-1 MUX.
- XOR is 1 for select values 01 and 10.
- So set , , , .
- 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 . 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 toggling flip-flops, each clocked by the previous one, is a ripple counter: it counts 0 to , and the last output is the clock divided by . A mod- counter needs flip-flops and a gate that clears them all when the count reaches (e.g. clear at for a decade counter). A Johnson counter (a shift register with its inverted last output fed back to the start) runs through states with flip-flops; a ring counter (one circulating 1) runs through .
Worked example. Three D flip-flops are clocked together with , , . Starting at , list the states.
- Each clock shifts left and brings in at the right: .
- Six states: a 3-bit Johnson counter, .
- The two missing states, and , 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 ().
- Two’s complement: invert and add 1; bits hold to ; 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: , , , , , De Morgan, consensus.
- K-maps: Gray-code order, loops of cells remove variables; largest and fewest loops; look at the 0s when there are fewer of them.
- Full adder: sum = parity, carry = majority. MUX: select lines for inputs.
- Flip-flops: D copies, JK with J = K = 1 toggles, SR forbids S = R = 1. Ripple counters divide by ; Johnson counters have 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
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.