# logical negation of (a implies b)

I know that the logical negation of $$\neg(a \rightarrow b)= a \wedge \neg b$$ I am not clear what that means in the following simple setting:

So its clear that $$x\geq 2 \to x^2\geq 4.$$ Now I can write the logical negation of $a\to b$ as $a \wedge \neg b$, but what does that intuitively mean?

Suppose I want to prove "$a \wedge \neg b$", what do i need to prove mathematically?

thnks

• prove $a$ and the negation of $b$ – Mirko May 22 '17 at 20:53
• what does it mean to prove a? For my example, "$a$" is just truth statement $[x\geq 2]$. Similarly for b, its just an indicator of $x^2\geq 4$ Its not clear what i need to prove here. – Annonymous May 22 '17 at 20:55
• if $a$ is $x\ge 2$ and $b$ is $x^2\ge4$ then $a$ does imply $b$, and you can't prove its negation. Pick different $a$ and $b$ if you wish to find an example when $a\not\to b$ – Mirko May 22 '17 at 20:58
• As it so happens, the implication "$\forall x\in \Bbb R~~x\geq 2 \implies x^2\geq 4$" is in fact true. The negation of this statement would have been "There exists an $x$ such that $x\geq 2$ despite $x^2<4$". Had there been an example of such an $x$ then your original statement would have been proven false. (as mentioned the statement was actually true, so no such example exists and your negation is therefore false) – JMoravitz May 22 '17 at 20:58
• $a\to b\equiv \lnot a\lor b$ happens to be true, given your example. So you cannot prove it's negation, because it's negation ($x\geq 2$ and $x^2\lt 4$) is false. If you have some implication, say, $p \to q$, when it is false, you can show this by proving that $p \land \lnot q$ is true. – amWhy May 22 '17 at 22:04

Say $a$ is $x\ge2$ and $b$ is $x^2\ge14$ (and formally an universal quantifier should be involved as in @JMoravitz comment, i.e. $\forall x, x\ge2\to x^2\ge14$ ). Pick $x=3$, then $a$ is true, but $b$ is false. In other words, $x\ge2$ does not imply that $x^2\ge14$. Formally, the negation here is $\exists x, (x\ge2 \land\neg x^2\ge14)$.

Formally, one may separate syntax from sematic (or form from meaning). Given any statements $a$ and $b$, the negation of the formula $a\to b$ is the formula $a\land\neg b$. If you want to prove that $a\land\neg b$ then you need to either use some previously proven formulas, or axioms (accepted without proof), or to interpret $a$ and $b$ in some known model (as for the reals above), giving each of $a$ and $b$ meaning and truth values.

• In the OPs case $a\rightarrow b$ is true. In your case, $a\to b$ is false, for the very reason you give. JMoriavitz correctly used $a$ to mean $x\geq 2$, $b$ to mean $x^2\geq 4$, so that indeed, $a\to b$ is true, or, more specifically, $\forall x (x\geq 2\to x^2\geq 4)$. The negation of this is $\exists x( x\geq 2 \land x^2 \lt 4)$ or more simply $a\land \lnot b$. – amWhy May 22 '17 at 21:59

a is $x\geq 2$ and $\neg b$ is $x^2\lt 4$.

So, the intuitive meaning of $a \wedge \neg b$ is that both of these cannot happen at the same time, $x\geq 2$ with $x^2\lt 4$ have no common elements in their solution sets.

To prove $a \wedge \neg b$, you should show that all elements in the domain of x satisfy both $x\geq 2$ and $x^2\lt 4$. However, this is impossible and that is why the negation of a true logical statement is false.

• Your last suggestion would seem to prove $\neg(a\land \neg b)$, that is, $a\to b$. – Mirko May 22 '17 at 21:31
• @Mirko , you are right. So the meaning should be the other way around, showing that this is true for the whole domain. I'm editing now. – Atakan Büyükoğlu May 24 '17 at 15:55

Our statement is $\neg (a\to b)$

This reads: "It is false that $a$ (materially)implies $b$".

Recall that a material implication is falsified only when the antecedant is false and the consequent is true.

So our statement must be infering that "$a$ is true and $b$ is false."

Which is written $a\wedge\neg b$.

And we can argue vice versa, so the statements are equivalent.

That is all.

Now the negation of $\bbox[lemonchiffon]{x\geq 2\to x^2\geq 4}$ is $\bbox[lemonchiffon]{x\geq 2\wedge x^2< 4}$.   If the latter is false the former will be true (and vice versa).

For example, when $x=3$ then $\bbox[lemonchiffon]{3\geq 2\to 3^2\geq 4}$ is true because $\bbox[lemonchiffon]{3\geq 2\wedge 3^2< 4}$ is false.

Another example, when $x=1$ then $\bbox[lemonchiffon]{1\geq 2\to 1^2\geq 4}$ is true (despite seeming absurd) because $\bbox[lemonchiffon]{1\geq 2\wedge 1^2< 4}$ is false.

Often when we write something like $x\geq 2\to x^2\geq 4$ we implicitly mean that the statement holds universally (for all $x$).   That is $\forall x~(x\geq 2\to x^2\geq 4)$.

The negation of this quantified statement is $\exists x~(x\geq 2\wedge x^2<4)$.   Since there is no real witness to this exitential, then the universal is infered to be true.