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$ 68 Answers
$\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$ $\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$ 2 $\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$ $\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$ $\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$ 1 $\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 truth.
$\endgroup$ $\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$ $\begingroup$The logical implication $P \Rightarrow Q$ essentially means that "from $P$ it is allowed to infer $Q$".
That is, we are allowed to infer true or false things from false assumptions, but we aren't allowed to infer false things from true assumptions.
$\endgroup$
