2

This feels like a dumb question but I just want to make sure I'm correct. I'm reading over some homework where we need to prove some statements are equivalent and one person tried to show $a \implies b$ by assuming $a \implies \neg b$ and coming to a contradiction. This isn't actually valid, correct?

Hosein Rahnama
  • 14,882
Bryyo
  • 369
  • 1
    If you assume $a$ is true, and then suppose that $\neg b$ is true and that leads to a contradiction, then in fact $a$ implies $b$. If you just assume $a$ implies $\neg b$ and find a contradiction, then that tells you that $a$ does not imply $\neg b$, but it doesn't necessarily tell you that $a$ implies $b$, I think. – Ashwin Iyengar Nov 11 '15 at 22:26
  • 1
    Nope. -(a => -b) => a & b – fleablood Nov 11 '15 at 22:28

4 Answers4

4

If $\lnot$(a $\rightarrow$ $\lnot$b), then a is true and $\lnot$b is false. Thus, a is true and b is true. So, (a $\rightarrow$ b).

However, if (a $\rightarrow$ b), it does NOT follow that $\lnot$(a $\rightarrow$ $\lnot$b), since a could be false, which renders both (a $\rightarrow$ b) and (a $\rightarrow$ $\lnot$b) true, making $\lnot$(a $\rightarrow$ $\lnot$b) false.

Doug Spoonwood
  • 11,211
2

No indeed. $A \Rightarrow \neg B$ is equivalent to $\neg(A \wedge \neg\neg B) = \neg(A \wedge B)$. Hence $\neg(A \Rightarrow \neg B)$ is $A \wedge B$.

For instance: if $A$ is $x = 0$ and $B$ is $x^2 = 0$ then $A \Rightarrow \neg B$ is false and $A\wedge B$ is true.

Simon S
  • 26,524
1

Everyone's right.

But my way of thinking:

a => b is only false when a is true and b is false. In other words it's only false 1 in 4 times. So the negation will only be true 1 in 4 times; when a is true and b is false. So the negation is a AND -b.

a => -b will only be false when a is true and b is true. In other word it's only false 1 in 4 times. So it can't be the negation of above because the negation of above can only be true 1 in 4 times.

(a => -b will only be false when a is true and b is true so a=> -b is the same as -(a AND b). Different thing altogether.)

fleablood
  • 124,253
0

Simple short answers. The following two are logically equivalent

$$(a \implies b) \iff (\neg b \implies \neg a)$$

and also the negation of an implication is not an implication

$$\neg (a \implies b) \iff (a \wedge \neg b)$$

If you want to prove $(a \implies b)$ is true by contradiction then you should prove that it's negation is false. Hence, you should prove that $(a \wedge \neg b)$ is false. :)

Hosein Rahnama
  • 14,882