As ⊕ is **commutative **and **associative **operator, so we can remove all the parentheses if required, and apply the following three properties

1. x⊕x = 0

2. 0⊕x = x

3. 1⊕x= x'

Answer will be (D)

The Gateway to Computer Science Excellence

+25 votes

Let $\oplus$ denote the exclusive OR (XOR) operation. Let '1' and '0' denote the binary constants. Consider the following Boolean expression for $F$ over two variables $P$ and $Q$:

$$F(P,Q)=\left( \left(1 \oplus P \right) \oplus \left( P \oplus Q \right )\right ) \oplus \left(\left(P \oplus Q\right) \oplus \left(Q \oplus 0\right)\right)$$

The equivalent expression for $F$ is

- $P+Q$
- $\overline{P+Q}$
- $P \oplus Q$
- $\overline {P \oplus Q}$

+34 votes

Best answer

XOR is associative and commutative. Also, $A \oplus A = 0$ and $A \oplus 1 = \overline{ A}$ and $A \oplus 0 = A$. So

$\left( \left(1 \oplus P \right) \oplus \left( P \oplus Q \right )\right ) \oplus \left(\left(P \oplus Q\right) \oplus \left(Q \oplus 0\right)\right)$

$\implies \left(1 \oplus P \right) \oplus \left( \left( P \oplus Q \right ) \oplus \left(P \oplus Q \right) \right) \oplus \left(Q \oplus 0\right)$

$\implies \left(1 \oplus 0 \right) \oplus \left( P \oplus Q \right) $

$\implies 1 \oplus \left( P\oplus Q \right)$

$\implies \overline {\left( P \oplus Q\right)}$

Correct Answer: $D$

$\left( \left(1 \oplus P \right) \oplus \left( P \oplus Q \right )\right ) \oplus \left(\left(P \oplus Q\right) \oplus \left(Q \oplus 0\right)\right)$

$\implies \left(1 \oplus P \right) \oplus \left( \left( P \oplus Q \right ) \oplus \left(P \oplus Q \right) \right) \oplus \left(Q \oplus 0\right)$

$\implies \left(1 \oplus 0 \right) \oplus \left( P \oplus Q \right) $

$\implies 1 \oplus \left( P\oplus Q \right)$

$\implies \overline {\left( P \oplus Q\right)}$

Correct Answer: $D$

+11 votes

Since there are only 2 variables putting in pair of values of P and Q in F and checking with the options is a time saving method.

But Lets solve it.

+2 votes

Using the properties of **associativity** and **commutativity, **and the below mentioned properties we can find the correct answer:

**1. $X⊕X = 0$**

**2. $X⊕1=X'$**

**3. $X⊕0=X$**

$F(P,Q)=((1⊕P)⊕(P⊕Q))⊕((P⊕Q)⊕(Q⊕0))$

$=(P'⊕(P⊕Q))⊕((P⊕Q)⊕(Q⊕0))$

$=((P'⊕P)⊕Q))⊕((P⊕Q)⊕(Q⊕0))$

$=((1⊕Q)⊕((P⊕Q)⊕(Q⊕0))$

$=(Q'⊕((P⊕Q)⊕(Q⊕0))) $

$=(Q'⊕((P⊕Q)⊕Q)) $

$=(Q'⊕(P⊕(Q⊕Q))) $

$=(Q'⊕(P⊕0)) $

$=(Q'⊕P) $

$=(Q⊕P)'$

So, the correct option is, **option no. D**.

+1 vote

We need to simplify the above expression. As the given operation is XOR, we shall see property of XOR. Let A and B be boolean variable. In A XOR B, the result is 1 if both the bits/inputs are different, else 0. Now,

( ( 1 X P) X (P X Q) ) X ( (P X Q) X (Q X 0) ) ( P' X P X Q ) X ( P X Q X Q ) ( as 1 X P = P' and Q X 0 = Q ) (1 X Q) X ( P X 0) ( as P' X P = 1 , and Q X Q = 0 ) Q' X P ( as 1 X Q = Q' and P X 0 = P ) PQ + P'Q' ( XOR Expansion, A X B = AB' + A'B ) This is the final simplified expression. Now we need to check for the options. If we simplify option D expression. ( P X Q )' = ( PQ' + P'Q )' ( XOR Expansion, A X B = AB' + A'B ) ((PQ')'.(P'Q)') ( De Morgan's law ) ( P'+ Q).(P + Q') ( De Morgan's law ) P'P + PQ + P'Q' + QQ' PQ + P'Q' ( as PP' = 0 and QQ' = 0 ) Hence both the equations are same. Therefore Option D.

52,345 questions

60,514 answers

201,933 comments

95,365 users