Boolean Algebra

Where this sits in GATE

The GATE 2027 CS syllabus lists Boolean algebra and minimization (the algebraic technique, the Karnaugh map and the tabular method) as the first item of Digital Logic, Section 2. In the tracker's GATE CS pack it sits under Digital Logic.

The laws

Boolean algebra laws (each has a dual: swap + with · and 0 with 1)

Law	OR form	AND form
Identity	$A + 0 = A$	$A \cdot 1 = A$
Null	$A + 1 = 1$	$A \cdot 0 = 0$
Idempotent	$A + A = A$	$A \cdot A = A$
Complement	$A + \overline{A} = 1$	$A \cdot \overline{A} = 0$
Absorption	$A + AB = A$	$A(A + B) = A$
Distributive	$A + BC = (A+B)(A+C)$	$A(B + C) = AB + AC$
De Morgan	$\overline{A + B} = \overline{A}\,\overline{B}$	$\overline{AB} = \overline{A} + \overline{B}$

The OR form of the distributive law, $A + BC = (A+B)(A+C)$ , has no counterpart in ordinary arithmetic, and it's the one most often forgotten.

Worked example: simplifying algebraically

Simplify $F = AB + A\overline{B} + \overline{A}B$ .

F = A(B + \overline{B}) + \overline{A}B = A + \overline{A}B = (A + \overline{A})(A + B) = A + B

The third step uses the OR distributive law. A truth table confirms it: $F$ is 0 only when $A = B = 0$ , exactly like $A + B$ .

Worked example: the consensus theorem

Show that $AB + \overline{A}C + BC = AB + \overline{A}C$ .

Solution: Multiply the redundant term by $1 = A + \overline{A}$ : $BC = ABC + \overline{A}BC$ . Then $ABC$ is absorbed by $AB$ and $\overline{A}BC$ by $\overline{A}C$ , so $BC$ adds nothing. Checking all 8 rows of the truth table gives the same result.

Worked example: a Karnaugh map

Minimise $F(A,B,C) = \sum m(0, 2, 4, 5, 6)$ .

K-map for F (rows A, columns BC in Gray-code order)

A \ BC	00	01	11	10
0	1 (m0)	0	0	1 (m2)
1	1 (m4)	1 (m5)	0	1 (m6)

Solution: The four 1s in columns 00 and 10 (minterms 0, 2, 4, 6) form a group that wraps around the map's edges; in all four $C = 0$ , so the group is $\overline{C}$ . Minterm 5 remains: pair it with minterm 4, where $A = 1$ and $B = 0$ , giving $A\overline{B}$ . So

F = \overline{C} + A\overline{B}

Check minterm 5 ( $A = 1, B = 0, C = 1$ ): $\overline{C} = 0$ but $A\overline{B} = 1$ , so $F = 1$ , as required.

Common mistakes

Complementing a product term by term without swapping the operator. $\overline{AB}$ is $\overline{A} + \overline{B}$ , not $\overline{A}\,\overline{B}$ .
Forgetting the K-map wraps around. The left and right columns are adjacent, as are the top and bottom rows on a 4-row map.
Using groups of 3, 5 or 6. K-map groups must contain a power of 2 cells.
Stopping at a correct but non-minimal form. Always check whether a larger group covers the same 1s.

Where this comes up in exams

The GATE 2027 CS syllabus lists, under Section 2, Digital Logic, Boolean algebra and minimization by the algebraic technique, the Karnaugh map and the tabular method. The GATE 2027 EC syllabus lists Boolean algebra and the minimization of functions using Boolean identities and the Karnaugh map under Digital Circuits.

Checked against GATE 2027 CS syllabus and GATE 2027 EC syllabus. Syllabi can change from year to year, so confirm with the latest official notification for your exam.

Fit it into your week with the free timetable generator.
Mark it off as you revise in the syllabus tracker.
See how long you have left: GATE 2027 countdown.