### slides

```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 xy”
• 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
xy
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. xy
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. xy
E. None/more than one
• Let U=P(N) (all subsets of integers)
•R=⊆
• Is R symmetric?
A. Yes
B. No
• Let U=P(N) (all subsets of integers)
•R=⊆
• Is R reflexive?
A. Yes
B. No
• Let U=P(N) (all subsets of integers)
•R=⊆
• Is R transitive?
A. Yes
B. No
• 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
• 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
• 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
```