2

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]
2
  • The other question is proving it for quantified logic which is going to be a bit different and harder.
    – virmaior
    Nov 14, 2015 at 1:09
  • Many people here may be able to help, but this might be better answered on the Mathematics SE.
    – Cort Ammon
    Nov 14, 2015 at 5:42

1 Answer 1

4

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.

1
  • I was a little confused at first by reading the proof of (p ∨ q) → ¬(¬p ∧ ¬q) but actually seeing the second proof helped so much. We were given ~40 practice problems over the weekend, and most of the problems I was stuck on came down to needing De Morgens proved at some point, which I think I get now. Thanks!
    – b17
    Nov 16, 2015 at 7:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .