in Digital Logic edited by
1,282 views
8 votes
8 votes

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

  1. $8$
  2. $16$
  3. $64$
  4. $32$
in Digital Logic edited by
by
1.3k views

2 Comments

Why not 2^3 =8
0
0
(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$
1
1

3 Answers

3 votes
3 votes
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
2 votes
2 votes

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))

by
1 vote
1 vote
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})}.$
Answer:

Related questions