INFO 150: A Mathematical Foundation for Informatics

Solutions to Practice First Midterm Exam

David Mix Barrington

6 October 2016

Directions:

Answer the problems on the exam pages.
There are five problems for 100 total points. Scale will be determined after the exam but a good guess is A = 90, C = 60.
If you need extra space use the back of a page.
No books, notes, calculators, or collaboration.

Question text is in black, solutions in blue

  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) for a statement to be a tautology
A tautology is a statement that is always true, no matter what truth values its component propositions take.
(b) a free variable in a quantified statement
A free variable is one whose value must be provided to define the meaning of a statement, as opposed to a bound variable that is governed by a quantifier.
(c) for a number x to be a multiple of y
A number x is a multiple of y if it equals ky for some integer k.
(d) the base case of an induction proof
The base case of an induction proof is where we prove that P(1) is true, where P(n) is the statement we are trying to prove for all n.
(e) a rational number
A number is rational if it can be written as p/q, where p is any integer and q is any nonzero integer.

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 is a dog and y is a number, the predicate A(x, y) means "dog x is age y". The symbols "<", "≤", "=", "≥", and ">" on numbers have their usual meaning.

(a) (to symbols) If Duncan is barking, then Cardie is not barking and Mia is age 5.
B(d) → (¬B(c) ∧ A(m, 5))
(b) (to English) ∃y: ∃z: A(c, y) ∧ A(m, z) ∧ (Y > z)
There are two numbers y and z such that Cardie is age y, Mia is age z, and y is greater than z. Equivalently, Cardie is older than Mia.
(c) (to symbols) Every dog has an age that is less than 15.
∀x:∃y: A(d, y) ∧ y < 15
(d) (to English) [∀x:B(x)] → [¬∃x:¬B(x)]
If every dog is barking, then there is no dog that is not barking.
(e) (to symbols) There is a dog whose age is less than Cardie's age but larger than Mia's age.
∃w:∃x:∃y:∃z: A(w, x) ∧ A(c, y) ∧ A(m, z) ∧ (x < y) ∧ (x > z)

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

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


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

Question 4 (20): Prove that for any number n, if n is the square of an even number and n > 10, then n - 1 is not a prime number.

Let n be (2k)² since it is the square of an even number. So n = 1 = 4k² - 1, which factors as (2k + 1) times (2k - 1). We may take k to be a positive number, since 2k and -2k have the same square. But k cannot be 1, since otherwise n would be 4, and we are told that n > 10. Since k > 1, we know that 2k + 1 > 3 and 2k - 1 > 1. In particular, both the factors of n - 1 are greater than one, so by definition n - 1 is not a prime number.

Question 5 (20): Prove by induction on n that the number 7ⁿ - 1 is divisible by 6.

For the base case, we observe that 7¹ - 1 = 6, which is divisible by 6.

For the inductive case, we assume that 7^n-1 - 1 is divisible by 6, and prove that 7ⁿ - 1 is divisible by 6. There are at least two ways to do this.

The first is to note that 7ⁿ - 1 = (7^n-1 - 1) + (7ⁿ - 7^n-1). The second term factors as 7^n-1(7 - 1), which is divisible by 6. The sum of two numbers, each divisible by 6, must be divisibe by 6. The second way is to note that if 7^n-1 - 1 is divisible by 6, it remains divisible by 6 if we multiply it by 7 to get 7ⁿ - 7. It then again remains divisible by 6 if we add 6 to it to get 7ⁿ - 1.

Last modified 6 October 2016/small>