GATE CSE 1987 | Question: 1-II

Question

The total number of Boolean functions which can be realised with four variables is:

• A. $4$
• B. $17$
• C. $256$
• D. $65, 536$

Comments

@svas7246

Your argument is correct, and on same argument we have a question in the GO Classes Test Series also, BUT in that question, we have EXPLICITLY defined everything that needs to be considered.

By default, if nothing is mentioned, Boolean Function itself implies Boolean Arguments.

https://en.wikipedia.org/wiki/Boolean_function

Video Solution of this question: https://youtu.be/qHnouulwPoc 

---

@Deepak Poonia Thank you for the point even i went with boolean by default now i am even  more sure 

---

I guess binary variables would be more appropriate

Answer 1

A Boolean function of $4$ variables is a function from a set of $2^4 = 16$ elements (all combinations of $4$ variables) to a set of $2 (\{0,1\})$ elements. So, number of such functions will be $2^{16} =65,536$

Correct Answer: $D$

Comments

For n variable, number of boolean functions = $2^{2^{n}}$

---

For a single variable let's say x

1. $x \rightarrow 0$
2. $x \rightarrow 1$
3. $\bar{x} \rightarrow 0$
4. $\bar{x} \rightarrow 1$

Total number of functions = 4

---

Using only one variable we got $4$ functions. 

$x$	$f_{1}$	$f_{2}$	$f_{3}$	$f_{4}$
0	0	0	1	1
1	0	1	0	1

References:

• https://math.stackexchange.com/questions/505393/how-many-semantically-different-boolean-functions-are-there-for-n-boolean-variab
• https://cs.fit.edu/~wds/classes/adm/Lectures/BooleanFunctions.pdf
• https://brilliant.org/wiki/logic-gates/

Answer 2

See this if you didn't understand

Answer 3

In a boolean function , there are two possibility for each midterm , that is it can either be present or absent in the boolean function . 

f = ABCD + ABCD’ + ABC’D + ABC’D’ + …………. 16terms

for example , 

          ABCD can be present or not in the boolean function therefore , the possible number of functions can be 

          2 x 2 x 2 x 2 x 2………..

         = 2^16

         = 65536

 

Answer 4

Let’s assume instead of 4, there is only one variable, say ‘a’.

for single variables, the number of input combinations will be 2 i.e. 0 and 1.

Function table for one variable

a	f1	f2	f3	f4
0	0	0	1	1
1	0	1	0	1

so here only 4 functions are possible in the case of one variable.

f1 = 0

f2= a

f3 = a’

f4 = 1

so from here, we can say that the number of functions is $2^{number of rows}$.

Number of rows =  $2^{number of variables}$.

In short, the Relation between the number of functions and the number of variables =  $2^{2^{number of variables}}$.

{Note: order should be maintained first do  $2^{number of variables}$ then what result you will get make that of power of 2}

Now in question, it is given that the number of variables = 4.

so, 

= $2^{2^{4}}$  

 = $2^{16}$.

= 65,536

The correct answer is Option D.