IST 230 Summer

IST 230 Summer, 2016 Final Exam

Questions 1-11 are worth 8 points each.

Question 12 is worth 12 points.

1. State in English the inverseof the contrapositive of “If it is raining, then my lawn is wet.”

2. Let S be a set, R be a binary relation on S, and x an element of S. Translate the following into a logical expression with the same meaning:

the negation of the statement “For all x in S, xRx.”

3. Let the function f from the positive integers to the positive integers be defined by f(x) = x*x (where the asterisk * denotes ordinary integer multiplication). Explain why this function f is or is not an onto function.

4. Let sets A and B be defined as follows: A = {a1} and B = {b1, b2}. List as separate sets of ordered pairs all the one-to-one functions from A to B, or explain why there are no such functions.

5. Let the set A be defined as A = {a, b, c, d}, and let the relations R and S on the set A be defined as

R = {(d, a), (a, b), (b, c), (b, d) }, and S = {(a, a), (b, d), (d, c)}.

Explain, using the definition of composition of relations on a set (see the second paragraph in Section 5.4 of the zyBook) why the ordered pair (b, d) is or is not an element of the composition of relations R and S (denoted S o R).

6. What is the value of the variable count after all the loops in the following pseudocode execute?

count:=0

For i= 1 to 2

For j=1 to 2

count:=2i[(j*count)+j]

End-for

End-for

8. Explain why a multiplicative inverse mod 7 of 13 does or does not exist. If one does exist, give a value for it and use appropriate calculations to show that it is a multiplicative inverse of 13 mod 7.

9. A husband and wife and their two children line up for a photo. How many ways are there for these four people to line up so that the husband and wife are *not* next to each other? Be sure to show your work.

10. Suppose you randomly draw two cards from a standard deck without replacement. What is the probability that neither card is the ace of spades?

11. Let V = {a, b, c, d, e} be a vertex set and E = { {a,c}, {b,d}, {c,d}, {d,e}, {e,a}} be the edge set corresponding to V. Explain why the pair (V, E) is or is not a tree.

12. Let vertex sets V1 and V2 be defined by V1= {1, 2, 3} and V2 = {a, b, c}. Let E1 = { { 1, 2}, {2, 3} }, and let E2 = { {a, b}, {b, c} } be the edge sets corresponding to the vertex sets V1 and V2, respectively. Write, as a set of ordered pairs, a function f that is a bijection from V1 to V2, satisfying the following condition: if x and y are elements in V1 such that {x,y} is in E1, then f(x) and f(y) are elements in V2 such that {f(x),f(y)} is in E2, and show that your function f satisfies this condition.

Note: you do not need to show that your function f is a bijection (though it must be, or you won’t get any credit), but you DO need to show that it satisfies the condition “if x and y are elements in V1 such that {x,y} is in E1, then f(x) and f(y) are elements in V2 such that {f(x),f(y)} is in E2.”