Overlap of Propositional Logic and Elementary Set Question

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.

Answer 1

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?

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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