Discrete Mathematics Solved Assignment

This document is a solved assignment for the Discrete Mathematics course. It includes answers to questions on relations, matrix representations, and properties. The assignment also includes a reference list.

1
Surname:
Discrete mathematics
Name:
Course:
Instructor’s name
affiliated Institution:
date:

2
Surname:
Discrete mathematics
Question one
1. a. the answer is false
b. the answer is true
c. the answer is false
d. the answer is false
e. the answer is true.
f. it is symmetric
g. it is transitive
h. it is reflexive
i. it is anti-symmetric
j) it satisfies the properties of (f), (g) and (h).
Question two
a) R ∪ S = { (1, 1) (1, 2) (1, 3) (1, 4) (2, 4) (3, 1) (3, 3) (4, 1) (4, 2) (2, 1) (3, 2) (4, 3) (4,
4 ) }
b) R ∩ S = { (1, 2), (2, 4), (3, 1) }
c) Matrix representations of relations
R∧S=
[ 1 1 1 1
1 0 0 1
1 1 1 0
1 1 1 1 ]
R ∘ S = { (1, 2) (1, 1) (1, 2, (1, 3) (2, 4) (3, 2) (3, 2) (4, 2) (4, 1) } (Schmidt, 2012)

3
Surname:
Question three
a) Binary matrix representation of
R=
[ 0 1 1 1 1
0 0 0 0 1
0 1 0 0 1
0 1 1 0 0
0 0 0 1 0 ]
b) Digraph associated to R
c) Yes, the transitivity of relation R is true since for every (x, y) ϵ R and (y, z) ϵ R → (x, z) ϵ
R
Illustration: (5, 4) ϵ R and (4, 3) ϵ R → (5, 3) ϵ R (Jaume, 2014)
5
1
4 3
2

4
Surname:
Question 4
For a relation to be equivalence, it must satisfy the following three properties:
Reflexivity, transitivity and symmetry
i. Since the main diagonal contains only 1’s then it implies that it is reflexive.
(a, a) ϵ R ∀a ϵ A
For instance, (1, 1) ϵ R, (2, 2) ϵ R and so on.
ii. Symmetric property
(x, y) ϵ R →(y, x) ϵ R
For example
(1, 2) → (2, 1) ϵ R=1
(1, 6) →N (6, 1) ϵ R = 0
iii. Transitive property
(x, y) ϵ R and (y, z) ϵ R→ (x, z) ϵ R
For example
(3, 4) ϵ R and (4, 5) ϵ R → (3,5) ϵ R

5
Surname:
Reference
Jaume, M. and Laurent, T., 2014. Teaching formal methods and discrete
mathematics. arXiv preprint arXiv:1404.6604.
Schmidt, G. and Ströhlein, T., 2012. Relations and graphs: discrete mathematics for
computer scientists. Springer Science & Business Media.