So I was given this proof in class:

~p ^ q = (~ p v q) ^ ~(~q ^ p)

= (~ p v q) ^ (q v ~p) by double negative law.

= ~p ^ (q ^ ~p) v ( q ^ ( q ^ ~p)) by distributive law.


Note: The prof said take ( q v ~p) to be r

Can someone explain how he went from the 2nd to 3rd step by the distributive law?

  • $\begingroup$ Your "by double negative law" is probably wrong. $$\neg(A\vee B) = \neg A \wedge \neg B$$ $\endgroup$ – peterwhy Sep 23 '15 at 0:20
  • $\begingroup$ @peterwhy edited, had the wrong sign. $\endgroup$ – misheekoh Sep 23 '15 at 0:25
  • $\begingroup$ Your "by double negative law" is still probably wrong. $$\neg(A\wedge B) = \neg A \vee \neg B$$ $\endgroup$ – peterwhy Sep 23 '15 at 0:28

The distributive law says that $$A \land (B \lor C) \equiv (A \land B) \lor (A \land C).$$ What you have so far is $$(\neg p \lor q) \land (q \lor \neg p).$$ Now let us write $r$ as shorthand for $(q \lor \neg p)$, so we can write it as $$(\neg p \lor q) \land r.$$ Using distributivity, this means $$(\neg p \lor q) \land r \equiv (r \land \neg p) \lor (r \land q),$$ and putting $(q \lor \neg p)$ back in again instead of $r$, we get $$(\neg p \lor q) \land (q \lor \neg p) \equiv ((q \lor \neg p) \land \neg p) \lor ((q \lor \neg p) \land q).$$


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.