# GATE2016-2-08

4.6k views

Let, $x_{1} ⊕ x_{2} ⊕ x_{3} ⊕ x_{4}= 0$ where $x_{1}, x_{2}, x_{3}, x_{4}$ are Boolean variables, and $⊕$ is the XOR operator.

Which one of the following must always be TRUE?

1. $x_{1}x_{2}x_{3}x_{4} = 0$
2. $x_{1}x_{3} + x_{2} = 0$
3. $\bar{x}_{1} ⊕ \bar{x}_{3} = \bar{x}_{2} ⊕ \bar{x}_{4}$
4. $x_{1} + x_{2} + x_{3} + x_{4} = 0$

edited
6
Mentioned condition ($x1⊕x2⊕x3⊕x4=0$) will be true if number of 1's are even.

Now option elimination could be used.

Let $x_1 =1\; x_2=1\;x_3=1\;\text{and}\; x_4=1$

such that $x_1\oplus x_2\oplus x_3 \oplus x_4= 1\oplus 1\oplus 1\oplus1=0$

1. $x_1x_2x_3x_4= 1.1.1.1=1$ , False
2. $x_1x_3+x_2= 1.1+1=1$ , False
3. is always True.
4. $x_1+x_2+x_3+x_4= 1+1+1+1=1$ , False

Correct Answer: $C$

edited
0
Thanks for the reply.But my doubt is How do you know that all the values have to be same to solve the problem as in the statement it has not been mentioned anywhere.
16

More you practice more You know how to tackle the problem.

0
EXOR is the mod 2 ?????

x1 + x2 + x3 + x4 = 1+1+1+1 =1  How ???
2

for + atleast one 1 there then result will be 1 always.

0
@ashwina  + is OR gate
11

XOR is an odd function, i.e, it is equal to 1 if the input variables have an odd number of 1's.

here it is given that x1⊕x2⊕x3⊕x4=0 so no. of 1's must be 0 or 2 or 4.

All 1's i.e x1=x2=x3=x4=1 --------> makes option A,B,D false.

0
@praveen_sainni, how EXOR is mod 2 can u please explain ..!
3
it means, if no of 1's is even, then xor is 0

and no of 1's is odd then , xor is 1, take some example to check that
0
got it ! thanks sir
0
Its option C, not D, please make it specific, its confusing.
0
As per the given explanation the option (C) is true but not (D).

Option C) x'1⊕x'3=x'2⊕x'4

It can be easily observed with Truth table method

 x1 x2 x3 x4 x1⊕x2⊕x3⊕x4 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0

0

When X1=0,X2=1,X3=1,X4=1

x1⊕x2⊕x3⊕x4=1

But here x1' xor x3' =1 right

And x2' xor x4' =0

​​Now both of them are not equal then why option c is true?

0
No we have to take such that x1,x2,x3,x4 xored to give zero as given in question
But u r taking a combination i.e x1=0,x2=1,x3=1,x4=1
When they r all xored it gives 1 which violates the question:lol
0
oh yes, i didn't notice that..

thanks for correcting me..yeah i violated the qn,now i got it!

We know $\mathrm{A}\oplus \mathrm{B}=\mathrm{A}\mathrm{\bar{B}}+\mathrm{\bar{A}}\mathrm{B}$ and $\overline{\mathrm{A}\oplus \mathrm{B}}=\mathrm{A}\mathrm{B}+\mathrm{\bar{A}}\mathrm{\bar{B}}$

Now let's have some facts from this boolean equation.

1. $\mathrm{A}\oplus \mathrm{A}=\mathrm{A}\mathrm{\bar{A}}+\mathrm{\bar{A}}\mathrm{A}=0$
2. $\mathrm{B}\oplus \mathrm{A}=\mathrm{B}\mathrm{\bar{A}}+\mathrm{\bar{B}}\mathrm{A}=\mathrm{\bar{A}}\mathrm{B}+\mathrm{A}\mathrm{\bar{B}}=\mathrm{A}\mathrm{\bar{B}}+\mathrm{\bar{A}}\mathrm{B}=\mathrm{A}\oplus \mathrm{B}$
3. $\mathrm{\bar{A}}\oplus \mathrm{\bar{B}}=\mathrm{\bar{A}}\mathrm{\bar{\bar{B}}}+\mathrm{\bar{\bar{A}}}\mathrm{\bar{B}}=\mathrm{\bar{A}}\mathrm{B}+\mathrm{A}\mathrm{\bar{B}}=\mathrm{A}\oplus \mathrm{B}$
4. $(\mathrm{A}\oplus \mathrm{B})\oplus \mathrm{C}=(\mathrm{A}\mathrm{\bar{B}}+\mathrm{\bar{A}}\mathrm{B}) \mathrm{\bar{C}}+(\mathrm{A}\mathrm{B}+\mathrm{\bar{A}}\mathrm{\bar{B}})\mathrm{C}=\mathrm{A}\mathrm{\bar{B}}\mathrm{\bar{C}}+\mathrm{\bar{A}}\mathrm{B}\mathrm{\bar{C}}+\mathrm{A}\mathrm{B}\mathrm{C}+\mathrm{\bar{A}}\mathrm{\bar{B}}\mathrm{C}=\mathrm{A}(\mathrm{B}\mathrm{C}+\mathrm{\bar{B}}\mathrm{\bar{C}})+\mathrm{\bar{A}}(\mathrm{B}\mathrm{\bar{C}}+\mathrm{\bar{B}}\mathrm{C})=\mathrm{A}(\overline{\mathrm{B} \oplus \mathrm{C}})+\mathrm{\bar{A}}(\mathrm{B} \oplus \mathrm{C})=\mathrm{A}\oplus (\mathrm{B}\oplus \mathrm{C})$

