3
$\begingroup$

I want to prove that $\neg(A \Rightarrow B) \iff A \land \neg B$ holds without using a truth table.

"$\Leftarrow$": This one is simple: Suppose $A \land \neg B$. We want to show: $(A \Rightarrow B) \Rightarrow \bot$. For that we suppose $A\Rightarrow B$. Now our goal is $\bot$. Since by our assumption $A$ and $A\Rightarrow B$ are true we get $B$ by using Modus ponens. Since $B$ and $\neg B$ holds we get $\bot$ by using Modus ponens again. $\square$

How does "$\Rightarrow$" work?

Thanks in advance!

$\endgroup$
5
  • $\begingroup$ The $\Leftarrow$ direction is valid intuitionistically, which is why you were able to find a direct proof. The $\Rightarrow$ direction is not, so you'll need to use something like the law of excluded middle or double-negation elimination. $\endgroup$
    – Clive Newstead
    Mar 21, 2020 at 12:59
  • 1
    $\begingroup$ Can you use logical equivalencies? E.g., $\lnot(A\to B) \iff \lnot (\lnot A\lor B) \iff (A\land \lnot B)$ $\endgroup$
    – amWhy
    Mar 21, 2020 at 12:59
  • $\begingroup$ When does $A\implies B$ is wrong ? When $A$ is true and $B$ is not true. $\endgroup$
    – Surb
    Mar 21, 2020 at 13:00
  • 1
    $\begingroup$ See also math.stackexchange.com/questions/3406816/…. $\endgroup$
    – Michael Hoppe
    Mar 21, 2020 at 15:15
  • $\begingroup$ Which deductive system are you using? $\endgroup$
    – user170039
    Mar 22, 2020 at 5:43

3 Answers 3

Reset to default
3
$\begingroup$

Following from my comment: the $\Rightarrow$ direction requires that you invoke a non-constructive rule, such as the law of excluded middle or double-negation elimination.

So assume $\neg (A \Rightarrow B)$. Using the law of excluded middle:

  • $A \vee \neg A$ is true. If $\neg A$ is true then $A \Rightarrow B$ is true by ex falso—contradiction! So $\neg A$ is true.
  • $B \vee \neg B$ is true. If $B$ is true then $A \Rightarrow B$ is true—contradiction! So $\neg B$ is true. [Edit: LEM is not actually required in this step.]

So $A \wedge \neg B$ is true.

$\endgroup$
2
  • 1
    $\begingroup$ The proof from $\neg(A \to B)$ to $\neg B$ is intuitionistically OK, no? Intuitionists allow vacuous conditional proof, so the supposition $B$ leads via $(A \to B)$ to contradiction, so $B$ is refuted (intuitionistically). $\endgroup$
    – Peter Smith
    Mar 21, 2020 at 13:23
  • 1
    $\begingroup$ Thank you! I think your conclusion from the first dot must be $A$ and from the second $\neg B$. $\endgroup$
    – Simon Hawk
    Mar 21, 2020 at 13:33
2
$\begingroup$

You are given $\neg(A \to B)$ [the use of the double arrow for the object-language conditional is to be strongly deprecated, by the way!] You need separate proofs for the two conjuncts.

Suppose $\neg A$. Suppose too $A$, then $\bot$ then $B$. So drop the second supposition and conclude $A \to B$. Contradiction. Hence $\neg\neg A$ and so $A$.

Suppose $B$. Then $A \to B$ (by vacuous conditional proof) so contradiction again. So conclude $\neg B$.

$\endgroup$
2
  • $\begingroup$ What's wrong with "$\Rightarrow$"? $\endgroup$
    – Zacky
    Mar 21, 2020 at 13:06
  • 1
    $\begingroup$ Some use it to mean $\to$, some $\vdash$, some $\vDash$, some as a sequent-former. Not at all a good idea to use something that can engender confusion. math.stackexchange.com/questions/286077/… $\endgroup$
    – Peter Smith
    Mar 21, 2020 at 13:16
1
$\begingroup$

Equivalently, you can prove $[A \implies B] \iff \neg [A \land \neg B]$, which is often given as The Definition in introductory courses, usually with $\equiv$ instead of $\iff$.

See my formal proof of this alternative (only 19 lines) using a form of natural deduction here. It makes use of direct proof, proof by contradiction, and elimination of double negations.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .