Challenge problem:

prove the laws of De Morgan:

~(p^q) <=> ~p v~q

~(p v q) <=> ~p ^~q ,by using the inference rules of the propositional calculus

Moderator approved. CB

Printable View

- Jun 18th 2010, 11:23 AMalexandrosproof of De Morgan laws
Challenge problem:

prove the laws of De Morgan:

~(p^q) <=> ~p v~q

~(p v q) <=> ~p ^~q ,by using the inference rules of the propositional calculus

Moderator approved. CB - Jun 18th 2010, 11:49 AMAckbeet
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. - Jun 18th 2010, 12:00 PMundefined
- Jun 18th 2010, 09:42 PMDrexel28
You could use the fact that the algebra of sets is Boolean isomorphic with sentence logic and then the idea (at least to me) is more obvious.

- Jun 19th 2010, 06:35 PMalexandros
On proof (=>) ,step (9) is wrong ,it should be : ~q v ~p instead of ~p v~q.

And then use commutativity to end up with : ~p v~q.

The rest is correct ,except the mentioning of the deduction theorem as a final step in both proofs.

The style of the proof is based on 7 basic laws :

1) Conjunction Introduction and Elimination

2) Disjunction Introduction and Elimination

3) The law of double negation

4) Contradiction and finally

5) The rule of conditional proof ( deduction theorem).

Good work - Jun 20th 2010, 06:02 AMalexandros

Actually you can prove : and

So definition is redundant.

Quote:

First one

__Spoiler__:

Is this acceptable methodology?

A complete and correct proof on the lines of your proof would be the following:

1) .................................................. ....................Assumption

2) .................................................. ..........From (1) and using the theorem (in propositional calculus)

3) .................................................. ....................From (2) and using the theorem

4) ............................................From (1) to (3) by using the rule of conditional proof

Usually in proofs in propositional calculus we use basic ,well known, rules of inference like the ones that Ackbeet used in his proof.

To use other theorems like you did in your proof you have to show the validity of those theorems by either writing proofs for those theorems or establish that they are tautologies thru true tables