Now option elimination could be used.

The Gateway to Computer Science Excellence

+25 votes

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**?

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

+47 votes

Best answer

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.

+8

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.

+8 votes

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?

+3 votes

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.

- $\mathrm{A}\oplus \mathrm{A}=\mathrm{A}\mathrm{\bar{A}}+\mathrm{\bar{A}}\mathrm{A}=0$
- $\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}$
- $\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}$
- $(\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**.

+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

0 votes

Answer c

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.

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 votes

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 ,

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

The reason why C is possible :

LHS can have combination of x1 and x3 as

- (1,1), when all of them are 1 and so RHS will also have (1,1) for (x2,x4).
- (0,0),when all of them are 0 and so RHS will also have (0,0) for (x2,x4).
- (1,0) or (1,1), when two them are 1 and so RHS will have (1,0) or (0,0) for (x2,x4).

0 votes

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.

(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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,542 answers

195,693 comments

101,535 users