Predicate Logic Negation Confusion

Question

I have a question in my discrete math class that I was having some confusion with.
If:

N(x): x is a non-negative integer
E(x): x is even
O(x): x is odd
P(x): x is prime

Negate each sentence and translate into logical notation.

1. There exists an even integer.
   
   Would this be: There is an integer that is not even. $∀x $~$ E(x)$
   
   

2. Every integer is even or odd.
   
   Would this be: There exists an integer that is not even or odd. $∃ x $~$ (E(x) $V$ O(x))$
   
   

3. All prime integers are non-negative.
   
   Would this be: There exists a prime that is not non-negative. $∃ x $~$ P(x) \Rightarrow N(x)$
   
   

4. The only even prime is 2.
   
   Would this be: The only even prime is not 2. $∀x $~$(P(x) \wedge E(x)) \Rightarrow 2$
   
   

5. Not all integers are odd.
   
   Would this be: All integers are odd. $∀xO(x)$
   
   

I was wondering if my logic in answering these questions was right.

Answer 1

(1.) and (2.) are correct. (3.) should be $\neg \forall x (P(x) \Rightarrow \neg N(x))$. This is equivalent to both $\exists x \neg(P(x)\Rightarrow N(x))$ and $\exists x (P(x) \land \neg N(x))$.

For (4.) you need the sentence "2 is not the only prime even number," which means either 2 is not a prime even number or there is another prime even number. It can be formalized as $\neg (P(2)\land E(2) \land \forall x ([P(x) \land E(x) ] \Rightarrow x=2)$.

(5.) is correct.

Answer 2

When negating a statement, we interchange "there exists" and "for all," and negate all statements.

1 should be "All integers are not even", in other words, "No integers are even."

2 should be "There exists an integer that is not (even or odd)," so "There exists an integer that is neither even nor odd."

3 is correct.

4 should be "There is a even prime that is not 2."

5 is correct.

Answer 3

1. There exists an even integer.

Would this be: There is an integer that is not even. $\forall x \neg E(x)$

You managed to get the logic expression correct, but the English should be "All integers are not even", or "No integer is even".

2. Every integer is even or odd.

Would this be: There exists an integer that is not even or odd. $∃ x \neg (E(x) \vee O(x))$

Yes, though it is better to say "... neither even nor odd", to clarify that the negation applies to "even or odd", rather than just to "even".

3. All prime integers are non-negative.

Would this be: There exists a prime that is not non-negative. $∃ x \neg P(x) \Rightarrow N(x)$

The English is parseable, but the FOL is not. You want : $$\underbrace{\exists x }_\text{There is an integer}(\underbrace{P(x)}_\text{that is prime}\;\underbrace{\wedge}_\text{and}\; \underbrace{\neg N(x)}_\text{not non-negative})$$

Remember that the negation of an implication is a conjunction with a negation (of the consequent). $$\;\neg (A\implies B) \;\equiv\; A\wedge \neg B\;$$

4. The only even prime is 2.

Would this be: The only even prime is not 2. $∀x \neg(P(x) \wedge E(x)) \Rightarrow 2$

No. The statement is actually short for "2 is an even prime and there exists no other even prime." So the negation would be "Either 2 is not an even prime, or there exists an even prime which is not 2".

$$\neg (P(2)\wedge E(2)) \vee \exists x(P(x)\wedge E(x)\wedge (x\neq 2))$$

Also, you can't simply state something implies $2$. That's nonsensical; $2$ is not a boolean value. You need to equate something with it (or deny the equality as the case may be).

5. Not all integers are odd.

Would this be: All integers are odd. $∀xO(x)$

Yes, it would.

Answer 4

I found the 1st and 5th to be correct , for the 2nd ) ∀x ( E(x) <--> ~O(x) ) and its negation would be ∃x ~( E(x) <--> ~O(x) ) and on simplifying we get ∃x ( E(x) <--> O(x) ) 3rd answer is posted above by graham and 4th) ( P(x) ∧ E(x) ) --> (x=2) so its negation (P(x) ∧ E(x)) ∧ (x≠2)