Report

CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/ Clicker frequency: CA Todays topics • Relations • Section 6.1 in Jenkyns, Stephenson (Binary) Relations • Model a relation between two families of objects • Examples: • < for integer numbers • A ⊂ for subsets of integers (Binary) Relations • Model a relation between two families of objects • Formally: • U universe set • Relation: ⊆ × • For , ∈ we write: as a shorthand for "(, ) ∈ “ • Example 1: x<y, formally… • U=N • “ < ” represents the relation = , : , ∈ , < • Example 1: x<y, formally… • U = P(N) • “ ⊂ ” represents the relation = { , : , ∈ (), ⊂ } Relations are graphs • Think of relations as directed graphs • U=nodes of graphs • xRy means “there in an edge xy” • Is R B. R C. Both D. Neither A. ? ? Relations are graphs • What does this relation captures? xRy means 2 A. x>y B. x=y 3 1 C. x divides y D. x+y E. None/more than one 4 6 5 Three important properties of relations • There are several important properties of relations • We will focus on the most important three • A relation R is symmetric if ∀, ∈ , ⇔ • A relation R is reflexive if ∀ ∈ , • A relation R is transitive if ∀, , ∈ , ( ∧ ) → Symmetric relations • A relation is symmetric if ∀, ∈ , ⇔ • As a graph, it is undirected • Which of the following is symmetric A. B. C. D. E. x<y x divides y x and y have the same sign xy None/more than one Types of relations • A relation is reflexive if ∀ ∈ , • As a graph, it has loops in all vertices • Which of the following is reflexive A. x<y B. x divides y C. x and y have the same sign D. xy E. None/more than one Types of relations • A relation is transitive if ∀, , ∈ , ( ∧ ) → • This is less intuitive, when viewed as a graph… • Which of the following is transitive A. x<y B. x divides y C. x and y have the same sign D. xy E. None/more than one Test your understanding • Let U=P(N) (all subsets of integers) •R=⊆ • Is R symmetric? A. Yes B. No Test your understanding • Let U=P(N) (all subsets of integers) •R=⊆ • Is R reflexive? A. Yes B. No Test your understanding • Let U=P(N) (all subsets of integers) •R=⊆ • Is R transitive? A. Yes B. No Test your understanding • Let U=P(N) • R = ⊊ (ie xRy = “x is proper subset of y”) • Is R symmetric / reflexive / transitive? A. Yes,Yes,Yes B. No,No,No C. Yes,Yes,No D. No,No,Yes E. Other Test your understanding • Let U=P(N) • R = ⊈ (ie xRy = “x is NOT a subset of y”) • Is R symmetric / reflexive / transitive? A. Yes,Yes,Yes B. No,No,No C. Yes,Yes,No D. No,No,Yes E. Other Test your understanding • Let U=“all Boolean formulas on n inputs” • xRy = “x and y compute the same Boolean function” • Is R symmetric / reflexive / transitive? A. Yes,Yes,Yes B. No,No,No C. Yes,Yes,No D. No,No,Yes E. Other Next class • Equivalence relations • Read section 6.2 in Jenkyns, Stephenson