CMSC 150 Fall 2015 Section 7981 - Final Exam due December 13
As usual, N will denote the set of positive integers, Z the set of all integers, Q the set of all rational
numbers, and R the set of all real numbers. After any problem statement, feel free to hit the Enter key as
often as you need to make space for your answer.
Note: In Problem 1, I have written the names of some symbols along with the symbols, because some
browsers and editors do not render these symbols correctly. In the event of a conflict between the symbol
and the name, rely on the name not the symbol.
Problem 1: Let A = {3, 5, 7, 9, 11}, B={2, 7}, C = {1, 3}. Compute the following sets:
A [intersection symbol] B =
A [union symbol] B =
A – B =
B – C =
A [symmetric difference symbol] C =
A × C =
Problem 2: In calculus and other branches of analysis, the notation (a, b) represents the set
{x Î R | a < x < b }. Consider all sets of the form (1, b) where b >= 0.
a. What is the union of all of these sets?
b. What is the intersection of all of these sets?
Problem 3: How many non-proper subsets does the set {2, 3, 4, 5, 6} have?
Problem 4: Let X be the set of all persons born on or after January 1, 1800. Define a relation on X as
follows: a is related to b if and only if a and b have a common ancestor in X. Is this relation reflexive?
Symmetric? Transitive? Justify you answers in each case. Feel free to apply real-world knowledge.
(“Ancestor” includes parent, grandparent, etc.)
Reflexive:
Symmetric:
Transitive:
Problem 5: Below is a diagram of a relation. See attachment for diagram.
(a) Is this an equivalence relation? If not, explain why not, stating which property or properties in
the definition of an equivalence relation is not satisfied.
(b) Is this a partial order relation? If not, explain why not, stating which property or properties in
the definition of a partial order relation is not satisfied.
(c) Is this a total order relation? If not, explain why not, stating which property or properties in the
definition of a total order relation is not satisfied.
(You may want to look up definitions in the readings or glossary.) SEE ATTACHMENT FOR PICTURE
Problem 6: Let X = {x Î R | x >= – 1 } and define a function g: X R by g(x) = x3 + 3. What is the
image of g?
Problem 7: Let g be as defined in Problem 6, and define h: R R by h(x) = 3x – 5.
(a) What is the domain of (h o g) ?
(b) What is the codomain of (h o g) ?
(c) Find (h o g) ( x) . .
Problem 8: How many different license plates are possible if each plate has two letters followed by four
digits, and no digit can be repeated?
Problem 9: A soccer team has 18 members, of which two are goalies. The coach chooses eleven
members to start the game, including a goalie. In how many ways can this be done? (Note: a player who
is a goalie can also play any other position.)
Problem 10: How many 8-bit bytes contain an odd number of zeros? Explain how you got (or could get)
your answer without listing all 256 8-bit bytes and counting.
Problem 11. Construct the truth table for (p\/ r)--> (r && s). Show all work.
Problem 12: Restate each of the following sentences in if…then form:
(a) A sufficient condition for collapse of the pressure vessel is submergence to 2500 feet.
(b) Adequate rain is necessary for a good crop.
For each of problems 13 and 14, (a) write the given sentence in a totally symbolic form, (b) using as many negation rules as can possibly be applied, write the symbolic form of the negation of the given sentence, and (c) write the negation in succinct English. (Do not be concerned about whether the statements are true or false; that would be a distraction.)
Problem 13: Every real number has a cube root.
Problem 14: If the sun is shining, then there will be at least one person swimming in the old mill pond.
Problem 14: A certain graph has 7 vertices. The degrees of the vertices are 1, 3, 4, 7, 4, 6 and 0. How many edges does this graph have?
Problem 15: Draw a directed graph having the following adjacency matrix:
A B C D
A 1 0 0 1
B 1 0 0 1
C 0 1 1 0
D 0 0 0 1
Problem 16: A certain tree has 28 edges. How many vertices does it have?