NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 20

Question

The possible number of Boolean function of $3$ variables $X,Y$ and $Z$ such that $f(X,Y,Z) = f(X’,Y’,Z’)$

• A. $8$
• B. $16$
• C. $64$
• D. $32$

Comments

Why not 2^3 =8

---

(X, Y, Z) is mutually exclusive to (X’, Y’, Z’)

number of mutually exclusive pair = $2^{n-1} = 2^2$

Output of each pair has two choice either 0 or 1

Therefore, number of functions are $2^{2^2} = 2^4 = 16$

---

Detailed Video Explanation: https://youtu.be/DbKnUyyzlZs?t=6433

Answer 1

f(x,y,z)=f(x',y',z')
(0,0,0)=(1,1,1)
(0,0,1)=(1,1,0)
(0,1,0)=(1,0,1)
(0,1,1)=(1,0,0)

Like above other input combinations also repeat after these inputs.
- We have 4 input pairs and produces output either o or 1.
- Total functions possible=2*2*2*2 (or) 2^4 =16

Answer 2

As per the above condition a particular input and its complement will have the same bit assigned to them.

Total possible inputs = 2^n = 2 ^3 = 8

 

Lets group together an input and its complement: 
 

(0,0,0), (1,1,1)
(0,0,1), (1,1,0)
(0,1,0), (1,0,1)
(0,1,1), (1,0,0)

 

Total groups = 4

2 Possibilities for each group i.e. 0/1

 

So, total number of functions possible = 2^4 = 16

 

In general for n variable function:

 

Total groups = 2^n / 2 = 2 ^(n – 1)

 

Total functions = 2 ^ (2 ^ (n – 1))

Answer 3

Detailed Video Explanation: https://youtu.be/DbKnUyyzlZs?t=6433

Understand the given function.

$f(X,Y,Z) = f(X’,Y’,Z’)$ means:

$f(0,0,0) = f(1,1,1)$ ;

$f(0,0,1) = f(1,1,0)$ ;

$f(0,1,0) = f(1,0,1)$ ;

$f(0,1,1) = f(1,0,0)$;

So, number of such functions over $3$ variables is $2^4 = 16.$

For $n$ variables:

$f(a_1,a_2, \dots a_n) = f(a_1’,a_2’, \dots a_n’)$ means:

For any row $0 \leq m \leq 2^n -1$, $f(m) = f(2^n – 1 – m).$

So, the number of boolean functions for which $f(a_1,a_2, \dots a_n) = f(a_1’,a_2’, \dots a_n’)$, is $2^{(2^{n-1})}.$

Detailed Video Explanation: https://youtu.be/DbKnUyyzlZs?t=6433

Answer 4

A function that takes three inputs (X, Y, Z), each 0 or 1, and produces one output (0 or 1).

There are 2³ = 8 possible input combinations (X, Y, Z can each be 0 or 1 → 8 rows in truth table)

Each of the 8 rows has 2 output choices (0 or 1), independently.

So total functions = 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 2⁸ = 256.

f(X,Y,Z) = f(X', Y', Z') constraint forces pairs to agree. So:

• For pair {0, 7}: both rows must equal the same value → 1 choice (either both 0 or both 1) → 2 options
• For pair {1, 6}: same → 2 options
• For pair {2, 5}: same → 2 options
• For pair {3, 4}: same → 2 options

Total: 2 × 2 × 2 × 2 = 2⁴ = 16

Answer: (B) 16