Exercises on quantifiers

Note: This page uses some Unicode characters for mathematical symbols; If you see blank boxes (or something like that) instead of letters, there is another page with the same exercises.

1. Express the following sentence in symbols without using the ‘divides’ symbol.

   If 𝑥 is even and 𝑥 is a perfect square, then 𝑥 is divisible by 4.

   Write the negation of this sentence in symbols and in words. Write the contraposition of the given sentence in symbols and in words.
2. For the universe of integers, determine whether the following are true or false. Justify briefly.
   1. ∀𝑥 (𝑥 > 0 ⇒ 𝑥 ≠ 𝑥),
   2. ∀𝑥 (𝑥 ≠ 𝑥 ⇒ 𝑥 > 0),
   3. ∃𝑥 (𝑥 > 0 ⇒ 𝑥 ≠ 𝑥),
   4. ∃𝑥 (𝑥 ≠ 𝑥 ⇒ 𝑥 > 0).
3. For the universe of integers, let 𝑝(𝑥,𝑦) mean 𝑥 divides 𝑦. State whether the following statements are true or false. Justify briefly.
   1. ∀𝑥 ∀𝑦 𝑝(𝑥,𝑦),
   2. ∀𝑥 ∃𝑦 𝑝(𝑥,𝑦),
   3. ∀𝑥 𝑝(𝑥,2𝑥),
   4. ∃𝑥 𝑝(𝑥,𝑥+1),
   5. ∃𝑥 ∀𝑦 𝑝(𝑥,𝑦),
   6. ∃𝑥 ∃𝑦 𝑝(𝑥,𝑦),
   7. ∀𝑥 ∃𝑦 ¬𝑝(𝑥,𝑦),
   8. ¬∀𝑥 ∃𝑦 𝑝(𝑥,𝑦),
   9. ¬∀𝑥 𝑝(𝑥,𝑥),
   10. ∃𝑥 ∃𝑦 ¬𝑝(𝑥,𝑦).
4. Let 𝑝(𝑛) stand for 𝑛 is odd, and 𝑞(𝑛) for 𝑛² is odd. Which of the following statements are logically equivalent?
   1. If the square of an integer is odd, then the integer is odd.
   2. ∀𝑛 [𝑝(𝑛) is necessary for 𝑞(𝑛)]
   3. The square of an odd integer is odd.
   4. There are some integers whose squares are odd.
   5. Given an integer whose square is odd, that integer is also odd.
   6. ∀𝑛 [¬𝑝(𝑥) ⇒ ¬𝑞(𝑛)]
   7. ∀𝑛 [𝑝(𝑛) is sufficient for 𝑞(𝑛)]
5. Negate and simplify.
   1. ∀𝑥 (𝑝(𝑥) ∧ ¬𝑞(𝑥) ⇒ 𝑟(𝑥))
   2. ∀𝑥 𝑝(𝑥) ⇒ ∃𝑦 𝑞(𝑦)
   3. ∀𝑥 ∀𝑦 (𝑥 > 𝑦 ⇒ 2𝑥 > 2𝑦)
6. From Velleman, page 72-73: Exercises 1 (c,d), 5, 6 (give two proofs: one direct and one using the hint), 7, 9.