COT3100/7094X Fall '99:
Exam 1 Sample Problems

Sample problems for Exam #1, covering chapter 1, all sections from §1.1 through §1.8. A real exam might contain about 8-10 problems similar to these.

The solutions can be found on a separate page.

  1. What is the truth value of (p r) (p r) when both p and r are false?

  2. Write (in English) the converse and contrapositive of the statement, ``I will go to Disneyworld only if the hurricane doesn't hit Florida.'' Also, indicate which of the two answers is logically equivalent to the original statement.

  3. Show that the two statements (p r) and ¬(r ¬p) are equivalent to each other, by both
    (a) using a truth table, and
    (b) using logical equivalences.

  4. Does an associative law hold for the biconditional operator? Answer by proving or disproving whether the two propositions ((p r) s) and (p (r s)) are equivalent to each other.

  5. Suppose that Q(x) is the statement ``x2 + 1 = x - 2.'' What are the truth values of x Q(x) and x Q(x), in a universe of discourse consisting of the real numbers?

  6. Let P(n,m) be the statement ``n is greater than or equal to m,'' where the universe of discourse is the set of non-negative integers. What are the truth values of the two statements m n P(n,m) and m n (P(n,m) P(m,n))?

  7. Let A = {0, 1, 2, 3, 4}, B = {0, 2, 4, 6, 8, 10}, and C = {2, 3, 5, 7, 11}. Find each of the following sets:
    (a) A C
    (b) A B C
    (c) A B
    (d) A B C
    (e) B - C
    (f) B - (A - C)

  8. Prove or disprove that if A, B, and C are sets then (A B) - C = (A - C) (B - C).

  9. Let A, B, and C be sets. Prove or disprove that A - (B C) = (A - B) (A - C).

  10. Let f(n) = 3n - 2. Can f be a one-to-one function from the set of integers to the set of reals? Can f be an onto function from the set of integers to the set of integers? Explain the reasons behind your answers.

  11. Suppose that f is the function from the set {1, 2, 3, 4} to itself with f(1) = 3, f(2) = 4, f(3) = 1, f(4) = 2. Find the inverse of f.

  12. Consider the function f(n) = n/3 from to . Is this function one-to-one? Is this function onto? Justify your answers.

  13. Show that the set of irrational numbers (that is, reals that are not rational) is uncountable.

  14. Find the values of
    5
    8
    j=3
    		 and
    3
    -j + 2
    j = -1
    		 .

  15. Find the values of
    300
    2x + 1
    x=1
    		 and
    50
    (-1)j
    j = 1
    		 .

  16. Let f(n) = 2n2 - 3n + 7. Show that f(n) is O(n2). Be sure to specify the values of the constants c and k from the definition of O().

  17. Show that
    n
    j2 + 1
    j=1
    		is O(n3).

  18. Show that the function f(x) = x1/2 log (3 x4) + log(2x) is O(x log x).