INFO 150: A Mathematical Foundation for Informatics

Solutions to Second Midterm Exam

David Mix Barrington

5 November 2017

Directions:

Answer the problems on the exam pages.
There are four problems, each with multiple parts, for 100 total points. Actual scale was A = 81, B = 67.5, C = 54, D = 40.5.
If you need extra space use the back of a page.
No books, notes, calculators, or collaboration.
Numerical answers may be given as expressions using addition, subtraction, multiplication, division, exponentiation, and the factorial function. But expressions such as P(n, k) or C(n, k) must be rewritten to use only these operations.

Question text is in black, solutions in blue.

  Q1: 15 points
  Q2: 30 points
  Q3: 30 points
  Q4: 25 points
Total: 100 points

Question 1 (15): Briefly identify the following terms or concepts (3 points each):

(a) the power set of a set
The power set P(S) of a set S is the set of all subsets of S, that is, {T: T ⊆ S}. If S has n elements, then P(S) has 2ⁿ elements.
(b) when a partial order is a total order
A partial order R is a total order if ∀x: ∀y: R(x, y) ∨ R(y, x), or equivalently, if there are no incomparable elements, that is, if ¬∃x: ¬R(x, y) ∧ ¬R(y, x).
(c) the identity function from a set to itself
The identity function i from A to A is the function that has i(a) = a for every element a of A.
(d) an equivalence relation (you may use either of the two definitions given in the text and lecture, without proving that they are the same)
Definition 1: R ⊆ A × A is an equivalence relation if there exists a partition of A such that for every two elements x and y of A, R(x, y) is true if and only if x and y are in the same set of the partition.
Definition 2: R ⊆ A × A is an equivalence relation if and only if it is reflexive (∀x: R(x, x)), symmetric (∀x:∀y: R(x, y) → R(y, x)) and transitive (∀x:∀y:∀z: (R(x, y) ∧ R(y, z)) → R(x, z)).
(e) the Sum Rule With Overlap for counting a union of two finite sets A and B
In symbols, |A ∪ B| = |A| + |B| - |A ∩ B|. In words, the size of the union is the sum of the sizes of the sets, minus the size of the intersection. (You count both sets and then subtract the number of elements that are counted twice.)

Question 2 (25): We have a set U = {c, d, m, s, t, w} of six dogs: Cardie, Duncan, Mia, Scout, Toby, and Whistle. We have two subsets of U, the female dogs F = {c, n, s} and the neighborhood dogs N = {c, d, m, w}. Recall that F' and N' are the complements of F and N respectively. In the first four parts of this question we are going to award prizes for Agility (a), Beauty (b), and Obedience (o), each to one of the dogs. (Five points each part.)

(a) In how many ways can we award the three prizes to three different dogs? (So we are counting situations like "Duncan gets a, Cardie gets b, and Scout gets o".)
Six choices for who gets a, five for who gets b, and four for who gets o, for P(6, 3) = 120 total choices.
(b) In how many ways can we choose which three dogs get prizes, if the prizes go to three different dogs? (So we are counting situations like "Mia, Toby, and Whistle get prizes".)
We want a subset of size three taken from a six-element set. There are C(6, 3) = 6×5×4 / 1×2×3 = 20 such subsets.
(c) In how many ways can we award the three prizes each to a dog, if it is possible that one dog gets more than one prize? (So we are counting situations like "Mia gets both b and o, and Whistle gets a".)
Six choices for a, six for b, and six for o, for 6³ = 216 total choices.
(d) In how many ways can we decide how many prizes each dog gets, if the three prizes do not necessarily go to three different dogs? (So we are counting situations like "Duncan gets two prizes and Toby gets one".)
By the "stars and bars" argument, we are looking for arrangements of the three prizes and the five "barriers" between the six dogs. These can be represented by binary strings with three 0's and five 1's, of which there are C(8, 3) = C(8, 5) = 8×7×6 / 1×2×3 = 56.
(e) In how many ways can we partition U into three sets, each containing one dog in F and one in F'?
Such a partition assigns exactly one distinct dog in F' to each dog in F, so it defines a bijection from F to F'. There are 3! = 6 of these.
(f) In how many ways can we partition U into two sets, each containing two dogs in N and one in N'?
One we pick one set, the other is determined. To pick such a set, we must decide which two of the four dogs in N to include (C(4, 2) = 6 choices) and which one of the two dogs in N' to include (C(2, 1) = 2). But this counts each partition exactly twice, so we must divide by two to get the final answer of six. Equivalently, we know that Scout is in one of the sets and Toby is in the other, so we can just decide which two of the four dogs in N go with Scout, in C(4, 2) = 6 ways.

Question 3 (30): Here are ten true/false questions, with no explanation needed or wanted and no penalty for guessing. The first five questions refer to the sets and scenarion of Question 2. (Three points each.)

