In this chapter, the following content will be discussed: Properties of relations; reflexive, symmetric and transitive relations; properties of “less than” relations; properties of congruence modulo 3; transitive closure of a relations. | (CSC 102) Lecture 16 Discrete Structures Previous Lecture Summery Basic concepts of relation Types of relations Relation on a set The inverse of a relation Representing relations using Digraphs N-ary Relations Today’s Lecture Properties of relations Reflexive, Symmetric and Transitive Relations Properties of “Less than” relations Properties of Congruence Modulo 3 Transitive closure of a relations Representing Relations Using Digraphs Definition A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs). The vertex a is called the initial vertex of the edge (a, b), and the vertex b is called the terminal vertex of this edge. We can use arrows to display graphs. Example: Display the digraph with V = {a, b, c, d} and E = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)}. a b c d An edge of the form (b, b) is called a loop. Representing Relations Using Digraphs Representing Relations Using Digraphs Let A = {3, 4, 5, 6, 7, 8} and define a relation R on A as follows: For all x, y ∈ A, x R y ⇔ 2 | (x − y). Draw the directed graph of R. Note that 3 R 3 because 3 − 3 = 0 and 2 | 0 since 0 = 2 · 0. Thus there is a loop from 3 to itself. Similarly, there is a loop from 4 to itself, from 5 to itself, and so forth, since the difference of each integer with itself is 0, and 2 | 0. Note also that 3 R 5 because 3 − 5 = −2 = 2 · (−1). And 5 R 3 because 5 − 3 = 2 = 2 · 1. Hence there is an arrow from 3 to 5 and also an arrow from 5 to 3. The other arrows in the directed graph, are obtained by similar reasoning. Directed Graph of a Relation Let A = {3, 4, 5, 6, 7, 8} and define a relation R on A as follows: For all x, y ∈ A, x R y ⇔ 2 | (x − y). Draw the directed graph of R. N-ary Relations A binary relation is a subset of a Cartesian product of two sets, similarly, an n-ary relation is a subset of a Cartesian product of n sets. Definition Given sets A1, A2, . . . , An, an n-ary . | (CSC 102) Lecture 16 Discrete Structures Previous Lecture Summery Basic concepts of relation Types of relations Relation on a set The inverse of a relation Representing relations using Digraphs N-ary Relations Today’s Lecture Properties of relations Reflexive, Symmetric and Transitive Relations Properties of “Less than” relations Properties of Congruence Modulo 3 Transitive closure of a relations Representing Relations Using Digraphs Definition A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs). The vertex a is called the initial vertex of the edge (a, b), and the vertex b is called the terminal vertex of this edge. We can use arrows to display graphs. Example: Display the digraph with V = {a, b, c, d} and E = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)}. a b c d An edge of the form (b, b) is called a loop. Representing Relations Using Digraphs Representing Relations Using
