What makes a relation an equivalence relation?
Answer: Reflexive, symmetric, and transitive.
Explanation
Equivalence relations partition a set into equivalence classes.
Explore · Flashcard deck
Discrete Mathematics: Logic, Sets, and Counting (University)
RelationsGraphsNumber theoryCountingLogicFunctionsSetsProofs
Shared from Quizcard. Flip through the cards below, or copy the deck to edit and study it in your own account — free.
Space flips · arrows move · Esc exits
Relations
What is a partial order?
Answer: A relation that is reflexive, antisymmetric, and transitive.
Explanation
Example: 'divides' on positive integers; ≤ on reals is a total order.
Graphs
What is a tree and how many edges does a tree with n vertices have?
Answer: A connected graph with no cycles; n − 1 edges.
Explanation
A spanning tree connects all vertices of a graph with minimal edges.
Euler path vs Hamiltonian path?
Answer: Euler path uses every edge exactly once (exists iff 0 or 2 odd-degree vertices); Hamiltonian path visits every vertex exactly once.
Explanation
No simple test for Hamiltonian paths.
What is a graph, and what are degree and the handshaking lemma?
Answer: A set of vertices and edges; degree is the number of edges at a vertex; the sum of degrees equals twice the number of edges.
Explanation
So the number of odd-degree vertices is even.
Number theory
What is the Fundamental Theorem of Arithmetic?
Answer: Every integer greater than 1 is a unique product of primes (up to order).
Explanation
Basis of many proofs.
How does the Euclidean algorithm find gcd(a, b)?
Answer: Repeatedly replace (a, b) with (b, a mod b) until the remainder is 0; the last nonzero remainder is the gcd.
Explanation
gcd(48, 18): 48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0 → 6.
What does a ≡ b (mod m) mean?
Answer: m divides a − b; a and b have the same remainder when divided by m.
Explanation
Arithmetic mod m is used in cryptography.
What is the division algorithm?
Answer: For integers a and d > 0, there are unique q and r with a = dq + r and 0 ≤ r < d.
Explanation
r is 'a mod d'.
Counting
State the binomial theorem.
Answer: (x + y)ⁿ = Σ C(n, k) xⁿ⁻ᵏ yᵏ for k = 0 to n.
Explanation
Row n of Pascal's triangle gives the coefficients.
How many binary strings of length n are there, and how many with exactly k ones?
Answer: 2ⁿ total; C(n, k) with exactly k ones.
Explanation
Links to the binomial theorem.
What is the pigeonhole principle?
Answer: If n items are placed in m boxes with n > m, some box has at least two items.
Explanation
Generalized: some box has at least ⌈n/m⌉ items.
Combinations formula
Answer: C(n, r) = n! / (r!(n − r)!), unordered selections of r from n.
Explanation
C(n, r) = C(n, n − r).
Permutations formula
Answer: P(n, r) = n! / (n − r)!, ordered selections of r from n.
Explanation
n! = n(n−1)…1; 0! = 1.
What is the product rule and sum rule?
Answer: Product: a task with m choices followed by n choices has m·n outcomes. Sum: choosing from m or n disjoint options gives m + n.
Explanation
Foundation of counting.
Logic
What is a proposition?
Answer: A statement that is either true or false, but not both.
Explanation
'2 + 2 = 4' is a proposition; 'x > 3' is not until x is specified.
What do the quantifiers ∀ and ∃ mean, and how are they negated?
Answer: ∀ = for all; ∃ = there exists. ¬∀x P(x) ≡ ∃x ¬P(x); ¬∃x P(x) ≡ ∀x ¬P(x).
Explanation
Order of mixed quantifiers matters.
State De Morgan's laws.
Answer: ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q
Explanation
Also for sets: complement of a union is the intersection of complements.
What are the converse, inverse, and contrapositive of p → q?
Answer: Converse: q → p. Inverse: ¬p → ¬q. Contrapositive: ¬q → ¬p (equivalent to the original).
Explanation
Converse and inverse are equivalent to each other.
Truth table for implication p → q
Answer: False only when p is true and q is false; true otherwise.
Explanation
A false hypothesis makes the implication vacuously true.
Functions
What are floor and ceiling functions?
Answer: ⌊x⌋ is the greatest integer ≤ x; ⌈x⌉ is the least integer ≥ x.
Explanation
⌊−2.5⌋ = −3, ⌈−2.5⌉ = −2.
Injective, surjective, bijective?
Answer: Injective (one-to-one): distinct inputs give distinct outputs. Surjective (onto): every output is hit. Bijective: both, so an inverse exists.
Explanation
Bijection between sets means equal cardinality.
Sets
What is the inclusion-exclusion principle for two sets?
Answer: |A ∪ B| = |A| + |B| − |A ∩ B|
Explanation
For three sets add back the triple intersection.
What is the Cartesian product A × B?
Answer: The set of all ordered pairs (a, b) with a ∈ A and b ∈ B; |A × B| = |A| · |B|.
Explanation
Basis for relations.
What is the power set and its size?
Answer: The set of all subsets of A; if |A| = n, the power set has 2ⁿ elements.
Explanation
Includes the empty set and A itself.
What are union, intersection, difference, and complement?
Answer: A ∪ B: elements in either; A ∩ B: in both; A − B: in A not B; Aᶜ: not in A.
Explanation
Venn diagrams visualize them.
Proofs
How does mathematical induction work?
Answer: Prove the base case (n = 1), then show that if the statement holds for k it holds for k + 1.
Explanation
Strong induction assumes all cases up to k.
What is proof by contrapositive?
Answer: Prove ¬q → ¬p instead of p → q.
Explanation
Useful when the negation is easier to work with.
What is proof by contradiction?
Answer: Assume the statement is false and derive a contradiction, so the statement must be true.
Explanation
Classic: √2 is irrational.
What is a direct proof?
Answer: Assume the hypothesis and derive the conclusion through valid steps.
Explanation
Used for 'if p then q' statements.
Make your own deck like this
Upload a PDF, Word doc, or slides and Quizcard writes the cards for you, or build them by hand. Free to start, no credit card required.