Logic Gates and Boolean Algebra: Exam Notes
Exam notes on logic gates and Boolean algebra: AND, OR, NOT, NAND, NOR, XOR gates, truth tables, De Morgan's theorems, universal gates and half adders.
By GK24 Editorial Team· Published · 5 min read

Every computer, however large, finally works with two states only: a high voltage treated as 1 and a low voltage treated as 0. The circuits that take such signals in and give a single signal out, according to a fixed rule, are called logic gates, and the algebra that describes their behaviour is Boolean algebra. The subject matters in competitive exams because the questions are self-contained: a truth table to identify, a theorem to state, a universal gate to name. The groundwork was laid by the English mathematician George Boole in the middle of the nineteenth century, when he showed that logical reasoning could be written as algebra on two values. Nearly a century later Claude Shannon showed that the same algebra described electrical switching circuits, and the digital computer became possible.
The three basic gates
An AND gate gives an output of 1 only when every input is 1; it behaves like two switches in series and is written as a dot or simply by placing the variables side by side. An OR gate gives an output of 1 when at least one input is 1; it behaves like two switches in parallel and is written with a plus sign. A NOT gate, the only gate with a single input, reverses whatever it receives, so 0 becomes 1 and 1 becomes 0; it is also called an inverter and is written with a bar or a prime over the variable. Every other gate can be built from these three.
Derived gates and the universal pair
A NAND gate is an AND gate followed by a NOT, so its output is 0 only when all inputs are 1. A NOR gate is an OR followed by a NOT, so its output is 1 only when all inputs are 0. An XOR or exclusive OR gate gives 1 when the inputs are different, which makes it the difference detector of digital electronics, and an XNOR gate gives 1 when the inputs are the same, which makes it an equality detector. NAND and NOR are called universal gates because any logic function at all, including the three basic gates, can be built using only NAND gates or only NOR gates; manufacturers therefore make whole chips of a single type, which is cheaper.
| A | B | AND | OR | NAND | NOR | XOR | XNOR |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
A truth table lists every possible combination of inputs against the output. For a circuit with n input variables there are two raised to the power n rows, so two inputs need four rows, three inputs need eight and four inputs need sixteen. Being able to read a table backwards and name the gate is the single most common question on this topic.
The laws of Boolean algebra
Boolean algebra works on two values and has its own set of laws. The identity laws say that a variable added to 0 or multiplied by 1 is unchanged. The null or annulment laws say that anything added to 1 gives 1 and anything multiplied by 0 gives 0. The idempotent laws say that a variable added to itself, or multiplied by itself, gives the same variable, which has no parallel in ordinary arithmetic. The complement laws say that a variable added to its complement gives 1, while a variable multiplied by its complement gives 0. The involution law says that complementing twice restores the original. The commutative, associative and distributive laws look familiar from ordinary algebra, except that Boolean algebra allows a second distributive form in which addition distributes over multiplication. The absorption law says that a variable added to the product of itself and anything else gives back the variable alone.
De Morgan's theorems
Two theorems named after Augustus De Morgan are asked more often than all the other laws together. The first says that the complement of a sum is the product of the complements, so NOT of A OR B equals NOT A AND NOT B. The second says that the complement of a product is the sum of the complements, so NOT of A AND B equals NOT A OR NOT B. In words, break the bar, and change the sign from plus to dot or from dot to plus. These theorems are what allow a designer to convert any circuit into NAND-only or NOR-only form, which is why they sit at the heart of the universal gate idea.
Simplification and small circuits
A Boolean function can be written as a sum of products or as a product of sums, and each row of a truth table that gives output 1 contributes a minterm. Simplifying such an expression reduces the number of gates a circuit needs, and besides algebraic manipulation designers use the Karnaugh map, a grid arranged so that neighbouring cells differ in one variable only, devised by Maurice Karnaugh in 1953. Gates are then combined into small building blocks. A half adder adds two bits and gives a sum from an XOR gate and a carry from an AND gate, but it cannot accept a carry coming in. A full adder accepts three inputs, the two bits and an incoming carry, and can be made from two half adders and an OR gate; a chain of full adders makes the arithmetic logic unit of a processor. Multiplexers select one of many inputs, decoders turn a code into a single active line, and flip-flops hold one bit, which is how registers and memory are built.
Exam Point of View
The commonest question gives a truth table and asks for the gate, or gives the gate and asks for the output of a stated input pair, so the table of all six gates should be memorised rather than reasoned out in the hall. Next come the named facts: Boole for the algebra, Shannon for switching circuits, Karnaugh for the map, De Morgan for the two theorems. Universal gates are asked almost every year and the trap is to answer AND and OR, or to name only NAND; the answer is NAND and NOR. Expect one question on a Boolean identity, usually a variable with its own complement, and one on the number of rows in a truth table, where candidates multiply instead of taking a power of two. In banking and railway technical papers the half adder and full adder appear: remember XOR for sum, AND for carry, and three inputs for the full adder. NOT being the only gate with a single input is also a favourite one-liner.
Important Facts
| Founder of Boolean algebra | George Boole, English mathematician, mid-nineteenth century |
|---|---|
| Applied Boolean algebra to circuits | Claude Shannon |
| Basic gates | AND, OR and NOT |
| Universal gates | NAND and NOR |
| Only single-input gate | NOT gate, also called an inverter |
| AND gate output | 1 only when every input is 1; like switches in series |
| OR gate output | 1 when at least one input is 1; like switches in parallel |
| XOR gate | Output 1 when inputs are different |
| XNOR gate | Output 1 when inputs are the same; an equality detector |
| Rows in a truth table | Two raised to the power n, for n input variables |
| De Morgan's first theorem | Complement of a sum equals the product of the complements |
| De Morgan's second theorem | Complement of a product equals the sum of the complements |
| Half adder | Sum from an XOR gate, carry from an AND gate; two inputs |
| Full adder | Three inputs; built from two half adders and one OR gate |
| Karnaugh map | Devised by Maurice Karnaugh in 1953 to simplify Boolean expressions |
Practice MCQs on this topic
Which gate is represented by the following truth table? Input A, Input B, Output: 0, 0, 0; 0, 1, 1; 1, 0, 1; 1, 1, 1
- A.NOT
- B.OR
- C.XOR
- D.AND
Show answer
Read the table row by row. The output is 0 only when both inputs are 0, and it is 1 in the other three rows, including the row where both inputs are 1.
Read the full explanation →Which of the following pairs is known as universal gates?
- A.AND and OR
- B.NAND and NOR
- C.XOR and XNOR
- D.NOT and AND
Show answer
Each of these gates alone is enough to build every other gate and so every logic circuit: a NAND with its two inputs tied together acts as a NOT, two NANDs in sequence give an AND, and a suitable arrangement of three gives an OR, and the same can be…
Read the full explanation →According to De Morgan's theorem, the complement of the product of two variables A and B is equal to
- A.The product of the complements of A and B
- B.The sum of the complements of A and B
- C.The product of A and B itself
- D.Always equal to 1
Show answer
De Morgan's second theorem states that NOT of A AND B equals NOT A OR NOT B. The working rule is to break the bar and change the sign, so a dot under a complement becomes a plus once the complement is distributed over the variables.
Read the full explanation →The output of an XOR gate is 1 when
- A.Both inputs are 1
- B.Both inputs are 0
- C.The two inputs are different
- D.The two inputs are the same
Show answer
An exclusive OR gate is a difference detector: it gives 1 for the combinations 0 and 1 or 1 and 0, and gives 0 when the inputs agree.
Read the full explanation →A 'literal' in Boolean Algebra means
- A.A variable in its uncomplemented form only
- B.A variable or with its complement
- C.A variable in its complemented form only
- D.A variable in its complemented or uncomplemented form
Show answer
In Boolean algebra a literal is any single appearance of a variable in an expression, whether it appears plain or with a bar over it.
Read the full explanation →Boolean algebra, the basis of digital logic, was developed by
- A.Charles Babbage
- B.George Boole
- C.Blaise Pascal
- D.John von Neumann
Show answer
The system was a work of pure mathematics for decades until Claude Shannon showed that it described electrical switching circuits exactly, which opened the way to digital computing.
Read the full explanation →In a half adder circuit, the sum output is produced by which gate?
- A.AND gate
- B.OR gate
- C.XOR gate
- D.NOR gate
Show answer
Adding two single bits gives a sum that is 1 when exactly one of the bits is 1 and 0 when both are 0 or both are 1, which is precisely the XOR rule; so in a half adder the sum line comes from an XOR gate.
Read the full explanation →Which logic gate is also known as an inverter?
- A.AND gate
- B.OR gate
- C.NOT gate
- D.NAND gate
Show answer
It is the only gate that takes a single input, and it simply reverses the logic level it receives, giving 1 for an input of 0 and 0 for an input of 1; because the output is the inverse or complement of the input, the circuit is called an inverter.
Read the full explanation →How many rows will the truth table of a logic circuit with three input variables have?
- A.3
- B.6
- C.8
- D.9
Show answer
Each input can take one of two values, so for three inputs the number of distinct combinations is two multiplied by itself three times, that is two raised to the power three, which is eight.
Read the full explanation →In Boolean algebra, the value of the expression A added to the complement of A is
- A.0
- B.1
- C.A
- D.The complement of A
Show answer
This is the complement law for addition, which corresponds to the OR operation. Whatever value A takes, one of A and its complement must be 1, and an OR gate gives 1 whenever any input is 1, so the expression is 1 in both cases.
Read the full explanation →Frequently Asked Questions
Why are NAND and NOR called universal gates?
Because either one alone is enough to build every other gate and therefore every logic circuit. A NAND with both inputs tied together works as a NOT, two NANDs give an AND, and three give an OR; the same can be done with NOR gates. Chip makers exploit this by producing packages of a single gate type, which lowers cost and simplifies manufacturing.
What is the difference between an OR gate and an XOR gate?
Both give 1 when exactly one input is 1. They part company when both inputs are 1: an OR gate still gives 1, but an XOR gate gives 0, because it responds only to a difference between its inputs. For that reason XOR is sometimes read as either but not both, and it is the gate that produces the sum bit in a half adder.
How many rows does a truth table have?
Two raised to the power of the number of input variables. Two inputs give four rows, three inputs give eight, four inputs give sixteen and five give thirty-two. Candidates often multiply the number of inputs by two instead of raising two to that power, which is why three inputs are wrongly answered as six.
What do De Morgan's theorems state in plain words?
Break the bar and change the sign. If the complement covers a sum, remove it and the plus becomes a dot, with each variable complemented: NOT of A OR B is NOT A AND NOT B. If the complement covers a product, the dot becomes a plus: NOT of A AND B is NOT A OR NOT B. The theorems make it possible to redraw any circuit using NAND or NOR gates only.
What is the difference between a half adder and a full adder?
A half adder adds only two bits and produces a sum and a carry, using one XOR and one AND gate, but it has no way to accept a carry arriving from a lower position. A full adder has three inputs, the two bits and the carry in, and gives a sum and a carry out; it can be built from two half adders and an OR gate, and a chain of them adds multi-bit numbers.
Which gate is called an inverter and why?
The NOT gate. It is the only gate with a single input, and it simply reverses the logic level it receives, turning 0 into 1 and 1 into 0, so the output is the inverse or complement of the input. In Boolean notation it is shown by a bar or a prime over the variable, and in a circuit diagram by a triangle with a small circle at its tip.
Sources
- Computer Science (Class XI), Chapter: Boolean Logic — NCERT
- An Investigation of the Laws of Thought — George Boole
- Computer Science (Class XII), Chapter: Computer Organisation — NCERT





