MIT ADVANCED DISCRETE
STRUCTURES REAL EXAM
CORE 2026 VERIFIED
ANSWERS WITH RATIONALES
Discrete Mathematics Final Exam
Question 1
Let \(A\) and \(B\) be finite sets such that \(\vert{}A\vert{} = 15\),
\(\vert{}B\vert{} = 22\), and \(\vert{}A \cup B\vert{} = 30\). Find the
cardinality of the power set of \(A \cap B\), denoted as
\(\vert{}\mathcal{P}(A \cap B)\vert{}\).
A. 7
B. 32
C. 128
D. 256 [1]
Answer: C. 128
Rationale: By the Principle of Inclusion-Exclusion, \(\vert{}A \cap
B\vert{} = \vert{}A\vert{} + \vert{}B\vert{} - \vert{}A \cup B\vert{} =
15 + 22 - 30 = 7\). The cardinality of the power set of a set with \(n\)
elements is given by \(2^{n}\). Therefore, \(\vert{}\mathcal{P}(A \cap
B)\vert{} = 2^7 = 128\). [1]
Question 2
Which of the following propositions is logically equivalent to the
conditional statement \(p \rightarrow q\)?
A. \(\neg p \rightarrow \neg q\)
B. \(q \rightarrow p\)
C. \(\neg q \rightarrow \neg p\)
D. \(\neg p \wedge q\)
,Answer: C. \(\neg q \rightarrow \neg p\)
Rationale: The statement \(\neg q \rightarrow \neg p\) is the
contrapositive of the conditional statement \(p \rightarrow q\). A
conditional statement and its contrapositive are always logically
equivalent (\(p \rightarrow q \equiv \neg q \rightarrow \neg p\)).
Question 3
Determine the truth value of the quantified statement \(\forall x \in
\mathbb{R} \, (x^2 \ge x)\) where the domain consists of all real
numbers.
A. True, because squaring any number always yields a value greater than
or equal to the base.
B. False, because counterexamples exist in the open interval \((0, 1)\).
C. True, because it holds for all negative integers and zero.
D. False, because it fails for all real numbers greater than 1. [1, 2, 3]
Answer: B. False, because counterexamples exist in the open
interval \((0, 1)\).
Rationale: The universally quantified statement asserts the inequality
holds for all real numbers. However, choosing \(x = 0.5\) yields \(0.25
\ge 0.5\), which is false. Since a counterexample exists within the
domain, the statement is false. [1, 2]
Question 4
How many distinct biographical arrangements can be formed using all
the letters in the word "DISCRETE"?
A. 40,320
B. 20,160
C. 10,080
D. 5,040
Answer: B. 20,160
Rationale: The word "DISCRETE" contains 8 letters total, where the
letter 'E' repeats 2 times and all other letters occur exactly once. The
number of unique permutations is calculated using the formula for
permutations with repetition: \(\frac{8!}{2!} = \frac{40,320}{2} =
20,160\). [1]
,Question 5
A simple graph \(G\) has 12 vertices and every vertex has a degree of 4.
How many edges does graph \(G\) possess?
A. 48
B. 36
C. 24
D. 12
Answer: C. 24
Rationale: According to the Handshaking Lemma, the sum of the
degrees of all vertices in a graph is equal to twice the number of edges
(\(\sum \deg(v) = 2\vert{}E\vert{}\)). Here, \(12 \times 4 =
2\vert{}E\vert{}\), which means \(48 = 2\vert{}E\vert{}\), solving to
\(\vert{}E\vert{} = 24\).
Question 6
Using modular arithmetic, determine the remainder when \(3^{45}\) is
divided by 7.
A. 1
B. 3
C. 5
D. 6 [1]
Answer: D. 6
Rationale: By Fermat's Little Theorem, since 7 is prime and \(\gcd(3, 7)
= 1\), we have \(3^{7-1} \equiv 3^6 \equiv 1 \pmod 7\). We rewrite the
exponent: \(45 = 6 \times 7 + 3\). Thus, \(3^{45} \equiv (3^6)^7 \times
3^3 \equiv 1^7 \times 27 \equiv 27 \pmod 7\). Since \(27 = 3 \times 7 +
6\), the remainder is 6. [1]
Question 7
Which binary relation \(R\) defined on the set of all integers
\(\mathbb{Z}\) is an equivalence relation?
A. \(xRy\) if and only if \(x \le y\)
B. \(xRy\) if and only if \(x + y\) is even
C. \(xRy\) if and only if \(x - y = 1\)
D. \(xRy\) if and only if \(x \times y > 0\)
, Answer: B. \(xRy\) if and only if \(x + y\) is even
Rationale: An equivalence relation must be reflexive, symmetric, and
transitive. \(x+x=2x\) is always even (reflexive); if \(x+y\) is even,
\(y+x\) is even (symmetric); if \(x+y\) and \(y+z\) are even, \(x\) and
\(y\) share parity, and \(y\) and \(z\) share parity, meaning \(x\) and
\(z\) share parity, making \(x+z\) even (transitive). [1]
Question 8
What is the coefficient of the term \(x^{3}y^{5}\) in the expansion of
\((2x - y)^8\)?
A. -448
B. 448
C. -1792
D. 1792
Answer: A. -448
Rationale: By the Binomial Theorem, the general term is given by
\(\binom{8}{k} (2x)^{8-k} (-y)^k\). To match \(x^{3}y^{5}\), we set
\(k = 5\). The term evaluates to \(\binom{8}{5} (2x)^3 (-y)^5 = 56
\times 8x^3 \times (-1)y^5 = -448x^3y^5\).
Question 9
Consider a function \(f: \mathbb{Z} \rightarrow \mathbb{Z}\) defined
by \(f(x) = 2x + 3\). Which of the following statements accurately
describes \(f\)?
A. \(f\) is bijective.
B. \(f\) is injective (one-to-one) but not surjective (onto).
C. \(f\) is surjective (onto) but not injective (one-to-one).
D. \(f\) is neither injective nor surjective. [1, 2, 3, 4, 5]
Answer: B. \(f\) is injective (one-to-one) but not surjective
(onto).
Rationale: It is injective because \(2x_1 + 3 = 2x_2 + 3 \implies x_1 =
x_2\). It is not surjective because odd images cannot map to even
targets; for example, there is no integer \(x\) such that \(2x + 3 = 0\)
(\(2x = -3\) has no integer solution). [1]
Question 10
STRUCTURES REAL EXAM
CORE 2026 VERIFIED
ANSWERS WITH RATIONALES
Discrete Mathematics Final Exam
Question 1
Let \(A\) and \(B\) be finite sets such that \(\vert{}A\vert{} = 15\),
\(\vert{}B\vert{} = 22\), and \(\vert{}A \cup B\vert{} = 30\). Find the
cardinality of the power set of \(A \cap B\), denoted as
\(\vert{}\mathcal{P}(A \cap B)\vert{}\).
A. 7
B. 32
C. 128
D. 256 [1]
Answer: C. 128
Rationale: By the Principle of Inclusion-Exclusion, \(\vert{}A \cap
B\vert{} = \vert{}A\vert{} + \vert{}B\vert{} - \vert{}A \cup B\vert{} =
15 + 22 - 30 = 7\). The cardinality of the power set of a set with \(n\)
elements is given by \(2^{n}\). Therefore, \(\vert{}\mathcal{P}(A \cap
B)\vert{} = 2^7 = 128\). [1]
Question 2
Which of the following propositions is logically equivalent to the
conditional statement \(p \rightarrow q\)?
A. \(\neg p \rightarrow \neg q\)
B. \(q \rightarrow p\)
C. \(\neg q \rightarrow \neg p\)
D. \(\neg p \wedge q\)
,Answer: C. \(\neg q \rightarrow \neg p\)
Rationale: The statement \(\neg q \rightarrow \neg p\) is the
contrapositive of the conditional statement \(p \rightarrow q\). A
conditional statement and its contrapositive are always logically
equivalent (\(p \rightarrow q \equiv \neg q \rightarrow \neg p\)).
Question 3
Determine the truth value of the quantified statement \(\forall x \in
\mathbb{R} \, (x^2 \ge x)\) where the domain consists of all real
numbers.
A. True, because squaring any number always yields a value greater than
or equal to the base.
B. False, because counterexamples exist in the open interval \((0, 1)\).
C. True, because it holds for all negative integers and zero.
D. False, because it fails for all real numbers greater than 1. [1, 2, 3]
Answer: B. False, because counterexamples exist in the open
interval \((0, 1)\).
Rationale: The universally quantified statement asserts the inequality
holds for all real numbers. However, choosing \(x = 0.5\) yields \(0.25
\ge 0.5\), which is false. Since a counterexample exists within the
domain, the statement is false. [1, 2]
Question 4
How many distinct biographical arrangements can be formed using all
the letters in the word "DISCRETE"?
A. 40,320
B. 20,160
C. 10,080
D. 5,040
Answer: B. 20,160
Rationale: The word "DISCRETE" contains 8 letters total, where the
letter 'E' repeats 2 times and all other letters occur exactly once. The
number of unique permutations is calculated using the formula for
permutations with repetition: \(\frac{8!}{2!} = \frac{40,320}{2} =
20,160\). [1]
,Question 5
A simple graph \(G\) has 12 vertices and every vertex has a degree of 4.
How many edges does graph \(G\) possess?
A. 48
B. 36
C. 24
D. 12
Answer: C. 24
Rationale: According to the Handshaking Lemma, the sum of the
degrees of all vertices in a graph is equal to twice the number of edges
(\(\sum \deg(v) = 2\vert{}E\vert{}\)). Here, \(12 \times 4 =
2\vert{}E\vert{}\), which means \(48 = 2\vert{}E\vert{}\), solving to
\(\vert{}E\vert{} = 24\).
Question 6
Using modular arithmetic, determine the remainder when \(3^{45}\) is
divided by 7.
A. 1
B. 3
C. 5
D. 6 [1]
Answer: D. 6
Rationale: By Fermat's Little Theorem, since 7 is prime and \(\gcd(3, 7)
= 1\), we have \(3^{7-1} \equiv 3^6 \equiv 1 \pmod 7\). We rewrite the
exponent: \(45 = 6 \times 7 + 3\). Thus, \(3^{45} \equiv (3^6)^7 \times
3^3 \equiv 1^7 \times 27 \equiv 27 \pmod 7\). Since \(27 = 3 \times 7 +
6\), the remainder is 6. [1]
Question 7
Which binary relation \(R\) defined on the set of all integers
\(\mathbb{Z}\) is an equivalence relation?
A. \(xRy\) if and only if \(x \le y\)
B. \(xRy\) if and only if \(x + y\) is even
C. \(xRy\) if and only if \(x - y = 1\)
D. \(xRy\) if and only if \(x \times y > 0\)
, Answer: B. \(xRy\) if and only if \(x + y\) is even
Rationale: An equivalence relation must be reflexive, symmetric, and
transitive. \(x+x=2x\) is always even (reflexive); if \(x+y\) is even,
\(y+x\) is even (symmetric); if \(x+y\) and \(y+z\) are even, \(x\) and
\(y\) share parity, and \(y\) and \(z\) share parity, meaning \(x\) and
\(z\) share parity, making \(x+z\) even (transitive). [1]
Question 8
What is the coefficient of the term \(x^{3}y^{5}\) in the expansion of
\((2x - y)^8\)?
A. -448
B. 448
C. -1792
D. 1792
Answer: A. -448
Rationale: By the Binomial Theorem, the general term is given by
\(\binom{8}{k} (2x)^{8-k} (-y)^k\). To match \(x^{3}y^{5}\), we set
\(k = 5\). The term evaluates to \(\binom{8}{5} (2x)^3 (-y)^5 = 56
\times 8x^3 \times (-1)y^5 = -448x^3y^5\).
Question 9
Consider a function \(f: \mathbb{Z} \rightarrow \mathbb{Z}\) defined
by \(f(x) = 2x + 3\). Which of the following statements accurately
describes \(f\)?
A. \(f\) is bijective.
B. \(f\) is injective (one-to-one) but not surjective (onto).
C. \(f\) is surjective (onto) but not injective (one-to-one).
D. \(f\) is neither injective nor surjective. [1, 2, 3, 4, 5]
Answer: B. \(f\) is injective (one-to-one) but not surjective
(onto).
Rationale: It is injective because \(2x_1 + 3 = 2x_2 + 3 \implies x_1 =
x_2\). It is not surjective because odd images cannot map to even
targets; for example, there is no integer \(x\) such that \(2x + 3 = 0\)
(\(2x = -3\) has no integer solution). [1]
Question 10
