Logical NOT of an implication

I was looking through my notes but I was unable to find the answer to this, which I need to start am assignment question.

What would the following be, in terms on moving the negation inside the brackets and keeping the implication:

$\neg (p \rightarrow q)$

Solution 1:

Recall that $p\rightarrow q$ is equivalent to $\lnot p\lor q$. From here:

$$\lnot(p\rightarrow q)\iff\lnot(\lnot p\lor q)\iff \lnot\lnot p\land\lnot q\iff p\land\lnot q$$

One can consider the truth table:

$$\begin{array}{ c | c || c | c |} p & q & p\rightarrow q & \lnot(p\rightarrow q) \\ \hline \text T & \text T & \text T & \text F\\ \text T & \text F & \text F & \text T \\ \text F & \text T & \text T & \text F \\ \text F & \text F & \text T & \text F \end{array}$$

And from this we can see that $\lnot(p\rightarrow q)\iff p\land\lnot q$.

It is also visible that $\rightarrow$ has a True value three out of four times. So $\lnot(p\rightarrow q)$ cannot be written as $\lnot p\rightarrow q$, or as a similar proposition using only a single $\rightarrow$.

This is because to say that $p$ does not imply $q$ says nothing about $p$ implying $\lnot q$, or about $\lnot p$ implying $q$.

Solution 2:

Since $p\to q\equiv \lnot p\vee q$, we can apply DeMorgan's laws to see that

$\lnot(p\to q)\equiv \lnot(\lnot p\vee q)\equiv p \wedge \lnot q$. You can write out a truth table of the left hand side of the formula and the right hand side to further affirm the statement.

Solution 3:

You (or other readers of this question) might be interested in the analysis here, and the related posts.