If P, Q, R are subsets of the universal set U, then (P ∩ Q ∩ R) ∪ (P^c ∩ Q ∩ R) ∪ Q^c ∪ R^c equals: A. P^c ∪ Q^c ∪ R^c B. P ∩ (Q ∪ R) C. U D. P ∪ (Q ∩ R)

GATE 2006 · Discrete Mathematics · Set Theory · medium

Answer: (P ∩ Q ∩ R) ∪ (P^c ∩ Q ∩ R) ∪ Q^c ∪ R^c = U — option C.

1. Simplify the first two terms: Factor Q ∩ R from both terms: (P ∩ Q ∩ R) ∪ (P^c ∩ Q ∩ R) = (P ∪ P^c) ∩ Q ∩ R. Since P ∪ P^c = U and U ∩ X = X for any X, this equals Q ∩ R.
2. Apply De Morgan's law and complement: The full expression is now (Q ∩ R) ∪ Q^c ∪ R^c = (Q ∩ R) ∪ (Q ∩ R)^c (by De Morgan: Q^c ∪ R^c = (Q ∩ R)^c). A set united with its complement always equals U.