1
$\begingroup$

In my textbook, it simplifies the following proposition $$ \neg(p \wedge \neg q) \vee (\neg p \wedge q) $$ to this step $$ \neg p \wedge (\neg q \vee q) $$ using distributive law, I am just really confused how the negation operation is being distributed. It is designed eventually to prove this equivalence. $$ \neg(p \vee q) \vee (\neg p \wedge q) \equiv \neg p $$

$\endgroup$
3
  • $\begingroup$ I got amWhy's answer - at the start, on the LHS, p intersected with not q does not include p intersected with q, so therefore the inverse of this does include p intersect q - so the LHS does include some of p - since we then use a union, the whole expression does include some of p, hence ¬ p can not be the correct answer. $\endgroup$
    – Cato
    Feb 8, 2017 at 16:29
  • $\begingroup$ Your textbook seems to have simplified $$\lnot(p \lor q)\lor (\lnot p \land q) \equiv (\lnot p \land \lnot q) \lor (\lnot p \land q).$$ And in the second section of my answer, I work on simplifying from there. $\endgroup$
    – amWhy
    Feb 8, 2017 at 17:24
  • $\begingroup$ The title and beginning part of your question suggests you made an error in applying Demorgan's rule to $\lnot (p \lor q) \equiv (\lnot p \land \lnot q)$ and instead of writing $(\lnot p \land \lnot q)$, you mistakenly wrote $\lnot(p \land \lnot q)$. It makes a huge difference whether $\lnot$ appears before the parentheses of a proposition contained in parentheses, or whether/when it appears within the parentheses $\endgroup$
    – amWhy
    Feb 8, 2017 at 17:25

1 Answer 1

1
$\begingroup$

$$¬(p ∧ ¬q) ∨ (¬p ∧ q)\equiv (\lnot p \lor \lnot \lnot q) \lor (\lnot p \land q)\tag{DeMorgan's Rule}$$

$$\equiv (\lnot p\lor q)\lor (\lnot p \land q)\tag{Double Negation}$$

$$\equiv((\lnot p \lor q)\lor \lnot p)\land((\lnot p \lor q) \lor q)\tag{distributivity}$$ $$\equiv ((\lnot p \lor \lnot p)\lor q) \land (\lnot p \lor (q \lor q))\tag{associativity of $\lor$}$$ $$\equiv(\lnot p \lor q) \land (\lnot p \lor q)\tag{simplification}$$

$$\equiv \lnot p \lor q\tag{simplification}$$


On the other hand, at the bottom of the post, it seems you need to prove the different proposition given by: $$¬(p ∨ q) ∨ (¬p ∧ q) \equiv \lnot p,$$

then we have $$\lnot (p\lor q) \lor (\lnot p \land q) \equiv (\lnot p \land \lnot q) \lor(\lnot p \land q)\tag{DeMorgan's}$$ $$ \equiv \lnot p\land \underbrace{(\lnot q \lor q)}_{\large \text{True}}\tag{Distributivity of $\land$ over $\lor$}$$ $$\equiv \lnot p \land \text{True} \equiv \lnot p$$


So the title proposition $$\color{blue}{\lnot (p \land \lnot q)} \lor (\lnot p \land q)\tag{1}$$ is not equivalent to the later proposition in your post: $$\color{blue}{¬(p ∨ q)} ∨ (¬p ∧ q)\tag{2}$$ because using Demorgan's on $(1)$ gives $\color{blue}{(\lnot p \lor q)}\lor (\lnot p \land q)\tag 1$

whereas, using DeMorgan's on $(2)$ gives us $\color{blue}{(\lnot p \land \lnot q)}\lor(\lnot p \land q)\tag{2}.$

$\endgroup$
2
  • $\begingroup$ My guess is that you took the step to apply DeMorgan's to $\lnot (p\lor q)$ and instead of writing (the correct translation) which would be $(\lnot p \land \lnot q)$, you mistakenly wrote $\lnot(p \land \lnot q)$. Note that $\lnot (a \lor b) \equiv (\lnot a \land \lnot b) \not\equiv \lnot(a \land \lnot b).$ $\endgroup$
    – amWhy
    Feb 8, 2017 at 17:02
  • $\begingroup$ Thanks amWhy, it's verified to be a textbook error $\endgroup$
    – Yolanda
    Feb 8, 2017 at 20:28

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.