Now

\begin{align} x_1\oplus x_2\oplus x_3\oplus x_4&=0\\ \Rightarrow x_1\oplus (x_2\oplus x_3)\oplus x_4&=0 ~;~[\mathrm{Using~no(4)}]\\ \Rightarrow x_1 \oplus (x_3\oplus x_2)\oplus x_4&=0 ~;~[\mathrm{Using~no(2)}] \\ \Rightarrow (x_1 \oplus x_3)\oplus (x_2\oplus x_4)&=0 ~;~[\mathrm{Using~no(4)}] \\ \Rightarrow x_1 \oplus x_3&=x_2\oplus x_4 ~;~[\mathrm{Using~no(1)}] \\ \Rightarrow \bar{x_1} \oplus \bar{x_3}&=\bar{x_2}\oplus \bar{x_4} ~;~[\mathrm{Using~no(3)}] \end{align}

So the correct answer is C as it must always be true.

0

@techbd123

How you write

$\implies x_{1}\oplus x_{3}=x_{2}\oplus x_{4}$ [using no $(1)$ ]?

1

The value of a boolean XOR operation is zero iff the two variables (or two expressions) are logically same (but NOT necessarily identical).

Let $f_1, f_2$ be the two boolean expressions.

If $f_1 \oplus f_2=0$, it definitely means $f_1 = f_2$.

0

@techbd123

Now I got it

thanks

1 vote

we know that XOR gate is odd 1s detector. The output will be 1 only when number of 1's in the input is odd else it is 0

So lets consider the case when the output can be zero i.e. number of 1s is even

 x1     x2      x3    x4 0       0        0      0 0       0        1      1 0       1        0      1 0       1        1      0 1       0        0      1 1       0        1      0   option B fails here 1       1        0      0 1       1        1      1   here option A and D fails

option C

$\overline{x_{1}} \oplus \overline{x_{3}}=\overline{x_{2}} \oplus \overline{x_{4} }$

=> $x_{1} \oplus x_{3}=x_{2} \oplus x_{4}$

option C holds for all the combinations

hence it is correct

edited by

Note that XOR is symmetric operation.For it to be zero the parity of number of 1s of mutually disjoint and exclusive sets should be same.
0
Can you elaborate on "number of 1s of mutually disjoint and exclusive sets" ?

A XOR B is simply the addition of  bits of A and B without carry.

So, out of 4 variables given here x1, x2, x3, x4 , given their XOR is 0 ,

1. they all should be 0  or
2. all should be 1 or
3. any two of them should be 1.

The reason why C is possible :

LHS can have combination of x1 and x3 as

1. (1,1), when all of them are 1 and so RHS will also have (1,1) for (x2,x4).
2. (0,0),when all of them are 0 and so RHS will also have (0,0) for (x2,x4).
3. (1,0) or (1,1), when two them are 1 and so RHS will have (1,0) or (0,0) for (x2,x4).
EXOR gate gives output as 1 when we have odd number of 1’s in the input.
(EXNOR gate gives output as 1 when we have even number of 0’s in the input.)

Now, given x1⊕x2⊕x3⊕x4=0 which means number of 1’s in the input is not odd (but even).
Possible input values of x1,x2,x3,x4 are: Zero 1’s, two 1’s or all four 1’s.

Now let’s check the options:
A) x1x2x3x4=0. False when we have all 1’s in the input.
B) x1x3+x2=0. False when two 1’s occur for the inputs x1,x3.
C) x¯1⊕x¯3=x¯2⊕x¯4. This is same as x1⊕x3=x2⊕x4
Now, since the number of 1’s in the input is even,
if number of 1’s in x1,x3 is even then number of 1’s in x2,x4 is also even and if number of 1’s in x1,x3 is odd then number of 1’s in x2,x4 is also odd. Hence this is always true.
D) x1+x2+x3+x4=0.  False when we have zero 1’s in the input.

edited

XOR is associative and commutative.

$x_1$ or $x_2$ or any other $x$'s order doesn't matter here.

$x_1⊕x_2⊕x_3⊕x_4= x_2⊕x_1⊕x_4⊕x_3$ or any other jumbled order.

The given function is true when we have two or four $1$'s

Since we can have four 1's; Options A and D are eliminated.

Since we can have two 1's, we can assign those 1's to $x_1$ and $x_3$ and Option B is eliminated.

It is a child's play to verify that Option C is the correct answer.

## Related questions

1
8k views
Consider an eight-bit ripple-carry adder for computing the sum of $A$ and $B$, where $A$ and $B$ are integers represented in $2$'s complement form. If the decimal value of $A$ is one, the decimal value of $B$ that leads to the longest latency for the sum to stabilize is ___________
Let $X$ be the number of distinct $16$-bit integers in $2's$ complement representation. Let $Y$ be the number of distinct $16$-bit integers in sign magnitude representation Then $X - Y$ is______.
Suppose the functions $F$ and $G$ can be computed in $5$ and $3$ nanoseconds by functional units $U_{F}$ and $U_{G}$, respectively. Given two instances of $U_{F}$ and two instances of $U_{G}$, it is required to implement the computation $F(G(X_{i}))$ for $1 \leq i \leq 10$. Ignoring all other delays, the minimum time required to complete this computation is ____________ nanoseconds.