Female chauvinist pigs ariel levy pdf

University of Maryland University College

CMSC 150 – Introduction to Discrete Structures

Final Examination

1. (10 pts) For each the following groups of sets, determine whether they form a

partition for the set of integers. Explain your answer.

a. A1 = {n  Z : n > 0}

A2 = {n  Z : n < 0}

b. B1 = {n  Z : n = 2k, for some integer k}

B2 = {n  Z : n = 2k + 1, for some integer k}

B3 = {n  Z : n = 3k, for some integer k}

2. (10 pts) Define f: Z  Z by the rule f(x) = 6x + 1, for all integers x.

a. Is f onto?

b. Is f one-to-one?

c. Is it a one-to-one correspondence?

d. Find the range of f.

Explain each of your answers.

3. (10 pts) f: R R and g: R  R are defined by the rules:

f(x) = x2 + 2  x  R

g(y) = 2y + 3  y  R

Find f ◦ g and g◦ f.

4. (10 pts) Determine whether the following binary relations are reflexive,

symmetric, antisymmetric and transitive:

a. x R y  xy ≥ 0  x, y  R

b. x R y  x > y  x, y  R

c. x R y  |x| = |y|  x, y  R

For each of the above, indicate whether it is an equivalence relation or a partial

order. If it is a partial order, indicate whether it is a total order. If it is an

equivalence relation, describe its equivalence classes.

5. (10 pts) Determine whether the following pair of statements are logically

equivalent. Justify your answer using a truth table.

p  (q  r) and p  q  r

6. (10 pts) Prove or disprove the following statement:

 n ,m Z, If n is even and m is odd, then n + m is odd

Then write the negation of this statement and prove or disprove it.

7. (10 pts) Prove the following by induction:

 i=1

n 3i – 2 =

3𝑛2−𝑛

2

8. (10 pts) Use the permutation formula to calculate the number permutations of

the set {V, W, X, Y, Z} taken three at a time. Also list these permutations.

9. (10 pts) Translate the following English sentences into statements of predicate

calculus that contain double quantifiers and explain whether it is a true

statement.

a. Every rational number is the reciprocal of some other rational

number.

b. Some real number is bigger than all negative integers.

10. (10 pts) Consider the following graph:

In each case, answer the question and then write the rationale for your answer.

a. Is this graph connected?

b. Is this a simple graph?

c. Does this graph contain any cycles?

d. Does this graph contain an Euler cycle?

e. Is this graph a tree?