# Overlap of Propositional Logic and Elementary Set Question

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.

-
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

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?

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

-

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.

-

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

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

-
I love your answer. – Nancy Rutkowskie Feb 2 '13 at 19:53