Chapter 3

RELATIONS

3.1 OPERATIONS ON RELATIONS

In this chapter we will study the difference between properties of relations and operations on relations. We will also study types of relations such as symmetry, transitivity, reflexivity, and discuss the concept of transitive closure (Warshall’s algorithm).

3.1.1 Set Operations

Relations are sets of tuples, so we can apply set operations. The intersection of two relations gives pairs satisfying both relations. The union gives pairs satisfying one-the union of “brother-of” and “sister-of” is “sibling-of”. Complement gives pairs not satisfying both relations.

3.1.2 Inverse

Definition If R is a relation on A × B, then R–1 is a relation on B × A given by R–1 = {(b,a)|(a,b) R}. It is just the relation ...

Get Discrete Mathematics now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.