# Math Help - proof of De Morgan laws

1. ## proof 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

2. 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
6 . . ~~p ~ Intro: 3-5
7 . . p ~ Elimination: 6
8 . . . ~q Assumption
9 . . . ~p v ~q v Intro: 8
11 . . ~~q ~ Intro: 8-10
12 . . q ~ Elimination: 11
13 . . p ^ q ^ Intro: 7, 12
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
6 . . ~(p ^ q) ~ Intro: 3-5
. . break
7 . . ~q Assumption
8 . . . p ^ q Assumption
9 . . . q ^ Elimination: 8
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.

3. Originally Posted by alexandros
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
I'm not sure about my approach, I'm using this reference:

Spoiler:

Propositional calculus - Wikipedia, the free encyclopedia (subheading: Example 1. Simple axiom system)

The rule of inference is modus ponens (i.e. from p and $(p \to q)$, infer q). Then $a \lor b$ is defined as $\neg a \to b$, and $a \land b$ is defined as $\neg(a \to \neg b)$.

First one

Spoiler:

1. $\neg(p \land q)$

2. $\neg(\neg(p \to \neg q))$ (definition)

3. $p \to \neg q$ (elimination of double negative)

4. $\neg\neg p \to \neg q$ (double negative introduction)

5. $\neg(\neg p) \to (\neg q)$ (adding parentheses to clarify)

6. $\neg p \lor \neg q$ (definition)

Is this acceptable methodology?

4. 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.

5. 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
6 . . ~~p ~ Intro: 3-5
7 . . p ~ Elimination: 6
8 . . . ~q Assumption
9 . . . ~p v ~q v Intro: 8
11 . . ~~q ~ Intro: 8-10
12 . . q ~ Elimination: 11
13 . . p ^ q ^ Intro: 7, 12
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
6 . . ~(p ^ q) ~ Intro: 3-5
. . break
7 . . ~q Assumption
8 . . . p ^ q Assumption
9 . . . q ^ Elimination: 8
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

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

Good work

6. Originally Posted by undefined
I'm not sure about my approach, I'm using this reference:

Spoiler:

Propositional calculus - Wikipedia, the free encyclopedia (subheading: Example 1. Simple axiom system)

The rule of inference is modus ponens (i.e. from p and $(p \to q)$, infer q). Then $a \lor b$ is defined as $\neg a \to b$, and $a \land b$ is defined as $\neg(a \to \neg b)$.

Actually you can prove : $a\vee b\Longleftrightarrow\neg a\Longrightarrow b$ and $a\wedge b\Longleftrightarrow\neg(a\Longrightarrow\neg b)$

So definition is redundant.

First one

Spoiler:

1. $\neg(p \land q)$

2. $\neg(\neg(p \to \neg q))$ (definition)

3. $p \to \neg q$ (elimination of double negative)

4. $\neg\neg p \to \neg q$ (double negative introduction)

5. $\neg(\neg p) \to (\neg q)$ (adding parentheses to clarify)

6. $\neg p \lor \neg q$ (definition)

Is this acceptable methodology?
Apart from few mistakes and the style of writing your proof is correct.

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

1) $\neg(p\wedge\neg q)$.................................................. ....................Assumption

2) $p\Longrightarrow\neg q$.................................................. ..........From (1) and using the theorem (in propositional calculus) $\neg(a\wedge b)\Longrightarrow a\Longrightarrow\neg b$

3) $\neg p\vee\neg q$.................................................. ....................From (2) and using the theorem $a\Longrightarrow\ b\Longrightarrow\neg a\vee b$

4) $\neg(p\wedge q)\Longrightarrow\neg p\vee\neg q$............................................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