Flashcards
Discrete Structures - Relations
Cards in this deck (13)
- 1Relations (SEE NOTES)- A binary relation (rho aka P squiggle) from set A to set B is a subset of A x B
Ex:
A = {a, b, c}
B = {1, 2, 3}
Rho (P squiggle) - {(a,1), (a,2), (b,3)} - 2Classifications of relations - One to One Relationeach element occurs only in one pair
- 3Classifications of relations - One to Many relationsome first element in some pairs occurs more than once
- 4Classifications of relations - Many to One Relationssome second element in some pairs occurs more than once
- 5Classifications of relations - Many to Many relationssome first and second elements occur more than once
- 6Properties of Relations - Reflexivityrelation rho on set A is reflexive iff
(∀x) (x ∈ A --> xPx)
example (loop to self)
Example: 4∈A, (4,4)∈P --> 4=4 - 7Properties of Relations - SymmetryRelation rho on set A is symmetric iff:
(∀x)(∀y) (x,y ∈ A, xPy --> yPx)
if loop from x to y, then we will get back the loop of y to x
4 does not equal 3 --> 3 does not equal 4
xPy --> yPx - 8Properties of Relations - Transitivityrelation rho on set A is transitive iff:
(∀x)(∀y)(∀z) (x, y, z ∈ A, xPy, yPz --> xPz - 9Equivalence relationRelation rho on set A which is reflexive, symmetric, and transitive is called an equivalence relation
- 10Irreflexivityrelation rho on set A is irreflexive iff:
(∀x) (x ∈ A --> (x,x) ∉ rho) - 11Antisymmetryrelation rho on set A is antisymmetric iff:
(∀x)(∀y)(x, y ∈ A, xPy, yPx --> x=y
example: a looping to itself (x =a and y = a in that case) - 12Closure relationsgiven relation rho on set A, relation rho* is the closure relation of rho with respect to property P if:
1. P ∈ rho*
2. rho* has property P
3. if rho ' satisfies condition 1 and condition 2, then rho*⊆ rho'
ex:
A = {a, b, c}
rho = {(a,a), (b,b)}
What is the reflexive closure of rho?
Rho* = {(a,a), (b,b), (c,c)}
rho' = {(a,a),(b,b),(c,c),(a,b)}
rho ∈ rho' (condition 1 met)
rho ' is reflexive (condition 2 met)
rho' ⊄ rho*
therefore, this is not a reflexive closure because it is the smallest relation satisfying 1.) and 2.) - 13equivalence classlet rho be an equivalence relation on set A, then the equivalence class of x ∈ A with respect to the equivalence relation rho, denoted by [x] is defined as:
[x] = {y ∈ A | xPy)
Information
- Description
- Flashcards on Discrete Structures - Relations, created by Spencer Ross on 17/12/2018.
- Created by
- Spencer Ross · Dec 2018
- Updated
- Dec 17, 2018
- Views
- 0
- Rating