6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ What is $\overline{P}$? $\endgroup$
    – Git Gud
    Feb 2 '13 at 19:02
  • $\begingroup$ @GitGud My textbook says $\overline{P}$ denotes the complement of $P$ with respect to $U$. Is that not standard notation? $\endgroup$ Feb 2 '13 at 19:04
  • $\begingroup$ 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$". $\endgroup$
    – Git Gud
    Feb 2 '13 at 19:06
10
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I understand much better now, thank you $\endgroup$ Feb 2 '13 at 19:14
  • $\begingroup$ @Paul: You’re welcome. $\endgroup$ Feb 2 '13 at 19:19
5
$\begingroup$

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]$$

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ Well done! Nice question, nice answer! +1 $\endgroup$
    – amWhy
    Feb 3 '13 at 0:19
4
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ I love your answer. $\endgroup$ Feb 2 '13 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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