3
$\begingroup$

I am just being introduced to how logic is used in mathematics and my lecturer mentioned that $\sim(P\rightarrow Q) \equiv p\wedge\sim q$. This is quite hard to grasp at first glance, so he gave an example: The negation of "if $x\neq 0$ then $y=0$" is "$x\neq 0 \wedge y\neq 0$".

Well, my question is, why should that be the case? Why is the negation of "if $x\neq 0$ then $y=0$" not "$x\neq 0 \wedge y=0$"?

Any explanations will be greatly appreciated :)

EDIT: Thank you all for your comments! I think I understand the logic better now!

$\endgroup$
2
$\begingroup$

Let me try once more:

Let's say I tell you "If you stop studying, you will get through college."

And you tell me "That is not true Grigori, I negate that".

Think for a second what would you mean by that negation, and how would the sentence sound..

You would tell me "If I stop studying, I will NOT get through college." (you negated the Q-consequence)

That means that in your head those two things I said can't exist together. The fact that you stop studying AND the fact that you finish college.

But statements of your answer align perfectly in your head. The fact that you stop studying AND the fact that you will NOT finish college can co-exist.

For the sake of the argument let's pretend we know for a fact that I'm lying and you are telling the truth. And so you, by negating the lie, get to the truth by $p\wedge\sim q$. If I was telling the truth, by the same process you would be saying something that is false. Hope this clarifies.

$\endgroup$
  • $\begingroup$ Thank you! Out of all of the other very insightful answers, I think this was the most intuitive. $\endgroup$ – Ethan Mark Jan 25 at 14:08
  • $\begingroup$ Thanks man, glad you like it $\endgroup$ – Grigori Perelman Jan 25 at 16:27
5
$\begingroup$

One can show $A\Rightarrow B \equiv \neg A\lor B$ using truth tables. By De Morgan's laws one concludes $$\neg (A\Rightarrow B) \equiv \neg (\neg A\lor B) \equiv A\land \neg B. $$


$x\neq 0\ \land\ y=0$ does not negate the initial statement, but implies it, in fact. For if "$x\neq 0\ \land\ y=0$", then certainly "if $x\neq 0$, then $y=0$".

$\endgroup$
3
$\begingroup$

If a implies b, that means every time a occurs, b must also occur. So if a occurs and not b, we now the implication ist false.

$\endgroup$
3
$\begingroup$

"If I come from Paris then I am French".

The negation is certainly not "I come from Paris and I am French" - because what if I really do come from Paris and am French? In that case, both the statement and its "negation" are true!


"If a person is French then they come from Paris". This is false, of course, but why?

To falsify "If a person is French then they come from Paris", I need to demonstrate an example of someone who is French but who does not come from Paris.

$\endgroup$
2
$\begingroup$

Important thing: When you negate the implication, you are negating the consequence.

$\underbrace {If\space one\space has\space the\space darkest\space hair,}_P$ $\underbrace{then}_{\implies}$ $\underbrace{one\space has\space dark \space hair.}_Q$

The proposed negation would be:

$\underbrace {One\space has\space the\space darkest\space hair}_P$ $\underbrace{and}_{\wedge}$ $\underbrace{one\space has\space not \space dark \space hair.}_{\sim Q}$

The statement is actually saying that there exists a man with the darkest hair and that there exists no man that has dark hair at all. Which is obviously contradiction, and leads to the fact that there can't be a man with the darkest hair because no one has dark hair at all.

Let me give you a better example with more obvious dependence:

$x-y=0 \implies x=y$ (an implication you know for a fact that is true)

Proposed negation:

$x-y=0 \wedge x \ne y$ which leads to the fact that $x-y\ne0$, what has to be true since we know it can't be $x-y=0$, because $x \ne y$.

$\endgroup$
2
$\begingroup$

I've heard that the drinking age example is often easier to understand than other examples.

Imagine a restaurant that serves both adults and children, and which has both soft drinks and whiskey. Of course, only the adults may drink whiskey; children may only drink soft drinks.

