INFO 150: A Mathematical Foundation for Informatics

Practice for First Midterm Exam

David Mix Barrington

5 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.

  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
(b) a free variable in a quantified statement
(c) for a number x to be a multiple of y
(d) the base case of an induction proof
(e) a rational number

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) (to English) ∃y: ∃z: A(c, y) ∧ A(m, z) ∧ (y > z)
(c) (to symbols) Every dog has an age that is less than 15.
(d) (to English) [∀x:B(x)] → [¬∃x:¬B(x)]
(e) (to symbols) There is a dog whose age is less than Cardie's age but larger than Mia's age.

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

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

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.

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

Last modified 6 October 2016