1
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ prove $a$ and the negation of $b$ $\endgroup$ – Mirko May 22 '17 at 20:53
  • $\begingroup$ 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. $\endgroup$ – Annonymous May 22 '17 at 20:55
  • $\begingroup$ 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$ $\endgroup$ – Mirko May 22 '17 at 20:58
  • $\begingroup$ 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) $\endgroup$ – JMoravitz May 22 '17 at 20:58
  • 2
    $\begingroup$ $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. $\endgroup$ – amWhy May 22 '17 at 22:04
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ – amWhy May 22 '17 at 21:59
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Your last suggestion would seem to prove $\neg(a\land \neg b)$, that is, $a\to b$. $\endgroup$ – Mirko May 22 '17 at 21:31
  • $\begingroup$ @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. $\endgroup$ – Atakan Büyükoğlu May 24 '17 at 15:55
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.