Discrete Mathematics · Quiz 1 · May 2026

**1. Distinguish membership from nesting:** The required element is the set \(\{2\}\), not the number 2 or the set \(\{\{2\}\}\). Examine the elements directly inside each outermost pair of braces. **2. Identify the sets:** B, C and D each list \(\{2\}\) as a direct element. A contains only 2; E contains only \(\{\{2\}\}\). **Answer: B, C, D — Sets B, C and D contain \(\{2\}\).** A: **Incorrect:** Its sole element is 2, not \(\{2\}\). B: **Correct:** It directly lists \(\{2\}\) alongside 2. C: **Correct:** It directly lists \(\{2\}\) alongside \(\{\{2\}\}\). D: **Correct:** Its first direct element is \(\{2\}\). E: **Incorrect:** Its sole direct element is \(\{\{2\}\}\), one nesting level deeper.

**1. Identify the elements:** \(\{\varnothing\}\) has exactly one element, the empty set. Thus \(\varnothing\in\{\varnothing\}\), but \(\{\varnothing\}\notin\{\varnothing\}\). **2. Check subsets and deeper nesting:** The empty set is a proper subset of every nonempty set. Also \(\{\varnothing\}\subset\{\varnothing,\{\varnothing\}\}\). In \(\{\{\varnothing\}\}\), the sole element is \(\{\varnothing\}\), not \(\varnothing\). **Answer: A, C, D — A, C and D.** A: **Correct:** The empty set is the sole element of \(\{\varnothing\}\). B: **Incorrect:** The sole element is \(\varnothing\), not its singleton. C: **Correct:** The empty set is properly contained in the nonempty singleton. D: **Correct:** Its only element is present on the right, which also has an additional element. E: **Incorrect:** The outer singleton contains \(\{\varnothing\}\), not \(\varnothing\).

**1. Check inclusions:** Adding C to a union cannot remove elements, so \(A\cup B\subseteq A\cup B\cup C\). Adding C to an intersection can remove elements, so the proposed reverse inclusion is not universal. **2. Simplify the partition:** \[(A\cap B)\cup(A\cap\overline B)=A\cap(B\cup\overline B)=A.\] The result need not equal B. **Answer: A, C — A and C.** A: **Correct:** Adding another set to a union preserves every existing member. B: **Incorrect:** The universal inclusion goes the other way; take \(A=B=\{1\}\), \(C=\varnothing\). C: **Correct:** The two parts partition A according to membership in B. D: **Incorrect:** The expression equals A and need not equal B.

**1. Identify the unsupported choices:** From \(P(c)\lor Q(c)\), neither \(P(c)\) alone in step 3 nor \(Q(c)\) alone in step 5 follows. Those invalid choices also invalidate the universal claims in steps 4 and 6. **2. Check the last inference:** If either universal claim were established, disjunction introduction would justify step 7. Its inference rule is valid, although the preceding proof has not established its premises. **3. Disprove the original claim:** On domain \(\{1,2\}\), let P hold only at 1 and Q only at 2. Then \(\forall x(P(x)\lor Q(x))\) is true, while both \(\forall xP(x)\) and \(\forall xQ(x)\) are false. **Answer: A, B, C, D — Steps 3, 4, 5 and 6.** A: **Correct:** Erroneous: a disjunction does not imply its first disjunct. B: **Correct:** Erroneous as part of this proof: its required arbitrary-instance premise was not established. C: **Correct:** Erroneous: a disjunction does not imply its second disjunct. D: **Correct:** Erroneous as part of this proof: it generalizes an unsupported premise. E: **Incorrect:** Not selected: disjunction introduction itself is valid if a universal premise is available.

**1. Read the multiplicities:** In \(P=\{3\cdot a,2\cdot b,1\cdot c\}\), b has multiplicity 2; in \(Q=\{2\cdot a,3\cdot b,4\cdot d\}\), it has multiplicity 3. **2. Apply intersection:** \(m_{P\cap Q}(b)=\min(2,3)=2\). **Answer: 2.**

**1. Read the multiplicities:** d is absent from \(P=\{3\cdot a,2\cdot b,1\cdot c\}\), so its multiplicity is 0. In \(Q=\{2\cdot a,3\cdot b,4\cdot d\}\), it is 4. **2. Apply union:** \(m_{P\cup Q}(d)=\max(0,4)=4\). **Answer: 4.**

**1. Choose the first index:** The domain consists of all nonnegative integers, so the induction basis is n=0. **2. Verify the identity:** The left side is \(1^2=1\); the right side is \((0+1)(2(0)+1)(2(0)+3)/3=1\). **Answer: 0.**

**1. Apply the inductive hypothesis:** Replace the sum through \((2k+1)^2\) with \((k+1)(2k+1)(2k+3)/3\), retaining the new term \((2k+3)^2\). Thus \[\text{(I)}=\frac{(k+1)(2k+1)(2k+3)}3+(2k+3)^2.\] **2. Factor the common term:** \[\text{(II)}=(2k+3)\left[\frac{(k+1)(2k+1)}3+(2k+3)\right].\] **3. Finish the step:** Combining the bracket gives \((2k^2+9k+10)/3=(2k+5)(k+2)/3\), which is the required formula at k+1. **Answer: C — The substitution and factorization in option C.** A: **Incorrect:** Its first blank omits the added square. B: **Incorrect:** Its first blank omits the added square and its second has an incorrect denominator distribution. C: **Correct:** It retains the square and factors the common term correctly. D: **Incorrect:** The displayed blanks reverse the substitution and factoring order.

