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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .