Simplify $\;\neg(p \wedge \neg q) \vee (\neg p \wedge q)$

587 Views Asked by At

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 $$

1

There are 1 best solutions below

2
On

$$¬(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}.$