10
$\begingroup$

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

  • 0
    @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.2011-10-24

5 Answers 5

17

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

  • 0
    @Max: Okay...???2015-03-04
5

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.

2

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

  • 0
    You can use `[text](URL)` for a link the comments, after a while it becomes easier to use that in answers as well.2011-10-11
1

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.

1

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