retagged by
10,004 views
34 votes
34 votes

What is the maximum number of different Boolean functions involving $n$ Boolean variables?

  1. $n^2$
  2. $2^n$
  3. $2^{2^n}$
  4. $2^{n^2}$
retagged by

4 Answers

Best answer
50 votes
50 votes
answer - C

size of domain = number of different combinations of inputs  $=2^{n}.$

size of codomain $= 2 ( \{0,1\} ).$

number of functions $= \text{(size of co-domain)}^{\text{(size of domain)}}$
edited by
23 votes
23 votes

With n boolean variables total number of rows in the truth table = 2^n

Each row of truth table can be taken or not taken (only 2 choices) .

So, maximum no of different boolean functions possible = 2^(2^n)

The correct answer is,(C) 2^(2^n).

18 votes
18 votes
We know that a K-map is used to represent and simplify a boolean function. Given 'n' no. of boolean variables, number of cells in the K-map is 2^n. Now each cell has two options. Either 1(True) or 0(False) [in case of SOP]. Different combinations of cells each having value=1 will give generate different functions (which later can be simplified but that is not our concern here). So in that way total number of functions will be 2^(2^n).
edited by
7 votes
7 votes

The number of m-ary functions in p-valued algebra having n-variables is given by $m^{p^{n}}$

Here, m = 2 (boolean functions), p = 2 (boolean variables) and n = n (number of variables)

So, total functions = $2^{2^{n}}$

 Alternative approach :

With n boolean variables, we can have ${2^{n}}$ combinations for functions. And now since each of these is designed to be a boolean function, it's output value can be either 1 or 0, i.e. 2 choices for each function. So total such functions = $2^{2^{n}}$

Answer:

Related questions

41 votes
41 votes
3 answers
2
60 votes
60 votes
5 answers
3
Kathleen asked Sep 21, 2014
19,417 views
How many different non-isomorphic Abelian groups of order $4$ are there?$2$$3$$4$$5$
26 votes
26 votes
3 answers
4
Kathleen asked Sep 21, 2014
8,502 views
Let $S$ be a set of $n$ elements. The number of ordered pairs in the largest and the smallest equivalence relations on $S$ are:$n$ and $n$$n^2$ and $n$$n^2$ and $0$$n$ an...