Why is the negation of $A \Rightarrow B$ not $A \Rightarrow \lnot B$?

Question

The book I am reading says that the negation of "$A$ implies $B$" is "$A$ does not necessarily imply $B$" and not "$A$ implies not $B$". I understand the distinction between the two cases but why is the first one considered true?

Answer 1

A implies B is logically equivalent to (not A or B ). And its negation by De Morgan's law is simply (A and not B). You may write it's truth table to see it.

The only way an implication will fail to hold is if it's hypothesis is true but conclusion is false. This is simply (A and not B). If you negate it you will get (not A or B) which is then logically equivalent to A implies B.

Answer 2

For a sentence $\phi$, its negation $\neg\phi$ is the sentence that is true exactly when $\phi$ is false. If $A$ is false, then both $A\Rightarrow B$ and $A\Rightarrow\neg B$ are true, so they aren't negations. But on the other hand, $A\Rightarrow B$ is equivalent to "$\neg A$ or $B$". The negation of this is "$A$ and $\neg B$", which means that $A$ can be true and $B$ can be false. So $A$ doesn't necessarily imply $B$.

Answer 3

I am going to assume you are familiar with two equivalences (if not, then simply write up truth tables to verify them): $$ A\to B\equiv\neg A\lor B\quad(1)\qquad\text{and}\qquad\neg(A\lor B)\equiv\neg A\land\neg B\quad(2). $$

---

Why your book is right: We can negate anything by simply tacking on "it is not the case that...," and this is basically what your authors have done. More specifically: "The negation of '$A$ implies $B$' is 'It is not the case that $A$ implies $B$'." Of course, simply saying "it is not the case" is hardly useful. That is why what your textbook authors are saying is correct, but what they are saying is not very meaningful (i.e., they don't give you any sense of what the negation of "$A$ implies $B$" actually means in any useful way).

---

Why you are wrong: Let's consider what the negation of $A\to B$ and $A\to\neg B$ are equivalent to by reducing them to easily understandable statements using $(1)$ and $(2)$. Doing this will show why your intuition is off-base.

For the negation of $A\to B$, we have the following: $$ \neg(A\to B)\equiv\underbrace{\neg(\neg A\lor B)}_{\text{used $(1)$}}\equiv \underbrace{A\land\neg B}_{\text{used $(2)$}}. $$ For $A\to\neg B$, we have the following: $$ A\to\neg B\equiv\underbrace{\neg A\lor\neg B)}_{\text{used $(1)$}}. $$ It should be fairly clear now that $$ \neg(A\to B)\equiv A\land\neg B\not\equiv\neg A\lor\neg B\equiv A\to\neg B, $$ but to further clarify, consider what happens when $A$ is false and $B$ is true. We would have that $A\land\neg B$ is false while $\neg A\lor\neg B$ is true, contradicting the thought that they are equivalent.

Does that clear things up?

Answer 4

Consider this simple example: $$x>0\Rightarrow x>1.$$ This is clearly a false statement.

Among the next two ones, which is true ? $$x>0\nRightarrow x>1$$ $$x>0\Rightarrow x\le1?$$

Answer 5

Definition: $A\implies B \equiv \neg[A \land \neg B]$.

Taking the negation, $\neg[A\implies B] \equiv A \land \neg B$.

By definition, we also have $A\implies \neg B \equiv \neg[A \land B]$.

Now, $A\land \neg B \not\equiv \neg [A \land B]$

Therefore, $\neg[A\implies B]\not\equiv A\implies \neg B$.

Answer 6

Here is a more intuitive explanation. Suppose that $A$ and $B$ are unrelated. For example, $A$ could be "France is a country in Europe" and $B$ could be "I will win the lottery". It is certainly the case that we know $A$ does not imply $B$ for these sentences: knowing that France is in Europe tells me nothing about the future! But we also do not know that $A \Rightarrow \lnot B$, for the same reason.

So in this case, we only know that $A \not \Rightarrow B$. This shows there is a difference between $A \not \Rightarrow B$ (which just says that $A$ does not imply $B$) and $A \Rightarrow \lnot B$ (which says $A$ does imply the negation of $B$).

This kind of intuition is important when you move from propositional logic to more general mathematics. For example, suppose we are looking at natural numbers. Let $A$ say "$x$ is an even natural number" and let $B$ say "$x$ is a natural number that is a multiple of $6$". Neither $A$ nor $B$ is true or false on its own, because the $x$ has no fixed value. Sometimes $A$ is true and sometimes it is false. But we still have that $A \not \Rightarrow B$ (e.g., $2$ is even but not a multiple of 6) and $B \Rightarrow A$ (because every multiple of 6 is even). We also do not have $A \Rightarrow \lnot B$ (because some even numbers are multiples of 6).

Rather than trying to analyze this more complicated kind of implication in terms of truth values, it is helpful to develop the right intuition: $A \Rightarrow B$ says that knowing $A$ alone is enough to know $B$. From that intuition, you can work out the formalities involving truth values, but more importantly you can do mathematics from that intuition.

Answer 7

$ \newcommand{\T} {\text{True}} \newcommand{\F} {\text{False}}$

$$\begin{array} {cc|cc} A & B & A \implies \lnot B & A \not \implies B \\ \hline \T & \T & \F & \F \\ \T & \F & \T & \T \\ \F & \T & \T & \F \\ \F & \F & \T & \F \\ \end{array}$$

So in fact for material implication, $A \implies \lnot B$ and $A \not \implies B$ are the same except for when $A$ is false. This makes it possible to construct a counter example:

True statement $A \implies B$:

If you are an alien, then you have not posted on math.se.

That is a true statement, because the qualifying phrase is false.

Incorrect negation: $A \implies \lnot B$

If you are an alien, then you have posted on math.se.

The qualifying phrase is still unchanged and so false, so the statement is true, so it is not a negation of the original statement.

Correct negation $A \not \implies B$:

You are an alien and you have posted on math.se.

That statement is (regrettably) false. That is because it is the negation of the original statement.

Answer 8

Try building both $\lnot$(A$\rightarrow$B) and (A$\rightarrow$$\lnot$B) up from their component well-formed formulas. Or write them in a prefix notation like the following:

$\lnot$($\rightarrow$(A, B)) and

$\rightarrow$(A, $\lnot$(B))

In the former we have "A" and "B" and then a conditional. Then we negate the conditional.

In the latter we have "A" and "B", then B gets negated, and finally we have a conditional.

This sentence " the negation of "A implies B" is "A does not necessarily imply B"" gets considered true, because "not necessarily" applies to "imply", it does NOT apply to B.

Answer 9

If the negation of $A\implies B$ were $A \implies \lnot B$, then they would have to have the opposite truth values for all valuations of $A$ and $B$. So let's just check that: $$\begin{array}{cc|cc} A & B & A\implies B & A\implies\lnot B \\\hline \text{False} & \text{False} & \text{True} & \color{red}{\text{True}} \\ \text{False} & \text{True} & \text{True} & \color{red}{\text{True}} \\ \text{True} & \text{False} & \text{False} & \text{True} \\ \text{True} & \text{True} & \text{True} & \text{False} \end{array}$$ As you see, whenever $A$ is false, $A\implies\lnot B$ has not the opposite truth value of $A\implies B$, therefore it cannot be its negation.