handout #11

CSE390D—Introduction to Discrete Math
Key to Sample Midterm

  1. Prime Factors (4 points). Indicate below the prime factorization of 490 and 900 along with the values of gcd(490, 900) and lcm(490, 900). You may express the gcd and lcm as a product of prime factors.

    2. 490 = 2 ⋅ 5 ⋅ 72
    900 = 2 2 ⋅ 32 ⋅ 52
    gcd(490, 900) = 2 ⋅ 5
    lcm(490, 900) = 22 ⋅ 32 ⋅ 52 ⋅ 72 ⋅

  2. Sets (8 points). Consider sets drawn from the universe of integers between 1 and 15 inclusive. Given the following sets:
    A = {1, 2, 3, 5, 8, 13}
    B = {1, 2, 3, 4, 5, 6, 7}
    C = {5, 7, 9, 11, 13, 15}
    Fill in the table below indicating the set that the expression evaluates to.

    Expression Value
    (A ∩ B) ∪ (A ∩ C) {1, 2, 3, 5, 13}
    C ∩ (A ∪ B) {5, 7, 13}
    C ∩ B {9, 11, 13, 15}
    B ∪ C {8, 10, 12, 14}

  3. Functions (8 points). Given the following sets:
    A = {x | x ∈ R ∧ x ≥ 1}
    B = {x | x ∈ R ∧ 0 ≤ x ≤ 1}
    C = {x | x ∈ R ∧ -1 ≤ x ≤ 1}
    Fill in the table below indicating "yes" or "no" whether the given function is onto and one-to-one for the given mapping.

    Function Mapping Onto? One-to-One?
    f(x) = 1/x A → B no yes
    f(x) = x2 B → C no yes
    f(x) = x2 B → B yes yes
    f(x) = x2 C → B yes no

  4. Sentence translation (20 points). Assume that the following predicates are defined where the the domain is the set of all people:

    Rude(x) means that x is a rude person
    Selfish(x) means that x is a selfish person
    Criticize(x, y) means that x criticizes y

    For the first three problems below, translate the given sentence into predicate logic using quantifiers when appropriate. No negation should appear in front of a quantifier or in front of a parenthesized expression.

    (5 points) Everyone criticizes each of the selfish people.

    ∀x (Selfish(x) → ∀y Criticize(y, x))

    (5 points) Some rude people are criticized by all of the selfish people.

    ∃x (Rude(x) ∧ ∀y (Selfish(y) → Criticize(y, x)))

    (5 points) Only people who are either rude or selfish are criticized by other people.

    ∀x (∃y Criticize(y, x) → (Rude(x) ∨ Selfish(x)))
    ∀x ∀y(Criticize(y, x) → (Rude(x) ∨ Selfish(x)))

    (5 points) Translate the following predicate into English:

    ∃x (Criticize(x, x) ∧ ∀y (Criticize(y, y) → x = y))
    There is exactly one person who criticizes himself.

  5. Mathematical reasoning (20 points). Assume that the following statements are true given that Martha, John, Susan, and Phillip are people and that each person has a single numeric age:

    1. A person has to be 21 or older to legally buy alcohol.

    2. Martha cannot legally buy alcohol.

    3. John can legally buy alcohol.

    4. Anyone who can legally buy alcohol can get a driver's license.

    5. Susan is 21 or older.

    6. If a person can't vote, then the person is not 21 or older.

    7. Phillip cannot get a driver's license.

    For each statement below, indicate whether or not the statement can be concluded from the facts above. If the statement can be concluded, list all of the statements above that are necessary to draw the conclusion (use the statement numbers to refer to them). If the statement cannot be concluded, just state that fact.

    (4 points) John is 21 or older.

    6. yes by 3, 1

    (4 points) Phillip cannot legally buy alcohol.

    yes by 7, 4

    (4 points) Susan can legally buy alcohol.

    no (cannot be concluded)

    (4 points) Martha is not 21 or older.

    no (cannot be concluded)

    (4 points) John can vote.

    yes by 3, 1, 6

  1. Proofs (10 points). Prove that for integers n and m, the difference between n2 and m2 is even whenever the difference between n and m is even. In solving this problem, you are limited to the Rosen textbook definition of odd and even (not to any properties of odds and evens proven in the book). Be sure to indicate the proof technique you are using to solve this problem.

    2. We can use a direct proof. Assume that the difference between n and m is even. Then we know that:

    n - m = 2k for some integer k

    We now show that n2 - m2 is even:

    n2 - m2 = (n - m)(n + m) = 2k(n + m)

    Because n2 - m2 can be expressed as 2 times an integer, it must be even. This completes the proof.

  2. Proofs (10 points). Prove that for all integers n, either 4 divides n2 - 1 or n is even. Be sure to indicate the proof technique you are using to solve this problem.

    3. We can prove this using a proof by contradiction. Assume that the proposition is false. Then there is some integer n for which 4 does not divide n2 - 1 and n is odd. By the definition of odd numbers, we know that:
    n = 2k + 1 for some integer k

    But then we have:

    n2 - 1 = (2k + 1)2 - 1
    = 4k2 + 4k + 1 - 1
    = 4k2 + 4k
    = 4(k2 + k)

    In other words, 4 divides n2 - 1, which contradicts our original assumption. Thus, we have proven that for all integers n, either 4 divides n2 - 1 or n is even.

  3. Induction (20 points). Prove using mathematical induction that:
    2/5 + 2/52 + 2/53 ... + 2/5n = 1/2 - 1/(2 ⋅ 5n)
    Provide a formal definition for the overall proposition being proved (P(n)) using summation notation and indicate the domain for n. Then provide an inductive proof, clearly indicating where you are applying the inductive hypothesis.

    4. Let P(n) be the statement that:
    n
    ∑
    i = 1    		 2/5i = 1/2 - 1/(2 ⋅ 5n)
    We can prove that P(n) holds for n ∈ Z+ using induction.

    We first prove P(1):

    2/5 = 3/10 = (5 - 2)/10 = 5/10 - 2/10 = 1/2 - 1/(2 ⋅ 51)
    Then we assume P(k) for some k ∈ Z+:
    k
    ∑
    i = 1    		 2/5i = 1/2 - 1/(2 ⋅ 5k)
    And we prove P(k + 1):
    k + 1
    ∑
    i = 1    		 2/5i = 1/2 - 1/(2 ⋅ 5k + 1)
    k + 1
    ∑
    i = 1    		 2/5i =
    k
    ∑
    i = 1    		 2/5i + 2/5k + 1=
    (by inductive hypothesis)
    = 1/2 - 1/(2 ⋅ 5k) + 2/5k + 1
    = 1/2 - 5/(2 ⋅ 5k + 1) + 4/(2 ⋅ 5k + 1)
    = 1/2 - (5 - 4)/(2 ⋅ 5k + 1)
    = 1/2 - 1/(2 ⋅ 5k + 1)
    Therefore P(n) holds for all n ∈ Z+.
Stuart Reges
Last modified: Fri Oct 25 08:41:38 PDT 2024