handout #13

CSE390D—Introduction to Discrete Math
Key to Midterm

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

    2. 350 = 2 ⋅ 52 ⋅ 7
    180 = 22 ⋅ 32 ⋅ 5
    gcd(350, 180) = 2 ⋅ 5
    lcm(350, 180) = 22 ⋅ 32 ⋅ 52 ⋅ 7

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

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

  3. Functions (8 points). Recall that:
    N = set of natural numbers (0, 1, ...)
    Z = set of integers
    Z+ = set of positive integers (1, 2, ...)
    R = set of reals
    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) = (x - 1)2 Z+ → N no yes
    f(x) = (x - 1)2 N → N no no
    f(x) = 2x - 1 Z → Z no yes
    f(x) = 2x - 1 R → R yes yes

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

    Animal(x) means that x is an animal
    Plant(x) means that x is a plant
    Furry(x) means that x is furry
    Eats(x, y) means that x eats 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) Some furry animal eats at least one furry plant.

    ∃x(Furry(x) ∧ Animal(x) ∧ ∃y(Eats(x, y) ∧ Furry(y) ∧ Plant(y)))

    (5 points) Any plant that eats an animal is furry.

    ∀x(Plant(x) ∧ ∃y(Eats(x, y) ∧ Animal(y)) → Furry(x))
    ∀x∀y(Plant(x) ∧ Eats(x, y) ∧ Animal(y) → Furry(x))

    (5 points) Some animal eats exactly one plant.

    ∃x (Animal(x) ∧ ∃y(Eats(x, y) ∧ Plant(y) ∧ ∀z(Eats(x, z) ∧ Plant(z) → z = y)))
    ∃x (Animal(x) ∧ ∃y(Eats(x, y) ∧ Plant(y) ∧ ∀z(Eats(x, z) → z = y ∨ ¬Plant(z))))
    (5 points) Translate the following predicate into English:
    ∀x (∃y (Furry(y) ∧ Animal(y) ∧ Eats(y, x)) → (¬Furry(x) ∧ Animal(x)))

    Everything that is eaten by a furry animal is a non-furry animal.
    Furry animals eat only non-furry animals.

  5. Mathematical reasoning (20 points). Assume that the following statements are true:

    1. Mary is a patient of Dr. Smith.

    2. Because Dr. Jones is Chief of Staff at the hospital, everyone admitted to the hospital is considered a patient of Dr. Jones.

    3. No patient of Dr. Smith has cancer.

    4. Chip is a patient of Dr. Jones.

    5. Only those admitted to the hospital are patients of Dr. Smith.

    6. Sam has cancer.

    7. Everyone admitted to the hospital is ill.

    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) Chip is ill.

    6. no (cannot be concluded)

    (4 points) Sam is not a patient of Dr. Smith.

    yes by 6, 3

    (4 points) Mary is a patient of Dr. Jones.

    yes by 1, 5, 2

    (4 points) Sam has been admitted to the hospital.

    no (cannot be concluded)

    (4 points) Mary is ill.

    yes by 1, 5, 7

  1. Proofs (10 points). Prove that the sum of the squares of two integers is odd only if the sum of the two integers is odd. In solving this problem, you are limited to the 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 need to prove that:
    a2 + b2 odd → a + b odd for integers a, b
    We can use an indirect proof. Assume that a + b is not odd, which means it is even. Then:
    a + b = 2k for some integer k
    (a + b)2 = (2k)2
    a2 + 2ab + b2 = 4k2
    a2 + b2 = 4k2 - 2ab
    a2 + b2 = 2(2k2 - ab)
    Thus, a2 + b2 is even, which means it is not odd. This completes the proof.
  2. Proofs (10 points). Prove that the square of an integer n is 4 more than a multiple of 8 if and only if the square of 5n is 4 more than a multiple of 8. Be sure to indicate the proof technique you are using to solve this problem.

    3. This is an equivalence proof that requires proving in both directions. First we need to prove that:
    n2 ≡ 4 (mod 8) → (5n)2 ≡ 4 (mod 8)
    We can prove this directly:
    n2 = 8k + 4 for some integer k
    (5n)2 = 25 n2
    = 25 (8k + 4)
    = 200k + 100
    = 8 (25k + 12) + 4
    qed
    Next we need to prove that:
    (5n)2 ≡ 4 (mod 8) → n2 ≡ 4 (mod 8)
    We can prove this directly:
    (5n)2 = 8k + 4 for some integer k
    25n2 = 8k + 4
    n2 = 8k + 4 - 24n2
    = 8(k - 3n2) + 4
    qed
  3. Induction (20 points). Prove using mathematical induction that:
    1 + 5 + 52 + 53 + ... + 5n = (5n + 1 - 1)/4
    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 = 0    		 5i = (5n + 1 - 1) / 4
    We can prove that P(n) holds for n ∈ N using induction.

    We first prove P(0):

    1 = 4 / 4 = (5 - 1) / 4 = (50 + 1 - 1) / 4
    Then we assume P(k) for some k ∈ N:
    k
    ∑
    i = 0    		 5i = (5k + 1 - 1) / 4
    And we prove P(k + 1):
    k + 1
    ∑
    i = 0    		 5i = (5k + 2 - 1) / 4
    k + 1
    ∑
    i = 0    		 5i =
    k
    ∑
    i = 0    		 5i + 5k + 1
    (by inductive hypothesis)
    = (5k + 1 - 1) / 4 + 5k + 1=
    = (5k + 1 - 1) / 4 + 4 ⋅ 5k + 1 / 4 =
    = (5k + 1 - 1 + 4 ⋅ 5k + 1) / 4 =
    = (5 ⋅ 5k + 1 - 1) / 4=
    = (5k + 2 - 1) / 4

    Therefore P(n) holds for all n ∈ N.
Stuart Reges
Last modified: Fri Nov 8 11:13:31 PST 2024