search
The objectives are
- Show a relation is an equivalence relation
- Identify equivalence relations from zero-one matrices
- Identify equivalence relations from directed graphs
- Define a partition with its identical equivalence relation
- Complete a relation to be an equivalence relation
- Identify relations that are partial orders
- Sort lists of tuples by lexicographic order
- Find maximal and minimal elements in a partial order
- Determine least upper bounds and greatest lower bounds given a partial order and a set
- Given a partial order, determine if it is also a lattice
- Draw Hasse diagrams for partial orders
- Show how a topological sort proceeds on a partial order
Problems
All problems are worth 3 points and reference problems in the course text. International book problems switch from chapter 9 to be chapter 7. The number is the same on all but the last as noted.
- (5 points) 9.5.2
- (4 points) 9.5.16 (ad = bc is multiplication and not concatenation)
- (1 points) 9.5.22
- (3 points) 9.5.24
- (4 points) 9.5.42
- (5 points) 9.5.44
- (4 points) 9.5.48
- (2 points) 9.5.67
- (5 points) 9.6.2
- (4 points) 9.6.4 (for part a, assume two different people can be the same height)
- (3 points) 9.6.16 (the symbol in part c is lexicographic comparison)
- (1 points) 9.6.20
- (4 points) 9.6.22
- (4 points) 9.6.34 (| is the divisibility operator, a|b is true if and only if b is a multiple of a)
- (4 points) 9.6.44
- (1 points) 9.6.62
- (2 points) 9.6.66 (7.6.64 intl)
