How is this proposition false?

Question

I have a proposition:

((x v y) <=> (~x => ~y))

When I solve this, I end up getting True but the answer is False. Here's how I solved it:

when we have a <=> b, we can write it as ~a.~b + a.b and a => b becomes ~a+b So the above equation becomes:

=> ~(x + y).~(~x => ~y) + (x + y).(~x => ~y)

=> ~(x+y).~(x+~y) + (x+y).(x+~y)

Using De Morgan's law (~(a+b) = ~a.~b and ~(a.b) = ~a+~b)

=> (~x.~y).(~x.y) + (x+y).(x+~y)

=> (~x.~x + ~x.y + ~y.~x + ~y.y) + (x.x + x.~y + y.x + y.~y)

=> (~x + ~x(y+~y) + 0) + (x + x(~y + y) + 0)

=> (~x + ~x) + (x + x)

=> ~x + x which is always True

But, according to another solution, <=> is only True when both sides result in the same solution, So, if we go by this:

=> LHS = x+y and RHS is (x + ~y), which can never be equal and hence, False.

So what am I doing wrong?

EDIT:

PS: This is where I got the question from.

mathcounterexamples.net · Answer 1 · 2020-06-30T08:25:59.303

2

There is at least one mistake when you go from:

$$\neg (x+y).\neg (x+ \neg y) + (x+y).(x+ \neg y)$$ to

$$(\neg x. \neg y).(\neg x.y) + (x.y).(x+ \neg y)$$ using De Morgan laws. You switched $x+y$ into $x . y$.

Also I don't understand how you go from this line to the next one:

$$(\neg x.\neg x + \neg x.y + \neg y.\neg x + \neg y.y) + (x.x + x.\neg y + y.x + y.\neg y).$$

It seems that you apply a kind of distributivity of $.$ over itself???

edited Jun 30 '20 at 08:25

answered Jun 30 '20 at 08:07

mathcounterexamples.net

70,018

Hi. Thanks for the answer. The first one was a mistake, which I have edited. Sorry about that.
I did apply the distributive property. But that's valid, right?
– Sarvagya Gupta Jun 30 '20 at 16:15
No, you don't have such a distributivity law of $\cdot$ vs. $\cdot$. One exists for $\cdot$ vs. $+$. – mathcounterexamples.net Jun 30 '20 at 16:34

zkutch · Accepted Answer · 2020-06-30T08:25:28.537

1

After line "Using De Morgan's law" You should have $$(\neg x.\neg y).(\neg x.y) + (x+y).(x+\neg y)$$ $$0+x+x .\neg y+y.x +y.\neg y$$ $$x+x.(y+\neg y) = x$$ So you end up with $x$: initial equivalence is True together with $x$

edited Jun 30 '20 at 08:25

answered Jun 30 '20 at 07:53

zkutch

13,410

How did you go from the first line to the next? – Sarvagya Gupta Jun 30 '20 at 16:18
In first member you have $\neg y.y=0$, in second member open brackets. – zkutch Jun 30 '20 at 16:24
So something like what @mathcounterexamples.net is trying to say? There's no distributive law between • and •. Only between • and + – Sarvagya Gupta Jul 01 '20 at 07:22
1

Yes. Distributive property we have between "$\cdot$" and "$+$" and reverse - also between "$+$" and "$\cdot$". – zkutch Jul 01 '20 at 07:25

5xum · Answer 3 · 2020-06-30T08:02:34.863

1

When I solve this, I end up getting True but the answer is False

The answer is not False. You can check it yourself by setting x=True, y=True, in which case you get

(T+T)<=>(F=>F)

which simplifies to

T <=> T

and further to just T.

The answer is also not True, and you can check this by setting x=False, y=True and you get

(T+T)<=>(T=>F)

which simplifies to

T <=> F

and further to just F.

=> LHS = x+y and RHS is (x + ~y), which can never be equal and hence, False.

This is incorrect. So long as x is true, x+y and x+~y can be equal (i.e., both true.

edited Jun 30 '20 at 08:02

answered Jun 30 '20 at 07:57

5xum

123,496
6
128
204

So if I get this option to a question like "which one is False?", should I tick this option? – Sarvagya Gupta Jun 30 '20 at 16:07
@SarvagyaGupta No. The statement is not False. The statement depends on the truth value of the input $x$. – 5xum Jul 01 '20 at 06:48

How is this proposition false?

3 Answers3