Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

5 Answers

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|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
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
    
Well done! Nice question, nice answer! +1 –  amWhy Feb 3 '13 at 0:19
add comment

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|improve this answer
    
I love your answer. –  Nancy Rutkowskie Feb 2 '13 at 19:53
add comment

Your Answer

 
discard

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.