GATE EC · EE · IN

Boolean algebra, logic gates and minimisation

Boolean algebra is the algebra of two-valued (0/1) logic: its laws (absorption, consensus, De Morgan, duality) simplify expressions, and canonical SOP/POS forms and Karnaugh maps turn a truth table into a minimal two-level circuit of gates. The skills this topic needs are exact ones: simplifying an expression, converting between minterm and maxterm lists, counting prime and essential prime implicants, counting functions of a given kind, and finding NAND/NOR gate counts.

22 previous-year questions · 22 solved · 6 practice questions

Conventions and the laws of Boolean algebra

Conventions used throughout. The complement of $A$ is written $\overline{A}$ (an overline, never a prime). $+$ is OR; a dot or plain juxtaposition is AND. Positive logic is assumed (HIGH = 1, LOW = 0). Precedence is NOT first, then AND, then OR. When rows of a truth table are numbered, the first-named variable is the most significant bit: for $f (A, B, C)$ the input $A = 1, B = 0, C = 1$ is row $5$ .

Boolean algebra has two values, 0 and 1, and three operations, AND, OR and NOT; AND and OR are both commutative and associative. Any identity can be proved by perfect induction, which means checking every row of the truth table. The same idea settles a doubtful option in the exam: a single input combination on which two expressions differ proves they are different, but agreement on a few combinations proves nothing. Only all $2^{n}$ rows prove an identity.

BASIC LAWS

A + 0 A + 1 A + A A + \overline{A} \overline{\overline{A}} = A, = 1, = A, = 1, = A A \cdot 1 A \cdot 0 A \cdot A A \cdot \overline{A} = A = 0 = A = 0

Identity, null (dominance), idempotent, complement and involution laws; each left-hand law is the dual of the one beside it.

DISTRIBUTIVE LAWS

A (B + C) = A B + A C, A + B C = (A + B) (A + C)

The second one (OR over AND) has no counterpart in ordinary algebra; it is the step that turns an SOP into a POS.

ABSORPTION

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

First row: in an SOP, a product term that contains every literal of another product term is redundant; dually, in a POS, a sum term that contains every literal of another sum term is redundant. Second row (the redundant-literal rule): when a literal stands alone as a term, its complement can be deleted from every other term.

COMBINING (ADJACENCY)

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

Two terms that are identical except for one variable, true in one and complemented in the other, merge into one and that variable drops out. Every K-map group and every Quine–McCluskey step is this law.

CONSENSUS THEOREM

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

It applies when exactly one variable appears true in one term and complemented in the other. The consensus term is then the AND of the remaining literals ( $B C$ ) in an SOP, or the OR of the remaining literals ( $B + C$ ) in a POS, and it is redundant. If two or more variables are opposed there is no consensus term. The redundant term still matters for hazards (last section).

DE MORGAN'S THEOREMS

\overline{A_{1} + A_{2} + \dots + A_{n}} = \overline{A_{1}} \overline{A_{2}} \dots \overline{A_{n}}, \overline{A_{1} A_{2} \dots A_{n}} = \overline{A_{1}} + \overline{A_{2}} + \dots + \overline{A_{n}}

Break the bar, change the operator. Applied to a whole expression it gives the complement: swap $+$ and $\cdot$ , swap 0 and 1, and complement every literal.

TRANSPOSITION

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

Multiplying out gives $A \overline{A} + A C + \overline{A} B + B C$ . $A \overline{A} = 0$ , and $B C$ is the consensus term of $A C$ and $\overline{A} B$ , so both drop. A fast route from POS to SOP.

SHANNON EXPANSION

f (A, B, \dots) = A f (1, B, \dots) + \overline{A} f (0, B, \dots) = [A + f (0, B, \dots)] [\overline{A} + f (1, B, \dots)]

Holds for any function and any chosen variable; it is the basis of multiplexer realisations and of the substitution shortcuts below.

SUBSTITUTION SHORTCUTS

A f (A, \overline{A}, B, \dots) = A f (1, 0, B, \dots), A + f (A, \overline{A}, B, \dots) = A + f (0, 1, B, \dots)

Here $f (A, \overline{A}, B, \dots)$ stands for any expression in which $A$ and $\overline{A}$ appear as literals. Inside a term ANDed with $A$ you may set $A = 1$ (and so $\overline{A} = 0$ ); inside an expression ORed with $A$ you may set $A = 0$ (and so $\overline{A} = 1$ ). Example: $A (\overline{A} + B + A C) = A (0 + B + C) = A B + A C$ .

Duality. The dual of an expression is obtained by swapping $+$ with $\cdot$ and 0 with 1, leaving every literal unchanged. The duality principle says that if an identity is true, its dual is true as well, which is why the laws above come in pairs. The complement is obtained by the same swaps and complementing every literal. So the dual and the complement differ only in the literals. For $f = A + \overline{B} C$ : dual $A (\overline{B} + C)$ , complement $\overline{A} (B + \overline{C})$ .

EXAM TIP

Put in the parentheses before you dualise or complement. AND binds tighter than OR, so the dual of $A + B C$ is $A (B + C)$ , not $A B + C$ . Also, the duality principle is about identities: the dual function $f^{d}$ is in general a different function from both $f$ and $\overline{f}$ .

Canonical SOP and POS: minterms and maxterms

With $n$ variables there are $2^{n}$ input rows. The minterm $m_{i}$ is the AND of all $n$ variables, each written uncomplemented where the corresponding bit of $i$ is 1 and complemented where it is 0; it equals 1 on row $i$ only. The maxterm $M_{i}$ is the OR of all $n$ variables, each complemented where the bit is 1; it equals 0 on row $i$ only. Hence $M_{i} = \overline{m_{i}}$ .

The canonical SOP (sum of minterms) is the OR of the minterms of the rows where $f = 1$ . The canonical POS (product of maxterms) is the AND of the maxterms of the rows where $f = 0$ . For a fixed order of the variables, each is unique for a given function, apart from the order in which the terms are written.

Row $i$	$A B C$	Minterm $m_{i}$	Maxterm $M_{i}$
0	0 0 0	$\overline{A} \overline{B} \overline{C}$	$A + B + C$
1	0 0 1	$\overline{A} \overline{B} C$	$A + B + \overline{C}$
2	0 1 0	$\overline{A} B \overline{C}$	$A + \overline{B} + C$
3	0 1 1	$\overline{A} B C$	$A + \overline{B} + \overline{C}$
4	1 0 0	$A \overline{B} \overline{C}$	$\overline{A} + B + C$
5	1 0 1	$A \overline{B} C$	$\overline{A} + B + \overline{C}$
6	1 1 0	$A B \overline{C}$	$\overline{A} + \overline{B} + C$
7	1 1 1	$A B C$	$\overline{A} + \overline{B} + \overline{C}$

CANONICAL FORMS

f = i \in S \sum m_{i} = i \in / S \prod M_{i}

$S$ is the set of rows where $f = 1$ , written $\sum m (S)$ . Example: $f (A, B, C) = \sum m (1, 4, 7) = \prod M (0, 2, 3, 5, 6)$ .

COMPLEMENT IN CANONICAL FORM

