CSE115ENGR160 Discrete Mathematics042612.ppt

* * * * * * * CSE115/ENGR160 Discrete Mathematics04/26/12 Ming-Hsuan Yang UC Merced * 9.3 Representing relations Can use ordered set, graph to represent sets Generally, matrices are better choice Suppose that R is a relation from A={a1, a2, …, am} to B={b1, b2, …, bn}. The relation R can be represented by the matrix MR=[mij] where mij=1 if (ai,bj) ?R, mij=0 if (ai,bj) ?R, A zero-one (binary) matrix * Example Suppose that A={1,2,3} and B={1,2}. Let R be the relation from A to B containing (a,b) if a∈A, b∈B, and a b. What is the matrix representing R if a1=1, a2=2, and a3=3, and b1=1, and b2=2 As R={(2,1), (3,1), (3,2)}, the matrix R is * Matrix and relation properties The matrix of a relation on a set, which is a square matrix, can be used to determine whether the relation has certain properties Recall that a relation R on A is reflexive if (a,a)∈R. Thus R is reflexive if and only if (ai,ai)∈R for i=1,2,…,n Hence R is reflexive iff mii=1, for i=1,2,…, n. R is reflexive if all the elements on the main diagonal of MR are 1 * Symmetric The relation R is symmetric if (a,b)∈R implies that (b,a)∈R In terms of matrix, R is symmetric if and only mji=1 whenever mij=1, i.e., MR=(MR)T R is symmetric iff MR is a symmetric matrix * Antisymmetric The relation R is symmetric if (a,b)∈R and (b,a)∈R imply a=b The matrix of an antisymmetric relation has the property that if mij=1 with i≠j, then mji=0 Either mij=0 or mji=0 when i≠j * Example Suppose that the relation R on a set is represented by the matrix Is R reflexive, symmetric or antisymmetric? As all the diagonal elements are 1, R is reflexive. As MR is symmetric, R is symmetric. It is also easy to see R is not antisymmetric * Union, intersection of relations Suppose R1 and R2 are relations on a set A represented by MR1 and MR2 The matrices representing the union and intersection of these relations are MR1?R2 = MR1 ? MR2 MR1?R2 = MR1 ? MR2 * Example Suppose that the relations R1 and R2 on a set