INFO 150: A Mathematical Foundation for Informatics

First Midterm Exam

David Mix Barrington

11 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 1 (15): Briefly identify the following terms or concepts (3 points each):

(a) a closed formula for a number sequence given by a recurrence
(b) the negation of a statement
(c) two logically equivalent compound propositions
(d) the premise of an implication
(e) the Division Theorem

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) (to English) ∀x: S(x, d) → (B(x) ∨ ¬B(m))
(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.
(d) (to English) (B(m) ∧ ¬S(d, m)) ∨ ¬(B(c) ∧ S(d, m))
(e) (to symbols) There is a dog that is the same size as every dog that is not barking.

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

The compound propositions "p → (q ∨ ¬r)" and "¬(r ∧ p ∧ ¬q)" 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.)

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.

Last modified 19 October 2016