DT6248 Discrete Maths Assessment Review 2015
Solutions
1)Consider the following sets:
Which of them are equal to A = ?
Answers: {y,w,z}, {y,z,w}, {w,y,z}
2)Define, with examples, the universal setU.
Answers: In every problem in set theory, the members of all sets belong to some fixed large set called the “Universal Set”. For example, in plane geometry, the universal set consists of all the points in the plane.
3)Prove that if A is a subset of the null set , then A = .
Answers: The null set is a subset of every set. In particular, . If , then.
4)Consider the following sets A = {1,2,3,4}, B = {2,4,6,8}, C = {3,4,5,6} and Universal set U = {1,2,3,…,9},
Find
Answers:
5)Shade the set
Answers:
6)Suppose . Show that .
Answers: Since we have and . Hence,
and
7) E = [{1,2,3},{2,3},{a,b}] Find the power set,of E.
Answers:
8) Determine whether each function is one-to-one. The domain of each function is the set of all real numbers. If the function is not one-to-one, prove it. Determine whether the function is onto the set of all real numbers. If the function is not onto, prove it.
a)
b)
Answers:
a)We can see from the graph of that the function is not one-to-one , eg. f(0) = f(1).
To show mathematically, we have to show that for all real numbers n1 and n2, if f(n1) = f(n2), then n1 = n2. Let’s assume that f(n1) = f(n2).
If , then .
This result is true, eg. . f(0) = f(1) and n1= 0, n2 = 1, n1 + n2 = 1. Also,
f(2) = f(-1) and n1= 2, n2 = -1, n1 + n2 = 1, etc. Therefore, is not one-to-one.
Again, from the graph we can see that the function is not onto.
We can solve for x when y = 0. does not give a real value. Therefore, the function is not onto since at least one value of y does not give a real value for x.
b)To show mathematically, we have to show that for all real numbers n1 and n2, if f(n1) = f(n2), then n1 = n2. Let’s assume that f(n1) = f(n2).
Therefore, is one-to-one.
To show if the function is onto, solve for x. . If y < 2,
then no real value for x exists. Therefore, the function is not onto.
9) Find the inverse of the following functions:
a)
b)
Answers: a)
b)
10)Decompose into a simpler function.
Answers:
11) Let f be the function from X = {0,1,2,3,4} to X defined by
Write f as a set of ordered pairs and draw the arrow
diagram of f. Is f one-to-one? Is f onto?
Answers: {(0,0),(1,4),(2,3),(3,2),(4,1)}
00
1 1
2 2
3 3
4 4
f is one-to-one and onto.
12) Let R be the relation on A = {1,2,3,4} defined by “x is less than y”. Write R as a set of ordered pairs.
Answers: R = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}
13)Find the inverse of R in problem 12.
Answers: R-1 = {(2,1),(3,1),(4,1),(3,2),(4,2),(4,3)}
14)Let R be the relation on the set N of positive integers defined by the equation
Find the domain of R and the equation for R-1.
Answers: , x cannot exceed 9 since y is positive, also x cannot
Be odd since is even. Dom(R) = {2,4,6,8}.
R = {(2,48), (4,42), (6,32), (8,18)}
R-1 = {( 48,2), (42,4), (32,6), (18,8)}
15) Draw the directed graph of the relation T on X = {1,2,3,4} defined by
T = {(1,1), (2,2), (2,3),(3,2),(4,2),(4,4)}.
Answers:
11
22
33
44
16)Let A = {1,2,3,4}, B = {a,b,c,d}, and C = {x,y,z}. Consider the relations R from A to B and S from B to C defined by
R = {(1,a),(2,d),(3,a),(3,b),(3,d)}, S = {(b,x), (b,z), (c,y), (d,z)}
Find the composition .
Answers: = {(2,z), (3,z), (3,x)}
17)Determine when relation on a set A is (a) not reflexive (b) not symmetric (c) not transitive
Answers:
18)(i) Let R, S, T be the relation on A = {1,2,3} defined by
R = {(1,1),(2,2),(3,3)}, S = {(1,2),(2,1),(3,3)}, T = {(1,2),(2,3),(1,3)}
Determine which relations are (a) reflexive. (b) symmetric (c) transitive
(ii) Determine if is (a) reflexive. (b) symmetric (c) transitive
Answers:
(i)a) R b) R and S c) R and T and S
(ii)a) not reflexive b) symmetric c) not transitive
19) Find all partitions of S = {1,2,3}.
Answers:
20)Is a partition on the set R of real numbers.
Answers: no, belongs to both
21)Let R be the relation on the set N of positive integers defined by R = {(a,b):a + b is even}. Is R an equivalence relation? Why or why not?
Answers: yes, for any is even and if is even then is even
(reflexive and symmetric). If and , (transitive)
22)Show that the relation of set inclusion is not an equivalence relation.
Answers: is reflexive and transitive, but does not imply
23) Let P be “He is tall” and let q be “he is handsome”. Write each of the following statements in symbolic form using p and q:
a)He is tall and handsome
b)He is tall but not handsome
c)It is false that he is short or handsome
d)He is neither tall nor handsome
Answers: a) b) c) d)
24) Find the truth table for (a) (b) .
Answers:
25)Prove the distributive law: using truth tables.
Answers:
26)Express in terms of and by showing
Answers: Use DeMorgan’s Laws to obtain:
27)Verify that is a tautology.
Answers:
28)Determine the contrapositive of each statement (a) If John is a poet, then he is poor. (b) Only if Marc studies will he pass the test.
Answers: a) If John is not poor, then he is not a poet.
b) If Marc does not study, then he will not pass the test.
29)Simplify (a) (b)
Answers: a)
b)
30)Let A = {1,2,3,4} be the universal set. Determine the truth value of each statement:
a)
b)
c)
Answers: a) False b) True c) False
31)Convert 45598410 into
a)Base 2
b)Base 16
Answers: a) 01101111010100110000 b) 6F530
32)Convert FA6547EB16 into
a)Base 10
b)Base 2
Answers: a) 420094154710 b) 11111010011001010100011111101011
33) Find
a)DA654B16 + FE543A16
b)1101100112 + 1001001112
Answers: a) 1D8B985 b) 10110110102
34)Find a recurrence relation and initial conditions that generate a sequence beginning with the following terms:
5, 8, 11, 14.
Answer:
35)Find the closed formulas for each of the following sequence.
a)7, 13, 25, 43, 67,…
b)5, 15, 45, 135, 405,…
c)5, 9, 21, 57,…
Answer: a) b) c)
36)Find a closed formula for the following recursive relation.
Answer:
37)A bacteria culture grows at a rate of per day.
a)Today the culture has 1,000,000 bacteria. How many days will it take for this number to double?
b)Suppose each day you remove a sample of 50,000 bacteria for testing. How many days will it take for the original 1,000,000 bacteria to double.
Answer:
a)
b)
38)Assume a person invests 5000 euros at 8% interest compounded annually.
= amount in account at end of n years.
a)Find the recurrence relation.
b)Find a closed formula for .
c)How long until the initial investment is tripled.
Answer:
a)
b)
c)
39)For the following recurrence relation, find a closed formula
40)For the following recurrence relation, find a closed formula
41)The following statement is false. Provide a counter example.
Answer:
42)Find solutions for x in the following equation.
Answer:
is divisible by 17.
so,
start with
43)Solve
Answer:
44)Prove that
Answer:
Page 1 of 10