# How can I prove that $\neg (A \Rightarrow B) \iff A \land \neg B$ on a more formal level?

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!

• 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. Mar 21, 2020 at 12:59
• Can you use logical equivalencies? E.g., $\lnot(A\to B) \iff \lnot (\lnot A\lor B) \iff (A\land \lnot B)$ Mar 21, 2020 at 12:59
• When does $A\implies B$ is wrong ? When $A$ is true and $B$ is not true.
– Surb
Mar 21, 2020 at 13:00
• Mar 21, 2020 at 15:15
• Which deductive system are you using?
– user170039
Mar 22, 2020 at 5:43

## 3 Answers

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.

• 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). Mar 21, 2020 at 13:23
• Thank you! I think your conclusion from the first dot must be $A$ and from the second $\neg B$. Mar 21, 2020 at 13:33

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$$.

• What's wrong with "$\Rightarrow$"? Mar 21, 2020 at 13:06
• 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/… Mar 21, 2020 at 13:16

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.