handout #10

CSE390D—Introduction to Discrete Math
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. 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)  
    C ∩ (A ∪ B)  
    C ∩ B  
    B ∪ C  

  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    
    f(x) = x2 B → C    
    f(x) = x2 B → B    
    f(x) = x2 C → B    

  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.

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

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

    (5 points) Translate the following predicate into English:

    ∃x (Criticize(x, x) ∧ ∀y (Criticize(y, y) → x = y))

  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. (4 points) Phillip cannot legally buy alcohol.

    (4 points) Susan can legally buy alcohol.

    (4 points) Martha is not 21 or older.

    (4 points) John can vote.

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

Stuart Reges
Last modified: Fri Oct 25 08:41:30 PDT 2024