Using First DeMorgan's Law to Derive the Second

Hi. I've been racking my brains a little longer than I anticipated on this question from section 1.2 of Velleman's "How to Prove It".

13. Use the first DeMorgan's Law and the double negation law to derive the second DeMorgan's Law.

After trying various starting combinations of P and Q and attempting to use the first DeMorgan's Law [(P and Q)' <-> P' or Q'], I've hit a brick wall in finding a workable starting point. Any and all help will be greatly appreciated. Thanks!

Re: Using First DeMorgan's Law to Derive the Second

I came across the same problem, but produced a different derivation. Can anyone verify it?

*below, the double arrow "<--->" is used to denote equivalent statements

Proof:

By hypothesis, we have ¬(P ∧ Q) <---> ¬P ∨ ¬Q. If we replace each occurrance of P with ¬P and replace each occurrance of Q with ¬Q, we obtain: ¬(¬P ∧ ¬Q) <---> ¬(¬P) ∨ ¬(¬Q). This expression becomes ¬(¬P ∧ ¬Q) <---> P ∨ Q by using the double negation law on the right-hand side. Since the two expressions on either side of the double arrow are equivalent, their negations are equivalent, so ¬¬(¬P ∧ ¬Q) <---> ¬(P ∨ Q). Lastly, using double negation once again: ¬P ∧ ¬Q <---> ¬(P ∨ Q), as desired.

Re: Using First DeMorgan's Law to Derive the Second

Yes, this is essentially the same derivation as in post #2.

Re: Using First DeMorgan's Law to Derive the Second

Math newbie here. I've been going over How To Prove It myself and came to this same question wondering how to prove it. I now feel like I know how, but I don't understand the comment above me about how the 2nd and 3rd posts are essentially the same derivation. To me, the second post is just proving the 1st law, not actually deriving the 2nd from the 1st which is what the third post seems to be doing. Any clarification would be appreciated.

Re: Using First DeMorgan's Law to Derive the Second

Quote:

Originally Posted by

**ludragon** To me, the second post is just proving the 1st law, not actually deriving the 2nd from the 1st which is what the third post seems to be doing.

Post #2 derives

$\displaystyle \neg P \wedge \neg Q\iff \neg (P \vee Q)$

and post #3 derives

¬P ∧ ¬Q <---> ¬(P ∨ Q)

They are exactly the same.