Venn diagrams and set identities - Discrete Math

1. Which of the following set identities is equivalent to the distributive law $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$?
   Answer: $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$ by complement distribution To verify equivalence, we can show that $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$ follows from the distributive law. Since $A \setminus X = A \cap X^c$, we have: $A \setminus (B \cap C) = A \cap (B \cap C)^c = A \cap (B^c \cup C^c)$ (by De Morgan's law) $= (A \cap B^c) \cup (A \cap C^c)$ (by distributive law) $= (A \setminus B) \cup (A \setminus C)$. Option A is the other distributive law, not equivalent but dual. Option B is De Morgan's law, which is independent. Option D involves symmetric difference, which has different properties than the basic distributive law.
2. Consider the set identity $(A \cup B)^c = A^c \cap B^c$. If this identity fails to hold for specific sets $A$ and $B$, what can we conclude about the universal set $U$?
   Answer: The identity cannot fail; it holds for all sets $A$ and $B$ in any universal set $U$ This is one of De Morgan's laws, which is a fundamental set identity that holds universally for any sets A and B within any properly defined universal set U. The identity $(A \cup B)^c = A^c \cap B^c$ is logically equivalent to the statement that an element is not in the union of two sets if and only if it is in neither set. This is always true by the definition of union and complement operations. If someone believes this identity fails, they have made an error in their calculations or definitions, not discovered a counterexample. The identity is independent of whether U is finite or infinite, and applies as long as A and B are subsets of U.
3. Let $A$ and $B$ be sets such that $|A| = 15$, $|B| = 12$, and $|A \cap B| = 7$. If $C$ is a set with $|C| = 10$ such that $A \cap B \cap C = \emptyset$ but $A \cap C \neq \emptyset$ and $B \cap C \neq \emptyset$, what is the maximum possible value of $|(A \cup B) \cap C|$?
   Answer: 10, achieved when $C \subseteq A \cup B$ Since $A \cap B \cap C = \emptyset$, set C can only intersect with $A \setminus B$ and $B \setminus A$, but not with $A \cap B$. We have $|A \setminus B| = 15 - 7 = 8$ and $|B \setminus A| = 12 - 7 = 5$, so $|(A \setminus B) \cup (B \setminus A)| = 8 + 5 = 13$. Since $(A \cup B) \cap C = (A \cap C) \cup (B \cap C) = (A \setminus B) \cap C \cup (B \setminus A) \cap C$, and these are disjoint, we want to maximize $|(A \setminus B) \cap C| + |(B \setminus A) \cap C|$. Since $|C| = 10$ and C cannot intersect $A \cap B$, the maximum occurs when C is entirely contained in $(A \setminus B) \cup (B \setminus A)$, giving $|(A \cup B) \cap C| = |C| = 10$.
4. Consider sets $A$ and $B$ where $A \subseteq U$ and $B \subseteq U$. Which of the following identities can be used to prove that $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ is equivalent to $\overline{A} \cup \overline{(B \cup C)} = (\overline{A} \cup \overline{B}) \cap (\overline{A} \cup \overline{C})$?
   Answer: De Morgan's laws and the distributive law for union over intersection To transform the first identity into the second, we need to take complements of both sides and apply set laws. Starting with $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$, take complements: $\overline{A \cap (B \cup C)} = \overline{(A \cap B) \cup (A \cap C)}$. Apply De Morgan's law to the left side: $\overline{A} \cup \overline{(B \cup C)}$. Apply De Morgan's law to the right side: $\overline{(A \cap B)} \cap \overline{(A \cap C)}$. Apply De Morgan's again: $(\overline{A} \cup \overline{B}) \cap (\overline{A} \cup \overline{C})$. This uses De Morgan's laws and the distributive law for union over intersection (the dual of the original). Option A incorrectly identifies the distributive law type. Options C and D reference laws not primarily used in this transformation.
5. Consider the identity $(A \cup B)^c = A^c \cap B^c$. If this identity is applied iteratively to simplify $\overline{\overline{(P \cap Q)} \cup \overline{(R \cup S)}}$, which of the following intermediate steps is correct?
   Answer: $\overline{\overline{(P \cap Q)}} \cap \overline{\overline{(R \cup S)}} = (P \cap Q) \cap (R \cup S)$ Starting with $\overline{\overline{(P \cap Q)} \cup \overline{(R \cup S)}}$, we first apply De Morgan's law $(A \cup B)^c = A^c \cap B^c$ with $A = \overline{(P \cap Q)}$ and $B = \overline{(R \cup S)}$. This gives us $\overline{\overline{(P \cap Q)}} \cap \overline{\overline{(R \cup S)}}$. Applying the double complement law $\overline{\overline{X}} = X$, we get $(P \cap Q) \cap (R \cup S)$. Option A correctly shows this intermediate step. Option B incorrectly substitutes De Morgan's law before applying the outer complement. Option C shows a later step but not the immediate application of the given identity. Option D uses complement notation instead of the overline notation and shows the final step rather than the intermediate step requested.
6. Which of the following statements about the absorption laws is false?
   Answer: $A \cup (A \cap B) = A$ can be proven using the distributive law: $A \cup (A \cap B) = (A \cup A) \cap (A \cup B) = A \cap (A \cup B) = A$ Statement A contains an error in the proof. The distributive law states $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$, but the reverse $A \cup (A \cap B) = (A \cup A) \cap (A \cup B)$ is not a valid application of distributivity. The correct proof of $A \cup (A \cap B) = A$ uses the fact that $A \cap B \subseteq A$, so $A \cup (A \cap B) = A$. Statement B correctly explains the other absorption law. Statement C is true—absorption laws hold in any Boolean algebra where distributivity is satisfied. Statement D outlines a valid proof technique using subset relationships in both directions.
7. For any sets $A$ and $B$, consider the identity $A \cup B = A \cup (B \setminus A)$. A student claims this can be generalized to three sets as: $A \cup B \cup C = A \cup (B \setminus A) \cup (C \setminus A)$. What is wrong with this generalization?
   Answer: The generalization is actually correct; the student made no error in extending the two-set identity When you encounter set identity questions, the key is to verify whether both sides of an equation represent the same collection of elements. Let's examine whether the student's generalization actually holds. The original identity $A \cup B = A \cup (B \setminus A)$ works because $B \setminus A$ captures exactly the elements in $B$ that aren't already in $A$. When we union this with $A$, we get all elements from both sets without any logical issues. For the three-set case, let's check if $A \cup B \cup C = A \cup (B \setminus A) \cup (C \setminus A)$ by examining what elements each side contains. The left side includes all elements from any of the three sets. The right side includes all elements in $A$, plus elements in $B$ but not $A$, plus elements in $C$ but not $A$. Both expressions actually capture the same collection of elements, making the generalization valid. Choice A incorrectly suggests that $(B \setminus A) \cap (C \setminus A)$ being non-empty creates problems. However, overlapping sets in a union don't cause "overcounting" - union operations naturally handle overlaps by including each element exactly once regardless of how many sets contain it. Choice C proposes an alternative form with $C \setminus (A \cup B)$, but this would exclude elements that are in both $C$ and $B$ (but not $A$), making it incorrect. Choice D incorrectly invokes associativity of set subtraction, which isn't the relevant concept here. Study tip: When evaluating set identities, trace through what types of elements each expression includes rather than getting caught up in apparent complexity.
8. Consider the set equation $X \cup A = X \cup B$ where $A$ and $B$ are known sets. Under what condition on sets $A$ and $B$ does this equation have a unique solution for $X$?
   Answer: Never; the equation $X \cup A = X \cup B$ always has infinitely many solutions for $X$ When you encounter set equations like $X \cup A = X \cup B$, you're dealing with finding all possible sets $X$ that satisfy the equation. The key insight is understanding what union operations tell us about the relationship between sets. Let's analyze what this equation means. For $X \cup A = X \cup B$ to hold, every element in $X \cup A$ must also be in $X \cup B$, and vice versa. This means any element that's in $A$ but not in $X$ must also be in $B$, and any element that's in $B$ but not in $X$ must also be in $A$. The correct answer is B because this equation always has infinitely many solutions regardless of what $A$ and $B$ are. Here's why: you can always choose $X$ to be any set that contains $A \cup B$. For instance, $X = A \cup B$ works, as does $X = A \cup B \cup C$ for any additional set $C$. Since there are infinitely many such choices, there are infinitely many solutions. Choice A is wrong because even when $A = B$, you still have infinitely many solutions—not a unique one. Choice C incorrectly suggests that disjoint sets somehow constrain $X$ uniquely, but they don't. Choice D makes the same error as A, just with extra steps. Study tip: For set equation problems, always check if there are multiple values that satisfy the equation by testing specific examples. Set equations rarely have unique solutions unless there are very restrictive constraints.
9. Let $A$, $B$, and $C$ be subsets of a universal set $U$. Using the distributive law and De Morgan's laws, which expression is logically equivalent to $\overline{(A \cap B) \cup (A \cap C^c)}$?
   Answer: $(\overline{A} \cup \overline{B}) \cap (\overline{A} \cup C)$ Starting with $\overline{(A \cap B) \cup (A \cap C^c)}$, apply De Morgan's law: $\overline{(A \cap B)} \cap \overline{(A \cap C^c)}$. Apply De Morgan's again to each term: $(\overline{A} \cup \overline{B}) \cap (\overline{A} \cup \overline{C^c})$. Since $\overline{C^c} = C$, this becomes $(\overline{A} \cup \overline{B}) \cap (\overline{A} \cup C)$. Option B would result from incorrectly applying distributivity. Option C incorrectly distributes the complement. Option D incorrectly applies De Morgan's law to the union.
10. Consider sets $A$, $B$, and $C$ where $A \triangle B = \{1, 3, 5, 7\}$ and $B \triangle C = \{2, 4, 6, 8\}$. If $A \cap B = \{9, 10\}$, which statement about $A \triangle C$ must be true?
    Answer: $|A \triangle C| \leq 8$ but the exact elements depend on the internal structure of sets $A$, $B$, and $C$ While it's tempting to use the identity $A \triangle C = (A \triangle B) \triangle (B \triangle C)$, this requires careful consideration. We know $A \triangle B = \{1, 3, 5, 7\}$ means these elements are in exactly one of A or B, and $A \cap B = \{9, 10\}$. Similarly, $B \triangle C = \{2, 4, 6, 8\}$. However, to find $A \triangle C$, we need to know which elements from $A \triangle B$ are in A vs B, and which elements from $B \triangle C$ are in B vs C. The symmetric difference operation $\triangle$ is not simply distributive in the way suggested in option C. Without knowing the specific membership of elements in the individual sets, we cannot determine $A \triangle C$ exactly, though we can bound its size. The relationship between the three symmetric differences is more complex than a simple combination.

Start this quiz