9.1 Relations and Their Properties:Def. 1: Let A and B be sets. A binary relation from A to B is a subset of A × B.Def. 2: A relation on a set A is a relation from A to A.Def. 3: A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A.Def. 4: A relation R on a set A is called symmetric if(b, a) ∈ R whenever(a, b) ∈ R, forall a, b ∈ A. A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈R, then a = b is called antisymmetric.Def. 5: A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R,then (a, c) ∈ R, for all a, b, c ∈ A.Def. 6: Let R be a relation from a set A to a set B and S a relation from B to a set C. Thecomposite of R and S is the relation consisting of ordered pairs (a, c), where a ∈ A, c∈ C, and for which there exists an element b ∈ B such that (a, b) ∈ R and (b, c) ∈ S.We denote the composite of R and S by S ◦ R.Def. 7: Let R be a relation on the set A. The powers Rn, n = 1, 2, 3,..., are definedrecursively by R1= R and Rn+1= Rn◦ R.Theorem 1: The relation R on a set A is transitive if and only if Rn⊆ R for n = 1, 2, 3,....9.2 n-ary Relations and Their Applications:Def. 1: Let A1, A2,..., Anbe sets. An n-ary relation on these sets is a subset of A1× A2×···× An. The sets A1, A2,..., Anare called the domains of the relation, and n is called itsdegree.Def. 2: Let R be an n-ary relation and C a condition that elements in R may satisfy. Thenthe selection operator sCmaps the n-ary relation R to the n-ary relation of all n-tuplesfrom R that satisfy the condition C.Def. 3: The projection Pi1i2,...,imwhere i1< i2< ··· < im, maps the n-tuple (a1, a2,..., an) tothe m-tuple (ai1, ai2,..., aim), where m ≤ n.Def. 4: Let R be a relation of degree m and S a relation of degree n. The join Jp(R, S),where p ≤ m and p ≤ n, is a relation of degree m + n − p that consists of all (m + n −p)-tuples(a1, a2,..., am−p, c1, c2,..., cp, b1, b2,..., bn−p), where the m-tuple (a1, a2,..., am−p, c1,c2,..., cp) belongs to R and the n-tuple (c1, c2,..., cp, b1, b2,..., bn−p) belongs to S.9.3 Representing Relations:Def. 1: A directed graph, or digraph, consists of a set V of vertices (or nodes) togetherwith a set E of ordered pairs of elements of V called edges (or arcs). The vertex a iscalled the initial vertex of the edge (a, b), and the vertex b is called the terminal vertex ofthis edge.9.4 Closures of RelationsDef. 1: A path from a to b in the directed graph G is a sequence of edges (x0, x1), (x1,x2), (x2, x3), . . . , (xn−1, xn) in G, where n is a non-negative integer, and x0= a and xn= b,that is, a sequence of edges where the terminal vertex of an edge is the same as theinitial vertex in the next edge in the path. This path is denoted by x0, x1, x2,..., xn−1, xnandhas length n. We view the empty set of edges as a path of length zero from a to a. Apath of length n ≥ 1 that begins and ends at the same vertex is called a circuit or cycle.Theorem 1: Let R be a relation on a set A. There is a path of length n, where n is apositive integer, from a to b if and only if (a, b) ∈ Rn.Def. 2: Let R be a relation on a set A. The connectivity relation R* consists of the pairs(a, b) such that there is a path of length at least one from a to b in R.Theorem 2: The transitive closure of a relation R equals the connectivity relation R*.Lemma 1: Let A be a set with n elements, and let R be a relation on A. If there is a pathof length at least one in R from a to b, then there is such a path with length notexceeding n. Moreover, when a != b, if there is a path of length at least one in R from ato b, then there is such a path with length not exceeding n − 1.Theorem 3: Let MRbe the zero-one matrix of the relation R on a set with n elements.Then the zero-one matrix of the transitive closure R* is MR*= MR∨ MR[2]∨ MR[3]∨···∨MR[n].Lemma 2: Let Wk= [wij[k]] be the zero-one matrix that has a 1 in its (i, j)th position if andonly if there is a path from vito vjwith interior vertices from the set {v1, v2,..., vk}. Thenwij[k]= wij[k−1]∨ (wik[k−1]∧ wkj[k−1]), whenever i, j, and k are positive integers not
View Full Document
Unlocking...