INFO 150: A Mathematical Foundation for Informatics

Solutions to First Midterm Exam

David Mix Barrington

19 October 2016

Directions:

  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):

  • 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".

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

    
    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:

    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 n3 - 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, n3 - n equals (3q)3 - 3q = 27q3 - 3q = 3(9q3 - q). Since the number in parentheses is an integer, we have shown that n3 - n is divisible by 3.

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

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

    Many of you observed that n3 - 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):

    Our statement P(n) is "an = (n3 - n)/3".

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

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

    (n3 - 3n2 + 3n - 1 - n + 1)/3 + n(n-1) =

    (n3 - 3n2 + 2n + 3n2 - 3n)/3 =

    (n3 - 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