GATE IT 2006 | Question: 6

Question

Given a boolean function $f (x_1, x_2, \ldots, x_n),$ which of the following equations is NOT true?

• A. $f (x_1, x_2, \ldots, x_n) = x_1'f(x_1, x_2, \ldots, x_n) + x_1f(x_1, x_2, \ldots, x_n)$
• B. $f (x_1, x_2, \ldots, x_n) = x_2f(x_1, x_2, \ldots , x_n) + x_2'f(x_1, x_2, \ldots ,x_n)$
• C. $f (x_1, x_2, \ldots, x_n) = x_n'f(x_1, x_2, \ldots, 0) + x_nf(x_1, x_2, \ldots,1)$
• D. $f (x_1, x_2, \ldots , x_n) = f(0, x_2, …, x_n) + f(1, x_2, \ldots, x_n)$

Comments

Option A,B are ofcourse correct if we take f(x1,x2….xn) common from RHS then it becomes equal to LHS. We can check Option C by taking two cases, in case 1 assume xn=0 then LHS  f(x1,x2….0)=1* f(x1,x2….0)+0*f(x1,x2….1). Clearly LHS=RHS. Similarly we can do in case 2 where we assume xn=1. In Option D if we take x1=1 then LHS=f(1,x2,x3….xn) and RHS remains unaffected so LHS!=RHS. No need to check case 2 although in that case also LHS!=RHS  i.e whatever value we take of x1 RHS remains same. So option D is incorrect. @Deepak Poonia sir is this correct approach of solving this question?

---

@Shukla_ helpful!!

---

here for option c and d 
-------------------------------------------------------------------------------------------------------------------------------------------------------
it is bolean function so any varible will takes input as 0 or 1.
---------------------------------------------------------------------------------------------------------------------------------------------------
new lets try to see intituvley.
f(x1,x2) is a boolean function and they have not given any specific function value so ho many function can be possible .

now here two varible so totol function ----2^(2^n)

where n is no of varible and codomain is 2.

and i hope you people know this forumula .
-----------------------------------------------------------------------------------------------------------------------------------------------------
now here 2^(2^2) function are possible means 16 any function can be possible
either 
f(x1,x2)=x1*x2;
f(x1+x2)=x1+x2
like this any think can be possible 
----------------------------------------------------------------------------------------------------------------------------------------------------
now llets come to the question.
---------------------------------------------------------------------------------
for option c 
line A  )f(x1,x2,x3------xn)=(xn)bar(f(x1,x2,------0)+(xn)(x1,x2,x3------1))#(bar wala first part and without bar second part)

now just look what at are the value which is poosible for xn-->(0,1).

case1) take x=0 means you are going to the funtion and were ever value  xn is present you are puttng xn=0

so if you will look at first part  of Line A then first part is doing the same and second part is doing reverse.

so. what you want 
you want first part should be as output  so here xn=0 when you will put second part will automatically get out of picture

and first part are comming as output.
case 2)

if you take xn=1)
--------------------------------
what you want second part so if you will put x=0 first part get out of picture and second part will come as output
------------------------------------------------------------------------------------------------------------------------------------------------
now for option d
-------------------------
f(x1,x2,x3------xn)=(f(0,x2,------xn)+(1,x2,x3------xn)  #(0 wala part 1 and 1 wala part 2)
now what are the possible value for x1=0
x1=0,1
now 
case 1)  when x1=0 what you want in output first part should be reflect 
but here you can see there is no way such that one part we can eliminate just like earlier question
--------------------------------------------------------------------------------------------------------
here it wont depedndet on x1 becuse if you keep x1=0 and x1=1 in both case you will get same answer
------------------------------------------------


 

 

Answer 1

Answer: D

Proceed by taking $f(x_1) = x_1$

LHS: $f(x_1)  = 0$ when $x_1 = 0$

LHS: $f(x_1)  = 1$ when $x_1 = 1$

RHS: $f(0) + f(1) = 0 + 1 =$ always $1$

Comments

@vivek18 means?

---

A. f(x1 , x2) = x1 ‘f(x1 , x2) + x1 f(x1 , x2)

                    = (f1’+f1) f(x1 , x2)= f(x1 , x2)

so we will never be able find value of f(x1,x2)

---

(x1’+x1) f(x1, x2) = f(x1, x2)
Here it is not asking for the value.

Answer 2

option D is NOT TRUE.

Comments

good example, thanx!

---

best answer so far here

---

You are trying to prove something by taking just one example. This is wrong.

Answer 3

A,B,C are true.

Because in all these three cases we could a boolean variable and its compliment is added to same function.

ie : if x= 1 then x' =0 and viceversa.

1.f(x) + 0.f(x) = f(x)

Hence D is false.

Answer 4

For option $A$

$$f(x_1,x_2,…,x_n)=x_1’f(x_1,x_2,…,x_n)+x_1f(x_1,x_2,…,x_n) =(x_1’+x_1)f(x_1,x_2,…,x_n)=1.f(x_1,x_2,…,x_n)=f(x_1,x_2,…,x_n) $$

So option $A$ is correct.

---

Similarly for option $B$

$$f(x_1,x_2,…,x_n)=x_2’f(x_1,x_2,…,x_n)+x_2f(x_1,x_2,…,x_n) =(x_2’+x_2)f(x_1,x_2,…,x_n)=1.f(x_1,x_2,…,x_n)=f(x_1,x_2,…,x_n) $$

So option $B$ is correct.

---

For option $C$,

Now the given function, we can have two possibilities: either $x_n$ is true or $x_n$ is false.

(1) when $x_n$ is false, the function becomes $f(x_1,x_2,…,0)$ and this situation as a whole is represented conditionally as : $x_n’f(x_1,x_2,…,0)$

(2) when $x_n$ is true, the function becomes $f(x_1,x_2,…,1)$ and this situation as a whole is represented conditionally as : $x_nf(x_1,x_2,…,0)$

Since our function is a logical “or” of the above two situations, so we have:

$$f(x_1,x_2,…,x_n)=x_n’f(x_1,x_2,…,0)+x_nf(x_1,x_2,…,1)$$

So option $C$ is true.

---

From this we can say that option $D$ is the wrong option. But why is it so?

This so because if you think logically the function is given as:

$$f(x_1,x_2,…,x_n)=f(0,x_2,…,x_n)+f(1,x_2,…,x_n)$$

Whatever function we consider, the function given on the RHS is independent of $x_1$ which is a problem.

Comments

great!

---

Nice .

---

If option D is like,

f(x1, x2,…, xn) =(~x1) f(0, x2,…, xn) + (x1)f(1, x2,…, xn)

then it will be correct right?