Demonstrating seconds Morgan's law using the first one and double negation

Question

These are the 2 Morgan's laws:

 1. NOT(A ^ B) = NOT(A) v NOT(B) 
 2. NOT(A v B) = NOT(A) ^ NOT(B)

This is the double negation law:

NOT(NOT(R)) = R

My solution (after 30 min) to find the second Morgan's law using the first Morgan's law and the double negation is this:

NOT(R) = NOT(A) v NOT(B)

NOT(NOT(A) v NOT(B)) = NOT(NOT(A ^ B)) = A ^ B

Do you think this is a valid demonstration?

I think you meant to put "NOT(A and B) = NOT(A) or NOT(B)" instead of "NOT(R) = " towards the end. — DanielV, Sep 24 '14 at 23:13
For anyone coming from Google, this is Exercise 1.2.13 in How To Prove It by Velleman. — Jack Steam, Sep 17 '20 at 14:13

score 2 · Accepted Answer · answered Sep 24 '14 at 23:19

You have $$\operatorname{NOT}(A \land B) = \operatorname{NOT}(A) \lor \operatorname{NOT}(B)\tag{T1}$$

Apply the NOT() to both sides like you did above:

$$\operatorname{NOT}(\operatorname{NOT}(A \land B)) = \operatorname{NOT}(\operatorname{NOT}(A) \lor \operatorname{NOT}(B)\tag{T2})$$

Apply double negation like you did above:

$$A \land B = \operatorname{NOT}(\operatorname{NOT}(A) \lor \operatorname{NOT}(B)\tag{T3})$$

Now let $X = \operatorname{NOT}(A)$ and $Y = \operatorname{NOT}(B)$, which by double negation gives

$$A = \operatorname{NOT}(X) \tag{T4}$$ $$B = \operatorname{NOT}(Y) \tag{T5}$$

So that (T3) becomes:

$$\operatorname{NOT}(X) \land \operatorname{NOT}(Y) = \operatorname{NOT}(X \lor Y\tag{T6})$$

And there you have the law again with the alternate conjunction/disjunction.

1 Answers1