1
$\begingroup$

In a course on logic and proofs the professor presented on the following lines to show an example of negation: $$ \neg (P \Rightarrow Q) \ \ \ \ \Longleftrightarrow \ \ \ \ P \wedge \neg Q $$ I can't wrap my head around why $\neg (P \Rightarrow Q)$ would be equivalent to the RHS of the above statement. Somehow, we are going from the fact the $P$ does not imply $Q$ to a statement that says that $P$ is true and $Q$ is not, while the LHS statement doesn't say anything about $P$ being true. Is it this line or I that am missing something?

The only logical implication that I can make out of this is that: $ \exists x. P(x) \Rightarrow \neg Q(x)$

$\endgroup$
  • 2
    $\begingroup$ Have you compared truth tables of LHS and RHS? $\endgroup$ – Error 404 Sep 5 '17 at 14:32
  • 1
    $\begingroup$ Very strongly related: math.stackexchange.com/questions/70736/… $\endgroup$ – Mees de Vries Sep 5 '17 at 14:35
  • $\begingroup$ Use truth tables... $P \to Q$ is FALSE only in case $P$ TRUE and $Q$ FALSE. Thus $\lnot (P \to Q)$ is TRUE only in case $P$ TRUE and $Q$ FALSE. $\endgroup$ – Mauro ALLEGRANZA Sep 5 '17 at 14:35
  • $\begingroup$ I think the fault of my logic was that I thought the negation of imply would be does not necessarily imply, while for a single statement $P$ (not $P(x)$ being considered for multiple $x$), the negation implies that if P is true Q cannot be true. $\endgroup$ – Bruno KM Sep 5 '17 at 14:53
  • 1
    $\begingroup$ A possible reading of $P \to Q$ is: "it is not the case that P is TRUE and Q is FALSE". Thus, its negation will be: "P is TRUE and Q is FALSE". $\endgroup$ – Mauro ALLEGRANZA Sep 5 '17 at 15:00
2
$\begingroup$

One way of putting this that might help is the following: what if I told you, "If the real number $x$ is irrational, then $x^2$ is irrational"? (Logically, writing $\mathbb I$ for the set of irrational numbers, this might look like $x \in \mathbb I \to x^2 \in \mathbb I$.) Of course, what I'm saying is false, so you object: "Actually, that's not true. For example $\sqrt{2}$ is irrational, yet $\sqrt{2}^2 = 2$ is rational." (Logically, this looks like $\sqrt{2} \in \mathbb I \land \neg (\sqrt{2}^2 \in \mathbb I)$.)

Do you see how your negation of my statement gave you the conjunction? Do you agree that giving an example where $x \in \mathbb I$ is false, such as $2 \notin \mathbb I \land 4 \notin \mathbb I$ would not have been a refutation of my statement?

$\endgroup$
  • $\begingroup$ Yes, I see your point. I think where I got caught up was that in your example there are irrational numbers for which both $x \in I \wedge x^2 \in I$, so the statement $P \wedge \neg Q$ is not true for all $x$. From what I understand now is that there is a distinction between $P$, and $P(x)$. I think what I was thinking about in my mind was $\exists x. \neg (P(x) \Rightarrow Q(x))$. $\endgroup$ – Bruno KM Sep 5 '17 at 14:49
  • 1
    $\begingroup$ That makes sense. Note that I secretly used quantifiers in my statement too: what I wrote as $x \in \mathbb I \to x^2 \in \mathbb I$ would more reasonably be written as $\forall x(x \in \mathbb I \to x^2 \in \mathbb I)$, and its negation would then be $\exists x(x \in \mathbb I \land \neg(x^2 \in \mathbb I))$. It's a little easier to explain implications with quantifiers. (See also the responses to a post I linked in the comments.) $\endgroup$ – Mees de Vries Sep 5 '17 at 14:54
3
$\begingroup$

It's because $A\to B$ is equivalent to $(\lnot A)\lor B$ and the negation of that is equivalent to $A\land \lnot B$.

$\endgroup$
3
$\begingroup$

All of this is loose, in layman's terms...

$P \Rightarrow Q$ means if P occurs, so does Q. $P$ either happens or it doesn't. So, either $\neg P$ happens or $P$ does, but the latter means $Q$ does, too. So, you can write out the truth table that $P \Rightarrow Q$ is the same as $\neg P \vee Q$. Now use DeMorgan's law on $\neg (P \Rightarrow Q)$, which is $\neg (\neg P \vee Q)$ as just explained. This is your right-hand side.

$\endgroup$
1
$\begingroup$

In logic, an implication ($P\Rightarrow Q$) is false if and only if the hypothesis ($P$) is true and the conclusion ($Q$) is false.

$\endgroup$
1
$\begingroup$

Try to do the Venn diagram of P / Q! What does "imply" mean in that setting and what does "not imply" mean?

That helped me atleast.

$\endgroup$
  • $\begingroup$ Thanks, that was useful to think about! $\endgroup$ – Bruno KM Sep 5 '17 at 14:54
0
$\begingroup$

Set this up as a truth table \begin{matrix} P & Q & P\implies Q & \neg(P\implies Q) \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \end{matrix} From this it is apparent that the far right column, the desired negation, is defined as $P \land \neg(Q)$

$\endgroup$
0
$\begingroup$

Your question concerns a statement made in the field of classical logic.

In this field of study one defines what a statement is and one defines what an implication, negation and conjunction is and thereby lays down the foundation of the theory.

Now i think it is important to emphasize that the only "logical" reason why your stated equivalence holds is that it satisfies the specific definition of equivalence within that set up axiomatic system. One could have defined those notions differently and maybe would not be able to prove the stated equivalence in that new system.

So the only way we can prove this statement is by strictly using the definitions of this system and not by using some kind of intuitive logic. One has to remember that.

Additionally we can then try to find arguments that somehow justify the definitions of classical logic and thereby justify your stated equivalence. (And as others have pointed out we can find many such arguments). But still these arguments are merely a justification of the result and have zero relevance for its actual truthness.

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