Discrete Mathematics Homework: Relations, Matrices, and Equivalence

This document presents a solved homework assignment in discrete mathematics, focusing on relations and their properties. The solution addresses questions related to the truth values of logical statements, operations on relations such as union and intersection, and their matrix representations. It further explores binary matrix representations and digraphs of relations, including the concept of transitivity. The assignment also delves into equivalence relations, verifying reflexivity, symmetry, and transitivity based on provided examples. The solution includes references to relevant academic sources, providing a comprehensive understanding of the concepts discussed.

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.