CS201: Data Structures and Discrete Mathematics I

CS201: Data Structures and Discrete Mathematics I

CS201: Data Structures and Discrete Mathematics I Relations and Functions 02/06/20 CS201 1 Relations 02/06/20 CS201 2 Ordered n-tuples

An ordered n-tuple is an ordered sequence of n objects (x1, x2, , xn) First coordinate (or component) is x1 n-th coordinate (or component) is xn An ordered pair: An ordered 2-tuple (x, y) An ordered triple: an ordered 3-tuple (x, y, z) 02/06/20 CS201 3 Equality of tuples vs sets

Two tuples are equal iff they are equal coodinate-wise (x1, x2, , xn) = (y1, y2, , yn) iff x1 = y1, x2 = y2, , xn = yn (2, 1) (1, 2), but {2, 1} = {1, 2} (1, 2, 1) (2, 1), but {1, 2, 1} = {2, 1} (1, 2-2, a) = (1, 0, a) (1, 2, 3) (1, 2, 4) and {1, 2, 3} {1, 2, 4} 02/06/20 CS201

4 Cartesian products Let A1, A2, An be sets The cartesian products of A1, A2, An is A1 x A2 x x An = { (x1, x2, , xn) | x1 A1 and x2 A2 and and xn An) Examples: A = {x, y}, B = {1, 2, 3}, C = {a, b} AxB={(x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3)} AxBxC = {(x, 1, a), (x, 1, b), , (y, 3, a), (y, 3, b)} Ax(BxC) = {(x, (1, a)), (x, (1, b)), , (y, (3, a)), (y, (3, b))}

02/06/20 CS201 5 Relations A relation is a set of ordered pairs Let x R y mean x is R-related to y Let A be a set containing all possible x Let B be a set containing all possible y Relation R can be treated as a set of ordered pairs R = {(x, y) AxB | x R y} Example: We have the relation is-capital-of between cities and countries: Is-capital-of = {(London, UK), (WashingtonDC, US), }

02/06/20 CS201 6 Relations are sets R AxB as a relation from A to B R is a relation from A to B iff R AxB Furthermore, x R y iff (x, y) R. If the relation R only involves two sets, we say it is a binary relation. We can also have an n-ary relation, which involves n sets. 02/06/20 CS201

7 Various kinds of binary relations One-to-one relation: each first component and each second component appear only once in the relation. One-to-many relation: if some first component s1 appear more than once. Many-to-one relation: if some second component s2 is paired with more than one first component. Many-to-many relation: if at least one s1 is paired with more than one second component and at least one s2 is paired with more than one first component. 02/06/20 CS201

8 Visualizing the relations One-to-one One-to-many Many-to-one Many-to-many 02/06/20 CS201 9

Binary relation on a set Given a set A, a binary relation R on A is a subset of AxA (R AxA). An example: A = {1, 2}. Then AxA={(1,1), (1,2), (2,1), (2,2)}. Let R on A be given by x R y x+y is odd. then, (1, 2) R, and (2, 1) R 02/06/20 CS201 10 Properties of Relations: Reflexive Let R be a binary relation on a set A. R is reflexive: iff for all x A, (x, x) R. Reflexive means that every member is related to

itself. Example: Let A = {2, 4, a, b} R = {(2, 2), (4, 4), (a, a), (b, b)} S = {(2, b), (2, 2), (4, 4), (a, a), (2, a), (b, b)} R, S are reflexive relations on A. Another example: the relation is reflexive on the set Z+. 02/06/20 CS201 11 Symmetric relations A relation R on a set A is symmetric iff for all x, y A, if (x, y) R then (y, x) R . Example: A = {1, 2, b} R = {(1, 1), (b, b)}

S = {(1, 2)} T = {(2, b), (b, 2), (1, 1)} R, T are symmetric relations on A. S is not a symmetric relation on A. The relation is reflexive on the set Z+, but not symmetric. E.g., 3 4 is in, but not 4 3 02/06/20 CS201 12 Anti-symmetric relations A relation R on a set A is anti-symmetric iff for all x, y A. if (x, y) R and (y, x) R then x = y. Example: A = {1, 2, b} R = {(1, 1), (b, b)} S = {(1, 2)}

T = {(2, b), (b, 2), (1, 1)} R, S are anti-symmetric relations on A. T is not an anti-symmetric relation on A. The relation is reflexive on the set Z+, but not symmetric. It is anti-symmetric. 02/06/20 CS201 13 Transitive relations A relation R on a set A is transitive iff for all x, y, z A, if (x, y) R and (y, z) R, then (x, z) R. Example: A = {1, 2, b} R = {(1, 1), (b, b)} S = {(1, 2), (2, b), (1, b)}

T = {(2, b), (b, 2), (1, 1)} R, S are transitive relations on A. T is not a transitive relation on A. The relation is reflexive on the set Z+, but not symmetric. It is also anti-symmetric, and transitive (why?). 02/06/20 CS201 14 Transitive closure Let R be a relation on A The smallest transitive relation on A that includes R is called the transitive closure of R. Example: A = {1, 2, b} R = {(1, 1), (b, b)}

S = {(1, 2), (2, b), (1, b)} T = {(2, b), (b, 2), (1, 1)} The transitive closures of R and S are themselves The transitive closure of T is T {(2, 2), (b, b)} 02/06/20 CS201 15 Equivalence relations A relation on a set A is an equivalence relation if it is Reflexive. Symmetric Transitive.

Examples of equivalence relations On any set S, x R y x = y On integers 0, x R y x+y is even On the set of lines in the plane, x R y x is parallel to y. On {0, 1}, x R y x = y2 On {1, 2, 3}, R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}. 02/06/20 CS201 16 Congruence relations are equivalence relations We say x is congruent modulo m to y That is, x C y iff m divides x-y, or x-y is an integral multiple of m. We also write x y (mod m) iff x is congruent to y

modulo m. Congruence modulo m is an equivalent relation on the set Z. Reflexive: m divides x-x = 0 Symmetry: if m divides x-y, then m divides y-x Transitive: if m divides x-y and y-z, then m divides (x-y)+(y-z) = x-z 02/06/20 CS201 17 An important feature Let us look at the equivalence relation: S = {x | x is a student in our class} x R y x sits in the same row as y

We group all students that are related to one another. We can see this figure: row-1 row-2 row-3 row-5 row-4 We have partitioned S into subsets in such a way that everyone in the class belongs to one and only one subset. 02/06/20 CS201 18

Partition of a set A partition of a set S is a collection of nonempty disjoint subsets (S1, S2, .., Sn) of S whose union equals S. S1 S2 Sn = S If i j then Si Sj = (Si Sj are disjoint) Examples, let A = {1, 2, 3, 4} 02/06/20 {{1}, {2}, {3}, {4}} a partition of A {{1, 2}, {3, 4}} a partition of A {{1, 2, 3}, {4}} a partition of A

{{}, {1, 2, 3}, {4}} not a partition of A {{1, 2}, {3, 4}, {1, 4}} not a partition of A CS201 19 Equivalent classes Let R be an equivalence relation on a set A. Let x A The equivalent class of x with respect to R is: R[x] = {y A | (x, y) R} If R is understood, we write [x] instead of R[x]. Intuitively, [x] is the set of all elements of A to which x is related. 02/06/20

CS201 20 Theorems on equivalent relations and partitions Theorem 1: An equivalence relation R on a set A determines a partition of A. i.e., the distinctive equivalence classes of R form a partition of A. Theorem 2: a partition of a set A determines an equivalence relation on A. 02/06/20

i.e., there is an equivalence relation R on A such that the set of equivalence classes with respect to R is the partition. CS201 21 An equivalent relations induces a partition Let A = {0, 1, 2, 3, 4, 5} Let R be the congruence modulo 3 relation on A The set of equivalence classes is: {[0], [1], [2], [3], [4], [5]} = {{0, 3}, {1, 4}, {2, 5}, {3, 0}, {4, 1}, {5, 2}} = {{0, 3}, {1, 4}, {2, 5}} Clearly, {{0, 3}, {1, 4}, {2, 5}} is a partition

of A. 02/06/20 CS201 22 An partition induces an equivalent relation Let A = {0, 1, 2, 3, 4, 5} Let a partition P = {{0, 5}, {1, 2, 3}, {4}} Let R = {{0, 5} x {0, 5} {1, 2, 3} x {1, 2, 3} {4} x {4}} = {(0, 0), (0, 5), (5, 0), (5, 5), (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 4)} It is easy to verify that R is an equivalent relation. 02/06/20

CS201 23 Partial order A binary relation R on a set S is a partial order on S iff R is Reflexive Anti-symmetric Transitive We usually use to indicate a partial order. If R is a partial order on S, then the ordered pair (S, R) is called a partially ordered set (also known as poset). We denote an arbitrary partially ordered set by (S, ). 02/06/20