\overline{f} = i \in / S \sum m_{i} = i \in S \prod M_{i}

Complementing swaps the index set. Keeping the same indices and switching $\sum$ to $\prod$ gives $\overline{f}$ , not $f$ .

MINTERM AND MAXTERM PROPERTIES

m_{i} m_{j} = 0, M_{i} + M_{j} = 1 (i \neq = j), i = 0 \sum 2^{n} - 1 m_{i} = 1, i = 0 \prod 2^{n} - 1 M_{i} = 0

Different minterms never overlap. The OR of two functions is the union of their minterm lists, and the AND is the intersection.

SIZE OF A TERM

a product (sum) term with k of the n variables covers 2^{n - k} minterms (maxterms)

Each variable appears at most once in the term. Use it to count minterms fast. Overlapping terms must be counted once, so list the minterms whenever terms can overlap.

Converting to canonical form

SOP to canonical SOP: multiply every product term that lacks a variable $X$ by $(X + \overline{X}) = 1$ and expand, then drop repeated minterms. Quicker: write the term as a bit pattern and fill the missing positions in every way. For $f (A, B, C)$ , $A \overline{C}$ is the pattern 1x0, so rows 100 and 110, i.e. $m_{4}, m_{6}$ .
POS to canonical POS: add $X \overline{X} = 0$ to every sum term that lacks $X$ and use $P + X \overline{X} = (P + X) (P + \overline{X})$ . Quicker: a sum term is 0 when each of its literals is 0, so $(\overline{A} + C)$ is 0 on the pattern 1x0, i.e. $M_{4}, M_{6}$ .
Canonical SOP to canonical POS: take the complementary index set, $\sum m (S) = \prod M (rows not in S)$ .
From a truth table: the 1-rows give $\sum m$ ; the 0-rows give $\prod M$ .

EXAM TIP

$\sum m (1, 4, 7)$ and $\prod M (1, 4, 7)$ are complements of each other, not the same function. The same function in POS form is $\prod M (0, 2, 3, 5, 6)$ . Always check that the two index lists together contain all $2^{n}$ rows exactly once.

Counting functions, dual functions and self-dual functions

A Boolean function of $n$ variables is fixed by its truth table: $2^{n}$ rows, each with an output of 0 or 1 chosen independently. Every counting question comes down to how many rows are free and how many are forced by the condition.

NUMBER OF BOOLEAN FUNCTIONS

N = 2^{2^{n}}

Counts every function of $n$ variables, including the constants 0 and 1 and functions that ignore some variables. For $n = 2$ there are 16, which is why there are 16 possible two-input gates.

DUAL FUNCTION

f^{d} (A, B, \dots) = \overline{f (\overline{A}, \overline{B}, \dots)}, f = \sum m (S) \Rightarrow f^{d} = \sum m {j : 2^{n} - 1 - j \in / S}

Swapping $+$ and $\cdot$ (and 0 and 1) in any expression of $f$ gives this same function. Row $2^{n} - 1 - j$ is the bitwise complement of row $j$ .

SELF-DUAL FUNCTION

f = f^{d} ⟺ f (\overline{x}) = \overline{f (x)} for every input x

Rows $i$ and $2^{n} - 1 - i$ must have opposite outputs, so exactly one of each complementary pair is a minterm and a self-dual function has exactly $2^{n - 1}$ minterms. Every self-dual function is therefore neutral (next block), but a neutral function need not be self-dual. Examples: any single literal, $A \oplus B \oplus C$ , and the majority function $A B + B C + C A$ .

OTHER COUNTS

exactly k minterms: self-dual: neutral (as many 0s as 1s): symmetric: output fixed on r given rows: (k 2 ^{n}) 2^{2^{n - 1}} (2 ^{n - 1} 2 ^{n}) 2^{n + 1} 2^{2^{n} - r}

Self-dual: the $2^{n}$ rows form $2^{n - 1}$ complementary pairs, each with 2 choices. Symmetric: the output depends only on how many inputs are 1, which takes $n + 1$ values.

FUNCTIONS THAT DEPEND ON ALL N VARIABLES

N_{all} (n) = k = 0 \sum n (- 1)^{n - k} (k n) 2^{2^{k}}

Inclusion–exclusion over the variables a function may ignore. For $n = 1, 2, 3, 4$ it gives 2, 10, 218 and 64594.

$n$	All functions $2^{2^{n}}$	Self-dual $2^{2^{n - 1}}$	Neutral $(2 ^{n - 1} 2 ^{n})$	Symmetric $2^{n + 1}$
1	4	2	2	4
2	16	4	6	8
3	256	16	70	16
4	65536	256	12870	32

EXAM TIP

XOR of an odd number of variables is self-dual; XOR of an even number is not (the dual of $A \oplus B$ is $A ⊙ B$ ). A quick self-dual test: the function must have exactly $2^{n - 1}$ minterms, and no $m_{i}$ may appear together with $m_{2^{n} - 1 - i}$ .

EXAM TIP

Read whether the functions must depend on all $n$ variables. $2^{2^{n}}$ includes constants and functions that ignore some variables: for $n = 2$ , only 10 of the 16 functions depend on both $A$ and $B$ (remove 0, 1, $A$ , $\overline{A}$ , $B$ , $\overline{B}$ ), as the formula above gives.

Karnaugh maps: 2 to 5 variables, prime implicants and don't-cares

A K-map is a truth table laid out so that cells whose inputs differ in exactly one variable sit next to each other. Rows and columns are labelled in Gray-code order 00, 01, 11, 10, and the map wraps around: the left and right edges are adjacent, and so are the top and bottom edges, so the four corners of a 4-variable map form one group. In an $n$ -variable map every cell has exactly $n$ neighbours. Grouping adjacent 1s is the law $X Y + X \overline{Y} = X$ done by eye.

The 2-variable map is 2 × 2 ( $A$ rows, $B$ columns). The 3-variable map has rows $A = 0, 1$ and columns $B C = 00, 01, 11, 10$ , so its cells read 0, 1, 3, 2 on the top row and 4, 5, 7, 6 on the bottom row. The 4-variable map, with rows $A B$ and columns $C D$ , is below.

AB (rows) / CD (columns)	00	01	11	10
00	0	1	3	2
01	4	5	7	6
11	12	13	15	14
10	8	9	11	10

GROUP SIZE AND LITERALS

group of 2^{k} adjacent cells in an n -variable map \leftrightarrow product term of n - k literals

Groups must be rectangles (wrap-around allowed) whose sides are 1, 2 or 4 cells long, so a group holds 1, 2, 4, 8 or 16 cells; in a 5-variable map a group may also be the same rectangle on both halves. A variable that changes inside the group drops out; one fixed at 1 appears uncomplemented and one fixed at 0 appears complemented. A 3-cell or L-shaped group is not a single term.

Definitions. An implicant of $f$ is a product term that is 1 only on rows where $f$ is 1 or a don't-care. A prime implicant (PI) is an implicant from which no literal can be removed without the term covering a 0-cell; on the K-map, its group is not contained in any larger valid group. An essential prime implicant (EPI) is a PI that covers at least one 1-cell that no other PI covers. A minimal SOP is made of PIs only, and it always contains every EPI. Minimal means the fewest product terms first, and then the fewest literals.

