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 books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
