Originally Posted by

**Ackbeet** Prove that ~(p^q) <=> ~p v~q.

I like using the natural deduction rules, with the introduction and elimination rules for each symbol. I also like Fitch-style proofs. I will use periods to denote subproofs.

=>

1 . ~(p ^ q) Assumption.

2 . . ~(~p v ~q) Assumption.

3 . . . ~p Assumption

4 . . . ~ p v ~q v intro: 3

5 . . . contradiction contradiction intro: 4, 2

6 . . ~~p ~ Intro: 3-5

7 . . p ~ Elimination: 6

8 . . . ~q Assumption

9 . . . ~p v ~q v Intro: 8

10 . . . contradiction contradiction intro 9, 2

11 . . ~~q ~ Intro: 8-10

12 . . q ~ Elimination: 11

13 . . p ^ q ^ Intro: 7, 12

14 . . contradiction contradiction intro: 1, 13

15 . ~~(~p v ~q) ~ Intro: 2-14

16 . ~p v ~q ~ elimination: 15.

<=

1 . ~p v ~q Assumption

2 . . ~p Assumption

3 . . . p ^ q Assumption

4 . . . p ^ Elimination: 3

5 . . . contradiction contradiction intro: 4, 2

6 . . ~(p ^ q) ~ Intro: 3-5

. . break

7 . . ~q Assumption

8 . . . p ^ q Assumption

9 . . . q ^ Elimination: 8

10 . . . contradiction contradiction Intro: 9, 7

11 . . ~(p ^ q) ~ Intro: 8-10

. . break

12 . ~(p ^ q) v Elimination: 1, 2-6, 7-11.

That, I think, does it for the first DeMorgan law.