# GATE2014-3-55

3.4k views

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

1. $P+Q$
2. $\overline{P+Q}$
3. $P \oplus Q$
4. $\overline {P \oplus Q}$
16

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'

0
This help so much to simplify expression

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$

edited
–1

@Arjun pls explain this simplification 0

⟹(1⊕P)⊕((P⊕Q)⊕(P⊕Q))⊕(Q⊕0)    //Sir is the expression in bold = 0 ? can u elaborate a bit ?
⟹(1⊕0)⊕(P⊕Q)

3

@Arjun Sir, in your second step:

⟹(1⊕P)⊕((P⊕Q)⊕(P⊕Q))⊕(Q⊕0)⟹(1⊕P)⊕((P⊕Q)⊕(P⊕Q))⊕(Q⊕0)
⟹(1⊕0)⊕(P⊕Q)

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

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

=P' ⊕ Q

=P ExNOR Q

=(P⊕Q)'

0
@Meghna yes, it is correct.

@Syed Yes, $A \oplus A = 0,$ here $A = (P \oplus Q)$
0
It is such a relief to not have to expand the options. -_-

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. Alternatively, You can follow this approach too: 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.

edited
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. 
0

# =(Q+P)'1

0
Great explanation
observe the common term p ex or q in both

consider a case where p and q are equal

then p ex or q results in 0

1)in first p is ex ored  with 1

2)in second q is ex ored with 0

so if p, q are same then either of one oresults in 1 and another to 0

1 ex or  0

it is exnor

## Related questions

1
5.3k views
The above synchronous sequential circuit built using JK flip-flops is initialized with $Q_2Q_1Q_0 = 000$. The state sequence for this circuit for the next $3$ clock cycles is $001, 010, 011$ $111, 110, 101$ $100, 110, 111$ $100, 011, 001$
Consider the following minterm expression for $F$: $F(P,Q,R,S) = \sum 0,2,5,7,8,10,13,15$ The minterms $2$, $7$, $8$ and $13$ are 'do not care' terms. The minimal sum-of-products form for $F$ is $Q \bar S+ \bar QS$ $\bar Q \bar S+QS$ $\bar Q \bar R \bar S+ \bar QR \bar S+Q \bar R S+QRS$ $\bar P \bar Q \bar S+ \bar P QS+PQS+P \bar Q \bar S$
Consider the equation: $(7526)_8 − (Y)_8 = (4364)_8$, where $(X)_N$ stands for $X$ to the base $N$. Find $Y$. $1634$ $1737$ $3142$ $3162$
Consider the following combinational function block involving four Boolean variables $x,\:y,\:a,\:b$ where $x,\:a,\:b$ are inputs and $y$ is the output. f(x, a, b, y) { if(x is 1) y = a; else y = b; } Which one of the following digital logic blocks is the most suitable for implementing this function? Full adder Priority encoder Multiplexor Flip-flop