GATE CSE 2007 | Question: 3

Question

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

• A. $n^2$
• B. $2^n$
• C. $2^{2^n}$
• D. $2^{n^2}$

Comments

In terms of digital:

n-variables

# of minterms=$2^n$

# of boolean functions=$2^{2^{n}}$

---

I am not sure my question is valid or not; but what if they ask 

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

then answer is 2^n ?

---

rajankakaniya I believe your question is the same as the one mentioned above? if that's the case, it will be still 2^2^n. 

---

………………………………………..

---

No of elements in the domain will be 2^n because there are total n boolean variables and for each variable we have two choices either to consider it in the boolean formula or not. No of possible functions will be |codomain|^|domain|. No of elements in codomain will be 2 so 2^(2^n) will be the answer.

---

https://staff.cdms.westernsydney.edu.au/cgi-bin/cgiwrap/zhuhan/dmath/dm_readall.cgi?page=3

Answer 1

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)}}$

Comments

According to u  this is mapping btw domain (n ) to co-domain (2 ) i.e boolean is given so co domain have 2 elements right!!

---

We have n boolean variables

So, we will have total of 2ⁿ combination of truth table values

For each of these 2ⁿ values, to define a boolean function they may be 0 or 1.

So we have 2 choices each for each 2ⁿ combination of truth table values

Hence the total number of boolean functions possible with n variables is $2^{2^{n}}$

---

Nicely explained thnx

---

@Ayush Upadhyaya this comment here should be an answer. Nice explanation.

Answer 2

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).

Comments

Thanks for simplified explanation :)

Answer 3

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).

Comments

Nice explanation@ mini

Answer 4

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}}$

Comments

consider we have 2 boolean variable a and b.--> n variables

They can have 4 diff combinations ab,ab',a'b,a'b'.--> 2^n combinations possible

example of boolean function can be ab+ab' or a'b or ab+ab'+a'b' and so on.

Now to be part of a function each combination have 2 options.--->each of  2^n combinations have 2 options

Therefore total functions are 2*2*2*2.

I hope my approach is correct.