GATE CSE 2007 | Question: 33

Question

Define the connective $*$ for the Boolean variables $X$ and $Y$ as: $$X * Y = XY + X'Y'.$$ Let $Z = X * Y$. Consider the following expressions $P$, $Q$ and $R$.
$$P : X = Y * Z, \\ Q :Y = X * Z, \\ R : X *Y * Z = 1$$
Which of the following is TRUE?

• A. Only $P$ and $Q$ are valid.
• B. Only $Q$ and $R$ are valid.
• C. Only $P$ and $R$ are valid.
• D. All $P$, $Q$, $R$ are valid.

Comments

Here, XNOR gate is given and XNOR gate does not obey associative law than how can someone put  X*Y instead of Z in 'R' ?

X*Y*Z = 0 always (because X*Y=Z means sum of 1's in X and Y is even and if I add Z in it than that will be even no. of 1's and that will make it odd term and is 0 always.)

If it is X*(Y*Z) than it is =1

otherwise for XNOR: x*Y*Z = 0

 

So only P & Q are valid.

---

Remarks : XNOR gate is commutative and associative.

---

Why can't we simply use the XNOR's property of associativity and commutativity while answering such question?

 

P:Y * Z

= Y * (X*Y)

= Y *(Y*X)       (commutative)

= (Y * Y) * X      (associative)

= 1 * X

= X = LHS

So, P is valid and so on.

---

for which input of x , y ,z these conditions in truth table is valid ? 

Z=X∗Y

 

R:X∗Y∗Z=1

for any 1 and 0 that is satisfying  ?

x	y	z	Q
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

Answer 1

P:

$Y * Z = Y * (X*Y)$
$= Y * (XY + X'Y')$
$= Y (XY + X'Y') + Y' (XY + X'Y')'$
$= XY + Y' ((X' + Y') (X+ Y))$
$= XY + Y' (X'Y + XY')$
$= XY + XY'$
$= X(Y + Y')$
$= X$

So, P is valid.

Q:

$X * Z = X * (X*Y)$
$= X * (XY + X'Y')$
$= X (XY + X'Y') + X' (XY + X'Y')'$
$= XY + X' ((X' + Y') (X+ Y))$
$= XY + X' (X'Y + XY')$
$= XY + X'Y$
$= Y(X + X')$
$= Y$

So, Q is also valid.

R:

$X * Y * Z = (X * Y) * (X * Y)$
$= (XY + X'Y') * (XY + X'Y')$
$= (XY + X'Y') (XY + X'Y') + (XY + X'Y')' (XY + X'Y')'$
$= (XY + X'Y') + (XY + X'Y')' (\because AA = A)$
$= 1 (\because A + A' = 1)$

So, R is also valid.

Hence, D choice.

Comments

How x*y*z = (x*y)*(x*y) ?

Please explain

---

Let Z = X * Y. It is given in the question.

Now, X * Y * Z = X * Y * X * Y.

Moreover, X * Y = XY + X'Y' = X $\odot$ Y.

* is XNOR.

X*Y*Z = X $\odot$ Y $\odot$ X $\odot$ Y = (X $\odot$ X) $\odot$ (Y $\odot$ Y) = 1 $\odot$ 1 = 1

---

Expression R can be done directly...

X*Y*Z=1

L.H.S = X*Y*Z

          = (X*Y)*Z

          = Z*Z

          = ZZ + Z'Z'

          = Z + Z'

          =1 R.H.S

So expression R is valid.....

Answer 2

P: rhs=Y*Z =Y*(X*Y)=(Y*Y)*X=1*X=X=lhs  so valid

(we can use the fact that X*Y IS EQUIV TO X XNOR Y which is associative AND commutative)

Q:rhs=X*Z =X*(X*Y)=(X*X)*Y=1*Y=Y=lhs  so valid

R:X*Y*Z=X*Y*(X*Y) =(X*X)*(Y*Y)=1 so valid

Comments

Y*Z =Y*(X*Y)=(Y*Y)*X=1*X=X 

for this case if Y*Y is 0*0 then it is equal to 0 . So, 0*X =0. so, the value of Y is require and it would be Y*X.

Then why it is only associating with value of 'x' ?

Answer 3

 

First of all here * operation represents XNOR.

P: X=Y∗Z = Y XNOR Z = Y xnor X xnor Y = Y xnor Y xnor X = 1 xnor X = X

Q:Y=X∗Z = X xnor X xnor Y = Y

R:X∗Y∗Z=1 

   LHS = X xnor Y xnor X xnor Y = 1 xnor 1 = 1

All are valid.

Comments

Simplest explanation that uses the  commutative property

Answer 4

The given operation * is XNOR. The law of XNOR : If A XNOR B = C then A XNOR C = B. This can also be verified by solving the equation. Just solve P and that will lead to X=X. So if P holds True, using the law Q also holds True(swap(Y,X)) gives the same output. Therefore P and Q holds.

Now coming to R:. XNOR has the property of odd number of 1’s detector(if inputs are odd) and even number of 1’s detector(if input is even). R: X(exnor)Y(exnor)Z = 1 it holds True, since the number of inputs are 3. 

Therefore D is the answer