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

option D.
((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
value of x may be 0 or 1 so it need not be false always
but all other option are true ( getting 1 after evaluating ) so closest possible ans is D

Answer 2

The question is saying which of the following is false not contradiction ..so by making the truth values u will see that options A,B and C are tutology . Here I'll prove C  (make truth table or follow the properties)  :

X->(XvY)=> ~XvXvY  => ~XvX is T and TvY=>T so option C is  a tutology

now coming to D make truth table(here only 2 variables so it's not that difficult)  n you will see that when x=F and y=F .It is False .

NOTE: option D is not a contradiction but it is a contigency 

Answer 3

option (d) because bi-implies means LHS should be equivalent to RHS, but here : L.H.S = (X V Y)

 

R.H.S = (~X ---> ~Y) = (~ ~X V ~Y) = (X V ~Y).

Comments

no if bi-impies is a tutology then only the L.H.S is equivlent to R.H.S

---

YES, we read P <=> Q as P is equivalent to Q, BUT in option (d) L.H.S is not equivalent to R.H.S, SO IT IS FALSE.

---

NO we read p<=>q  as p if and only if q or if p then q ^ if q then p.  if p<=>q is a tautology then only we say that p is equivalent to q.

Answer 4

Let us assume the given proposition is false first then if we get any contradiction, our assumption is wrong i.e., the given proposition is not false