1 / 12100%
MODULE FIVE PROBLEM SET
This document is proprietary to Southern New Hampshire University. It and
the problems within may not be posted on any non-SNHU website.
Jacqueline Amoah
1
| |
Directions: Type your solutions into this document and be sure to show all steps
for arriving at your solution. Just giving a final number may not receive full credit.
P
ROBLEM
1
Indicate whether the two functions are equal. If the two functions are not equal,
then give an element of the domain on which the two functions have different values.
(a)
f
:
Z
Z
, where
f
(x)
=
x
2
.
g :
Z
Z
, where g(x) =
|
x
|
2
.
(b)
Both
iii
functions
i
are
i
a
i
positive
i
value.x
2
i
is
i
positive
i
and
i
x
i
2
i
can
i
never
i
be
i
negative.
f
:
Z
×
Z
Z
, where
f
(x, y)
=
|
x
+
y
|
.
g :
Z
×
Z
Z
, where g(x, y) =
|
x
|
+
|
y
|
.
These two functions are not equal.
Proof: Let x
=
-2 and y
=
2
f
(x, y)
=
|
2
2
|
=
0
g(x, y) =
|
2
|
+
|
2
2
|
= 2
as:
P
ROBLEM
2
The domain and target set of functions f and g is
R
. The functions are defined
f
(x)
=
2x
+
3
g(x) = 5x + 7
(a)
f g?
f (g(x)) = f (5x + 7)
=
2(5x
+
7)
+
3
=
10x
+
14
+
3
f
g
=
10x
+
17
(b)
g
f
?
g(f (x)) = g(2x + 3)
=
5(2x
+
3)
+
7
=
10x
+
15
+
7
g
f =
10x
+
22
(c) (f
g)
1
?
y
=
10x
+
17
x
=
10y
17
Thus
x = (f
g)
1(y)
=
10y
17
(f
g)
1(x)
=
10x
17
(d)
f
1
g
1
?
(f
1
g
1)(x)
=
1(g
1(x))
= f
1(5x 7) = 25x 7 3
= 25x
7
15 = 10x
22
(e) g
1
f
1
?
(g
1
f
1)(x)
=
g
1(f
1)(x))
= g
1(2x
3) = 52x
3
7
= 52x
3
14 = 10x
17
Are any of the above equal?
(f
g)
-1
= g
-1
f
-1
are
equal
P
ROBLEM
3
0
1
1
(a)
Give the matrix representation for the relation depicted in the arrow dia-
gram. Then, express the relation as a set of ordered pairs.
The arrow diagram below represents a relation.
Figure 1:
An arrow diagram shows three vertices, 1, 2, and 3. An arrow
from vertex 1 points to vertex 3, and another arrow from vertex 2 points to
vertex 3. Two self loops are formed, one at vertex 1 and another at vertex
2.
R = (1, 1); (1, 3); (2, 2); (2, 3)
1 0 1
0 0 0
(b)
Draw the arrow diagram for the relation.
The domain for the relation A is the set
{
2, 5, 7, 8, 11
}
. For x, y in the
domain, xAy if
|
x
y
|
is less than 2.
P
ROBLEM
4
For each relation, indicate whether the relation is:
Reflexive, anti-reflexive, or neither
Symmetric, anti-symmetric, or neither
Transitive or not transitive
Justify your answer.
(a)
The domain of the relation
L
is the set of all real numbers. For x, y
R
, xLy if x
<
y.
For
i
x
i
i
R
i
x
i
¡
i
x
i
will
i
be
i
false
i
because
i
(x,x)
i
do
i
not
i
belong
i
to
i
L
Because
i
of
i
this,
i
L
i
is
i
anti-reflective
(b)
The domain of the relation A is the set of all real numbers. xAy if
|
x
y
|
2
For
i
every
i
x
R
i
it
i
is
i
true
i
that
i
x
i
-
i
x
i
=
i
0 2
This
i
would
i
mean
i
that
i
(x,x)
i
does
i
belong
i
to
i
A,
i
also
i
meaning
i
that
i
A
i
is
i
reflective
i
and
i
not
i
anti-reflective.
(c)
The domain of the relation
Z
is the set of all real numbers. xZy if y
=
2x
For
i
every
i
x
i
i
R
i
x
i
=
i
2x
i
is
i
false
i
and
i
(x,x)
i
does
i
not
i
belong
i
to
i
Z.
This
i
means
i
that
i
Z
i
is
i
anti-reflective
P
ROBLEM
5
The number of watermelons in a truck are all weighed on a scale. The scale
rounds the weight of every watermelon to the nearest pound. The number of
pounds read off the scale for each watermelon is called its measured weight. The
domain for each of the following relations below is the set of watermelons on the
truck. For each relation, indicate whether the relation is:
Reflexive, anti-reflexive, or neither
Symmetric, anti-symmetric, or neither
Transitive or not transitive
Justify your answer.
(a)
Watermelon
i
x
i
is
i
related
i
to
i
watermelon
i
y
i
if
i
the
i
measured
i
weight
i
of
i
water-
i
melon
i
x
i
is
i
at
i
least
i
the
i
measured
i
weight
i
of
i
watermelon
i
y.
i
No
i
two
i
water-
i
melons
i
have
i
the
i
same
i
measured
i
weight.
This
i
relation
i
is
i
viewed
i
as
i
reflective
i
since
i
x
i
is
i
related
i
to
i
x
i
for
i
all
i
wa-
i
termelons(x).
If
i
x
i
has
i
a
i
weight
i
of
i
z
i
pounds,
i
then
i
x
i
is
i
atleast
i
z
i
pounds.
i
This
i
would
i
mean
i
that
i
the
i
relation
i
is
i
reflective.
Let:
i
x
i
have
i
20lbs
i
and
i
let
i
y
i
have
i
30lbs.
y
i
is
i
related
i
to
i
x,
i
but
i
x
i
is
i
not
i
related
i
to
i
y.
Because
i
no
i
watermelon
i
weighs
i
the
i
same,
i
it
i
is
i
anti-symmetric.
if
i
x
i
is
i
related
i
to
i
y,
i
and
i
y
i
related
i
to
i
z:
i
weight
i
of
i
x
i
¿
i
weight
i
of
i
y
i
¿
i
weight
i
of
i
z
This
i
relation
i
is
i
transitive
(b)
Watermelon
i
x
i
is
i
related
i
to
i
watermelon
i
y
i
if
i
the
i
measured
i
weight
i
of
i
water-
i
melon
i
x
i
is
i
at
i
least
i
the
i
measured
i
weight
i
of
i
watermelon
i
y.
i
All
i
watermelons
i
have
i
exactly
i
the
i
same
i
measured
i
weight.
Fori thisi wei needi toi imaginei thati alli watermelonsi havei thei samei weight.i
Becausei everyi watermeloni hasi thei samei value,i thisi makesi iti reflexive,i
symmetrici andi transitive.
P
ROBLEM
6
Part 1.
Give the adjacency matrix for the graph G as pictured below:
Figure 2:
A graph shows 6 vertices and 9 edges. The vertices are 1, 2, 3, 4,
5, and 6, represented by circles. The edges between the vertices are represented by
arrows, as follows: 4 to 3; 3 to 2; 2 to 1; 1 to 6; 6 to 2; 3 to 4; 4 to 5; 5 to 6; and
a self loop on vertex 5.
0 0 0 0 0 1
1 0 0 0 0 0
0 1 0 1 0 0
0 0 1 0 1 0
0 0 0 0 1 1
0 1 0 0 0 0
Part 2.
A directed graph G has 5 vertices, numbered 1 through 5. The 5 5
matrix A is the adjacency matrix for G. The matrices A
2
and A
3
are given below.
A
2
=
A
2
A
3
=
Use the information given to answer the questions about the graph G.
(a)
Which vertices can reach vertex 2 by a walk of length 3?
To find the vertices that can reach vertex 2 by a walk of 3 lengths
(vertex x to vertex y):
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
0
1
1
0
1
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
1
0
1
1
1
0
1
0
We can use: [A
3
]xy
Find for x:
[A
3
]xy 0
[A
3
]
22
=
1 0
Vertex 2 is the only vertex able to reach vertex 2 by a walk of 3 lengths.
(b)
Is there a walk of length 4 from vertex 4 to vertex 5 in G? (Hint: A
4
=
A
2
·
A
2
.)
Using the given adjacency matrices.
A
4
=
A
2
A
2
To achieve the requested walk, you would need [A
4
]
54
=
0 which such
a walk does not exist.
P
ROBLEM
7
Part 1.
The drawing below shows a Hasse diagram for a partial order on the set
{
A, B, C, D, E, F, G, H, I,
J
}
Figure 3:
A Hasse diagram shows 10 vertices and 8 edges. The vertices, rep-
resented by dots, are as follows: vertex
J;
vertices H and
I
are aligned vertically to
the right of vertex
J;
vertices A, B, C, D, and
E
forms a closed loop, which is to
the right of vertices H and
I;
vertex G is inclined upward to the right of vertex E;
and vertex
F
is inclined downward to the right of vertex
E.
The edges, represented
by line segments, between the vertices are as follows: Vertex
J
is connected to no
vertex; a vertical edge connects vertices H and
I;
a vertical edge connects vertices
B and C; and 6 inclined edges connect the following vertices, A and B,
C
and D,
D and
E,
A and
E, E
and G, and
E
and
F.
(a)
Whati arei thei minimali elementsi ofi thei partiali order?
Sincei minimali elementsi arei elementsi thati arei noti proceededi byi
otheri elements,i youi cani orderi thei elementsi likei so:
{
J,I,A,F
}
(b)
Whati arei thei maximali elementsi ofi thei partiali order?
Sincei maximali elementsi arei elementsi thati arei noti succeededi byi thei
samei element:
{
J,
i
H,
i
D,
i
G
}
(c)
Which
i
of
i
the
i
following
i
pairs
i
are
i
comparable?
(A,
i
D),
i
(J,
i
F
i
),
i
(B,
i
E),
i
(G,
i
F
i
),
i
(D,
i
B),
i
(C,
i
F
i
),
i
(H,
i
I),
i
(C,
i
E)
Comparable
i
Pairs:
i i
(A,D),(G,F),(D,B),(H,I)
Comparable
i
for
i
given
i
partial
i
order:
i
(D
i
i
A),
i
(F
i
i
G),
i
(B
i
i
D),
i
(I
i
i
H)
Part 2.
Each relation given below is a partial order. Draw the Hasse diagram for
the partial order.
(a)
The domain is
{
3, 5, 6, 7, 10, 14, 20, 30, 60
}
. x
y if x evenly divides y.
(b)
The domain is
{
a, b, c, d, e, f
}
. The relation is the set:
{
(b, e), (b, d), (c, a), (c, f ), (a, f ), (a, a), (b, b), (c, c), (d, d), (e, e), (f, f )
}
P
ROBLEM
8
Determine whether each relation is an equivalence relation. Justify your answer.
If the relation is an equivalence relation, then describe the partition defined by the
equivalence classes.
(a)
The domain is a group of people. Person x is related to person y under
relation M if x and y have the same favorite color. You can assume that
there is at least one pair in the group, x and y, such that xMy.
Consider
i
the
i
given
i
relation
i
M.
A
i
person
i
has
i
the
i
same
i
favorite
i
color
i
as
i
themselves.
Relation
i
M
i
is
i
Reflexive.
If
i
person
i
x
i
has
i
the
i
same
i
favorite
i
color
i
as
i
person
i
y,
i
then
i
y
i
has
i
the
i
same
i
favorite
i
color
i
as
i
person
i
x.
Relation
i
M
i
is
i
Symmetric.
If
i
person
i
x
i
has
i
the
i
same
i
favorite
i
color
i
as
i
person
i
y.
and
i
y
i
has
i
the
i
same
i
favorite
i
color
i
as
i
person
i
z.
then
i
person
i
x
i
has
i
the
i
same
i
favorite
i
color
i
as
i
person
i
z.
M
i
is
i
transitive.
i
Therefore,
i
the
i
given
i
relation
i
M
i
is
i
an
i
equivalence
i
relation.
i
All
i
persons
i
having
i
one
i
favorite
i
color
i
is
i
considered
i
as
i
one
i
equivalence
i
class.
(b)
The domain is the set of all integers. xEy if x
+
y is even. An integer z is
even if z
=
2k for some integer k.
The
i
relation
i
is
i
reflexive:
if
i
x
i
is
i
an
i
integer,
i
that
i
also
i
means
i
x
i
+
i
x
i
=
i
2x
i
is
i
also
i
an
i
integer.
i
We
i
can
i
find
i
if
i
the
i
relation
i
is
i
symmetric
i
by:
if
i
x
i
+
i
y
i
is
i
even,
i
y
i
+
i
x
i
will
i
also
i
be
i
even.
i
This
i
is
i
true.
i
Since
i
x,
i
y,
i
and
i
z
i
are
i
integers
We
i
can
i
assume
i
that
i
x
i
+
i
y
i
is
i
even.
i
for
i
integer
i
a:
i
x
i
+
i
y
i
=
i
2a
for
i
integer
i
k:
i
y
i
+
i
z
i
=
i
2k
x
i
+
i
z
i
=
i
2a
i
-
i
y
i
+
i
2k
i
-
i
y
i
=
i
2(a
i
+
i
k
i
-
i
y)
Both
i
(a
i
+
i
k
i
-
i
y)
i
and
i
x
i
+
i
z
i
are
i
integers,
i
therefore
i
this
i
relation
i
is
i
an
i
equivalence
i
relation.
Students also viewed