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
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.
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
Actually you can prove : and
So definition is redundant.
Apart from few mistakes and the style of writing your proof is correct.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