GATE 2014 EC (EC2) – Question 24

Digital Circuits · Combinatorial Circuits · 1 mark · Multiple choice

For an n-variable Boolean function, the maximum number of prime implicants is ______.

$2(n-1)$
$n/2$
$2^n$
$2^{n-1}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $2^{n-1}$

Explanation

The official answer is **2^(n−1),D**, the count attained by an n-variable parity function whose isolated1cells are prime implicants. However this is not a universal maximum on the number of prime implicants. For n=3, a function equal to1at all inputs except000and111has six prime implicants:xȳ,x̄y,xz̄,x̄z,yz̄,ȳz, exceeding2²=4. Preserve D for official grading, but do not use the claimed bound as a general theorem.