# 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)$

-
The negation of $\neg (p \rightarrow q)$ is $\neg\neg (p \rightarrow q)$, more commonly written as $p \rightarrow q$ (though you have now changed the question). –  Henry Oct 11 '11 at 21:01
In $p \rightarrow q$, three of the four possibilities are true. In $\neg (p \rightarrow q)$ only one of the four possibilities is true. So it is not an implication in any simple way. Similarly, when you negate $p$ AND $q$, the result is not an AND statement. It is an OR statement. –  GEdgar Oct 12 '11 at 0:03
@Tim: It has been two weeks since you have asked this question. If there is anything missing from my answer, or anyone else's, please let us know. –  Asaf Karagila Oct 24 '11 at 22:28

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

-
Sorry, I edited my question to make it more clear. I would like to keep the implication but move the negation inside of the brackets somehow, but I see that it cannot be done. –  Tim Cooper Oct 11 '11 at 21:04
@Tim: So have I. I'm not sure if this is the answer you have been looking for, but if you are willing to alter the implication completely then it may be possible to write this. –  Asaf Karagila Oct 11 '11 at 21:05

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.

-

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

-
Are you sure this shouldn't really be a comment? –  Asaf Karagila Oct 11 '11 at 21:14
@AsafKaragila: you are right, but I was in a hurry, and I get some editing tools and a preview to check that the link is working when I do an answer. Sorry if this is against protocol. –  Mark Bennet Oct 11 '11 at 21:20
You can use [text](URL) for a link the comments, after a while it becomes easier to use that in answers as well. –  Asaf Karagila Oct 11 '11 at 21:21

The equivalent form of this statement with negations inside brackets and keeping the implication can be constructed if we use logical relationship contraposition so we may write following:

$\lnot(p\Rightarrow q) \Leftrightarrow \lnot(\lnot q \Rightarrow \lnot p)$

but you cannot write any form that satisfies your conditions without negation in front of the brackets.

-

I interpret your question as basically asking "can we write a formula F logically equivalent to ¬(p→q) where F 1. is a conditional and 2. has a negation somewhere inside the conditional?" The answer is yes. I'll try to explain how I saw this first before providing an actual formula which does this.

First, since this question asks about the primary connective of a logical statement, let's rewrite all formulas in prefix notation. In other words, let's rewrite all formulas such that all logical operations precede their arguments (e. g. (p→q) becomes →pq). The first symbol for a formula in prefix notation indicates the type of statement. So, our problem becomes to find a formula with "→" as its first symbol with a negation symbol somewhere else in the formula.

Now implication and negation together form a set of adequate connectives for (two-valued) propositional logic. In other words, all formulas in (two-valued) propositional logic come as equivalent, in prefix notation, to a formula which has a conditional symbol or a negation symbol as its first symbol. Now The Sheffer Stroke "D", or Alternative Denial (NAND), by itself consists of an adequate connective; where D can get defined by the following table with 0 symbolizing falsity and 1 symbolizing truth:

D  0  1
0  1  1
1  1  0


The following logical equivalences (==) hold: 1. Dxx == ¬x, 2. Dxy == →x¬y. Now, since all formulas come as equivalent to a conditional or a negation, and every conditional or negation comes as equivalent to a Sheffer Stroke formula, and every Sheffer Stroke formula comes as equivalent to a conditional with a negation somewhere inside that conditional by 2., it follows that all formulas in classical propositional logic come as equivalent to such a conditional. One could make a similar argument using Peirce's arrow, or joint denial (NOR).

So, how might "¬(p→q)" or equivalently "¬→pq" look as a conditional? Well, substitute →pq for x in 1. above and we have ¬→pq comes as logically equivalent to D→pq→pq. Next, substituting →pq for both x and for y in 2. above we have D→pq→pq as logically equivalent to →→pq¬→pq. In infix notation that goes ((p→q)→(¬(p→q))).

-