CSCI 2400/SENG 1010
Solutions for practice questions set 1012

1. Suppose that the domain of discourse is the set of all integers. Say whether each of the following is true or false.
   1. ∀n∃m( n² < m ) True.
      
      
   2. ∃n∀m( n² < m ) False. (The smallest you can get n² to be is 0. But 0 is not less than 0.)
      
      
   3. ∃n∃m( n² + m² = 5 ) True. (n = 2 and m = 1 works.)
      
      
   4. ∃n∃m( n² + m² = 6 ) False.
      
      
   5. ∀n∀m∃r( m + n = 2r ) False. (What if m + n is odd?)
   
   
   
2. Express the negation of each of the following without using the negation symbol.

   This question got mixed up in translation from another document. For illustration, I have negated each one. These are not the original questions that you were asked.

   1. ¬∀x( x > 1 )

      ∃x( x ≤ 1 )

      
      
      
   2. ¬∃x( x < 0 )

      ∀x( x ≥ 0 )

      
      
      
   3. ¬∃x( −2 < x < 3 )

      ∀x( x ≤ −2 ∨ 3 ≤ x ) (Be careful. Notation (−2 < x < 3) is shorthand for (−2 < x ∧ x < 3). You need to apply DeMorgan's law, converting the ∧ to ∨.

   
   
   
3. Let Q(x, y) mean "x is a student at your school who has been a contestant on quiz show y." Express each of the following using quantifiers, logical connectives and predicate Q(x, y).
   1. There is a student at your school who has been a contestant on a quiz show.

      ∃x∃yQ(x, y)

      
      
      
   2. There is a student at your school who has been a contestant on Jeopardy! and Wheel of Fortune.

      ∃x(Q(x, "Jeopardy") ∧ Q(x, "Wheel of Fortune"))

      
      
      
   3. Every quiz show has had a student from your school as a contestant.

      ∀y∃xQ(x, y)

      
      
      
   4. At least two students from your school have been contestants on Wheel of Fortune.

      ∃x∃y(x ≠ y ∧ Q(x, "Wheel of Fortune") ∧ Q(y, "Wheel of Fortune"))