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

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.

  • 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 '15 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.