GATE CSE 1996 | Question: 2.3

Question

Which of the following is NOT True?

(Read $\wedge$ as AND, $\vee$ as OR, $\neg$ as NOT,  $\rightarrow$ as one way implication and $\leftrightarrow$ as two way implication)

• A. $((x \rightarrow y) \wedge x) \rightarrow y$

• B. $((\neg x \rightarrow y) \wedge (\neg x \rightarrow \neg y)) \rightarrow x$

• C. $(x \rightarrow (x \vee y))$

• D. $((x \vee y) \leftrightarrow (\neg x \rightarrow \neg y))$

Comments

Two ways to solve these kind of problem ....

(1) -> Derivation

(2) -> Digital logic  [Assuming the values to be true or false ]

---

Puja don't you think both methods would be time consuming. Yes! sometime expanding logic formula might be of some help but putting T/F is not supposed to be a good idea , can't it happen that logic formula is tautology for all possibilities except one.Here in tht question , the most easy way to solve it is either converting it to English or otherwise use premise/conclusion method.

---

Depends on Practice ....

Answer 1

$A. \ \ ((x \rightarrow y) \wedge x)\rightarrow y$
$\quad \quad \equiv \ \ \neg ((\neg x \vee y) \wedge x)\vee y$
$\quad \quad \equiv \ \ (( x \wedge \neg y) \vee \neg x)\vee y$
$\quad \quad \equiv \ \ (( x \vee \neg x)\wedge(\neg x\vee \neg y))\vee y$
$\quad \quad \equiv \ \ (T \wedge(\neg x\vee \neg y))\vee y$
$\quad \quad \equiv \ \ (\neg x\vee \neg y)\vee y$
$\quad \quad \equiv \ \ (y\vee \neg y)\vee \neg x$
$\quad \quad \equiv \ \ T\vee \neg x$
$\quad \quad \equiv \ \ T$

$B. \ \ ((\neg x \rightarrow y)\wedge(\neg x \rightarrow\neg y))\rightarrow x$
$\quad \quad \equiv \ \ \neg (( x \vee y)\wedge( x \vee \neg y))\vee x$
$\quad \quad \equiv \ \ ((\neg x \wedge \neg y)\vee( \neg x \wedge y))\vee x$
$\quad \quad \equiv \ \ ((\neg x \wedge (\neg y \vee y))\vee x$
$\quad \quad \equiv \ \ (\neg x \wedge T)\vee x$
$\quad \quad \equiv \ \ (\neg x \vee x)$
$\quad \quad \equiv \ \ T$

$C. \ \ (x \rightarrow(x \vee y))$
$\quad \quad \equiv \ \ (\neg x \vee (x \vee y))$
$\quad \quad \equiv \ \ (\neg x \vee x) \vee y$
$\quad \quad \equiv \ \ T \vee y$
$\quad \quad \equiv \ \ T$

$D.\ \ ((x \vee y)\Leftrightarrow (\neg x \rightarrow \neg y))$
$\quad \quad \equiv \ \ ((x \vee y)\Leftrightarrow ( x \vee \neg y))$
$\quad \quad \equiv \ \ ((x \vee y)\rightarrow ( x \vee \neg y)) \wedge (( x \vee \neg y)\rightarrow (x \vee y))$
$\quad \quad \equiv \ \ (\neg (x \vee y)\vee( x \vee \neg y)) \wedge (\neg ( x \vee \neg y)\vee (x \vee y))$
$\quad \quad \equiv \ \ ((\neg x \wedge \neg y)\vee(x \vee \neg y)) \wedge (\neg x \wedge y) \vee( (x \vee y) )$
$\quad \quad \equiv \ \ (((\neg x \wedge\neg y) \vee x)\neg y) \wedge ((( \neg x \wedge y)\vee x)\vee y)$
$\quad \quad \equiv \ \ (((\neg x \vee x) \wedge(x \vee \neg y)) \vee \neg y) \wedge (((\neg x \vee x)  \wedge(x \vee y)) \vee y) $
$\quad \quad \equiv \ \ ((T \wedge (x \vee \neg y)) \vee \neg y) \wedge((T \wedge (x \vee y)) \vee y)$
$\quad \quad \equiv \ \ ((x \vee \neg y) \wedge (x \vee y) ) $
$\quad \quad \equiv \ \ (x \wedge x) \vee (x \wedge y) \vee (x \wedge \neg y) \vee(\neg y \wedge y) $
$\quad \quad \equiv \ \ x \vee (x \wedge y) \vee (x \wedge \neg y) \vee F$
$\quad \quad \equiv \ \ x \vee (x \wedge y) \vee (x \wedge \neg y)$
$\quad \quad \equiv \ \ x$
 
Hence, Option(D). $((x \vee y)\Leftrightarrow (\neg x \rightarrow \neg y))$.

Comments

Yes, you are right.Updated.Thanks!!

---

That means this questions is wrong. It should be "Which of the following could be False" instead of "Which of the following is False".

---

D.  ((x∨y)⇔(¬x→¬y))
≡  ((x∨y)⇔(x∨¬y))

≡  x∨ (y⇔¬y)

≡  x∨ F

≡  x

 

Easy to use below rule (source : Wikipedia)

Distribution of disjunction over equivalence

Please, correct if anything is wrong.

Answer 2

OPTION D...  when x= F  & y=F

Comments

For  x=False and y=True also option D is invalid.

                 

---

ya right @rajesh

---

((x or y) <-> (x' -> y' ))
=((x+y) <-> (x+y'))
=(x+y)'.(x+y')' + (x+y).(x+y') (as we know <-> evaluated as Xnor gate like A<->B = A'B' +AB)
=x'y'.x'.y + x+yy'
=0+x+0
=x

I'm getting option D as X not 0. Means it can be 0 or 1. Can you please explain?

Answer 3

A. ((x→y)∧x)→y = ((x'+y).x)'+y = (xy)'+y = x'+y'+y = x'+1=1 ( TRUE)

B. ((∼x→y)∧(∼x→∼y))→x = ((x+y).(x+y'))'+x = (x+yy')'+x = x'+x =1 ( TRUE )

C. (x→(x∨y)) = x'+x+y = 1+y =1 ( TRUE )

D. ((x∨y)↔(∼x→∼y)) = (x+y)↔(x+y') =((x+y)'.(x+y')).((x+y')'(x+y)) = (x'y'.(x+y')).((x'y.(x+y)) = x'y'.x'y= 0 ( FALSE)

so ans is D

Answer 4

X->Y will be false when X is true and Y is false.

For option A) if we take y is true then the expression cant be false.

For option B) if we take x as true then the expression cant be false

For option C) expression is false when x is true ans x\/y is false but if x is true the x\/y cant be false.

so option D is false.