INFO 150: A Mathematical Foundation for Informatics

Solutions to First Midterm Exam

David Mix Barrington

19 October 2016

Directions:

Answer the problems on the exam pages.
There are five problems for 100 total points. Actual scale was A = 90, B = 72, C = 54.
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) a closed formula for a number sequence given by a recurrence
A closed formula is a rule that gives the value of the n'th number of the sequence in terms of n, rather than using other terms of the sequence.
(b) the negation of a statement
The negation of a statement p is the statement "it is not the case that p", which is true when p is false and false when p is true.
(c) two logically equivalent compound propositions
Two compound propositions (using the same atomic variables) are logically equivalent if they have the same truth value as one another for each possible setting of the atomic variables.
(d) the premise of an implication
In the implication "p → q", p is the premise. It is the statement which, if it is true, requires the conclusion to be true as well for the implication to be true.
(e) the Division Theorem
The Division Theorem says that for every integer a and every positive integer b, there exist integers q and r such that a = qb + r and 0 ≤ r < b.

Question 2 (25): Translate the following statements as indicated. The dogs Cardie, Duncan, and Mia are denoted symbolically by c, d, and m respectively. If x is a dog, the predicate B(x) means "x is barking". If x and y are both dogs, the predicate S(x, y) means "dog x and dog y are the same size". All variables are of type "dog".

(a) (to symbols) Either Duncan is not barking, or Cardie and Mia are both barking.
¬B(d) ∨ (B(c) ∧ B(m)). The parentheses are necessary.
(b) (to English) ∀x: S(x, d) → (B(x) ∨ ¬B(m))
Given any dog, if it is the same size as Duncan, then either it is barking or Mia is not barking.
(c) (to symbols) If Cardie and Mia are the same size, then any dog that is the same size as Mia is not the same size as Duncan.
S(c, m) → ∀x: [S(x, m) → ¬S(x, d)]
(d) (to English) (B(m) ∧ ¬S(d, m)) ∨ ¬(B(c) ∧ S(d, m))
Either Mia is barking and is not the same size as Duncan, or it is not the case that Cardie is barking and Duncan is the same size as Mia.
Equivalently, using DeMorgan, you could say "Either Mia is barking and is not the same size as Duncan, or Cardie is not barking, or Duncan is not the same size as Mia."
(e) (to symbols) There is a dog that is the same size as every dog that is not barking.
∃x: ∀y: (¬B(y) → S(x, y))

Question 3 (20): Establish the following fact with truth tables:

The compound propositions "p → (q ∨ ¬r)" and "¬(r ∧ p ∧ ¬q)" are logically equivalent.


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

Since the columns representing the values of the entire expressions (the → on the left and the ¬ on the right) are identical, the two compound propositions are logically equivalent.

Question 4 (20): Prove the following statement:

If n is any integer, then n³ - n is divisible by 3.
(Hint: Use the Division Theorem and consider the three cases of the possible remainder when n is divided by 3. You don't want to use induction, since you need all integers and not just positive ones.)

By the Division Theorem, n may be written as 3q + r where r equals 0, 1, or 2. (Many of you instead used the Division Theorem on n³ - n, which would have been ok if you had shown that the r = 1 and r = 2 cases led to contradictions, but you didn't.)

In the case where r = 0, n³ - n equals (3q)³ - 3q = 27q³ - 3q = 3(9q³ - q). Since the number in parentheses is an integer, we have shown that n³ - n is divisible by 3.

In the case where r = 1, n³ - n equals (3q+1)³ - (3q+1) = 27q³ + 27q² + 9q + 1 - 3q - 1 = 3(9q³ + 9q² + 2q). Since the number in parentheses is an integer, we have shown that n³ - n is divisible by 3.

In the case where r = 2, n³ - n equals (3q+2)³ - (3q+2) = 27q³ + 54q² + 36q + 8 - 3q - 2 = 3(9q³ + 18q² + 11q + 2). Since the number in parentheses is an integer, we have shown that n³ - n is divisible by 3.

Many of you observed that n³ - n may be rewritten as (n+1)n(n-1). This allows for an easier proof, because in the case where r = 0 we have that n is divisible by 3, in the case where r = 1 we have that n-1 is divisible by 3, and in the case where r = 2 we have that n+1 is divisble by 3. So the product always contains a factor divisible by 3, and thus is itself divisible by 3.

Question 5 (20):

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

Our statement P(n) is "a_n = (n³ - n)/3".

For our base case, we must prove P(1). The number a₁ is defined to be 0, and (1³ - 1)/3 is also 0, so P(1) is true.

For the inductive case, we assume that a_n-1 = ((n-1)³ - (n-1))/3 and use the rule that a_n = a_n-1 + n(n-1). This tells us that a_n is equal to

(n³ - 3n² + 3n - 1 - n + 1)/3 + n(n-1) =

(n³ - 3n² + 2n + 3n² - 3n)/3 =

(n³ - n)/3

The algebra simplifies somewhat if you keep a common factor of n-1 in all the terms. In any event, we have assumed P(n-1) and proved P(n), which completes the inductive case.

Last modified 19 October 2016