1

I had to analyse the logical form of some statements, one of them is this:

$P \cup (Q \cap R) \subset A \cup(B \setminus C)$

which I analysed with these expressions:

$\exists x (x \in ( P \lor (Q \land R) \rightarrow x \in (A \lor (B \setminus C)))$

$\exists x (x \in P \lor x \in (Q \land R) \rightarrow (x \in A \lor x \in (B \setminus C)))$

$\exists x (x \in P \lor x \in (Q \land R) \rightarrow(x \in A \lor (x \in B \land \neg(x \in C)))$

Is this correct?

2 Answers2

2

"Simplification" of the statement $$P \cup (Q \cap R) \subset A \cup(B \setminus C),$$

with no further directions as to "what counts as properly simplified?", is somewhat open to interpretation. It seems to me you are aiming to break down the statement using definitions of subset, union, intersection, and setminus.

You've got the right idea, but need to be a bit more careful with your notation: for example $$x \in P \cup(Q \cap R)\iff \Big(x \in P \lor x\in (Q\cap R)\Big)\iff \Big(x \in P \lor (x \in Q \land x\in R)\Big)$$ is a meaningful statement, whereas $\;x \in P\lor(Q\land R)$ is not. You also need the universal quantifier, if $X\subset Y$, then by definition, each and every element in $X$ is an element in $Y$.

Looking past that, what you end with is certainly correct. I would just take it just a step or two further (again, how far to "unpack" the original statement is open to interpretation.) I'll start from the beginning:

$$\begin{align}& P \cup (Q \cap R) \subset A \cup (B \setminus C) \\ &\iff \forall x\Big(\Big( x \in P \lor x \in (Q\cap R)\Big) \rightarrow \Big(x \in A \lor x \in (B\setminus C)\Big)\Big)\\ &\iff \forall x \Big(\Big(x \in P \lor (x \in Q \land x\in R)\Big) \rightarrow \Big( x \in A \lor (x\in B \land x \notin C)\Big)\Big)\\ &\iff \forall x\Big(\Big((x \in P \lor x\in Q) \land (x \in P \lor x \in R)\Big) \rightarrow \Big((x\in A\lor x \in B) \land (x\in A \lor x\notin C)\Big)\Big) \end{align}$$

amWhy
  • 209,954
1

We just need to remind the proper definitions of subset, set union, intersection and difference:

$P \cup (Q \cap R) \subset A \cup(B \setminus C)\Rightarrow$

$\Rightarrow \forall x (x \in ( P \cup (Q \cap R) \rightarrow x \in (A \cup (B \setminus C)))$

$\Rightarrow \forall x ((x \in P \vee x \in (Q \cap R)) \rightarrow (x \in A \vee x \in (B \setminus C)))$

$\Rightarrow \forall x ((x \in P \vee (x \in Q \wedge x \in R)) \rightarrow (x \in A \vee (x \in B \wedge x \notin C)))$

$\Rightarrow\forall x (\neg(x \in P \vee (x \in Q \wedge x \in R)) \vee (x \in A \vee (x \in B \wedge x \notin C)))$

$\Rightarrow\forall x ((x \notin P \wedge \neg (x \in Q \wedge x \in R)) \vee (x \in A \vee (x \in B \wedge x \notin C)))$

$\Rightarrow\forall x ((x \notin P \wedge (x \notin Q \vee x \notin R)) \vee (x \in A \vee (x \in B \wedge x \notin C)))$

At the last three steps, we just remind that a conditional $\phi \rightarrow \psi$ is logically equivalent to the more simple (in disjunctive normal form) formula $\neg \phi \vee \psi$. We also make use the De Morgan Laws.