CS 191 Exam Three Terms and Concepts

Hein Section 4.1 Properties of Binary Relations

• Be familiar with the properties reflexive, symmetric, transitive, irreflexive, and antisymmetric. In particular be able to identify which of these properties particular relations over a set have.
• Be familiar with the idea of composition of relations.
• Know what closures of relations are, particularly symmetric closures and transitive closures. Be able to calculate these for a relation.

Hein Section 4.2 Equivalence Relations

• Know what it takes for a relation to be an equivalence relation.
• Be able to identify why a particular relation is not an equivalence relation.
• Be able to define the set of equivalence classes for particular equivalence relations.

Hein Section 4.3 Order Relations

• Know what properties are required for a relation to be a partial order.
• Be able to perform a topological sort on a partially ordered set.
• Know how to draw poset diagrams for partially ordered sets.
• Have an idea of what it takes for a set to have well-founded order.