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

@pooja Be sure before making wrong edits. 

Please Check this: https://www.geeksforgeeks.org/gate-gate-cs-2007-question-3/

---

  @Puja Mishra

for a $n$ variable Boolean function $= 2^{2^{n}}$

---

with n  k-array variables(each variable can take any one of k value) mapped to m value function can have m^(k^n ) functions.

 

here m=2 k=2 n=4 hence 2^(2^4)

---

There is a point missing they should have said it as 4 boolean variables there could be ternary variables

---

@svas7246

The word “Boolean Function” implicitly implies that the variables are boolean. 

---

$\color{red}{\text{Find Detailed Video Solution Below}}$ $\color{BLACK}{\text{  , containing different methods to solve it:}}$

https://youtu.be/qHnouulwPoc

---

@Deepak Poonia But doesn’t boolean function mean after we take  variables and then we map the the set to a function which is boolean basically like  we map the variables to a function  which produces either 0/1 

If we say the total number of boolean functions which can be realized with ternary variables

then the total number will be 2^(3^n) right 

3*3*3* ….n mapped to a boolean function so it will be 2^(3^n)

Please correct if i am wrong  and if there is a concept that is missing in my  process
 

---

@Deepak Poonia Thank you for the video solution 

---

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