# Using First DeMorgan's Law to Derive the Second

• Jan 23rd 2010, 07:21 PM
GGB1387
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!
• Jan 23rd 2010, 07:58 PM
Jhevon
Quote:

Originally Posted by GGB1387
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!

They gave you the starting point. double negation.

since you never stated what level of rigor you needed, i won't be too rigorous.

$\neg P \wedge \neg Q \Leftrightarrow \neg \neg (\neg P \wedge \neg Q)$

$\Leftrightarrow \neg [\neg (\neg P \wedge \neg Q)]$

$\Leftrightarrow \neg [ \neg( \neg P) \vee \neg (\neg Q)]$ (by the first law)

$\Leftrightarrow \neg (P \vee Q)$
• Nov 21st 2011, 09:27 PM
Syrus
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.
• Nov 22nd 2011, 01:29 AM
emakarov
Re: Using First DeMorgan's Law to Derive the Second
Yes, this is essentially the same derivation as in post #2.
• Oct 1st 2013, 04:32 PM
ludragon
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.
• Oct 1st 2013, 04:45 PM
emakarov
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

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

and post #3 derives

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

They are exactly the same.