Discrete Math for Computer Science, unit: Relations. Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a relation, in discrete mathematics?
Show answer
A set of ordered pairs describing a connection between elements of two sets- What is a binary relation?
Show answer
A relation between elements of exactly two sets (or one set with itself)- What is a reflexive relation?
Show answer
A relation where every element is related to itself- What is a symmetric relation?
Show answer
A relation where if a is related to b, then b is also related to a- What is a transitive relation?
Show answer
A relation where if a relates to b and b relates to c, then a relates to c- What is an antisymmetric relation?
Show answer
A relation where if a relates to b and b relates to a, then a must equal b- What is an equivalence relation?
Show answer
A relation that is reflexive, symmetric, and transitive- What is an equivalence class?
Show answer
The set of all elements related to a given element under an equivalence relation- What is a partial order?
Show answer
A relation that is reflexive, antisymmetric, and transitive- What is a total order?
Show answer
A partial order where every pair of elements is comparable- What is the composition of two relations?
Show answer
A new relation formed by chaining pairs from the first relation to pairs in the second- What is the inverse of a relation?
Show answer
A relation formed by reversing the order of every ordered pair in the original relation- What is a Hasse diagram used for?
Show answer
Visually representing a partial order, omitting reflexive and transitive edges for clarity- What is a relation's representation as a matrix called?
Show answer
A relation matrix, indicating with 1s and 0s which pairs are related- What does it mean for a relation to be a function?
Show answer
Each element of the domain is related to exactly one element of the range
FlashKeepers