Uecm1303 Discrete Mathematics With Applications Answer 5

UECM1303 DISCRETE MATHEMATICS WITH APPLICATIONS
ANSWER 5
1.
A B C = {(a, 1, #), (a, 1, *), (a, 2, #), (a, 2, *), (b, 1, #), (b, 1, *), (b, 2, #),
(b, 2, *), (c, 1, #), (c, 1, *), (c, 2, #), (c, 2, *)}
2.
b
1
2
3.
b
3
2
1
1 2 3
Yes
Yes
(b)
(d)
4.
(a)
(c)
5.
{{a, b, c, d, e, f}, {g, h, i, j, k}, {l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}}
6.
{{a, b, c, d}}
{{a}, {b, c, d}}, {{b}, {a, c, d}}, {{c}, {a, b, d}}, {{d}, {a, b, c}}, {{a, b},
{c, d}}, {{a, c}, {b, d}}, {{a, d}, {b, c}}
{{a}, {b}, {c, d}}, {{a}, {c}, {b, d}}, {{a}, {d}, {b, c}}, {{b}, {c}, {a, d}},
{{b}, {d}, {a, c}}, {{c}, {d}, {a, b}},
{{a}, {b}, {c}, {d}},
7.
(a)
(c)
(e)
Yes
Yes
Yes
(b)
(d)
8.
(a)
Dom(R) = {a, b, c, d},

1 1 0
1 0 0
MR =
0 1 0
Ran(R) = {1, 2}
1 0 0
(b)
R = {(1, 1), (2, 4), (3, 9)}

1
No
No
No
No

Dom(R) = {1, 2, 3},
Ran(R) = {1, 4, 9}
1 0 0 0
MR =
(c)
0 1 0 0
0 0 0 1
0 0 0 0
R = {(1, 1), (1, 4), (1, 6), (1, 9), (2, 4), (2, 6), (3, 6), (3, 9), (4, 4)}
Dom(R) = {1, 2, 3, 4},
Ran(R) = {1, 4, 6, 9}
1 1 1 1
0 1 1 0
MR = 0 0 1 1
0 1 0 0
0 0 0 0
(d)
9.
R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3,
3), (3, 4), (3, 5), (4, 4), (4, 5), (5, 5)}
Dom(R) = {1, 2, 3, 4, 5},
Ran(R) = {1, 2, 3, 4, 5}
1 1 1 1 1
1
0 1 1 1 1
MR = 0 0 1 1 1
2
5
0 0 0 1 1
0 0 0 0 1
3
4
Dom(R) = [5, 5]
Ran(R) = [5, 5]
b
5
5
5
R({1, 7}) = R(1) R(7) = { 3 2 3 , 3 2 3 }
R({3, 4, 5}) = R(3) R(4) R(5) = { }
10.
(a)
(b)
11.
R = {(1, 1), (1, 2), (1, 4), (2, 2), (2, 3), (3, 3), (3, 4), (4, 1)}
1

12.
R = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (4, 1), (4, 4), (4, 5)}
0 1 1 1 0
0 1
MR = 0 0
1 0
0 0
Vertex
In-degree
Out-degree
13.
1
0
0
0
0
0
1
0
a
1
3
0
0
1
0
b
2
2
2 = 1, 6, 4,
6 = 3, 3, 4
11 = 4, 3, 4,
15 = 6, 4, 3
c
2
0
(a)
1 = 1, 2, 3,
5 = 3, 3, 3
10 = 4, 3, 3,
14 = 6, 4, 1,
3 = 2, 3, 3,
7 = 3, 4, 5,
12 = 4, 1, 2
16 = 6, 4, 5
(b)
R2 = {(1, 3), (1, 4), (2, 3), (2, 4), (3, 3),
(3, 4), (3, 5), (3, 1), (4, 3), (4, 4),
(4, 2), (4, 6), (6, 1), (6, 3), (6, 5)}
d
2
3
e
1
0
4 = 2, 3, 4,
8 = 3, 4, 3, 9 = 3, 4, 1
13 = 4, 1, 6,
2
3
4
(c)
1
5
R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), (2, 4), (2,
5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (4, 1), (4, 2), (4, 3), (4, 4),
(4, 5), (4, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)}
1 1 1 1 1 1
1 1 1 1 1 1
(d)
M R =
1 1 1 1 1 1
1 1 1 1 1 1
0 0 0 0 0 0
1 1 1 1 1 1
14.
R = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)}
1
2
5
3
R2 = {(1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 5)}
R3 = {(1, 4), (1, 5), (2, 5)}
3

1 1 0 0
15.
(a)
(i)
MR =
1 1 0 0
0 0 1 1
0 0 1 1
R is relflexive, symmetric and transitive. So R is an equivalence
relation.
1 0 0 0
(ii)
MR =
0 1 0 0
0 0 1 0
0 0 0 0
R is symmetric, antisymmetric, and transitive. So R is not an
equivalence relation.
0 0 0 0
(iii)
MR =
0 0 0 0
0 0 0 0
0 0 0 0
R is irreflexive, symmetric, antisymmetric and transitive. So R
is not an equivalence relation.
1 1 1 1
(iv)
MR =
1 1 1 1
1 1 1 1
1 1 1 1
R is reflexive, symmetric and transitive. So R is an equivalence
relation.
(v)
R is reflexive, symmetric and transitive. So R is an equivalence

relation
1 1 1 0 1
0 0 1 0 0
(vi)
MR = 0 0 0 0 0
0 1 1 1 1
0 0 1 0 0
R is antisymmetric and transitive. So R is not an equivalence
relation.
4

