INFO 150: A Mathematical Foundation for Informatics

Solutions to 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 text is in black, solutions in blue.

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

(a) the base case of a proof by induction
The base case is the proof of P(1), where P(n) is the statement we want to prove true for all n by induction.
(b) the contrapositive of an implication
The contrapositive of an implication "p → q" is the statement "¬q → ¬p". It is logically equivalent to the original implication.
(c) a counterexample to a universally quantified statement
If ∀x:P(x) is a universally quantified statement, a counterexample to it is any element a of the type of x such that P(a) is false. Its existence proves that ∀x:P(x) is false.
(d) a recurrence relation defining a sequence of numbers
A recurrence relation defines a sequence of numbers by giving its first element (a₁) and a rule for computing each new element in terms of previous elements.
(e) a rational number
A rational number is a real number that can be written as p/q, where p is any integer and q is any nonzero integer.

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:∀x:PG(x) → I(x, b)" ("There is some breed that all of Professor Gill's dogs have") or "∀x:∀y:(PG(x) ∧ PG(y))) → SB(x, y)" ("Any two of Professor Gill's dogs are of the same breed")
(b) (to English) ¬∃b:∃x:∃y: I(x, b) ∧ I(y, b) ∧ PB(x) ∧ PG(y)
"There do not exist two dogs of the same breed such that one belongs to Professor Barrington and the other to Professor Gill."
(c) (to symbols) Either Mia or Whistle, but not both, is of the same breed as Cardie.
"SB(m, c) ⊕ SB(w, c)" or "(SB(m, c) ∨ SB(w, c)) ∧ ¬(SB(m, c) ∧ SB(w, c))" or "∃b:I(c, b) ∧ (I(m, b) ∨ I(w, b)) ∧ ¬(I(m, b) ∧ I(w, b))". Strictly speaking, we should not assume in our translation that a dog cannot have more than one breed (the third response here does this).
(d) (to English) PB(d) ∧ ∃x:∀y:(PB(y) ∧ (y ≠ d)) ↔ (x = y)
"Duncan belongs to Professor Barrington, and there is another dog x such that any dog other than Duncan belongs to Professor Barrington if and only if it is x," or "Professor Barrington has exactly two dogs, one of whom is Duncan".
(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.)
"¬∃x:∃y: PB(x) ∧ PB(y) ∧ (x ≠ y) ∧ SB(x, y)" or "¬∃x:∃y:∃b: PB(x) ∧ PB(y) ∧ (x ≠ y) ∧ I(x, b) ∧ I(y, b)".

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

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


     (q and (p or not r)) --> (p or (q and not r))
      0  0   0  1  1  0    1   0  0  0  0   1  0
      0  0   0  0  0  1    1   0  0  0  0   0  1
      1  1   0  1  1  0    1   0  1  1  1   1  0
      1  0   0  0  0  1    1   0  0  1  0   0  1
      0  0   1  1  1  0    1   1  1  0  0   1  0
      0  0   1  1  0  1    1   1  1  0  0   0  1
      1  1   1  1  1  0    1   1  1  1  1   1  0
      1  1   1  1  0  1    1   1  1  1  0   0  1

Since the column under the implication (the last operation to be executed in evaluating the statement) is all ones, the statement is true in all eight cases and it thus 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.)

Let z be the number n³ + n² + n + 1. By the Division Theorem, we know that n can be written as 5q + r where 0 ≤ r < 5. We are interested in how the remainder, when 5 is divided by 5, depends on the value of r.

Following one student's example, we will save calculation by computing z in terms of q and r before breaking into cases. Writing n as 5q + r, we get z = (5q + r)³ + (5q + r)² + (5q + r) + 1. Expanding the powers, we get a lot of terms, but nearly all of them are clearly divisible by 5. The exceptions are the terms r³, r², r, and 1.

Now we break into five cases:

If r = 0, the remainder is 0 + 0 + 0 + 1 = 1, which is not divisible by 5, so z is not divisible by 5. This is good for us, since in this case n cannot be written in any of those three forms.
If r = 1, the remainder is 1 + 1 + 1 + 1 = 4, which is not divisible by 5. Again this is good, as n cannot be written in any of the three forms.
If r = 2, the remainder is 8 + 4 + 2 + 1 = 15 which is divisible by 5, so z is divisible by 5, and n is clearly written as 5q + 2.
If r = 3, the remainder is 27 + 9 + 3 + 1 = 40 which is divisible by 5, so z is divisible by 5, and n is clearly written as 5q + 3.
If r = 4, the remainder is 64 + 16 + 4 + 1 = 85 which is divisible by 5, so z is divisible by 5, and n is clearly written as 5q + 4.
In each of the five cases the given ↔ statement is true, so it is always true and the ∀n statement is proved.

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}

We prove this by induction.

For the base case, we are given that a₁ = 1, and we want to prove that a₁ = 5 - 2^3-1. Since 1 = 5 - 4, this is true.

For the inductive case, we asssume that a_n-1 = 5 - 2^3-(n-1) = 5 - 2^{4 - n} is true. Our inductive goal is a_n = 5 - 2^3-n. Using the rule, we compute that a_n = (a_n-1 + 5)/2 = (by the IH) (5 - 2^4-n + 5)/2 = (10 - 2^4-n)/2 = 5 - 2^3-n. This satisfies the inductive goal and completes the proof.

Last modified 22 October 2017