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 $$
$\begingroup$
$\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$– CatoFeb 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$– amWhyFeb 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$– amWhyFeb 8, 2017 at 17:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
$$¬(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}.$
-
$\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$– amWhyFeb 8, 2017 at 17:02
-
$\begingroup$ Thanks amWhy, it's verified to be a textbook error $\endgroup$– YolandaFeb 8, 2017 at 20:28