5.2.  Some Operations on Relations

Definition 2.7 (Inverse Relation)

If R: X ↔ Y is a relation, then the inverse realtion

R~: Y ↔ X is defined as { (y,x) | (x,y) ∈ R }.

Consequently, xRy == yR~x

Definition 2.8 (Composition of R and S)

Let R: X ↔ Y and S: Y ↔ Z be two relations. The composition of R and S denoted by R O S contains the pairs (x,z) if and only if there is an intermediate object y such that (x,y) ∈ R and and (y,z) ∈ S.

Consequently:

x(R O S)z == it exists y with xRy and yRz

Examples:

• There are five people: A, B, C, D and E. C owns a motorbike called Speedy and E owns a motorbike called Slow. A has the friends B and D, B has the friend C and C has the friend E.

Let R be the relation x has a friend y and let S be the relation y owns a motorbike.

Find the relation R O S. R: x has a friend y

Solution:

R:	{ (x,y) | x has a friend y } and x,y ∈ { A, B, C, D, E } =


	{ (A,B), (A,D), (B,C), (C,E) }


S:	{ (x,m) | y owns a motorbike } and
		x ∈ { A, B, C, D } and
		m ∈ { Speedy and Slow } =


	{ (C, Speedy), (E, Slow) }

So we know: R O S = { (B, Speedy), (C, Slow) }

A graphically representation of the composition → board

If x has a friend y means also y has a friend x. Calculate: R O S

Definition 2.9 (Associative Operations)

If R, S, and P are three Relations, then the following holds:

( R O S ) O P = R ( S O P )

Examples:

R = { (x1, y3,), (x2,y1), (x3, y4)}
S = { (y1, z4,), (y2,z3), (y4, z1)}
R O S = { (x2, z4), (x3, z1) }

Last modified 22/May/97