Question regarding De Morgan's law and contrapositives

Question

Give the contrapositive of the following proposition concerning an integer $p$:

["]If $p$ is odd and $p>3$ then $p+1$ and $p-1$ are not primes[."]

The answer is:

["]if $p+1$ or $p-1$ is a prime then $p$ is even or $p\le3$[."]

I'm talking about the switch between "and" to "or" in the sentences. The switch between "and" and "or" technically makes sense, but the negation in symbols of the second part of the original, (i.e. $p+1$ and $p-1$ are not primes) is:

["]if $\ \underbrace{p+1\textrm{ is a prime}}_{r}\ $ and $\ \underbrace{p-1\textrm{ is not a prime}}_{s}$[",]

then $\lnot\lnot r\land\lnot\lnot s$ which is the same as $r\land s$. I don't understand how that got to "p or r" when it is "p and r" in symbols, so why wouldn't it be ["]$p+1$ and $p-1$ is a prime[".]? They also said they were using De Morgan's law so I guess it might be that, but I don't know in what way they used it.

Answer 1

Symbolically, the original proposition was $$ (\mathit{odd}(p) \land p>3) \to (p+1\notin\mathbb P \land p-1\notin\mathbb P)$$ The contrapositive of this is $$ \neg(p+1\notin\mathbb P \land p-1\notin\mathbb P) \to \neg(\mathit{odd}(p) \land p>3)$$ Now we can use De Morgan's law to simplify each of the sides of the $\to$ separately. First on the left: $$ (\neg(p+1\notin\mathbb P) \lor \neg(p-1\notin\mathbb P)) \to \neg(\mathit{odd}(p) \land p>3)$$ and then on the right: $$ (\neg(p+1\notin\mathbb P) \lor \neg(p-1\notin\mathbb P)) \to (\neg\mathit{odd}(p) \lor \neg(p>3))$$ Finally apply the negations to the atomic propositions one by one: $$ (p+1\in\mathbb P \lor p-1\in\mathbb P) \to (\mathit{even}(p) \lor p\le 3)$$

Answer 2

The contraposition for $(P\wedge Q)\to(R\wedge S)$ is $\neg(R\wedge S)\to\neg(P\wedge Q)$ and by deMorgan that is $(\neg R\vee\neg S)\to(\neg P\vee\neg Q)$.   (Note: all three statements are equivalent).

So taking it one step at a time.

• "If $p$ is odd and $p>3$ then $p+1$ and $p-1$ are not primes."
• "If not ($p+1$ and $p-1$ are not primes), then not ($p$ is odd and $p>3$)"
• "If $p+1$ or $p-1$ is not not prime, then $p$ is not odd or not $p>3$"
• "If $p+1$ or $p-1$ is prime, then $p$ is even or $p\leq 3$"

Answer 3

By De Morgan's law, which can be proved with a truth table:

$$\lnot(p\lor q)\iff\lnot p\land\lnot q,\\ \lnot(p\land q)\iff\lnot p\lor\lnot q.$$