I'm trying to understand a proof for $B \cap A = A \setminus (A \setminus B) $, with $B \subseteq A$ which goes like this:

In general: $y \in A \setminus B \Leftrightarrow y \in A \land \lnot(y \in B)$

$x \in A \setminus (A \setminus B)$

$\Leftrightarrow x \in A \land \lnot(x \in A \land \lnot(x \in B))$

$\Leftrightarrow x \in A \land \lnot (x \in A) \lor \lnot\lnot(x \in B)$

$\Leftrightarrow x \in A \land \lnot (x \in A) \lor (x \in B)$

$\Leftrightarrow x \in A \land x \in B$

I don't understand how the last step works. In a footnote it says that $p \land \lnot(p \land \lnot q)$ is equivalent to $p \land q$. I don't quite understand why though. Could someone explain?

  • $\begingroup$ Um, do you mean if $B\subset A$ then $B=A \setminus (A \setminus B)$? Because $B \subseteq A = A \setminus (A \setminus B)$ is not true. $\endgroup$ – Thomas Andrews Oct 29 '15 at 17:30
  • $\begingroup$ Don't remove the parenthesis: $U\land (V\lor W)$ is different than $(U\land V)\lor W$. $\endgroup$ – Thomas Andrews Oct 29 '15 at 17:32
  • $\begingroup$ Whoops, I mixed some things up, I corrected it. $\endgroup$ – logicislogical Oct 29 '15 at 17:34
  • $\begingroup$ Well, now it's true, but the condition $B\subseteq A$ is not required for it to be true. $\endgroup$ – Thomas Andrews Oct 29 '15 at 17:35

\begin{align} p \land \lnot (p \land \lnot q) &= p \land (\lnot p \lor q) &\qquad \mbox{de Morgan rule}\\ &= (p \land \lnot p) \lor (p \land q) &\qquad \mbox{By distributivity}\\ &= (p \land q) &\qquad \mbox{since $x \land \lnot x = 0$ and $0 \lor x = x$} \end{align}


\begin{align*} p \land \lnot(p \land \lnot q) &\iff p \land(\lnot p \lor q) && \text{(DeMorgan's Law)}\\ &\iff (p \land \lnot p) \lor (p \land q) && \text{(Distributivity of logical conjunction)} \\ &\iff p \land q && (p \land \lnot p) \text{ is a contradiction} \end{align*}


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.