GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
111 views

Given $x,y,z$ are Boolean variables and $f(x,y,z)=f(y',x',z)$. How many such functions are possible with $x, y, z$?

  1. $0$
  2. $2^2$
  3. $2^4$
  4. $2^6$ 
asked in Set Theory & Algebra by Junior (953 points)  
retagged by | 111 views
yes $2^6$
i want explanation i didn't get the explanation which was given in source.
unable to understand the que?? wht is que asking??

plz explain

1 Answer

+5 votes
Best answer

In a three variable boolean function if all of the truth table rows are independent w.r.t the O/P, then total no of boolean function possible is $2^{2^3} = 256$

  • because in the O/P of a truth table we have $2^n= 2^3$ places to fill with 0 or 1. 
  • This is possible because we have not specified any constraint on the boolean function.

 The question here provide us with a constraint equation $f(x,y,z) = f(y',x',z)$

because of this constraint, all 8 rows of the truth table are not independent now. They are in 6 groups.

  1. $f(0,0,0) \ \ \ \text{ and } \ \ f(1,1,0)$ are having same O/P.
  2. $f(0,0,1) \text{ and } f(1,1,0)$ are having same O/P.
  3. $f(0,1,0) ,f(0,1,1) ,f(1,0,0) ,f(1,0,1) ,$ are independent.

So in these 6 rows of the truth table, we can fill up O/P with 0 or 1. 

$\Rightarrow$ total $2^6$ functions possible.

note : we can also solve by calculating no of minterms and taking combinations of them. 

answered by Veteran (50.9k points)  
selected by
highly appreciated !

question has same logic as Self dual function



Top Users Aug 2017
  1. ABKUNDAN

    4654 Points

  2. Bikram

    4012 Points

  3. akash.dinkar12

    3136 Points

  4. rahul sharma 5

    2832 Points

  5. manu00x

    2644 Points

  6. makhdoom ghaya

    2370 Points

  7. just_bhavana

    2040 Points

  8. Tesla!

    1742 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1554 Points


24,864 questions
31,941 answers
74,060 comments
30,062 users