GATE CSE 2014 Set 3 | Question: 55

Question

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

• A. $P+Q$
• B. $\overline{P+Q}$
• C. $P \oplus Q$
• D. $\overline {P \oplus Q}$

Comments

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)

---

This help so much to simplify expression

---

Adding more to @Manu Thakur’s comment:-

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

Answer 1

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$

Comments

@Meghna yes, it is correct.

@Syed Yes, $A \oplus A = 0,$ here $A = (P \oplus Q)$

---

It is such a relief to not have to expand the options. -_-

---

Sir but A (EXOR) 1 = A’ or A only ?

Answer 2

D)
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.


 

Answer 3

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.

Answer 4

Alternatively, You can follow this approach too:

Comments

exactly the way I did...