(b)
R is reflexive.
R is not symmetric.
R is not asymmetric.
R is not antisymmetric.
R is not transitive.
(c)
R is reflexive and R is not irreflexive.

So R is symmetric.
R is not antisymmetric and not asymmetric.
R is not an equivalence relation.
(d)
R is not reflexive.
R is not irreflexive.
R is symmetric
R is not asymmetric and not antisymmetric.
16.
(ii)
[(2, 3)] = {(1, 6), (2, 3), (3, 2), (6, 1)}
17.
(i)
R = {(2, 2), (2, 4), (2, 6), (2, 8), (4, 2), (4, 6), (6, 2), (6, 4), (6, 8), (8,
2), (8, 6)}
R is not an equivalence relation.
(ii)
18.
R = {(1, 1), (1, 3), (1, 5), (2, 2), (2, 4), (3, 1), (3, 3), (3, 5), (4, 2), (4, 4), (5, 1),
(5, 3), (5, 5)}
19.
(ii)
20.
A/R = {[1], [4]}
21.
A/R = {[(1, 1)], [(1, 2)], [(1, 3)], [(1, 4)], [(2, 4], [(3, 4)], [(4, 4)]}.
22.
(i)
(ii)
(iii)

23.
(a)
(b)
(c)
(d)
[1] = the set of odd integers.

[2] = the set of even integers
R S is the relation consists of all ordered pairs (x, y) where x, y

and x y.
R1 is the relation consists of all ordered pairs (x, y) where x, y
and y > x.

R = {(2, 3), (3, 2), (3, 6), (3, 12), (6, 3), (12, 3)}
R S = {(2, 2), (3, 3), (6, 6), (6, 12), (12, 6), (12, 12)}
R S = {(2, 2), (2, 6), (2, 12), (3, 3), (3, 6), (3, 12), (6, 2), (6, 3), (6,
6), (6, 12), (12, 2), (12, 3), (12, 6), (12,12)}
S1 = {(2, 2), (3, 3), (3, 6), (3, 12), (6, 3), (6, 6), (6, 12), (12, 3), (12, 6),
(12, 12)}

24.
(a)
(b)
(c)
(d)
S = {1, 1), (1, 4), (2, 2), (2, 3), (3, 3), (3, 4)}.
R S = {(1, 2), (2, 4), (3, 1), (3, 2)}.
R S = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 4), (3, 1), (3, 2), (3, 3)}
S1 = {(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (4, 2)}
25.
(a)
Reflexive closure of R = {(1, 1), (2, 1), (2, 2), (2, 3), (3, 2), (3, 3), (2,
2), (4, 2), (4, 4)}.
Symmetric closure of R = {(1, 2), (2, 1), (2, 3), (3, 2), (3, 3), (2, 2), (4,
2), (2, 4)}.
(b)
1 1 1
26.
M R
= 1 1 1
1 1 1
R =AA
1 0 0 1 0
0 1 0 0 0
27.
W1 = 0 0 0 1 1
1 0 0 1 0
0 1 0 0 1
1 0 0 1 0
0 1 0 0 0
W2 = 0 0 0 1 1
1 0 0 1 0
0 1 0 0 1
1 0 0 1 0
0 1 0 0 0
W3 = 0 0 0 1 1
1 0 0 1 0
0 1 0 0 1
1 0 0 1 0
0 1 0 0 0
M R = 1 1 0 1 1
1 0 0 1 0
0 1 0 0 1
R = {(a1, a1), (a1, a4), (a2, a2), (a3, a1), (a3, a2), (a3, a4), (a3, a5), (a4, a1), (a4, a4),
(a5, a2), (a5, a5)}
6

1 1 0 0
28.
M R =
1 1 0 0
0 0 0 0
0 0 1 0
29.
(R S) = A A
30.
(R S) = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 4), (4,
5), (5, 4), (5, 5)}
31.
[3] = [17], [7] = [0], [12] = [2]
32.
(i)
y
y = |x|
(ii)
(iii)
R is not reflexive
R is not symmetric
R is transitive.
R is not an equivalence relation
33.
(a)
(b)
(c)
(d)
(e)
False.
True
False
False
True
34.
(i)
(ii)
(iii)
R is not a partial order.

R is not a partial order.
R is a partial order on A.
35.
(i)
(ii)
R = {(1, 1), (2, 2), (3, 3), (4,4 ), (1, 3), (2, 3), (3, 4), (2, 4), (1, 4)}.
R = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3,
4)}.
a
36.
b
c
d
7

37.
5
4
3
2
1
38.
(i)
(ii)
30
10
32
16
15
4
2
1
(iii)
(iv)
72
60
12
36
3
39.
40.
(i)
(ii)
6
5
1
1, 3, 2, 4, 6, 5, 7, 8
4, 1, 2, 3, 5, 6, 7, 8, 9
10
12
30
Topological sorting: abdcefg

8
15
3

Uecm1303 Discrete Mathematics With Applications Answer 5

Uploaded by

Copyright:

Available Formats

Uecm1303 Discrete Mathematics With Applications Answer 5

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Uecm1303 Discrete Mathematics With Applications Answer 5

Uploaded by

Copyright:

Available Formats

UECM1303 DISCRETE MATHEMATICS WITH APPLICATIONS

{{a, b, c, d, e, f}, {g, h, i, j, k}, {l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}}

Dom(R) = {a, b, c, d},

R = {(1, 1), (2, 4), (3, 9)}