The expression 2^n counts truth-table rows, while 2^(2^n) counts complete Boolean functions. That extra exponent is where an otherwise easy question goes wrong. Every count in the ten questions below comes from two numbers: how many input rows the variables create, and how many of those rows you are still free to choose an output for. Row counts, unrestricted function counts, self-dual counts, duality, complementation and Shannon expansion are that same arithmetic applied to different amounts of freedom. If the surrounding algebra needs a refresh, begin with these Boolean algebra and K-map MCQs.
1. The two-stage counting model to use before every question
With n Boolean variables, each variable can be 0 or 1. The input side therefore has 2^n distinct rows. A Boolean function assigns one independently chosen output, again 0 or 1, to every row. Hence the number of possible output columns is:
2 × 2 × ... × 2, with 2^n factors, which is 2^(2^n).
Variables | Truth-table rows | Distinct functions |
|---|---|---|
1 | 2 |
|
2 | 4 |
|
3 | 8 |
|
4 | 16 |
|
Keep three quantities separate: variables n, rows 2^n, and functions 2^(2^n). Use the cue inputs first, output columns second.
2. Questions 1 to 3: rows first, then concrete function counts
Question 1: truth-table rows for n variables
Stem: A truth table will need how many rows if there are n variables.
Options:
2*nn2n
none of these
Answer: 2n. Each of the n variables independently has two values. The Cartesian product therefore has 2 × 2 × ... × 2 = 2^n assignments. For n=3, they are 000, 001, 010, 011, 100, 101, 110, 111, exactly 8, not 6 or 3.
Question 2: all functions of two variables
Stem: In two-valued Boolean algebra, the maximum number of Boolean functions for two variables will be
Options:
81216More than one of the aboveNone of the above
Answer: 16. The inputs (0,0), (0,1), (1,0), (1,1) make four rows. Every function is one four-bit output column, so there are 2^4=16 columns. AND, OR, XOR, constants, projections, and complements are examples among these 16, not extra functions outside the count.
Question 3: all functions of four variables
Stem: How many different Boolean functions of degree 4 are there ?
Options:
24
28
212
216
Answer: 216. Four variables produce 2^4=16 input rows. Choosing one binary output for every row gives 2^16=65,536 functions. The first option, 2^4, counts rows, not functions.
3. Questions 4 to 5: read the nested exponent correctly
Question 4: the general count in symbolic form
Stem: How many different Boolean functions of degree 𝑛 are there?
Options:
2^(2^𝑛)
(2^2)^𝑛
2^(2^𝑛) − 1
2^𝑛
Answer: 2^(2^𝑛). Build the formula: 2^n rows, then two output choices for each row. By contrast, (2^2)^n=2^(2n) grows much more slowly. Subtracting one would wrongly discard a valid output column, such as the constant-zero function.
Question 5: the same count in compact typesetting
Stem: What is the maximum number of different Boolean functions involving n Boolean variables?
Options:
n2
2n
22ⁿ
2n²
Answer: 22ⁿ, meaning 2^(2^n). For n=3, the options represent n^2=9, 2^n=8, and 2^(2^n)=2^8=256. Cramped superscripts can hide the nesting, so always compute the inner 2^n first.
4. Question 6: count self-dual functions by complementary input pairs
Question 6: unrestricted versus self-dual counts
Stem: The dual of a Boolean function F(x₁,x₂,…,xₙ, +, ·, ′) written as Fᴰ is the same expression as that of F with + and ⋅ swapped. F is said to be self-dual if F = Fᴰ. The number of self-dual functions with n Boolean variables is
Options:
2^n
2^(n−1)
2^(2^n)
2^(2^(n−1))
Answer: 2^(2^(n−1)). Pair every input word with its bitwise complement. The 2^n rows form 2^(n-1) pairs. In a self-dual function, choosing one output in a pair forces the other, so there are 2^(n-1) independent output bits and 2^(2^(n-1)) functions.
For n=3, the pairs are 000↔111, 001↔110, 010↔101, and 011↔100. Four free bits produce 2^4=16 self-dual functions. Without the self-dual restriction, eight free bits produce 2^8=256 functions.
5. Questions 7 to 8: dual and complement are different operations
Question 7: the mechanical rule for forming a dual
Stem: The dual of a Boolean expression is obtained by interchanging
Options:
Boolean sums and Boolean productsBoolean sums and Boolean products or interchanging 0’s and 1’sBoolean sums and Boolean products and interchanging 0’s & 1’sInterchanging 0’s and 1’s
Answer: Boolean sums and Boolean products and interchanging 0’s & 1’s. Apply both swaps together: + ↔ · and 0 ↔ 1. Variables and existing complements remain unchanged. Thus the dual of x + 0 is x · 1, while the dual of x(y + 0) is x + (y · 1).
Question 8: apply DeMorgan after removing duplicate terms
Stem: Which of the following is the complement of the boolean function.
A'B+CD'+A'B+CD'
Options:
A'B+CD'(A'+B)(C+D')(A+B')(C'+D)A(C' + D)
Answer: (A+B')(C'+D). First use idempotence to remove the repeated term: F=A'B+CD'. Then apply DeMorgan step by step: F'=(A'B+CD')'=(A'B)'(CD')'=(A+B')(C'+D). Simplification removed duplication; complementation changed the outer sum to a product and complemented the literals. Contrast that with Question 7: the dual of A'B+CD' is (A'+B)(C+D'), which swaps the operators but leaves every literal exactly as it stands. That expression is the second option above, offered precisely because a dual looks like a complement until you check the literals.
6. Questions 9 to 10: involution and Shannon expansion checks
Question 9: double complement
Stem: If x is a Boolean variable, then ((x′)′) will be
Options:
x'xx+x'More than one of the aboveNone of the above
Answer: x. The involution law is (x')'=x. Also, x+x'=1, not x, so the option x+x' is not an alternative form of the answer. That also eliminates More than one of the above.
Question 10: identify the equation that drops the selector variable
Stem: Given a boolean function f (x1, x2, ..., xn), which of the following equations is NOT true
Options:
f(x1, x2, …, xn) = x1'f(x1, x2, …, xn) + x1f(x1, x2, …, xn)
f(x1, x2, ..., xn) = x2f(x1, x2, …, xn) + x2'f(x1, x2, …, xn)
f(x1, x2, ..., xn) = xn'f(x1, x2, …, 0) + xnf(x1, x2, …,1)
f(x1, x2, ..., xn) = f(0, x2, …, xn) + f(1, x2, ..., xn)
Answer: the fourth equation, f = f(0, x2, ..., xn) + f(1, x2, ..., xn), is NOT true. In each of the first two equations, factor out f: (x_i'+x_i)f=1·f=f. The third equation is Shannon expansion about x_n, with the selector terms present.
For the fourth equation, take f(x_1,...,x_n)=x_1. Its left side is x_1, but its right side is f(0,...)+f(1,...)=0+1=1. When x_1=0, the claimed equality becomes 0=1, so it fails.
7. Exam traps, one-minute revision, and the next practice route
Turn the solutions into five checks:
Do not confuse rows
2^nwith functions2^(2^n).Do not flatten
2^(2^n)into2^(2n).For self-dual functions,
2^(n-1)is the number of free bits, not the final count.When forming a dual, swap both the operators and the constants.
In Shannon expansion, retain the selector terms with their cofactors.
Now close the page and rebuild this six-line recap:
rows=2^nall functions=2^(2^n)n=2 → 16n=4 → 65,536self-dual functions=2^(2^(n-1))f=x'f(0)+xf(1)
Derive each line from a truth table instead of reciting it. For the neighbouring method, work through Boolean algebra and K-map minimization.
Choose the next route by need. GATE Guidance by Sanchit Sir gives structured Digital Electronics concept and PYQ study, while the GATE Test Series is the route for timed practice. Use the GATE category for broader exam navigation.
Finish by redoing Questions 3, 5, 6, 8, and 10 without looking at the explanations. In order, they test concrete function counts, nested exponents, complementary input pairs, DeMorgan, and Shannon expansion.