**1. Remove the outer implication:** Write \(F=(\neg p\Rightarrow q)\Rightarrow(p\Leftrightarrow\neg q)\). Its antecedent is \(p\lor q\), so \[F\equiv\neg(p\lor q)\lor[(p\land\neg q)\lor(\neg p\land q)].\] **2. Simplify:** This is true at (p,q)=(F,F),(T,F),(F,T) and false only at (T,T). Hence \(F\equiv\neg p\lor\neg q\). **Answer: D — \(\neg p\lor\neg q\).** A: **Incorrect:** At p=q=true, \(p\lor q\) is true but F is false. B: **Incorrect:** At p=false,q=true, \(p\lor\neg q\) is false but F is true. C: **Incorrect:** At p=true,q=false, \(\neg p\lor q\) is false but F is true. D: **Correct:** It is false exactly when both p and q are true.

**1. Simplify the proposition:** The original implication is false only when p and q are both true, so it equals \(\neg p\lor\neg q\). **2. Check CNF syntax:** A CNF is a conjunction of clauses, each a disjunction of literals. \[(\neg p\lor p)\land(\neg p\lor\neg q)\] is CNF; its first clause is a tautology, so the expression remains equivalent to the original. **Answer: C — \((\neg p\lor p)\land(\neg p\lor\neg q)\).** A: **Incorrect:** It is equivalent but has a negated compound and nested conjunctions rather than CNF syntax. B: **Incorrect:** It is an OR of conjunctions, hence DNF rather than CNF. C: **Correct:** It is an AND of literal-disjunction clauses and is equivalent.

**1. Identify satisfying assignments:** The proposition is true at (F,F),(T,F),(F,T). **2. Form the DNF minterms:** \[(\neg p\land\neg q)\lor(p\land\neg q)\lor(\neg p\land q).\] Each term describes one satisfying assignment, and their disjunction is a DNF. **Answer: B — \((\neg p\land\neg q)\lor(p\land\neg q)\lor(\neg p\land q)\).** A: **Incorrect:** Its first term negates a compound disjunction; it is not in DNF until De Morgan’s law is applied. B: **Correct:** It is the disjunction of the three satisfying minterms. C: **Incorrect:** It is an AND of clauses, so it is CNF rather than DNF.

**1. Compute both compositions:** \((f\circ g)(x)=a(cx+d)+b=acx+ad+b\), while \((g\circ f)(x)=c(ax+b)+d=acx+bc+d\). **2. Compare constants:** Equality for every x holds exactly when \(ad+b=bc+d\). Identical functions, with a=c and b=d, satisfy this condition. **3. Test weaker conditions:** Taking a=c=2,b=0,d=1 satisfies a=c but fails commutation. Taking a=1,b=1,c=2,d=2 satisfies ad=bc but still has unequal composition constants. **Answer: A, B — \(ad+b=bc+d\); or identical functions a=c and b=d.** A: **Correct:** This is the exact equality of the constant terms. B: **Correct:** Identical functions always commute with themselves. C: **Incorrect:** Equality of ad and bc alone omits the remaining b and d terms. D: **Incorrect:** Either equality alone need not ensure equal composition constants. E: **Incorrect:** A is necessary and sufficient, and B is sufficient.

**1. Check infinity:** The natural numbers are infinite but countable, disproving the first statement. **2. Check closure:** Two countable sets can be enumerated by interleaving their lists and skipping repetitions, so their union is countable. Their intersection and set difference are subsets of a countable set and hence also countable. **Answer: B, C, D — Union, intersection and set difference are countable.** **Convention note:** “Countable” includes finite sets here, as is standard. An intersection or difference may be finite or empty. A: **Incorrect:** The natural numbers give an infinite countable counterexample. B: **Correct:** Interleaving enumerations lists the union. C: **Correct:** The intersection is a subset of either countable set. D: **Correct:** The difference is a subset of the first countable set.

**1. Locate the cancellation:** Step 4 is \((a-b)(a+b)=b(a-b)\). Step 5 cancels a-b to claim a+b=b. **2. Check the divisor:** Since a=b, \(a-b=0\). Cancelling that factor divides by zero and is invalid. The later steps use valid algebra on the already invalid result. **Answer: C — Step 5.** A: **Incorrect:** Subtracting b² from both sides is valid. B: **Incorrect:** The factorization is valid. C: **Correct:** It cancels the zero factor a−b. D: **Incorrect:** Substituting a=b is valid; the error already occurred in step 5. E: **Incorrect:** Dividing by positive b is valid; the earlier false premise caused the contradiction.

**1. Sum over j:** For fixed i, \[\sum_{j=0}^3(3i+2j)=4(3i)+2(0+1+2+3)=12i+12.\] **2. Sum over i:** \(\sum_{i=0}^2(12i+12)=12(0+1+2)+3(12)=36+36=72\). **Answer: 72.**

**1. Enumerate S1:** The negative multiples of 10 are \(-10,-20,-30,\ldots\), indexed by positive integers through n↦−10n. Thus S1 is countably infinite. **2. Classify S2:** A nondegenerate real interval between 0 and 2 is uncountable, whether its endpoints are included or excluded. **Answer: B — S1 countable; S2 uncountable.** A: **Incorrect:** A real interval is uncountable. B: **Correct:** The discrete multiples are enumerable, while the real interval is not. C: **Incorrect:** This reverses the cardinality classifications. D: **Incorrect:** The negative multiples are countable.

**1. Compute the first value:** Starting with \(f(0)=3\), \(f(1)=2f(0)+3=2(3)+3=9\). **2. Compute the requested value:** \(f(2)=2f(1)+3=2(9)+3=21\). **Answer: 21.**

**1. Apply the recurrence twice:** \(f(1)=2(3)+3=9\), then \(f(2)=2(9)+3=21\). **2. Apply it once more:** \(f(3)=2f(2)+3=2(21)+3=45\). **Answer: 45.**