Function Equivalence MCQs: 12 Solved Boolean Algebra Problems

Function-equivalence options often differ by one complemented literal, one redundant consensus term or one missing minterm. Visual similarity is therefore unreliable. This set gives you exactly 12 solved questions, moving from named laws and absorption to variable independence, minterm matching, counterexamples and a multi-select proof.

Before opening an explanation, commit to an option and write either one algebraic reduction or one decisive input row. KnowledgeGate has about 40 published questions in this exact Function Equivalence subtopic, giving you room to practise after this set. You can place the topic within the wider syllabus through CS Fundamentals.

1. Three dependable tests for function equivalence

Use named Boolean laws when you can see a complement pair, absorption pattern or consensus term. For two or three inputs, a complete 2^n truth table is often quickest. For four variables, compare minterm sets or K-map groups. The proof standard matters: one mismatching row proves that two functions are not equivalent, but a few matching rows never prove equivalence.

For calibration, take F(A,B)=A'B'+AB'+A'B:

A'B'+AB'=B'(A'+A)=B'

B'+A'B=(B'+A')(B'+B)=A'+B'=(AB)'

For AB=00, 01, 10, 11, the values of F are 1, 1, 1, 0. The function is NAND, not OR or XOR. This collection applies those decisions under MCQ pressure.

2. Function equivalence MCQs 1-3: De Morgan, absorption and NAND

Question 1

Which Boolean Law is represented in the following?

U' + V' = (U · V)'

(Computer Science, KVS 2026 question)

• (a) Absorption Law

• (b) Commutative Law

• (c) De Morgan’s Law

• (d) Associative Law

Answer: (c) De Morgan’s Law.

The identity is (U·V)'=U'+V'. At U=1,V=0, the product is 0, so its complement is 1; the sum of complements is also 0+1=1. Absorption removes a repeated literal, commutation changes order and association changes grouping. Only De Morgan moves the complement across the operator.

Question 2

In Boolean algebra, A · (A + B) is logically equivalent to:

(EMRS 2023, Computer Science)

• (a) B

• (b) A · B

• (c) A + B

• (d) A

Answer: (d) A.

Apply absorption directly: A(A+B)=A. If A=0, the product is 0 for either value of B. If A=1, the bracket is 1+B=1, so the product is 1 for either value of B. The output always follows A.

Question 3

The Boolean expression

A′B′ + AB′ + A′B is equivalent to:

(NVS 2023, Computer Science)

• (a) A NAND B

• (b) A NOR B

• (c) A XOR B

• (d) A OR B

Answer: (a) A NAND B.

As above, the expression reduces to (AB)', with output sequence 1,1,1,0 for 00,01,10,11. That is NAND. Input 00 separates it from OR and XOR, which are both 0 there. NOR agrees at 00 but fails at 01 and 10.

3. Function equivalence MCQs 4-6: eliminate variables and collapse expressions

Question 4

The boolean expression AB + AB'+ A'C + AC is independent of the boolean variable

(Computer Science, ISRO 2015 question)

• (a) A

• (b) B

• (c) C

• (d) None of these

Answer: (b) B.

Reduce in pairs: AB+AB'=A(B+B')=A, while A'C+AC=C(A'+A)=C. The function is A+C, so B disappears. For example, (A,B,C)=(0,0,1) and (0,1,1) both give 1. Likewise, (1,0,0) and (1,1,0) both give 1.

Question 5

The Boolean function x'y' + xy + x'y is equivalent to

(GATE 2004, Computer Science)

• (a) x' + y'

• (b) x + y

• (c) x + y'

• (d) x' + y

Answer: (d) x' + y.

Group the x' terms: x'y'+x'y=x'(y'+y)=x'. The expression becomes x'+xy=x'+y by absorption. At the decisive row x=1,y=0, both the original expression and option (d) are 0, while options (a), (b) and (c) are 1.

Question 6

The boolean expression $\overline{A} \cdot B + A \cdot \overline{B}+ A \cdot B$ is equivalenet to

(UGC NET 2018 December, Computer Science)

• (a) $\overline{A} \cdot B$

• (b) $\overline{A+B}$

• (c) $A \cdot B$

• (d) $A+B$

Answer: (d) $A+B$.

Combine the last two terms: AB'+AB=A(B'+B)=A. Then A+A'B=A+B. Its complete truth signature is AB=00 -> 0, 01 -> 1, 10 -> 1, 11 -> 1, exactly the OR function.

4. Function equivalence MCQs 7-9: custom operators and minterm structure

Question 7

Let * be defined as

x * y = x' + y.

Let

z = x * y.

Value of

z * x

is

(GATE 1997, Computer Science)

• (a) x'+y

• (b) x

• (c) 0

• (d) 1

Answer: (b) x.

