Number of Boolean Functions

Computer Science Level 3

How many different Boolean functions can be made using 3 Boolean variables?

Details and Assumptions

Functions should be in the simplified form. $i.e, F(x,y,z)=x+\overline{x}+y+z$ is equivalent to $G(x,y,z)=1$ $\implies$ they are not different.

The answer is 256.

5 solutions

Agnishom Chattopadhyay
Mar 8, 2014

Each function looks like this

f(0,0,0) = a1
f(0,0,1) = a2
f(0,1,0) = a3
f(0,1,1) = a4
f(1,0,0) = a5
f(1,0,1) = a6
f(1,1,0) = a7
f(1,1,1) = a8

Now each of these a variables can be plugged in with either 0 or 1. For 8 variables, there are 2^8 ways to do it.

Thus, the answer is 256

Let us prove that for $n$ variables, $2^{2^n}$ functions are possible. First of all, we need to choose $n$ numbers, each $0$ or $1$ , for the input. $2^n$ ways are possible, because to select one number, $2$ ways are possible. Furthermore, the output of each of these $2^n$ inputs can be a $0$ or a $1$ . So a total of $2^{2^n}$ functions are possible. For $n=3$ , $2^{2^3}$ or $256$ boolean functions are possible.

Shourya Pandey - 7 years, 3 months ago

Muhammad Jehanzeb Adil
Mar 11, 2014

No. of Rows in Truth Table = r =2^n

Where n = No. of Variables in Truth Table .

No. of Possible Boolean Functions = Fn =2^r

Where r = No. of Rows in Truth Table .

Now

n =3

r =2^3=8,

Fn =2^8=256

Gopi Vishwakarma
Mar 13, 2014

let say, n=3. There are 2^3 sequences of length 3 made up of 0's and / or 1's.
To make a Boolean function, for each of these sequences, we can independently choose the value of our function at the sequence.
Thus there are 2^(2^n) Boolean functions of n variables.

Therefore for n =3 answer is 2^(2^3) = 256

Yash Bansal
Mar 9, 2014

$2^{2^{3}}$ is simple to arrive at. More importantly, one should know that all the 256 mathematical permutations of the functions can be realised. i.e. one does not need to check whether a particular function is possible or not. In that case the solution would have been dificult.

Using an idea similar to Karnaugh Maps it can be shown that all these 256 combinations can be acquired.

Aditya Sriram - 7 years, 3 months ago

Perhaps, using the same idea. Infact Karnaugh map can be prepared because of this property.

Yash Bansal - 7 years, 3 months ago

Singanamala Kiran Kumar
Mar 9, 2014

Suppose we take boolean variable 'a' possible functions are => f(a)= 0, f(a)=1, f(a) = a, f(a)= ~a => 4 combinations Suppose we take boolean variables 'a,b' possible functions are => f(a,b)= (a AND b) or (a NAND b) or (a OR b) or (a NAND b) or (a EQUI b) or (a XOR b) or (a IMPLIES b)or (~(a IMPlES b)) or (b IMPLIES a)or (~(b IMPlES a)) or False or True or a or ~a or b or ~b => 16 combinations

Number of Boolean Functions

The answer is 256.

5 solutions

0 pending reports