[Math] Predicate Logic Negation Confusion

logicpredicate-logicquantifiers

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.

Best Answer

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

  1. 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".

  1. 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\;$$

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

  1. Not all integers are odd.

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

Yes, it would.

Related Question