Podcast
Questions and Answers
Which property must a relation satisfy to be considered an equivalence relation?
Which property must a relation satisfy to be considered an equivalence relation?
- Reflexivity and Symmetry only
- Reflexivity, Symmetry, and Transitivity (correct)
- Reflexivity and Transitivity only
- Symmetry and Transitivity only
If a divides b and b divides c, then a divides c. This statement illustrates the reflexive property of divisibility.
If a divides b and b divides c, then a divides c. This statement illustrates the reflexive property of divisibility.
False (B)
In the context of modular arithmetic Z/14, what is the additive identity?
In the context of modular arithmetic Z/14, what is the additive identity?
[0]
According to the pigeonhole principle, if you have more pigeons than ______, then at least one hole must contain more than one pigeon.
According to the pigeonhole principle, if you have more pigeons than ______, then at least one hole must contain more than one pigeon.
Match the set operation with its corresponding definition.
Match the set operation with its corresponding definition.
Which of the following is the correct formula for permutations?
Which of the following is the correct formula for permutations?
The greatest common divisor (gcd) of two positive integers a and b is always greater than or equal to both a and b.
The greatest common divisor (gcd) of two positive integers a and b is always greater than or equal to both a and b.
What is the remainder when -10 is divided by 7, as per the division algorithm, where the remainder must be non-negative?
What is the remainder when -10 is divided by 7, as per the division algorithm, where the remainder must be non-negative?
A function f from set A to set B is onto (or surjective) if every element in ______ has a corresponding element in A.
A function f from set A to set B is onto (or surjective) if every element in ______ has a corresponding element in A.
What does the inclusion-exclusion principle calculate for two sets A and B?
What does the inclusion-exclusion principle calculate for two sets A and B?
A relation R on a set A is symmetric if and only if for every a and b in A, if (a, b) is in R, then (b, a) is also in R.
A relation R on a set A is symmetric if and only if for every a and b in A, if (a, b) is in R, then (b, a) is also in R.
Explain the difference between a permutation and a combination.
Explain the difference between a permutation and a combination.
The ______ theorem states that every integer greater than 1 can be written uniquely as a product of prime numbers, up to the order of the factors.
The ______ theorem states that every integer greater than 1 can be written uniquely as a product of prime numbers, up to the order of the factors.
Given a set A = {1, 2, 3, 4}, how many subsets of size 2 can be formed?
Given a set A = {1, 2, 3, 4}, how many subsets of size 2 can be formed?
The function $f(x) = x^2$ from the set of real numbers to the set of non-negative real numbers is injective (one-to-one).
The function $f(x) = x^2$ from the set of real numbers to the set of non-negative real numbers is injective (one-to-one).
What is Z/n?
What is Z/n?
If a relation is both symmetric and antisymmetric, then the elements are related to ______
If a relation is both symmetric and antisymmetric, then the elements are related to ______
Which of the following is a valid interpretation of mathematical induction?
Which of the following is a valid interpretation of mathematical induction?
Every function has an inverse
Every function has an inverse
What is Cantor's diagonalization argument used to prove?
What is Cantor's diagonalization argument used to prove?
Flashcards
Directed Graph (Relations)
Directed Graph (Relations)
A directed graph visually represents a relation by using nodes for elements of a set and directed edges to indicate the relationships between them.
Equivalence Relation Criteria
Equivalence Relation Criteria
For a relation to be an equivalence relation, it must be reflexive, symmetric, and transitive.
Equivalence Class
Equivalence Class
An equivalence class is a set of all elements related to each other within a set following an equivalence relation.
b divides ac, prove b divides cd
b divides ac, prove b divides cd
Signup and view all the flashcards
Modular Arithmetic
Modular Arithmetic
Signup and view all the flashcards
Multiplicative Inverse in Z/n
Multiplicative Inverse in Z/n
Signup and view all the flashcards
Well-Defined Map
Well-Defined Map
Signup and view all the flashcards
Combinations
Combinations
Signup and view all the flashcards
Permutations
Permutations
Signup and view all the flashcards
Division Algorithm Theorem
Division Algorithm Theorem
Signup and view all the flashcards
Prime Factorization Theorem
Prime Factorization Theorem
Signup and view all the flashcards
Pigeonhole Principle
Pigeonhole Principle
Signup and view all the flashcards
Inclusion-Exclusion Principle (Sets)
Inclusion-Exclusion Principle (Sets)
Signup and view all the flashcards
Divisibility Transitivity
Divisibility Transitivity
Signup and view all the flashcards
Study Notes
- The exam is for MATH 381, Practice Midterm Exam II, Discrete Mathematics
- It is instructed by Daping Weng, and is scheduled for April 11th, 2025
- The exam is 50 minutes long and has 5 questions across 7 pages; the total points possible are 100
- Textbooks, lecture notes, phones, calculators, and computers are prohibited
- Showing work is required to receive partial credit
Question 1
- Consider the relation R = {(1, 1), (1, 3), (2, 2), (3, 1)} on the set {1, 2, 3}
- Part (a) asks about drawing a directed graph that represents the relation R
- Part (b) asks to explain why R is not an equivalence relation
- Part (c) asks what element can be added to R to make it an equivalence relation
- Part (d) asks for a list of all equivalence classes resulting from the equivalence relation in part (c)
Question 2
- Given positive integers a and b, let d = gcd(a, b)
- Given c, another positive integer such that b divides ac, prove b divides cd
- Write d as a linear combination of a and b
Question 3
- Consider Z/14 which refers to integers modulo 14
- Part (a) asks to compute [5]([6] – [10]) in Z/14. Write the answer as [a] with 0 ≤ a < 14
- Part (b) asks if [8] has a multiplicative inverse in Z/14, such that [8][a] = [1]
- Part (c) involves a map f: Z/14 → Z/3 defined as f([a]) = [a] and asks whether this map is well-defined and why or why not
Question 4
- Compute the size of each of the following sets using permutation and combination numbers, without evaluating
- Part (a) is regarding the set of 5-element subsets in an 8-element set
- Part (b) is regarding the ways to put 100 identical blank exam papers into 3 bins where some bins may be empty
- Part (c) is regarding the permutations of the letters ABCDEFG that contain substrings BC and EF
- Part (d) is regarding the subset of permutations in part (c) where the substring EF appears before the letter D
Question 5
- True or False questions, no justification is needed
- Part (a): "-10 divided by 7 has a quotient -1 and a remainder -3" under the division algorithm theorem
- Part (b): "Any integer can be factored into a product of positive prime numbers" under the prime factorization theorem
- Part (c): If 10 students walked into 3 classrooms, then there must be at least one classroom with 4 or more students, according to the pigeonhole principle
- Part (d): |A ∪ B| = |A| + |B| + |A ∩ B| by the inclusion-exclusion principle
- Part (e): The divisibility relation is transitive (i.e., if a|b and b|c, then a|c)
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
