INFO 150: A Mathematical Foundation for Informatics

David Mix Barrington

Fall, 2017

This is the homework index page for INFO 150.

The textbook for the course is Discrete Mathematics: Mathematical Reasoning and Proof with Puzzles, Patterns, and Games by Douglas E. Ensley and J Winston Crawley. Most of the assignments are from this text.

• HW#1, due Friday 8 September 2017: From EC section 1.1, pages 8-9:
  • 1.1.2: Explain why, in the card trick of section 1.1, after each of steps 2-7, the packet of cards always contains exactly one card reversed from the others. (Originally the four cards are all face up. Step one turns the top card over. Steps 2, 4, and 6 each move any number of cards, one at a time, from the top to the bottom of the bottom. Steps 3 and 5 each turn over the top two cards as one. Step 7 either turns over the entire deck or does nothing.
  • 1.1.5: The text shows that a tennis game cannot consist of exactly seven points. What other numbers of total points are impossible?
  • 1.1.7: Suppose you toss three coins, a nickel, dime and quarter, and record the results in that order. For example, HTH would mean heads on the nickel, tails on the dime, and heads on the quarter. (a) In a systematic way, list all the different results you could record. (b) Draw a game tree for the recording of the results. (c) On the game tree, label each possible result either 0, 1, 2, or 3, indicating how many heads it has. Do you think a person who tosses three coins is more likely to get all three heads, or to get exactly two heads?
  • (extra question) The text describes a grid game where the two players alternate moves, and a legal move is to pick a row or column with at least one blank space, and X out one or more spaces in that row or column. The first player who cannot move loses the game. Suppose you are going to play this game on a 2 by 2 grid (instead of the 4 by 4 in the text). Would you rather be the first or the second player? Show that if you get to choose, you can win the game every time.

• Assignment #2, due Monday 11 September: From EC Section 1.2, pages 20-23.
  • 1.2.2 parts b and f: For each of these sequences, calculate a_k+1 and a_k-1, and algebraically simplify the expressions for each: (b) a_n = 3n² + n, (f) a_n = n(2n-1)(n+2)/6
  • 1.2.6 parts b and d: For each of the given sequences, use the given closed form and algebra to check whether the given recursive formula is true.
    • (b) Given that a_n = n² for all n ≥ 1, is it true that a_n = a_n-1 - 2n?
    • (d) Given that a_n = 1 - 1/2ⁿ for all n ≥ 1, is is true that a_n = a_n-1 + 1/2ⁿ?
  • 1.2.12: Give an algebraic expression that describes the n'th even two-digit number. Indicate which values of n give you such a number.
  • 1.2.18: Give an algebraic expression for the n'th term in the arithmetic progression a, a+d, a+2d, a+3d,...
  • 1.2.26 parts a, b, d, f: For each of these sequences, give a characterization of the sequence. For each, we suggest the type that may be easiest to use, but you may give characterizations of other types.
    • (a) 1, 9, 25, 49, 81,... (formula for n'th term)
    • (b) 1, 2, 2, 4, 8, 32, 256,... (relate term to previous terms)
    • (d) 1, 4, 27, 256, 3125,... (formula for n'th term)
    • (f) 1, 3, 4, 7, 11, 18,... (relate term to previous terms

• Assignment #3, due Wednesday 13 September: On EC Section 1.3, pages 37-70.
  • 1.3.1 part (c) only: You come across three inhabitants of Smullyan's Island. A says "B and C are both lying". B says "Only one of the other two is lying". C says "At least one of us is lying". Who if anyone is telling the truth?
  • 1.3.5 parts b and d only: Use the letter f to represent "this person is female", a for "this person is over age 30", and m for "this person is a math major". Use these names along with the basic operations AND (∧), OR (∨), and NOT (¬) to write each of the following English sentences with symbolic logic:
    • (b) This person is a female math major over age 30.
    • (d) Either this person is not female or this person is over age 30.
  • 1.3.11 parts b and e only: Complete truth tables for the following compound expressions:
    • (b) ¬p ∧ (p ∨ q)
    • (e) (p ∧ q) ∨ r
  • 1.3.17: Use truth tables to verify that p ∨ (p ∧ q) is logically equivalent to p, establishing the second absorption property in Theorem 2.
  • 1.3.22: For each of the following statements, rewrite them in propositional logic notation, making the meaning of your propositional variables clear. Use truth tables to find any pairs among these statements that are logically equivalent.
    • (a) Jillian likes playing in the sand or volleyball, but she does not like sailing.
    • (b) Jillian likes playing in the sand, and she likes sailling or volleyball.
    • (c) Jillian likes playing in the sand and volleyball, or she likes sailing.
    • (d) Jillian likes playing in the sand and sailing, or she likes volleyball and sailing.

• Assignment #4: due in class Friday 14 September: From EC Section 1.3, pages 37-40.

  • 1.3.12, parts b, d, e only: Rewrite each of the following statements in propositional logic notation, making the meaning of your propositional variables clear, and then create a truth table for the sentence.
    • (b) The staff is friendly, or else they are not friendly but very well paid.
    • (d) You play sports of you play mahjong or nobody knows your name.
    • (e) You do not play mahjong or you do not play sports , and nobody knows your name.

  • 1.3.21, parts b, d, and e only: Use truth tables to check if each of the given pairs of symbolic logic statements are equivalent:
    • (b) "(p ∨ q) ∧ (¬p ∨ q)" and "q"
    • (d) "p ∧ (q ∨ r)" and "(p ∧ q) ∨ r"
    • (e) "(p ∨ q) ∧ (q ∨ r)" and "(p ∧ r) ∨ q"

  • 1.3.23, parts c and d only: Use the double negative property and DeMorgan's laws to rewrite each of the following as an equivalent statement that never has the not symbol (¬) outside of a parenthesized expression.
    • (c) ¬(¬(¬p ∧ q))
    • (d) ¬(p ∧ (q ∨ ¬p))

  • 1.3.24, parts b and c only: By quoting the parts of Theorem 2, verify the following logical equivalences. In each case, start from the left side and use parts of the theorem to change the problem, ending up with the right side. Remember that "t" and "c" are EC's symbols for the boolean constants "true" and "false" (or 1 and 0) respectively.
    • (p ∨ t) ∧ (p ∨ c) ≡ p
    • q ∧ (p ∨ r) ≡ (p ∧ q) ∨ (q ∧ r)

  • 1.3.25: By using parts of Theorem 2 as algebraic rules, simplify that expression (p ∨ q) ∧ ¬(¬p ∧ r) as much as you can.

• Assignment #5: Due in class Monday 18 September: From EC section 1.4, pages 51-53:
  • 1.4.2, parts a, b, c, only: For each of the given values of x and y, determine which of the following four statements are true: (1) both x and y are positive, (2) at least one of x and y is positive, (3) exactly one of x and y is positive, and (4) neither x nor y is positive. For part (a), x = 8 and 7 = 3. For part (b), x = -5 and y = 0. For part (c), x = 7 and y = -7.

  • 1.4.9: Write each of the following statements using quantifiers and predicates. In each case, you must specify the domain and define the predicates you use.
    • (a) For every integer n, 2n ≠ 9.
    • (b) There exists a triangle T that is equilateral and has perimeter 10.
    • (c) Every circle has an integer diameter or an integer area.
    • (d) Every two real numbers have an integer in between.

  • 1.4.12: For each of the following English sentences, specify a domain (data type) and a predicate, and write the quantified statement symbolically using either the form "¬∃x∈D: P(x)" or the form "∀x∈D: P(x)".
    • (a) Even numbers are never prime.
    • (b) Triangles never have four sides.
    • (c) There are no integers a and b for which a²/b² = 2.
    • (d) No square number immediately follows a prime number.

  • 1.4.14 parts b and d: Write the negation of each of the following rules using Proposition 1 (the rules for negating a single quantifier), and the rules for negating propositions, to simplify each to the point that no ¬ symbol occurs to the left of a quantifier. (Recall that Z denotes the set of all integers, and R denotes the set of all real numbers.)
    • (b) ∃y ∈ R, ∀x ∈ R, x + y = x
    • (d) ∀x ∈ Z, ∃y ∈ R, x/y = 2

  • 1.4.15, all parts: For each statement in Exercise 1.4.14, is the original statement or its negation true? These two statements are included:
    • (a) ∀a ∈ R, ∀b ∈ Z, a² + b ∈ Z
    • (c) ∀ x∈ Z, ∃y ∈ R, x = 2y.

• Assignment #6, due Wednesday 20 September: from EC section 1.4, pp. 50-53, plus two extra problems

  • 1.4.16: Write the negation of each of the following statements as an English sentence. You might find it helpful to write a symbolic expression as an intermediate step.
    • (a) Every time you roll a "6", you have to take a card.
    • (b) There is a day in your life that is better than every other day.
    • (c) In every good book, there is a plot twist or a surprise ending.
    • (d) Every math course has a topic that everyone finds easy to do.

  • 1.4.19: Write the negation of each of the following statements as an English sentence:
    • (a) For all odd integers b, there is no real number x such that x² + bx + 15 = 0.
    • (b) For every two real numbers x and y, there is an integer n such that x < n < y.
    • (c) For every pair of integers that sum to 5, at least one of the numbers must be bigger than 2.

  • 1.4.20: For each statement in Exercise 1.4.19, is the original statement or its negation true? (Justify your claim with a sentence.)

  • Extra problem 6-1: Let D be a set of dogs, let c and d be the constant dogs Cardie and Duncan, let the predicate T(x) mean "dog x is a terrier", and let WS(x, y) mean "dog x weighs the same as dog y". Translate the following English statements into symbolic language:
    • (a) Every dog that weighs the same as Duncan is a terrier who weighs the same as Cardie.
    • (b) There is a terrier other than Duncan who does not weigh the same as either Cardie or as any dog who is not a terrier.
    • (c) No terrier except possibly Duncan weighs the same as any dog who is not a terrier.

  • Extra problem 6-2: Using the same domain, constants, and predicates as in extra problem 6-1, translate the following symbolic statements into English:
    • (a) ∀x:∃y:¬T(x) ∨ WS(y, c)
    • (b) ∀x:∀y:(WS(x, y) ∧ WS(y, x)) ∨ (¬WS(x, y) ∧ ¬WS(y, x))
    • (c) ¬∃x:¬T(x) ∧ ¬WS(x, x) ∧ (x ≠ c).

• Assignment #7, due Monday 25 September: From EC section 1.5, pages 65-68:
  • 1.5.4, parts b, d, f: Complete truth tables for the following compound expressions:
    • (b) ¬p → (p ∨ q)
    • (d) ¬p ∧ (¬q → p)
    • (f) (p ∧ q) → (p ∨ r)

  • 1.5.11: Let D be the set {1, 3, 5, 7, 8, 10, 11, 12}. For each of the following, decide whether it is true for all the elements of D. If it is not, give a counterexample.
    • (a) If x is even and x > 7, then x < 20.
    • (b) If x is odd, then x < 10.
    • (c) If x < 10 and x ≠ 8, then x is odd.
    • (d) If x is odd or x < 5, then x - 1 is even.
    • (e) If x > 5 and x < 7, then x is negative.

  • 1.5.13: For each of the following statements, describe the predicates P and Q that make the formal statement "there exists an integer n such that P(n) ∧ Q(n)" correctly represent the statement.
    • (a) Some odd numbers n make 2ⁿ - 1 a multiple of 7.
    • (b) At least one multiple of 5 does not have a ones' digit of 0.
    • (c) It is possible for a multiple of 3 to have a ones' digit of 7.

  • 1.5.25, parts b, d, e: Form the contrapositive of each of these statements:
    • (b) We will go if you go.
    • (d) If a quadrilateral is a square, it has four equal sides and has four equal angles.
    • (e) If a triangle has either two equal sides or two equal angles, then it is an isoceles triangle.

  • 1.5.30 parts b, d, f, g: Express each of the following using quantified statements over the domain S of all college students and the predicates C(x), meaning "x is a computer science major", and D(x), meaning "x takes discrete mathematics". Which statements are negations of one another?
    • (b) Some computer science majors take discrete mathematics.
    • (d) Not every computer science major takes discrete mathematics.
    • (f) You must take discrete mathematics if you are a computer science major.
    • (g) Some computer science majors do not take discrete mathematics.

• Assignment 8, due Wednesday 27 September: From EC section 5, pages 65-68.
  • 1.5.17
  • 1.5.18
  • 1.5.21
  • 1.5.23
  • 1.5.28 part b only

• Assignment #9, due Friday 29 September: This is a single problem with multiple parts, based on the non-book lecture of Wednesday 27 September. We have a computer that can execute a billion (10⁹) steps per second. For any value of n, we have five algorithms we want to run. Algorithm A takes n ln n steps, where ln n is the natural (base-e) logarithm of n. Algorithm B takes n² steps, C takes n³, D takes 2ⁿ, and E takes n! (the factorial of n).

  Make a table with a column for each of the five algorithms, and a row for each of the following values of n: 10, 20, 50, 100, 200, 500, and 1000. In the entry for each row and column, put the time that the algorithm would take for that n, in terms of seconds, days, or years (whichever is most informative. If the answer is "more than 10¹⁰⁰ years", you can just say "too long".

• Assignment #10, due Monday 2 October: From EC Section 2.1, pages 96-98:
  • 2.1.3
  • 2.1.8
  • 2.1.10
  • 2.1.14

• Assignment #11, due Wednesday 4 October: From EC Section 2.2, pages 107-110:
  • 2.2.7 parts b, d, f only
  • 2.2.10
  • 2.2.13 parts b, c only
  • 2.2.14 part b only
  • 2.2.17

• Assignment #12, due Friday 6 October: From EC Section 2.2, pages 107-110:
  • 2.2.15
  • 2.2.19
  • 2.2.21
  • 2.2.25
  • 2.2.29

• Assignment #13, due Tuesday 10 October: From EC Section 2.3, pages 121-122:
  • 2.3.2
  • 2.3.3 parts b, e, f only
  • 2.3.4
  • 2.3.5
  • 2.3.7

• Assignment #14, due Wednesday 11 October: From EC Section 2.3, pages 121-122:
  • 2.3.8 parts b, d, only
  • 2.3.9 part b only
  • 2.3.12
  • 2.3.13

• Assignment #15, due Friday 13 October: From EC Section 2.4, pages 130-132:
  • 2.4.3 parts b, c only
  • 2.4.8 parts b, c only
  • 2.4.13
  • 2.4.14 parts b, c, only
  • 2.4.16

• Assignment #16, due Monday 16 October: This assignment will be specified in the notes for today's lecture on program correctness. This will be ready by the end of Friday 13 October.

• No homework due Wednesday 18 October, due to midterm.

• Assignment #17, due Friday 20 October: From EC Sections 3.1, 3.2, 3.3:
  • 3.1.18
  • 3.2.11
  • 3.2.20
  • 3.3.3 (There is an error in part (d). The two given sets are not equal -- prove instead that the first is a subset of the second.)
  • 3.3.10

• Assignment #18: due Monday 23 October: From EC Sections 4.1 (pages 264-268) and 4.2 (pages 277-283)
  • 4.1.9
  • 4.1.18
  • 4.1.28
  • 4.2.9
  • 4.2.18

• Assignment #19: due Wednesday 25 October: From EC Section 4.3 (pages 298-301)
  • 4.3.4
  • 4.3.6
  • 4.3.10 parts b, d, f only
  • 4.3.12
  • 4.3.13

• Assignment #20: due Friday 27 October: From EC Sections 4.4 and 4.5
  • 4.4.6
  • 4.4.10
  • 4.5.7
  • 4.5.8 parts b, d, e only
  • 4.5.17

• Assignment #21: due Monday 30 October: From EC Section 5.1 (pages 381-385)
  • 5.1.2
  • 5.1.6
  • 5.1.10
  • 5.1.15
  • 5.1.21

• Assignment #22: due Wednesday 1 November: From EC Section 5.2 (pages 395-397)
  • 5.2.4
  • 5.2.10
  • 5.2.15
  • 5.2.21
  • 5.2.35

• Assignment #23: due Friday 3 November: From EC Section 5.3 (pages 406-408)
  • 5.3.4
  • 5.3.8 (changed 5 pm Wed 1 Nov)
  • 5.3.18
  • 5.3.20
  • 5.3.26

• Assignment #24, due Monday 6 November: From EC Section 5.4, pages 416-418
  • 5.4.4
  • 5.4.6
  • 5.4.11
  • 5.4.20
  • 5.4.28

• Assignment #25, due Monday 13 November: From EC Section 6.1 and 6.2, pages 446-448 and 458-460
  • 6.1.6
  • 6.1.10
  • 6.1.13
  • 6.2.6
  • 6.2.18

• Assignment #26, due Wednesday 15 November: From EC Section 6.3, pages 464-5
  • 6.3.6
  • 6.3.12
  • 6.3.13
  • 6.3.15
  • 6.3.21

• Assignment #27, due Friday 17 November: From EC Section 6.4, pages 474-475
  • 6.4.4
  • 6.4.7
  • 6.4.10
  • 6.4.15
  • 6.4.22 (find a set of at least 50 series -- the baseball World Series is probably easiest to get)

• Assignment #28, due Wednesday 29 November: From EC Section 6.6, pages 500-501, plus extra.

  Let the matrices A and B be:

  			    A = 1 1      B = 1 0
  			        0 1          1 1
  			    

  • Prove by induction that for any positive integer n, Aⁿ and Bⁿ are given by

    				A^n = 1 n      B^n = 1 0
    				      0 1            n 1
    				
    			    

  • Compute (AB)⁷ and (BA)⁷.
  • Recall that the Fibonacci sequence is given by F(1) = F(2) = 1 and F(n+1) = F(n) + F(n-1). Prove by induction for every positive integer n that (AB)ⁿ =

    				    F(2n+1)  F(2n)
    				    F(2n)    F(2n-1)
    				    

  • Problem 6.6.20
  • Problem 6.6.22

• Assignment #29, due Friday 1 December: From EC Section 6.6, pages 500-501
  • 6.6.2
  • 6.6.8 -- record the results of your ten trials
  • 6.6.12
  • 6.6.31
  • 6.6.32

• Assignment #30, due Wednesday 6 December: From EC Section 7.4, pages 564-567
  • 7.4.2
  • 7.4.9
  • 7.4.14
  • 7.4.20
  • 7.4.29

• Assignment #31, due Friday 8 December: From EC Section 7.1, pages 515-519
  • 7.1.3
  • 7.1.6
  • 7.1.8
  • 7.1.10
  • 7.1.22

• Assignment #32, due Monday 11 December: From EC Section 7.2, pages 529-533
  • 7.2.6
  • 7.2.8
  • 7.2.13
  • 7.2.15
  • 7.2.22

Last modified 8 December 2017