Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am a bit stuck on a basic sets problem:

We know from resolutions that $(p \lor q) \land (\neg p \lor r) \to q \lor r$. Use this fact to show that $(P \cup Q) \cap (\overline{P} \cup R) \subseteq (Q \cup R)$

I remember reading that it might be helpful to think of $\cup$ as $\lor$ and $\cap$ as $\land$, but this question seems to be saying they are interchangeable? I also don't understand what is meant by "use this fact to show".

I'm not looking for an answer, but it would be really helpful if someone could explain how to approach this type of problem, and what it even means.

share|cite|improve this question
What is $\overline{P}$? – Git Gud Feb 2 '13 at 19:02
@GitGud My textbook says $\overline{P}$ denotes the complement of $P$ with respect to $U$. Is that not standard notation? – Paul Spinelli Feb 2 '13 at 19:04
It is, it's just that you didn't mention the universe $U$ in your question and I wanted to be sure what it meant. You probably meant "$\overline{P}$ denotes the complemente of $P$". – Git Gud Feb 2 '13 at 19:06
up vote 10 down vote accepted

They’re not interchangeable, but the statement about sets can be reduced to an instance of the logical statement. Let

$$\begin{align*} p&\text{ mean }x\in P,\\ q&\text{ mean }x\in Q,\text{ and}\\ r&\text{ mean }x\in R\;. \end{align*}$$

Then $x\in(P \cup Q) \cap (\overline{P} \cup R)$ if and only if $x\in(P\cup Q)$ and $x\in(\overline{P}\cup R)$, which is the case if and only if $(p\lor q)\land(\neg p\lor r)$. Similarly, $x\in Q \cup R$ if and only if $q\lor r$. Can you finish it from there?

share|cite|improve this answer
I understand much better now, thank you – Paul Spinelli Feb 2 '13 at 19:14
@Paul: You’re welcome. – Brian M. Scott Feb 2 '13 at 19:19

Just use : $$x\in A\cap B \iff [x\in A\land x \in B]$$ $$x\in A\cup B \iff [x\in A\lor x \in B]$$ $$x\in A^c \iff \lnot (x \in A)$$ Finally: $$A\subseteq B\iff \forall x[x\in A\implies x\in B]$$

share|cite|improve this answer

Let $p$ be the statement "$x\in P$"; $q$, "$x\in Q$"; $r$, "$x\in R$". Then, realize that (for example) $\neg p$ is the same as the statement "$x\in\overline{P}$", and $p\vee q$ is the same as the statement "$x\in P\cup Q$". Now, use the fact.

share|cite|improve this answer

Let $x\in (P \cup Q) \cap (\overline{P} \cup R)$. So $$x\in (P \cup Q)\wedge x\in (\overline{P} \cup R) $$ So $$[P(x)\vee Q(x)]\wedge[\overline{P}(x)\vee R(x)]$$ So $$[P(x)\vee Q(x)]\wedge[\sim P(x)\vee R(x)]$$ But as your assumption, the latter statement is equal to $Q(x)\vee R(x)$. This means that $x\in(Q\cup R)$.

share|cite|improve this answer
Well done! Nice question, nice answer! +1 – amWhy Feb 3 '13 at 0:19

Hint: You'll want to choose specific statements for $p$, $q$, and $r$ so that any element $x \in (P \cup Q) \cap (\overline{P} \cup R)$ satisfies $(p \vee q) \wedge (\sim p \vee r)$.

share|cite|improve this answer
I love your answer. – Nancy Rutkowskie Feb 2 '13 at 19:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.