How can you derive De Morgan's Law?

Question

Can someone help me prove De Morgan's Law. In my logic class we are using a very basic set of rules for derivations and I can't for the life of me figure out how to prove the law with them. It's not homework; my TA gave me extra problems to practice for the midterm. By the way, I know this article is asking the same question, but I do not understand the notation so I don't know if they're restricted to the same rules.

Prove p&q <-> ~(~pV~q) and/or pvq <-> ~(~p&~q) using only these rules: &Intro/Elim, vIntro/Elim, ~Intro/Elim, ->Intro/Elim, <->Intro/Elim. Please use this notation as well.

As far as I can tell, the proof should look like this:

|pVq            Hyp

|-

||~p&~q         Hyp[for ~Intro]

||-

||~p            &Elim[~p^~q]

||q             **I'm not sure how to prove that ~p -> q with the limited rules**

||~q            &Elim[~p^~q]

|~(~p&~q)       ~Intro[~p&~q, q, ~q]

Answer 1

You are on the right track.

From the assumption [a] : ¬p ∧ ¬q you correctly derive ¬p and ¬q by ∧-Elimination :

1) p ∨ q --- premise

2) ¬p ∧ ¬q --- assumed [a]

3) ¬p --- from 2) by ∧-Elim

4) ¬q --- from 2) by ∧-Elim

5) p --- assumed [b] for ∨-Elimination

6) ⊥ --- contradiction, from 3) and 5)

7) q --- assumed [c] for ∨-Elimination

8) ⊥ --- contradiction, from 4) and 7)

9) ⊥ --- from 1), 5)-6) and 7)-8) by ∨-Elimination, discharging [b] and [c]

10) ¬(¬p ∧ ¬q) --- from 2) and 9) by ¬-Introduction, dicharging the assumption [a]

(p ∨ q) → ¬(¬p ∧ ¬q) --- from 1) and 10) by →-Introduction.

---

In order to prove :

¬(¬p ∧ ¬q) → (p ∨ q),

we need :

1) ¬(¬p ∧ ¬q) --- premise

2) ¬(p ∨ q) --- assumed [a]

3) p --- assumed [b]

4) p ∨ q --- by ∨-Introduction

5) ¬p --- from 3) by ¬-Introduction and the contradiction between 2) and 4), discharging [b]

6) q --- assumed [c]

7) p ∨ q --- by ∨-Introduction

8) ¬q --- from 6) by ¬-Introduction and the contradiction between 2) and 7), discharging [c]

9) ¬p ∧ ¬q --- from 5) and 8) by ∧-Introduction

10) ¬¬(p ∨ q) --- from 2) by ¬-Introduction and the contradiction between 1) and 9), discharging [a]

11) (p ∨ q) --- from 10) by Double Negation-Elimination

¬(¬p ∧ ¬q) → (p ∨ q) --- from 1) and 11) by →Introduction.