Question

If we can generate a maximum of 4 Boolean functions using n Boolean variables, what will be minimum value of n?
1. 65536
2. 16
3. 1
4. 4

Answer 1

Correct Answer - Option 3 : 1

The correct answer is 1

• First, we need to understand that when there are no variables, there are two expressions :
  • False=0 and True=1
• For one variable p, four functions can be constructed. A function maps each input value of a variable to one and only one output value.
  • The False(p) function maps each value of p to 0 (False).
  • The identity (p) function maps each value of p to the identical value.
  • The flip (p) function maps False to True and True to False.
  • The True (p) function maps each value of p to 1 (True).
• For one variable: 
  • ​4 = \(2^{2^1}\), functions can be constructed.This information can be collected into a table: 

  • Input	Function
    p	False	p	-p	True
    0	0	0	1	1
    1	0	1	0	1

• For n Variables:

  • Number of Variables	Number of Boolean Functions
    0	\(2^{2^0}\) = 20 = 2
    1	\(2^{2^1}\) = 22 = 4
    2	\(2^{2^2}\) = 24 = 16
    3	\(2^{2^3}\) = 28 = 256
    4	\(2^{2^4}\) = 216 = 65536
    n	\(2^{2^n}\)

• Therefore, according to the above table, a maximum of 4 Boolean functions can be generated with 1 variable.