Suppose you come across a person who is drinking some beverage. Under what circumstances is this permitted? It's permitted when and only when the following statement is true:

If the person is a child, then the person is not drinking whiskey.

(There are lots of alternative, equivalent statements we could have picked instead; I picked this one.)

Suppose again that you come across a person who is drinking some beverage. Under what circumstances is this not permitted? It's prohibited when and only when the following statement is true:

The person is a child and the person is drinking whiskey.

Notice that the second statement describes exactly the opposite situation to the first statement. In other words, the second statement is true when and only when the first statement is false.

So, this means that the second statement is the negation of the first statement.

$\endgroup$
2
$\begingroup$

I think the problem is that the meaning of $P \Rightarrow Q$ in logic doesn't correspond precisely with the meaning of "if ... then ..." in natural language.

Natural language sentences of the form "if ... then ..." are usually understood to be general statements. For example, "if it's raining then I take an umbrella" would be understood as a statement about my behaviour in general, not my behaviour on one particular day. So if we were to translate it into formal logic, it should be something like:

$$\forall d : R(d) \Rightarrow U(d)$$

where $R(d)$ means it's raining on day $d$, and $U(d)$ means I take an umbrella on day $d$. Note that it's the universal quantifier $\forall$, not the use of $\Rightarrow$, that makes this a general statement.

Now suppose my statement that "if it's raining, then I take an umbrella" is negated. This would mean that sometimes, it's raining but I don't take an umbrella. That would be written in formal logic as follows:

$$\exists d : R(d) \land \neg U(d)$$

In formal logic, $\neg \forall x : \phi$ is equivalent to $\exists x : \neg \phi$. Our intuition is that the second quantified expression above should be the negation of the first; so for that intuition to hold formally, it must be the case that $R(d) \land \neg U(d)$ is equivalent to $\neg\big(R(d) \Rightarrow U(d)\big)$.


If you read $P \Rightarrow Q$ as meaning "if P then Q" then your intuition can easily lead you astray. For example, the formula $(P \Rightarrow Q) \lor (Q \Rightarrow R)$ is a tautology. But if we apply our intuition, then a sentence like "either (if you play golf then you're the king) or (if you're the king then you live in space)" is clearly not a tautology, because not every golfer is the king, and the king doesn't live in space.

On the other hand, if you translate "if P then Q" as $\forall x : P(x) \Rightarrow Q(x)$ then the above statement would be more like:

$$\big( \forall x : P(x) \Rightarrow Q(x) \big) \lor \big( \forall x : Q(x) \Rightarrow R(x) \big)$$

which is indeed not a tautology in formal logic. So the conclusion is, it's often untenable to interpret $\Rightarrow$ as a general statement of the form "if ... then ...", because $\Rightarrow$ alone doesn't make it a general statement.

$\endgroup$
  • $\begingroup$ Wow, being so new to this field of mathematics, this is really deep, but I will take my time to digest this! Thank you! $\endgroup$ – Ethan Mark Jan 27 at 5:31
2
$\begingroup$

Maybe it is better to think of $A\to B$ as of $B$ is not less true than $A$. Indeed, we are only interested in the relation of the truth-values. We don't need to know if $B$ somehow actually follows from $A$. Then the negation of $A\to B$ would be the formula suggesting that $B$ is less true than $A$, i.e $A$ is true and $B$ is false a.k.a. $A\wedge\neg B$.

$\endgroup$
0
$\begingroup$

In classical logic, the form of logic that is used almost universally in mathematics, $P$ implies $Q$ means only that it is false that both $P$ is true and $Q$ is false.

$P\implies Q \space \space \equiv \space \space \neg(P \land \neg Q) \space \space$ (a far more intuitive definition of '$\implies$' in my opinion)

(The right-hand expression is equivalent to $\neg P \lor Q$ by De Morgan's Law.)

The negation of $P$ implies $Q$ is that $P$ is true and $Q$ is false by the above definition.

$\neg (P\implies Q) \space \space \equiv \space \space \neg\neg(P \land \neg Q) \space \space \equiv \space \space P \land \neg Q$

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