INFO 150: A Mathematical Foundation for Informatics

First Midterm Exam

David Mix Barrington

15 October 2017

Directions:

Answer the problems on the exam pages.
There are five problems for 100 total points. Actual scale was A = 90, B = 75, C = 60.
If you need extra space use the back of a page.
No books, notes, calculators, or collaboration.

  Q1: 15 points
  Q2: 25 points
  Q3: 20 points
  Q4: 20 points
  Q5: 20 points
Total: 100 points

Question 1 (15): Briefly identify the following terms or concepts (3 points each):

(a) the base case of a proof by induction
(b) the contrapositive of an implication
(c) a counterexample to a universally quantified statement
(d) a recurrence relation defining a sequence of numbers
(e) a rational number

Question 2 (25): Translate these five statements as indicated. We have a set of dogs D including (among others) the named dogs Cardie, Duncan, Mia and Whistle who are denoted symbolically by c, d, m and w respectively. If x is a dog, the predicate PB(x) means "x belongs to Professor Barrington" and PG(x) means "x belongs to Professor Gill". We also have a set B of breeds, a predicate I(x, y) meaning "dog x is of breed y", and a predicate SB(x, y) meaning "dog x and dog y are of the same breed". Variables in quantifiers are of type "dog" or of type "breed" -- you can tell which by how they are used in predicates.

(a) (to symbols) All of Professor Gill's dogs are of a single breed.
(b) (to English) ¬∃b:∃x:∃y: I(x, b) ∧ I(y, b) ∧ PB(x) ∧ PG(y)
(c) (to symbols) Either Mia or Whistle, but not both, is of the same breed as Cardie.
(d) (to English) PB(d) ∧ ∃x:∀y:(PB(y) ∧ (y ≠ d)) ↔ (x = y)
(e) (to symbols) No two of Professor Barrington's dogs have the same breed. (Hint: If you mean for two variables to represent different dogs, then you need to say that they are not equal.)

Question 3 (20): Prove the following using truth tables:

The compound propositions "(q ∧ (p ∨ ¬r)) → (p ∨ (q ∧ ¬r))" is a tautology.

Question 4 (20): Prove the following statement:

If n is any integer, then n³ + n² + n + 1 is divisible by 5 if and only if n can be written as either 5k + 2, 5k + 3, or 5k + 4 for some integer k.
(Hint: Use the Division Theorem and consider the five cases of the possible remainder when n is divided by 5. You don't want to use induction, since you need all integers and not just positive ones.)

Question 5 (20):

Let a₁, a₂, a₃,... be the sequence of numbers defined by the following rules: a₁ = 1 and, for any n with n > 1, a_n = (a_n-1 + 5)/2. Prove by induction that for all positive integers n, a_n = 5 - 2^{3 - n}

Last modified 22 October 2017