1

I need to find the negation of a statement on my homework, specifically problem 19 of secton 3.2 in Discrete Mathematics with Applications by Susanna Epp. The problem is as follows:

\begin{align} \neg\left(\forall n\in \mathbb{Z},\:n\:\text{is > prime}\:\longrightarrow\:n\:\text{is odd or}\: n=2.\right)\tag{1} \end{align}

In this case, do I have to negate the if-then, or is it simply as I have written it already in which I have negated either side: \begin{align} \Longleftrightarrow \exists n\in\mathbb{Z},\:n\:\text{is not prime}\longrightarrow\:n\:\text{is not or}\:n\neq 2.\tag{2} \end{align} My gut is telling me that I have it wrong, which is why I would appreciate a second opinion. Once again, I realize that it is not your job to do my homework. Tips and hints to get better along the way would be much appreciated, however.

Carl Mummert
  • 81,604
bjd2385
  • 3,017
  • This question is not really about mathematical logic, so I have removed the 'logic' tag (see its tag description) – Carl Mummert Feb 01 '15 at 22:24
  • @CarlMummert My apologies. I suppose I may have mistakenly added it given that just earlier at this time I was working on logic problems. – bjd2385 Feb 02 '15 at 00:59

1 Answers1

3

No, $(2)$ is wrong. Consider the simpler case :

$$ \neg(\forall n\in\mathbb Z)(P(n)\to D(n)). $$

Since $P(n)\to D(n)$ is equivalent to $\neg P(n)\vee D(n)$ we get :

$$ \begin{align} \neg(\forall n\in\mathbb Z)(P(n)\to D(n))&\iff\neg(\forall n\in\mathbb Z)(\neg P(n)\vee D(n))\\ &\iff(\exists n\in\mathbb Z)\neg(\neg P(n)\vee D(n)). \end{align} $$

Can you proceed from there?

Workaholic
  • 6,763
  • 1
    in the last line you want $(\exists n \in Z) \cdots$ – abel Jan 24 '15 at 23:17
  • 1
    @abel Actually I wanted to write $\neg(\forall n\in\mathbb Z)\ldots$, but for some reason I didn't write the $\neg$. Fixed now, thanks. – Workaholic Jan 24 '15 at 23:19
  • Thank you @Workaholic, I went and looked in another textbook for an identity that would help and I found the same: $$P\longrightarrow Q \Longleftrightarrow \neg\left(P\vee Q\right).$$ Thanks for answering! – bjd2385 Jan 24 '15 at 23:45
  • @bd1251252 No it's $;P\to Q \iff \neg P \vee Q;$ only the antecedant ($P$) is negated, not the whole disjunction. This leads to another the identity, how to negate an implication: $; \neg(P\to Q) \iff P\wedge \neg Q;$. – Graham Kemp Jan 25 '15 at 00:22
  • My bad, I wrote it wrong (careless mistake). If I could edit my comment I would – bjd2385 Jan 25 '15 at 00:59