Minimal SOP from a K-map

Enter the 1s, the 0s and the don't-cares (X).
For every 1-cell, find the largest groups that contain it and collect all the distinct PIs. Don't-cares may be used to make a group bigger.
Mark as essential every PI that is the only PI covering some 1-cell, and include all of them.
Cover the remaining 1-cells with as few further PIs as possible; among covers with equally few terms, pick the one with the fewest literals. If two covers tie, the minimal SOP is not unique.
Never add a group that covers only don't-cares, and never use a group smaller than it could be.

Minimal POS. Group the 0s (together with any useful don't-cares) in exactly the same way. This gives the minimal SOP of $\overline{f}$ , and De Morgan turns it into the minimal POS of $f$ . You can also read a group of 0s straight off as a sum term: a variable fixed at 0 throughout the group appears uncomplemented, and a variable fixed at 1 appears complemented. The minimal SOP and minimal POS can have different numbers of terms, so work out both when a question asks for the cheapest two-level circuit.

Five variables. With $A$ as the MSB, draw two 4-variable maps in $B, C, D, E$ : one for $A = 0$ (cells 0–15) and one for $A = 1$ (cells 16–31). As well as the usual adjacencies inside each map, every cell is adjacent to the cell in the same position in the other map. A group that appears in the same place on both maps loses $A$ ; a group on one map only keeps $\overline{A}$ or $A$ .

WORKED EXAMPLE

Find the minimal SOP of $f (A, B, C, D) = \sum m (1, 3, 4, 5, 9, 11, 14, 15) + d (6, 12)$ , where $d$ lists don't-care rows and $A$ is the MSB. Also list its prime implicants and essential prime implicants.

Solution

Plot the map: 1s at 1, 3, 4, 5, 9, 11, 14, 15; X at 6 and 12; 0s at 0, 2, 7, 8, 10, 13.
Quads: $\overline{B} D$ covers 1, 3, 9, 11 (all 1s). $B \overline{D}$ covers 4, 6, 12, 14 (two 1s and both X). These are PIs.
$m_{5}$ : every quad through it contains a 0-cell (0, 7 or 13), so its largest groups are the pairs $\overline{A} B \overline{C}$ (4, 5) and $\overline{A} \overline{C} D$ (1, 5). $m_{15}$ : every quad through it contains 7, 10 or 13, so its largest groups are the pairs $A B C$ (14, 15) and $A C D$ (11, 15).
PIs: $\overline{B} D, B \overline{D}, \overline{A} B \overline{C}, \overline{A} \overline{C} D, A B C, A C D$ , six in all.
EPIs: $m_{3}$ and $m_{9}$ are covered only by $\overline{B} D$ , so it is essential. Every other 1-cell lies in two PIs ( $m_{4}$ : $B \overline{D}$ or $\overline{A} B \overline{C}$ ; $m_{5}$ : $\overline{A} B \overline{C}$ or $\overline{A} \overline{C} D$ ; $m_{14}$ : $B \overline{D}$ or $A B C$ ; $m_{15}$ : $A B C$ or $A C D$ ). There is exactly one EPI.
Still to cover: 4, 5, 14, 15. Two PIs do it: $\overline{A} B \overline{C}$ (4, 5) and $A B C$ (14, 15). Taking the big quad $B \overline{D}$ instead covers 4 and 14 but leaves 5 and 15, which need two more pairs, so that route needs 4 terms.
The minimal SOP has 3 terms and 8 literals, and no other 3-term cover exists. Both don't-cares end up as 0.

Answer: $f = \overline{B} D + \overline{A} B \overline{C} + A B C$ . It has 6 prime implicants and 1 essential prime implicant ( $\overline{B} D$ ), and this minimal SOP is unique.

EXAM TIP

The rule is EPIs first, not the largest group first. In the example the quad $B \overline{D}$ is a genuine prime implicant and uses both don't-cares, yet it is not in the minimal cover.

EXAM TIP

Use a don't-care only where it makes a group bigger. The minimal SOP and minimal POS of the same incompletely specified function may treat an X differently, so they can disagree on the don't-care rows and both still be correct. Compare expressions on the specified rows only.

Quine–McCluskey (tabular) method in brief

The tabular method does the K-map's job by systematic comparison, so it works for any number of variables and can be programmed. It applies $X Y + X \overline{Y} = X$ to binary patterns, writing a dash for the variable that drops out.

Procedure

Write every minterm and don't-care in binary and group the patterns by their number of 1s.
Compare every pattern with every pattern in the next group. If two differ in exactly one bit, combine them, put a dash in that bit, and tick both.
Repeat with the combined patterns; two patterns can combine only if their dashes are in the same positions and they differ in exactly one other bit. Patterns that are never ticked are the prime implicants; drop any that covers only don't-cares.
Draw the PI chart: one row per PI and one column per minterm. Don't-cares do not get columns.
A column with a single cross marks an essential PI. Select it and delete every column it covers.
Shrink what remains by dominance. Row dominance: if one PI covers every remaining minterm that another covers and has no more literals, delete the dominated PI. Column dominance: if every PI that covers $m_{j}$ also covers $m_{k}$ , delete column $m_{k}$ , since covering $m_{j}$ covers $m_{k}$ automatically. If a cyclic chart is left, choose by trial or by Petrick's method: write the covering condition as a product of sums and multiply it out.

EXAM TIP

A function can have prime implicants but no essential one (a cyclic function). For example, $f (A, B, C) = \sum m (0, 1, 2, 5, 6, 7)$ has six two-literal PIs, none of them essential, and two different minimal covers of three terms each. When a question asks for the number of PIs and the number of EPIs, count them separately.

Logic gates, universal gates and XOR/XNOR

Gate	Output $Y$ (2 inputs)	$Y = 1$ when	Remark
AND	$A B$	all inputs are 1	passes $A$ when $B = 1$ , blocks it when $B = 0$
OR	$A + B$	at least one input is 1	passes $A$ when $B = 0$
NOT	$\overline{A}$	the input is 0	single input
NAND	$\overline{A B} = \overline{A} + \overline{B}$	at least one input is 0	universal; same as OR with inverted inputs
NOR	$\overline{A + B} = \overline{A} \overline{B}$	all inputs are 0	universal; same as AND with inverted inputs
XOR	$A \oplus B = A \overline{B} + \overline{A} B$	an odd number of inputs are 1	parity; controlled inverter ( $A \oplus 1 = \overline{A}$ )
XNOR	$A ⊙ B = A B + \overline{A} \overline{B}$	the two inputs are equal	equality detector; $A ⊙ B = \overline{A \oplus B}$

XOR/XNOR IDENTITIES

A \oplus 0 A \oplus A \overline{A \oplus B} = A, = 0, = \overline{A} \oplus B = A \oplus \overline{B} = A ⊙ B, A \oplus 1 A \oplus \overline{A} \overline{A} \oplus \overline{B} = \overline{A} = 1 = A \oplus B

XOR is commutative and associative. Complementing one input complements the output; complementing both leaves it unchanged.

MORE XOR RELATIONS

A \oplus B A + B A (B \oplus C) A \oplus A B A \oplus B = C = (A + B) (\overline{A} + \overline{B}) = A \oplus B \oplus A B = A B \oplus A C = A \overline{B} ⟺ A \oplus C = B

AND distributes over XOR, but OR does not. If $A B = 0$ (the terms never both equal 1) then $A + B = A \oplus B$ .

MULTI-INPUT PARITY

A_{1} \oplus A_{2} \oplus \dots \oplus A_{n} = 1 ⟺ an odd number of the A_{i} are 1, A ⊙ B ⊙ C = A \oplus B \oplus C

Here $A ⊙ B ⊙ C$ means two cascaded 2-input XNOR gates, $(A ⊙ B) ⊙ C$ : it gives the 3-input XOR, not its complement. An $n$ -variable XOR has $2^{n - 1}$ minterms and no two of them are adjacent on a K-map (a checkerboard), so its minimal SOP needs all $2^{n - 1}$ terms of $n$ literals each.

Universal gates. A set of gates is functionally complete if every Boolean function can be built from it. NAND alone and NOR alone are complete. A NAND makes NOT (tie the inputs together, or hold the other input at 1); a NAND followed by a NOT is AND; and a NAND fed with complemented inputs is OR, because $\overline{\overline{A} \overline{B}} = A + B$ . NOR works dually (hold the other input at 0 for NOT). Other complete sets are {AND, NOT}, {OR, NOT}, and {AND, XOR} with the constant 1 available. {AND, OR} is not complete, because it can never produce a complement. {XOR, XNOR, NOT} is not complete either: everything it builds is a constant or an XOR of some of the inputs, possibly complemented, so it can never make AND.

EXAM TIP

A test for completeness. A set of gates is functionally complete exactly when, for each of these five properties, the set contains at least one function that lacks it: preserves 0 ( $f (0, \dots, 0) = 0$ ); preserves 1 ( $f (1, \dots, 1) = 1$ ); self-dual; monotone (raising an input from 0 to 1 never lowers the output from 1 to 0); linear (a constant, or an XOR of some of the inputs, possibly complemented). {AND, OR} fails because both are monotone; {XOR, XNOR, NOT} fails because all are linear; NAND alone lacks all five. A 2:1 multiplexer $Y = \overline{S} I_{0} + S I_{1}$ is complete when the constants 0 and 1 are available: select $A$ with $I_{0} = 1, I_{1} = 0$ gives $\overline{A}$ , and with $I_{0} = 0, I_{1} = B$ gives $A B$ .

Function	Fewest 2-input NAND gates	Fewest 2-input NOR gates
NOT	1	1
AND	2	3
OR	3	2
NAND	1	4
NOR	4	1
XOR	4	5
XNOR	5	4
3-input NAND	3	7
3-input NOR	7	3
Half adder (sum and carry)	5	5
Full adder (sum and carry)	9	9

Each count is the minimum when only the uncomplemented inputs are available and no constants are used: no circuit with fewer 2-input gates exists. Circuits that achieve them: XOR from NANDs is $G_{1} = \overline{A B}$ , then $A \oplus B = \overline{\overline{A G_{1}} \cdot \overline{B G_{1}}}$ , and XNOR from NORs is the dual construction. In the NAND half adder the carry $A B$ is $G_{1}$ inverted, which costs one gate. The NOR half adder is built differently: $\overline{A}$ , $\overline{B}$ , carry $= NOR (\overline{A}, \overline{B}) = A B$ , $G = NOR (A, B) = \overline{A} \overline{B}$ and sum $= NOR (A B, G) = A \oplus B$ , again 5 gates. In the NAND full adder the first XOR stage makes $A \oplus B$ (4 gates, the first being $G_{1} = \overline{A B}$ ) and the second makes $A \oplus B \oplus C_{in}$ (4 gates, the first being $G_{5} = \overline{(A \oplus B) C_{in}}$ ); the carry $NAND (G_{1}, G_{5}) = A B + (A \oplus B) C_{in}$ costs one more gate, 9 in all.

Two-level NAND and NOR realisations

Minimal SOP to NAND–NAND: replace every AND of the AND–OR circuit by a NAND, and the output OR by a NAND. A product term with a single literal goes straight into the output NAND, complemented.
Minimal POS to NOR–NOR: replace every OR by a NOR and the output AND by a NOR (the dual rule). A single-literal sum term enters the output NOR complemented.
Gate count of NAND–NAND for an SOP of two or more terms, with gates of as many inputs as needed: one NAND for each product term of two or more literals, plus one output NAND. If complemented inputs are not available, add one inverter (a NAND with its inputs tied) for each variable whose complement the circuit needs: every variable that appears complemented inside a multi-literal term, and every single-literal term written uncomplemented, because it enters the output NAND complemented. Example: $A + \overline{B} C$ needs $NAND (\overline{B}, C)$ , the output NAND, and inverters for $\overline{B}$ and $\overline{A}$ , so 4 gates. NOR–NOR from a POS follows the same rule with sum and product terms swapped.
Bubble pushing for multilevel circuits: a NAND is an OR with inverted inputs, a NOR is an AND with inverted inputs, and two inversions in series on one line cancel.

EXAM TIP

The other two-level forms. AND–OR and NAND–NAND realise an SOP of $f$ ; OR–AND and NOR–NOR realise a POS of $f$ . AND–NOR (equivalently NAND–AND) gives $f = \overline{P_{1} + P_{2} + \dots}$ , so group the 0s of $f$ to find the product terms $P_{i}$ . OR–NAND (equivalently NOR–OR) gives $f = \overline{S_{1} S_{2} \dots}$ , so group the 1s of $f$ and read each group as a sum term $S_{i}$ (a variable fixed at 0 appears uncomplemented, one fixed at 1 complemented). Example: $A + \overline{B} C = \overline{\overline{A} \overline{C} + \overline{A} B} = \overline{\overline{A} (B + \overline{C})}$ .

EXAM TIP

NAND and NOR are commutative but not associative: $NAND (NAND (A, B), C) = A B + \overline{C}$ , not $\overline{A B C}$ . A 3-input NAND built from 2-input NANDs needs an AND first, $\overline{A B C} = NAND (AND (A, B), C)$ , which is 3 two-input NAND gates.

EXAM TIP

A 3-input XOR symbol with an output bubble means $\overline{A \oplus B \oplus C}$ (1 for an even number of 1s). That is the complement of two cascaded 2-input XNOR gates, which give $A \oplus B \oplus C$ . Check which one the question draws.

EXAM TIP

Positive and negative logic: under negative logic the same physical gate performs the dual function. A positive-logic NAND is a negative-logic NOR, and a positive-logic AND is a negative-logic OR.

Hazards in brief

The steady-state output of a circuit is set by its Boolean expression. While an input is changing, though, paths with unequal delays can briefly produce a wrong output, called a glitch. In these notes every gate has the same propagation delay $t_{p d}$ , the time from an input change to the resulting output change, and each gate is treated as a pure delay: its output follows its inputs $t_{p d}$ later, however short the input pulse. A hazard means a glitch that can occur when a single input changes.

Hazard	Output should	Output actually does	Where to look for it
Static-1	stay at 1	1 → 0 → 1	two-level SOP circuits (AND–OR, NAND–NAND)
Static-0	stay at 0	0 → 1 → 0	two-level POS circuits (OR–AND, NOR–NOR)
Dynamic	change once, e.g. 1 → 0	changes three or more times, e.g. 1 → 0 → 1 → 0	multilevel circuits with three or more paths of different delay from the changing input to the output

Detecting and removing static hazards

In an SOP realisation, draw its product terms on the K-map. Each pair of adjacent 1-cells that is not inside a single product term gives a possible static-1 hazard, for a change of the one variable in which the two cells differ.
Remove the hazard by adding a product term that covers both cells: the consensus term of the two product terms, or a prime implicant that contains it. By the consensus theorem this leaves $f$ unchanged.
For single-input changes, a two-level SOP that includes every prime implicant of $f$ is free of static-1 hazards.
In a POS realisation, dually, adjacent 0-cells that are not inside one sum term give a static-0 hazard; add a sum term that covers both (the POS consensus term).
A two-level SOP in which no product term contains both a variable and its complement has no static-0 or dynamic hazard for a single input change, so only static-1 hazards need checking. The dual statement holds for POS.

WORKED EXAMPLE

The function $f (A, B, C) = \overline{A} B + A C$ is to be built from NAND gates only, with only $A$ , $B$ and $C$ available (no complemented inputs). (a) How many 2-input NAND gates does the two-level NAND–NAND realisation need? (b) With every gate a pure delay of $t_{p d}$ , does the circuit have a static hazard, and how is it removed?

Solution

NAND–NAND form: $f = \overline{\overline{\overline{A} B} \cdot \overline{A C}}$ . The gates are $G_{1} = NAND (A, A) = \overline{A}$ , $G_{2} = NAND (G_{1}, B)$ , $G_{3} = NAND (A, C)$ and $G_{4} = NAND (G_{2}, G_{3}) = \overline{A} B + A C$ : 2 product-term gates + 1 output gate + 1 inverter = 4 gates.
On the K-map ( $A$ is the MSB), $f = \sum m (2, 3, 5, 7)$ . $\overline{A} B$ covers $m_{2}, m_{3}$ and $A C$ covers $m_{5}, m_{7}$ . Cells $m_{3}$ (011) and $m_{7}$ (111) are adjacent 1s, differing only in $A$ , but they lie in different product terms: a static-1 hazard when $B = C = 1$ and $A$ changes.
Timing for $B = C = 1$ and $A$ going $1 \to 0$ at $t = 0$ : $G_{3}$ rises to 1 at $t_{p d}$ ( $A C$ switches off). $G_{1}$ rises at $t_{p d}$ , so $G_{2}$ falls to 0 only at $2 t_{p d}$ ( $\overline{A} B$ switches on). From $t_{p d}$ to $2 t_{p d}$ both inputs of $G_{4}$ are 1, so $G_{4}$ drops to 0 at $2 t_{p d}$ and returns to 1 at $3 t_{p d}$ : a 1 → 0 → 1 glitch of width $t_{p d}$ .
For $A$ going $0 \to 1$ , $G_{3}$ falls at $t_{p d}$ and $G_{2}$ rises only at $2 t_{p d}$ . In between both are 0, so $G_{4}$ stays at 1 and there is no glitch in that direction with these delays. The design is still hazardous, because whether the glitch shows depends only on which path is slower.
Remove it by adding the consensus term of $\overline{A} B$ and $A C$ , which is $B C$ (it covers $m_{3}$ and $m_{7}$ ): $f = \overline{A} B + A C + B C$ . With $B = C = 1$ , $G_{5} = NAND (B, C) = 0$ holds the output NAND at 1 whatever $A$ does.
The hazard-free NAND circuit uses $G_{1}, G_{2}, G_{3}, G_{5}$ (2-input) and a 3-input output NAND: 5 gates.

Answer: (a) 4 two-input NAND gates. (b) Yes: a static-1 hazard when $A$ changes with $B = C = 1$ (a glitch of width $t_{p d}$ when $A$ falls). Adding the consensus term $B C$ removes it, at the cost of one more gate and a 3-input output NAND.

EXAM TIP

A hazard-free design is deliberately non-minimal: the consensus term is redundant for the logic but needed for the timing. If a question asks for the minimal expression, leave it out; if it asks for a hazard-free one, put it in. A hazard belongs to the realisation, not to the function: the same $f$ built with the extra term has none.

PREVIOUS-YEAR QUESTIONS

22 questions from the EC, EE and IN papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE ECE 2026 · GATE ECE 2025 · GATE ECE 2024 · GATE ECE 2022 · GATE ECE 2018 · GATE EE 2026 · GATE EE 2025 · GATE EE 2024 · GATE EE 2018 · GATE IN 2025 · GATE IN 2024 · GATE IN 2023 · GATE IN 2022 · GATE IN 2020 · GATE IN 2018

GATE 2026 EC Q.56

GATE 2026 · ECQ.56 · 2 marks · MSQ

Consider the four-variable Boolean function,

$f (w, x, y, z) = \sum m (0, 2, 5, 7, 8, 10, 13, 14, 15)$ with ' $w$ ' as MSB and ' $z$ ' as LSB.

Which of the following expressions is/are the valid form(s) of $f (w, x, y, z)$ ?

(Complement is printed as an overbar and is written here with \overline{}.)

(A)
$\overline{x} \overline{z} + x z + w x y$
(B)
$x z + w x y + w \overline{x} \overline{z} + \overline{w} x y \overline{z}$
(C)
$\overline{x} \overline{z} + w x y + w \overline{x} \overline{z} + \overline{w} x y \overline{z}$
(D)
$\overline{x} \overline{z} + x z + w y \overline{z}$

Answer and solution

GATE 2026 EC Q.56: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 EC Q.56: answer and solution

GATE 2026 EE Q.45

GATE 2026 · EEQ.45 · 2 marks · MCQ

The digital circuit shown has 3 inputs ( $x$ , $y$ , and $z$ ).

[Figure]

The simplified logical expression for the output (OUT) is:

GATE 2026 EE question 45: Three inputs x, y, z enter from the left on three horizontal lines, x on top, then y, then z. — Figure from the GATE 2026 EE paper. It is part of the question.

(A)
$\overset{x}{ˉ} \overline{y z}$
(B)
$0$
(C)
$\overset{x}{ˉ} (y + z)$
(D)
$1$

Answer and solution

GATE 2026 EE Q.45: answer and solution

GATE 2025 EC Q.23

GATE 2025 · ECQ.23 · 1 mark · MCQ

A 3-input majority logic gate has inputs $X, Y,$ and $Z$ . The output $F$ of the gate is logic '1' if two or more of the inputs are logic '1'. The output $F$ is logic '0' if two or more of the inputs are logic '0'.

Which one of the following options is a Boolean expression of the output $F$ ?

(A)
$X Y + Y Z + Z X$
(B)
$X \oplus Y \oplus Z$
(C)
$X + Y + Z$
(D)
$X Y Z$

Answer and solution

GATE 2025 EC Q.23: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 EC Q.23: answer and solution

GATE 2025 EE Q.37

GATE 2025 · EEQ.37 · 2 marks · MCQ

A Boolean function is given as

f = (\overline{u} + \overline{v} + \overline{w} + \overline{x}) \cdot (\overline{u} + \overline{v} + \overline{w} + x) \cdot (\overline{u} + v + \overline{w} + \overline{x}) \cdot (\overline{u} + v + \overline{w} + x)

The simplified form of this function is represented by

GATE 2025 EE question 37: All four options are gate-level circuit figures. — Figure from the GATE 2025 EE paper. It is part of the question.

(A)
Figure — u and w each through a NOT gate, the two inverted signals into a 2-input OR gate, output f (i.e. $f = \overline{u} + \overline{w}$ )
(B)
Figure — u and w directly into a 2-input OR gate, output f (i.e. $f = u + w$ )
(C)
Figure — v and x each through a NOT gate, the two inverted signals into a 2-input OR gate, output f (i.e. $f = \overline{v} + \overline{x}$ )
(D)
Figure — v and x directly into a 2-input OR gate, output f (i.e. $f = v + x$ )

Answer and solution

GATE 2025 EE Q.37: answer and solution

GATE 2025 IN Q.29

GATE 2025 · INQ.29 · 1 mark · MCQ

A Boolean function $X$ is given as $X = \overline{A} \overline{B} + \overline{A} \overline{C}$ . The reduced form of $\overline{X}$ is

(A)
$\overline{A} + \overline{B} + \overline{C}$
(B)
$A + B C$
(C)
$\overline{A} + \overline{B} + C$
(D)
$B + A C$

Answer and solution

GATE 2025 IN Q.29: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 IN Q.29: answer and solution

GATE 2024 EC Q.19

GATE 2024 · ECQ.19 · 1 mark · MCQ

For the Boolean function

F (A, B, C, D) = \sum m (0, 2, 5, 7, 8, 10, 12, 13, 14, 15),

the essential prime implicants are ________.

(A)
$B D, \overline{B} \overline{D}$
(B)
$B D, A B$
(C)
$A B, \overline{B} \overline{D}$
(D)
$B D, \overline{B} \overline{D}, A B$

Answer and solution

GATE 2024 EC Q.19: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 EC Q.19: answer and solution

GATE 2024 EE Q.24

GATE 2024 · EEQ.24 · 1 mark · MCQ

Simplified form of the Boolean function

F (P, Q, R, S) = \overline{P} \overline{Q} + \overline{P} QS + P \overline{Q} \overline{R} \overline{S} + P \overline{Q} R \overline{S}

(Complement is written with .)

(A)
$\overline{P} S + \overline{Q} \overline{S}$
(B)
$\overline{P} \overline{Q} + \overline{Q} \overline{S}$
(C)
$\overline{P} Q + R \overline{S}$
(D)
$P \overline{S} + Q \overline{R}$

Answer and solution

GATE 2024 EE Q.24: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 EE Q.24: answer and solution

GATE 2024 IN Q.16

GATE 2024 · INQ.16 · 1 mark · MCQ

Among the given options, the simplified form of the Boolean function $F = (A + \overline{A} . B) + \overline{A} . (A + \overline{B}) . C$ is

(A)
$A + B + C$
(B)
$A . B . C$
(C)
$B + \overline{A} . C$
(D)
$\overline{A} + B . C$

Answer and solution

GATE 2024 IN Q.16: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 IN Q.16: answer and solution

GATE 2023 IN Q.17

GATE 2023 · INQ.17 · 1 mark · MCQ

Match the Exclusive-OR (XOR) operations (i) to (iv) with the results (p) to (s), where $X$ is a Boolean input.

| Operation | Result |
|---|---|
| (i) $X \oplus X$ | (p) $1$ |
| (ii) $X \oplus \overline{X}$ | (q) $0$ |
| (iii) $X \oplus 0$ | (r) $\overline{X}$ |
| (iv) $X \oplus 1$ | (s) $X$ |

(A)
(i) - (q), (ii) - (r), (iii) - (s), (iv) - (p)
(B)
(i) - (q), (ii) - (r), (iii) - (p), (iv) - (s)
(C)
(i) - (p), (ii) - (s), (iii) - (q), (iv) - (r)
(D)
(i) - (q), (ii) - (p), (iii) - (s), (iv) - (r)

Answer and solution

GATE 2023 IN Q.17: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 IN Q.17: answer and solution

GATE 2023 IN Q.40

GATE 2023 · INQ.40 · 2 marks · MCQ

The simplified form of the Boolean function $F (W, X, Y, Z) = Σ (4, 5, 10, 11, 12, 13, 14, 15)$ with the minimum number of terms and smallest number of literals in each term is ________.

(A)
$W X + \overline{W} X \overline{Y} + W \overline{X} Y$
(B)
$W X + W Y + X \overline{Y}$
(C)
$X \overline{Y} + W Y$
(D)
$\overline{X} Y + \overline{W} \overline{Y}$

Answer and solution

GATE 2023 IN Q.40: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 IN Q.40: answer and solution

GATE 2022 EC Q.27

GATE 2022 · ECQ.27 · 1 mark · MSQ

Select the Boolean function(s) equivalent to $x + y z$ , where $x$ , $y$ , and $z$ are Boolean variables, and $+$ denotes logical OR operation.

(A)
$x + z + x y$
(B)
$(x + y) (x + z)$
(C)
$x + x y + y z$
(D)
$x + x z + x y$

Answer and solution

GATE 2022 EC Q.27: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 EC Q.27: answer and solution

GATE 2022 EC Q.49

GATE 2022 · ECQ.49 · 2 marks · MSQ

Consider a Boolean gate (D) where the output $Y$ is related to the inputs $A$ and $B$ as, $Y = A + \overline{B}$ , where $+$ denotes logical OR operation. The Boolean inputs '0' and '1' are also available separately. Using instances of only D gates and inputs '0' and '1', ________ (select the correct option(s)).

(A)
NAND logic can be implemented
(B)
OR logic cannot be implemented
(C)
NOR logic can be implemented
(D)
AND logic cannot be implemented

Answer and solution

GATE 2022 EC Q.49: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 EC Q.49: answer and solution

GATE 2022 IN Q.21

GATE 2022 · INQ.21 · 1 mark · MCQ

The logic block shown has an output $F$ given by ________

GATE 2022 IN question 21: Two inputs, B (upper) and A (lower), enter from the left as horizontal lines. — Figure from the GATE 2022 IN paper. It is part of the question.

(A)
$A + B$
(B)
$A . \overline{B}$
(C)
$A + \overline{B}$
(D)
$\overline{B}$

Answer and solution

GATE 2022 IN Q.21: answer and solution

GATE 2022 IN Q.48

GATE 2022 · INQ.48 · 2 marks · MCQ

$A = a_{1} a_{0}$ and $B = b_{1} b_{0}$ are two 2-bit unsigned binary numbers. If $F (a_{1}, a_{0}, b_{1}, b_{0})$ is a Boolean function such that $F = 1$ only when $A > B$ , and $F = 0$ otherwise, then $F$ can be minimized to the form ________

(A)
$a_{1} \overline{b}_{1} + a_{1} a_{0} \overline{b}_{0}$
(B)
$a_{1} \overline{b}_{1} + a_{1} a_{0} \overline{b}_{0} + a_{0} \overline{b}_{0} \overline{b}_{1}$
(C)
$a_{1} a_{0} \overline{b}_{0} + a_{0} \overline{b}_{0} \overline{b}_{1}$
(D)
$a_{1} \overline{b}_{1} + a_{1} a_{0} \overline{b}_{0} + a_{0} \overline{b}_{0} b_{1}$

Answer and solution

GATE 2022 IN Q.48: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 IN Q.48: answer and solution

GATE 2020 IN Q.8

GATE 2020 · INQ.8 · 1 mark · MCQ

Given $f (A, B, C, D) = \sum m (0, 1, 2, 6, 8, 9, 10, 11) + \sum d (3, 7, 14, 15)$ is a Boolean function, where $m$ represents min-terms and $d$ represents don't-cares. The minimal sum of products expression for $f$ is ____

(A)
$f = A \overline{B} + C B$
(B)
$f = \overline{B} + C$
(C)
$f = \overline{D} + A$
(D)
$f = \overline{A} B + \overline{C} D$

Answer and solution

GATE 2020 IN Q.8: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 IN Q.8: answer and solution

GATE 2020 IN Q.11

GATE 2020 · INQ.11 · 1 mark · MCQ

The Boolean expression for the shaded regions as shown in the figure is ____

GATE 2020 IN question 11: Venn diagram: a square (the universal set) containing two overlapping circles, labelled A (left) and B (right). — Figure from the GATE 2020 IN paper. It is part of the question.

(A)
$(A + B) \cdot (\overline{A} + \overline{B})$
(B)
$(A + \overline{B}) \cdot (\overline{A} + B)$
(C)
$(\overline{A} + B) \cdot (\overline{A} + \overline{B})$
(D)
$(\overline{A} + \overline{B}) \cdot (A + \overline{B})$

Answer and solution

GATE 2020 IN Q.11: answer and solution

GATE 2018 EC Q.9

GATE 2018 · ECQ.9 · 1 mark · MCQ

A function $F (A, B, C)$ defined by three Boolean variables $A$ , $B$ and $C$ when expressed as sum of products is given by
$F = \overline{A} \cdot \overline{B} \cdot \overline{C} + \overline{A} \cdot B \cdot \overline{C} + A \cdot \overline{B} \cdot \overline{C}$
where, $\overline{A}$ , $\overline{B}$ , and $\overline{C}$ are the complements of the respective variables. The product of sums (POS) form of the function F is

(A)
$F = (A + B + C) \cdot (A + \overline{B} + C) \cdot (\overline{A} + B + C)$
(B)
$F = (\overline{A} + \overline{B} + \overline{C}) \cdot (\overline{A} + B + \overline{C}) \cdot (A + \overline{B} + \overline{C})$
(C)
$F = (A + B + \overline{C}) \cdot (A + \overline{B} + \overline{C}) \cdot (\overline{A} + B + \overline{C}) \cdot (\overline{A} + \overline{B} + C) \cdot (\overline{A} + \overline{B} + \overline{C})$
(D)
$F = (\overline{A} + \overline{B} + C) \cdot (\overline{A} + B + C) \cdot (A + \overline{B} + C) \cdot (A + B + \overline{C}) \cdot (A + B + C)$

Answer and solution

GATE 2018 EC Q.9: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 EC Q.9: answer and solution

GATE 2018 EC Q.47

GATE 2018 · ECQ.47 · 2 marks · NAT

The logic gates shown in the digital circuit below use strong pull-down nMOS transistors for LOW logic level at the outputs. When the pull-downs are off, high-value resistors set the output logic levels to HIGH (i.e. the pull-ups are weak). Note that some nodes are intentionally shorted to implement "wired logic". Such shorted nodes will be HIGH only if the outputs of all the gates whose outputs are shorted are HIGH.

[Figure]

The number of distinct values of $X_{3} X_{2} X_{1} X_{0}$ (out of the 16 possible values) that give $Y = 1$ is ________.

GATE 2018 EC question 47: Inputs X0, X1, X2, X3 on the left; — Figure from the GATE 2018 EC paper. It is part of the question.

Answer and solution

GATE 2018 EC Q.47: answer and solution

GATE 2018 EE Q.14

GATE 2018 · EEQ.14 · 1 mark · MCQ

In the logic circuit shown in the figure, Y is given by

GATE 2018 EE question 14: Three two-input NAND gates, each drawn as an AND shape with an output bubble. — Figure from the GATE 2018 EE paper. It is part of the question.

(A)
Y = ABCD
(B)
Y = (A + B)(C + D)
(C)
Y = A + B + C + D
(D)
Y = AB + CD

Answer and solution

GATE 2018 EE Q.14: answer and solution

GATE 2018 EE Q.37

GATE 2018 · EEQ.37 · 2 marks · MCQ

Digital input signals $A, B, C$ with $A$ as the MSB and $C$ as the LSB are used to realize the Boolean function $F = m_{0} + m_{2} + m_{3} + m_{5} + m_{7}$ , where $m_{i}$ denotes the $i^{t h}$ minterm. In addition, $F$ has a don't care for $m_{1}$ . The simplified expression for $F$ is given by

(A)
$\overline{A} \overline{C} + \overline{B} C + A C$
(B)
$\overline{A} + C$
(C)
$\overline{C} + A$
(D)
$\overline{A} C + B C + A \overline{C}$

Answer and solution

GATE 2018 EE Q.37: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 EE Q.37: answer and solution

GATE 2018 IN Q.43

GATE 2018 · INQ.43 · 2 marks · MCQ

The product of sum expression of a Boolean function $F (A, B, C)$ of three variables is given by

F (A, B, C) = (A + B + \overline{C}) \cdot (A + \overline{B} + \overline{C}) \cdot (\overline{A} + B + C) \cdot (\overline{A} + \overline{B} + \overline{C})

The canonical sum of product expression of $F (A, B, C)$ is given by

(A)
$\overline{A} \overline{B} C + \overline{A} B C + A \overline{B} \overline{C} + A B C$
(B)
$\overline{A} \overline{B} \overline{C} + \overline{A} B \overline{C} + A \overline{B} C + A B \overline{C}$
(C)
$A B \overline{C} + A \overline{B} \overline{C} + \overline{A} B C + \overline{A} \overline{B} \overline{C}$
(D)
$\overline{A} \overline{B} \overline{C} + \overline{A} B C + A B \overline{C} + A B C$

Answer and solution

GATE 2018 IN Q.43: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 IN Q.43: answer and solution

GATE 2018 IN Q.46

GATE 2018 · INQ.46 · 2 marks · MCQ

The Boolean function $F (X, Y)$ realized by the given circuit is

GATE 2018 IN question 46: Four 2-input NAND gates (every gate has an output bubble), inputs X and Y, output F. — Figure from the GATE 2018 IN paper. It is part of the question.

(A)
$\overline{X} Y + X \overline{Y}$
(B)
$\overline{X} \overline{Y} + X Y$
(C)
$X + Y$
(D)
$\overline{X} \cdot \overline{Y}$

Answer and solution

GATE 2018 IN Q.46: answer and solution

PRACTICE

6 questions to test yourself

PRACTICE 11 mark · NAT

How many Boolean functions $f (A, B, C)$ of three variables are self-dual and also satisfy $f (0, 0, 0) = 0$ ? (A function is self-dual if $f = f^{d}$ , where $f^{d} (A, B, C) = \overline{f (\overline{A}, \overline{B}, \overline{C})}$ .)

Answer and solution

Answer: $8$

$f$ is self-dual exactly when $f (x) \neq = f (\overline{x})$ for every input $x$ . Row $i$ and its bitwise complement, row $7 - i$ , form 4 pairs: (0,7), (1,6), (2,5), (3,4).
Exactly one row of each pair has output 1. The condition $f (0, 0, 0) = 0$ settles the first pair: $m_{0}$ is out and $m_{7}$ is in.
Each of the other 3 pairs has 2 choices, giving $2^{3} = 8$ .

PRACTICE 22 marks · MSQ

Consider $f (A, B, C, D) = \sum m (0, 4, 5, 7, 10, 13, 15) + d (2, 8)$ , where $A$ is the MSB and $d$ lists don't-care rows. A prime implicant is counted only if it covers at least one minterm of $f$ . Which of the following statements is/are correct?

(A)
$f$ has exactly four prime implicants.
(B)
Exactly two of the prime implicants are essential.
(C)
The minimal sum-of-products expression of $f$ is unique.
(D)
Every minimal sum-of-products expression of $f$ has 3 product terms and 7 literals in total.

Answer and solution

Answer: (A), (B), (D)

$B D$ covers 5, 7, 13, 15 (all 1s). $\overline{B} \overline{D}$ covers the four corners 0, 2, 8, 10 (1, X, X, 1). Both are PIs.
$m_{4}$ has neighbours 0 (1), 5 (1), 6 (0) and 12 (0), and every quad through $m_{4}$ contains a 0-cell (1, 6 or 12). So the pairs $\overline{A} \overline{C} \overline{D}$ (0, 4) and $\overline{A} B \overline{C}$ (4, 5) are PIs. There are no others, so there are 4 PIs: (A) is true.
$m_{7}$ is covered only by $B D$ and $m_{10}$ only by $\overline{B} \overline{D}$ , so both are essential. $m_{4}$ is covered by two non-essential PIs, so there are exactly 2 EPIs: (B) is true.
Minimal SOP: $\overline{B} \overline{D} + B D + \overline{A} \overline{C} \overline{D}$ or $\overline{B} \overline{D} + B D + \overline{A} B \overline{C}$ . There are two of them, so (C) is false, and each has 3 terms and $2 + 2 + 3 = 7$ literals, so (D) is true.

PRACTICE 32 marks · NAT

The number of minterms in the canonical sum-of-products form of $F (A, B, C, D) = (A + \overline{B} + C) (\overline{A} + D) (B + \overline{C} + D)$ is ________.

Answer and solution

Answer: $9$

$F = 0$ exactly when at least one sum term is 0.
$(A + \overline{B} + C) = 0$ when $A = 0, B = 1, C = 0$ : rows 4, 5. $(\overline{A} + D) = 0$ when $A = 1, D = 0$ : rows 8, 10, 12, 14. $(B + \overline{C} + D) = 0$ when $B = 0, C = 1, D = 0$ : rows 2, 10.
The union of the zero rows is ${2, 4, 5, 8, 10, 12, 14}$ , which is 7 rows (row 10 is counted once).
Minterms: $16 - 7 = 9$ , i.e. $F = \sum m (0, 1, 3, 6, 7, 9, 11, 13, 15)$ .

PRACTICE 41 mark · NAT

The function $f (A, B, C) = \sum m (1, 4, 5, 6, 7)$ , with $A$ as the MSB, is realised as a two-level NAND–NAND circuit of its minimal SOP. Only $A$ , $B$ and $C$ are available (no complemented inputs), so every complemented signal the circuit needs must come from a NAND gate with its inputs tied together. Gates may have any number of inputs. The total number of NAND gates, including those used as inverters, is ________.

Answer and solution

Answer: $4$

On the K-map, rows 4 to 7 form the quad $A$ , and $m_{1}$ can pair only with $m_{5}$ ( $m_{0}$ and $m_{3}$ are 0), giving $\overline{B} C$ . The minimal SOP is $f = A + \overline{B} C$ , and it is unique.
NAND–NAND form: $f = \overline{\overline{A} \cdot \overline{\overline{B} C}}$ . The product term $\overline{B} C$ needs one NAND and the output needs one NAND.
Complemented signals needed: $\overline{B}$ (inside $\overline{B} C$ ) and $\overline{A}$ (the single-literal term $A$ enters the output NAND complemented). That is two inverters.
Total: $1 + 1 + 2 = 4$ . Counting inverters only for variables that appear complemented in the SOP would give 3, and that circuit has no way to make $\overline{A}$ .

PRACTICE 51 mark · MCQ

Using $\overline{X}$ for the complement of $X$ , the expression $F = A \overline{B} + \overline{A} C + \overline{B} C + A B C$ simplifies to

(A)
$C + A \overline{B}$
(B)
$A \overline{B} + \overline{A} C$
(C)
$\overline{B} + C$
(D)
$A + C$

Answer and solution

Answer: (A)

Minterms ( $A$ is the MSB): $A \overline{B} \to 4, 5$ ; $\overline{A} C \to 1, 3$ ; $\overline{B} C \to 1, 5$ ; $A B C \to 7$ . So $F = \sum m (1, 3, 4, 5, 7)$ .
On the K-map, 1, 3, 5, 7 form the quad $C$ , and $m_{4}$ pairs with $m_{5}$ to give $A \overline{B}$ . So $F = C + A \overline{B}$ .
Check the others: (B) gives 0 at $A = B = C = 1$ ; (C) includes $m_{0}$ ; (D) includes $m_{6}$ . All three are wrong.

PRACTICE 62 marks · MCQ

Three 2-input NAND gates are connected as $G_{1} = NAND (A, B)$ , $G_{2} = NAND (A, G_{1})$ and $Y = NAND (G_{2}, C)$ . The output $Y$ equals

(A)
$A \overline{B} + \overline{C}$
(B)
$\overline{A} B + C$
(C)
$(A + \overline{B}) \overline{C}$
(D)
$\overline{A} \overline{B} + \overline{C}$

Answer and solution

Answer: (A)

$G_{1} = \overline{A B}$ .
$G_{2} = \overline{A \cdot \overline{A B}} = \overline{A (\overline{A} + \overline{B})} = \overline{A \overline{B}} = \overline{A} + B$ .
$Y = \overline{(\overline{A} + B) C} = \overline{\overline{A} + B} + \overline{C} = A \overline{B} + \overline{C}$ .

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE EC

Combinatorial circuits: Boolean algebra, minimization of functions using Boolean identities and Karnaugh map, logic gates

GATE EE

combinatorial … logic circuits

GATE IN

truth table, minimization of Boolean functions

Preparing in Kolkata? IAE Academy's course for GATE ECE, GATE EE or GATE IN.