How would you convert set logic to propositional logic? In particular, I'm not sure how to handle converting $\subseteq$

For example: $$A-(\bar{B} \cup \bar{C}) \subseteq B \cap C$$

My attempt at converting to propositional logic: $$ x \in A \land (x \in B \lor x \in C) \implies x \in B \land x \in B$$

Is this the right way?


Yes, you're correct that $\subseteq$ corresponds to the conditional connective $\rightarrow$.

But you've made an error: The antecedent in your translation corresponds to $A - (B \cup C)$, whereas we need to translate $A - (\overline B \cup \overline C)$. So we need DeMorgan's: In particular, note how the side to the left of the conditional is translated:

$$A-(\overline{B} \cup \overline{C}) \subseteq B \cap C$$

$$x\in A \land \lnot [x \in (\overline B \cup \overline C)] \rightarrow x \in B \land x \in C$$ $$\iff A \land \lnot[\lnot (x \in B\cap C)] \rightarrow x \in B \land x \in C\tag{DeMorgan's}$$ $$\iff x \in A \land (x\in B \land x \in C) \rightarrow x \in B \land x\in C$$

  • $\begingroup$ Truly in your element! +1 :-) $\endgroup$ – Amzoti Nov 18 '13 at 0:08

You're close, but it's not quite correct. It looks like you forgot to switch the $\cup$ to a $\cap$ (or perhaps the $\vee$ to a $\wedge$) when you applied de Morgan's law. It should be $x \in B \wedge x \in C$, not $x \in B \vee x \in C$. In general, the fast-and-loose rule is to convert $A - B$ to $A \wedge \neg B$, $A \cup B$ to $A \vee B$, $A \cap B$ to $A \wedge B$, and $\overline{A}$ to $\neg A$, using de Morgan's laws as you go. Try drawing a Venn diagram too; in this case it would be very helpful.


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.