Mathematical Techniques for Computer Science (COMP11120)
Class notes
Lecture Notes on Equivalence Relations and Modular Arithmetic (COMP11120)
7 views 0 purchase
Course
Mathematical Techniques for Computer Science (COMP11120)
Institution
The University Of Manchester (UOM)
Dive into the concepts of equivalence relations and modular arithmetic with these comprehensive lecture notes for COMP11120. Covering key topics such as the properties and applications of equivalence relations, and the fundamentals of modular arithmetic, these notes provide clear explanations and i...
Mathematical Techniques for Computer Science (COMP11120)
All documents for this subject (9)
Seller
Follow
jpxoi
Content preview
Equivalence Relations and Modular Arithmetic
Binary relations
When consider relations from We show this directed graph
discussing relations have - as
as we seen sometimes , we a set can a as
follows
.
S to itself.
V
Instead of R
saying R from S usually say that binary
is a relation 5 to wo is a
1
relation on S
.
L
>
We can represent binary relations as a directed graph. 2 wh
-v
Y
-
X
Example : Let S = Ev ,
w
,
x
, Y, 2)
Let R be a
binary relation on S where
R ((v =
, w) , (v, x) , (2 , 2), (W , v) , (W , 2) (W x) ( -, ) (2
, , , , , 2)]
Properties of relations
Reflexivity Symmetry Transitivity
Informally a relation is
reflexive if every element
is A relation is symmetric if we can
go from one A relation is transitive if
for all s
,
sin S if there is
related to itself. element to another , then we can also go back
.
a path between two elements s and S' , then there
to s
A
binary relation R On a set S is symmetric if and only
is an
edge from s
A binary relation R is reflexive if and
only if for all
if we have for all s, s'ES if (5 5) ER ,
,
then
SES , (5 3) EIR (s' 5) R A relation R S transitive if
E
binary set is and only if
,
,
On a we
have for all s'ES if (5 5) ER s, ,
and (sis") ER
,
then 15 S") ER
,
.
We have
already seen that the identify relation for a Example : The binary relation Ron S =
Ev ,
w
,
x
, y, 2)
set S defined shown is not symmetric (v , X) ER ,
s
is as as
but (X , v) R There are other pairs
((5 5) SxSses]
.
Ig = ,
missing also
V
1
A binary relation R on S is reflexive if and
only if
"
Is &R wh Ev 2)
2 [
Example : The binary relation R on S =
,
W
,
X
, y, shown
is not transitive as (V , W) and (W , v) are in the
relation ,
but (v , v) is not.
Example : The binary relation R on S =
Ev ,
w
,
x
, y, 2) Y
shown is not reflexive as (v , v) &R
,
V
(W w),
R, and (y Y) # R
,
. 1
Symmetric Closure of a
Binary Relation
L
>
V 2 wh
The
symmetric
[
closure allows us to take a relation and
1
add a minimum number of pairs to make it
symmetric .
·
L
>
2 wh Y
Recall that the opposite relation for a
binary
relation R on a set S is defined as
Y · Rop =
((5; 3) =Sx 5/(s s) ,
ER] Transitive Closure of a
Binary Relation
The transitive closure allows us to take a relation and
add number of to make it
Reflexive
a minimum pairs
Closure of a
Binary Relation The symmetric closure of the binary relation R on the
transitive.
Set S is
given by
The reflexive closure allows us to take a relation and
add it The transitive closure of the binary relation R on the set
a minimum number of pairs to make reflexive .
RuRO = Rud(sis)eSxS((s 5) , E
R] S is
given by adding the set of pairs (Si , Sul to R
where S1 , S2 Sn ins with n = 2 such that for
The reflexive closure of R by , ...
is
given
all 1 i < n-1 we have (Si , Sin1) ER
seS]
.
Rulg =
Ru((s s) ,
If a relation R is both reflexive and symmetric ,
We can represent it as an Undirected Graph
A
i V
Z
·
su 3 2 W
y? · Y X
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller jpxoi. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $9.89. You're not tied to anything after your purchase.