CS201 24 Examples On a set of integers, x R y x y is a partial order ( is a partial order). for integers, a, b, c. a a (reflexive) a b, and b a implies a = b (anti-symmetric) a b and b c implies a c (transitive) Other partial order examples: On the power set P of a set, A R B A B On Z+, x R y x divides y. On {0, 1}, x R y x = y2 02/06/20

CS201 25 Some terminology of partially ordered sets Let (S, ) be a partially ordered set If x y, then either x = y or x y. If x y, but x y, we write x < y and say that x is a predecessor of y, or y is a successor of x. A given y may have many predecessors, but if x < y and there is no z with x < z

Visualizing partial order: Hasse diagram Let S be a finite set. Each of the element of S is represented as a dot (called a node, or vertex). If x is an immediate predecessor of y, then the node for y is placed above node x, and the two nodes are connected by a straight-line segment. The Hasse diagram of a partially ordered set conveys all the information about the partial order. We can reconstruct the partial order just by looking at the diagram 02/06/20 CS201 27

An example Hasse diagram on the power set P({1, 2}): Poset: (P({1, 2}), ) P({1, 2}) = {, {1}, {2}, {1, 2}} consists of the following ordered pairs (, ), ({1}, {1}), ({2}, {2}), ({1, 2}, {1, 2}), (, {1}), (, {2}), (, {1, 2}), ({1}, {1, 2}), ({2}, {1, 2}) {1, 2} {1} 02/06/20 {2} CS201

28 Total orders A partial order on a set is a total order (also called linear order) iff any two members of the set are related. The relation on the set of integers is a total order. The Hasse diagram for a total order is on the right 02/06/20 CS201 29 Least element and minimal element

Let (S, ) be a poset. If there is a y S with y x for all x S, then y is a least element of the poset. If it exists, is unique. An element y S is minimal if there is no x S with x < y. In the Hasse diagram, a least element is below all orders. A minimal element has no element below it. Likewise we can define greatest element and maximal element 02/06/20 CS201 30 Examples: Hasse diagram f

Consider the poset: b a e c The maximal elements are a, b, f The minimal elements are a, c. A least element but but b e no greatest element A greatest element no leastf element b

c 02/06/20 CS201 e 31 Summary A binary relation on a set S is a subset of SxS. Binary relations can have properties of reflexivity, symmetry, anti-symmetry, and transitivity. Equivalence relations. A equivalence relation on a set S defines a partition of S. Partial orders. A partial ordered set can be represented graphically.

02/06/20 CS201 32 Functions 02/06/20 CS201 33 High school functions Functions are usually given by formulas f(x) = sin(x) f(x) = ex f(x) = x3

f(x) = log x A function is a computation rule that changes one value to another value Effectively, a function associates, or relates, one value to another value. 02/06/20 CS201 34 general functions We can think of a function as relating one object to another (need not be numbers). A relation f from A to B is a function from A to B iff for every x A, there exists a unique y B such that x f y, or equivalently (x, y) f

Functions are also known as transformations, maps, and mappings. 02/06/20 CS201 35 Notational convention Sometimes functions are given by stating the rule of transformation, for example, f(x) = x + 1 This should be taken to mean f = {(x, f(x)) AxB | x A} where A and B are some understood sets. 02/06/20

CS201 36 Examples Let A = {1, 2, 3} and B = {a, b} 1 R = {(1, a), (2, a), (3, b)} is a function from A to B R = {(1, a), (1, b), (2, a), (3, b)} is not a function from A to B 02/06/20 CS201

a 2 3 1 b a 2 3 b 37

Notations and concepts Let A and B be sets, f is a function from A to B. We denote the function by: f: A B A is the domain, and B is the codomain of the function. If (a, b) f, then b is denoted by f(a); b is the image of a under f, a is a preimage of b under f. The range of f is the set of images of f. The range of f is the set f(A). 02/06/20 CS201 38 An example

Let the function f be 1 2 3 a b c Domain is {1, 2, 3} Codomain is {a, b, c} Range is {a, c} 02/06/20 CS201 39

Equality of functions Let f: A B and g: C D. We denote function f = function g iff set f = set g Note that this force A = C, but not B = D Some require B = D as well. 02/06/20 CS201 40 Properties of functions: onto Let f: A B The function f is an onto or surjective function iff the range of f equals to the codomain of f.

Or for any y B, there exists some x A, such that f(x) = y. The function on the right is onto. f: Z Z with f(x) = x2 is not onto 02/06/20 1 a 2 3 CS201 b