Substitute the definition instead of treating * as multiplication. Since z=x'+y, z*x=z'+x=(x'+y)'+x=xy'+x=x. When x=0, z=1 and z*x=0. When x=1, z=y and z*x=z'+1=1. The result follows x for either y.

Question 8

Consider the following boolean function of four variables, f (w, x, y,z) = Σ(1, 3, 4, 6, 9, 11, 12, 14], the function is

(ISRO 2009, Computer Science)

• (a) Independent of one variable

• (b) Independent of two variables

• (c) Independent of three variables

• (d) Dependent on all variables

Answer: (b) Independent of two variables.

The indices 1,3,9,11 share x=0,z=1, with w and y free. The indices 4,6,12,14 share x=1,z=0, again with w and y free. Therefore f=x'z+xz'=x XOR z, independent of exactly w and y.

Question 9

The switching expression corresponding to f(A, B, C, D) = Σ (1, 4, 5, 9, 11, 12) is

(Computer Science, GATE 2005 and ISRO 2009 question)

• (a) BC'D' + A'C'D + AB'D

• (b) ABC' + ACD + B'C'D

• (c) ACD' + A'BC' + AC'D'

• (d) A'BD + ACD' + BCD'

Answer: (a) BC'D' + A'C'D + AB'D.

Expand option (a) by covered minterms. BC'D' covers 4 and 12 because A is free. A'C'D covers 1 and 5 because B is free. AB'D covers 9 and 11 because C is free. Their union is exactly {1,4,5,9,11,12}, with nothing extra.

5. Function equivalence MCQs 10-12: modelling, counterexamples and MSQ proof

Question 10

Consider the following statements:

(a) Boolean expressions and logic gates networks correspond to labelled acyclic digraphs

(b) Optimal boolean expressions may not correspond to simplest networks.

(c) Choosing essential blocks first in a Karnaugh map and then greedily choosing the largest remaining blocks to cover may not give an optimal expression

Which of these statement(s) is/are correct?

(UGC NET 2015 June, Computer Science)

• (a) (a) only

• (b) (b) only

• (c) (a) and (b)

• (d) (a), (b) and (c)

Answer: (d) (a), (b) and (c).

Statement (a) models feed-forward gate connections as a labelled directed graph without combinational cycles. For (b), minimising literals is not always the same as minimising gate count, gate inputs or delay, particularly when subexpressions are shared. For (c), the remaining K-map cover is a set-cover choice, so selecting the locally largest group need not minimise the final cost.

Question 11

Let f(w, x, y, z) = ∑(0, 4, 5, 7, 8, 9, 13, 15). Which of the following expressions are NOT equivalent to f?

(GATE 2007, Computer Science)

• (a) x'y'z' + w'xy' + wy'z + xz

• (b) w'y'z' + wx'y' + xz

• (c) w'y'z' + wx'y' + xyz + xy'z

• (d) x'y'z' + wx'y' + w'y

Answer: (d) x'y'z' + wx'y' + w'y.

Use a counterexample. At (w,x,y,z)=(0,0,1,0), minterm 2 is absent from the target, so f=0; option (d) is 1 because w'y=1. Options (a), (b) and (c) each cover exactly {0,4,5,7,8,9,13,15}, while (d) covers {0,2,3,6,7,8,9}.

Question 12

Which of the following Boolean algebraic equation(s) is/are CORRECT?

(Computer Science, GATE 2025 Set 2 question)

• (a) $\overline{A}BC + A\overline{B}\,\overline{C} + \overline{A}\,\overline{B}\,\overline{C} + A\overline{B}C + ABC = BC + \overline{B}\,\overline{C} + \overline{A} \overline{B}$

• (b) $AB + \overline{A}C + BC = AB + \overline{A}C$

• (c) $(A + C)(\overline{A} + B) = AB + \overline{A}C$

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

Answer: (b), (c) and (d).

Reject (a) at (A,B,C)=(0,0,1): its left side is 0 and right side is 1. In (b), BC is the removable consensus term. Expanding (c) gives AB+A'C+BC, then the same identity applies. For (d), De Morgan gives A'BD+C'D'+AC'D'+A'B'D; pair the first and fourth terms as A'D, then absorb AC'D' into C'D', leaving A'D+C'D'.

6. The five traps these Boolean equivalence questions expose

Use a 60-second routine. For two inputs, write all four rows. For three inputs, use all eight rows only if the algebra does not collapse quickly. For four inputs, compare minterm sets or K-map groups. For an MSQ, reset and verify all four options independently. Then continue with Boolean Algebra and K-Map MCQs: 12 Solved (GATE) for broader practice.

7. Retest the weak method, then move to structured practice

Redo Questions 3, 4, 8, 9, 11 and 12 without looking. They test, respectively, a truth signature, variable elimination, minterm pairing, exact cover, a counterexample and independent MSQ verification. If a law question goes wrong, write the identity and its dual. For an independence miss, pair minterms differing only in the candidate free variable. For a minterm miss, expand every product into its exact index set. For an MSQ miss, treat each equation as a separate true-or-false claim.

If Questions 1 or 3 were weak, use NAND and NOR Universal Gates: 12 Solved MCQs. Continue with the Digital Electronics complete course, or use GATE Guidance by Sanchit Sir for the broader GATE route.

The short version: equivalent Boolean functions agree for every input. One mismatching input is enough to reject a candidate.