(a) There exists an injection (a one-to-one function) from U to F.
FALSE. Since U has strictly more elements than F, an injection is impossible.
(b) Not all functions from U to N are surjections (onto functions).
TRUE. For example, there is a function that takes all six elements of U to Cardie, and this function is not onto since no element is mapped to Duncan.
(c) The answer to Question 2(e) is also the number of functions from F to F'.
FALSE. It is the number of bijections, not the number of all functions.
(d) The answer to Question 2(d) is also the number of binary strings with three 0's and three 1's.
FALSE. As we saw above, it is the number fo binary strings with three 0's and five 1's.
(e) The answer to Question 2(c) is also the number of binary strings with three 0's and five 1's. And C(8, 3) = 56 ≠ C(6, 3) = 20.
FALSE. To represent a three-element subset of a six-element set by a binary string, we use three 0's and three 1's. Ana again, C(8, 3) ≠ C(6, 3).
(f) Let A = {a}. Then every relation R ⊆ A × A is both antisymmetric and transitive.
TRUE. The rule for antisymmetry is true trivially because its conclusion is "x = y", which must be true because both x and y have to be equal to a. The rule for transitivity reduces to (R(a, a) ∧ R(a, a)) → R(a, a), which is a tautology.
(g) Let A = {a}. If R ⊆ A × A is reflexive, then it is both an equivalence relation and a partial order.
TRUE. Reflexivity means that R(a, a) is true, and this is the only bit needed to define the relation. Part (f) proves that the resulting relation is a partial order. The only other property needed is symmetry, which also reduces to (R(a, a) ∧ R(a, a)) → R(a, a) which is a tautology.
(h) Let X, Y, and Z be any three finite sets. Recall that |S| denotes the number of elements in any set S. Then |X ∪ Y ∪ Z| = |X| + |Y ∪ Z| - |X ∩ (Y ∪ Z)|.
TRUE. This is an application of the Sum Rule With Overlap to the two sets X and Y ∪ Z.
(i) The number of possible passwords with one upper-case letter and seven lower-case letters (such as fruiTbat) is equal to the number of possible passwords with eight lower-case letters (such as fruitbat).
FALSE. In each case we choose eight times from a set of 26 letters, but in the first case we also choose which one of the eight letters is upper-case. So the number in the first case is 8× 26⁸ and the number in the second case is just 26⁸.
(j) Let W be a set of 2¹¹ = 2048 distinct words. Then the number of passwords I can make by taking a sequence of four words from W (with replacement, and with order mattering) is 2⁴⁴.
TRUE. We simply apply the Product Rule and the laws of exponents to multiply together four copies of 2¹¹, getting 2⁴⁴.

Question 4 (30): Here are two proofs involving sets and functions.

(a, 10) Let X, Y, and Z be any three sets. Prove that X ∪ (Y ∩ Z') is a subset of Y ∪ Z ∪ (X ∩ Z'). Remember that S' denotes t he complement of a set S.
We need to show ∀a: [a ∈ X ∪ (Y ∩ Z')] → [a ∈ Y ∪ Z ∪ (X ∩ Z')]. This translates to saying that the compound proposition
[(a ∈ X) ∨ ((a ∈ y) ∧ (a ∉ Z)] → [(a ∈ Y) ∨ (a ∈ Z) ∨ ((a ∈ X) ∧ (a ∉ Z))] is a tautology. We can prove this by a truth table:
```
      x  or (y and not z) --> y or z or (x and not z)
      0   0  0   0   1 0   1  0  0 0 0   0  0   1  0
      0   0  0   0   0 1   1  0  1 1 1   0  0   0  1
      0   1  1   1   1 0   1  1  1 0 1   0  0   1  0
      0   0  1   0   0 1   1  1  1 1 1   0  0   0  1
      1   1  0   0   1 0   1  0  0 0 1   1  1   1  0
      1   1  0   0   0 1   1  0  1 1 1   1  0   0  1
      1   1  1   1   1 0   1  1  1 1 1   1  1   1  0
      1   1  1   0   0 1   1  1  1 1 1   1  0   0  1
    
```
Alternatively, we observe that any element a must either (1) be in X or Y, making membership in the rght-hand set clear and making the implication true trivially, or (2) be in Y' ∩ Z', which makes the implication reduce to "(a ∈ X) → 0 ∨ 0 ∨ ((a ∈ X) ∧ 1)", which is also a tautology.
(b, 15) Define a function f from N to N as follows. Using Java notation for integer division, let f(n) = 10 * (n/10) + (9 - n%10). So, for example, f(42) = 10 * (42/10) + (9 = 42&10) = 10* 4 + (9 - 2) = 47. Prove that f is an invertible function. (You could prove that it is both one-to-one and onto, or prove that it has an inverse.)
This function f is its own inverse. By the Division Theorem, any natural n may be written as 10q + r, with 0 ≤ r < 10. We can compute that f(n) = 10q + (9 - r), making f(f(n) equal 10q + (9 - (9 - r)) = 10q + r = n.
To prove the onto and one-to-one properties directly, we can note that 10q + r is the image under f of the natural 10q + (9 - r), making f onto, and that if f(n) = f(n'), we must have 10q + (9 - r) = 10q' + (9 - r'), from which we can derive q = q' and r = r'. This forces n = n' and proves that f is one-to-one.

Last modified 25 November 2017