41 One-to-one functions A function f: A B is one-to-one, or injective if no member of B is the image under f of two distinct elements of A. Let A = {1, 2, 3} 1 a Let B = {a, b, c, d} b 2 c Let f = {(1, b), (2, c), (3, a)} 3 d The function f is one-to-one f: Z Z with f(x) = x2 is not one-to-one because f(2) = f(-2) = 4.

02/06/20 CS201 42 Bijections (one-to-one correspondences) A function f: A B is bijective if f is both one-to-one and onto. Let A = {1, 2, 3} 1 a b Let B = {a, b, c} 2 c Let f = {(1, b), (2, c), (3, a)} 3 The function f is one-to-one

f: Z Z with f(x) = x2 is not bijective because it is not one-to-one. 02/06/20 CS201 43 Composition of functions Let f: A B and g: B C. Then the composition function , g f, is a function from A to C defined by (g f)(a) =g(f(a)). Note that the function f is applied first and then g. Let f: R R be defined by f(x) = x2. Let g: R R be defined by g(x) = x. (g f)(2.3) = g(f(2.3)) =g((2.3)2) = g(5.29) = 5.29 = 5. 02/06/20

CS201 44 Inverse functions Identity function: the function that maps each element of a set A to itself, denoted by iA. We have iA: A A. Let f: A B. If there exists a function g: B A such that g f=ia and f g=ib, then g is called the inverse function of f, denoted by f -1 Theorem: Let f: A B. f is a bijection iff f -1 exists. Example: f: R R given by f(x) = 3x+4. f -1 = (x - 4)/3 (f f -1)(x) = 3(x-4)/3 + 4 = x identity function 02/06/20

CS201 45 Summary We have introduced many concepts, 02/06/20 Function

Domain, codomain Image, preimpage Range Onto (surjective) One-to-one (injective) Bijection (one-to-one correspondence) Function composition Identity function Inverse function CS201 46

Recently Viewed Presentations

  • The American Revolution Chapter 6 1776 -1783 Chapter

    The American Revolution Chapter 6 1776 -1783 Chapter

    Revolutionary WarNewspaper Project. Write and report the complete paper from Loyalist view OR Patriot view. Collaborate with Newspaper Staff on helping one another while working on your assignment: War Correspondent, Personalities Reporter, Lifestyles Reporter, Business/Ads Editor, Opinion/Editorial
  • Compressed Sensing

    Compressed Sensing

    The applications the RLE researchers investigated do something similar, but rather than using mirrors to modify a signal, they use another signal, one that alternates between two values — high and low — in a random pattern.
  • Name of your training here - The Budget Office

    Name of your training here - The Budget Office

    Parking & Transportation Capital ImplementationAdvisory Committee (PTCIAC) Charter. While the 2001 City adopted and University approved WWU Institutional Master Plan (IMP) laid out a framework of principles and hierarchies for circulation to meet the University and community's needs, it did...
  • The Birds

    The Birds

    While her roles earned her critical acclaim and made her star, Hedren's relationship with Hitchcock quickly soured and the two parted ways. While continuing her work in television and film, Hedren has also devoted a good portion of her time...
  • Figure 6. Caption - Mars at UMHB

    Figure 6. Caption - Mars at UMHB

    Figure 6.8 Probability density function using the Student's t-distribution. Figure 6.9 Confidence interval for the t-distribution. Slide 22 Table 6.6 (continued) Student's t as a function of and Figure 6.10 Chi-squared distribution function. Figure 6.11 Confidence interval for the chi-squared...
  • Dominant Firm / Competitive Fringe

    Dominant Firm / Competitive Fringe

    P = DM Q Comparison vs. Monopoly Dominant Firm as Natural Monopoly COSTLESS ENTRY COSTLESS ENTRY Dominant Firm / Competitive Fringe Model 1. Draw DM, MCf, ACf, Sf, MCDF, ACDF 2. Find P @ MCf = ACf 3.
  • Chapter 5 Similar Triangles Copyright  Cengage Learning. All

    Chapter 5 Similar Triangles Copyright Cengage Learning. All

    Associating pairs of consecutive and corresponding vertices of similar polygons, we determine the endpoints of the corresponding sides. cont'd. Similar Polygons. With an understanding of the terms corresponding angles and corresponding sides, we can define similar polygons. ...
  • Notice &amp; Note - Schoolwires

    Notice & Note - Schoolwires

    Stop! Notice and Note Signpost #4: Words of the Wiser. When you are reading and a character takes the main character aside and gives . serious advice . that is helpful at this moment in the story but could also...