0

# Proof help

Sat 2 Dec, 2017 06:09 am
I'm reading this book on propositional logic. And so far the rules of inference introduced in the book are: modus ponens, modus tollens, conditional proof, &,v-introduction, &,v-elimination and reduction ad absurdum. Meaning the proofs should be based on no more than these. (De Morgan's laws cannot be used).

(¬PvQ)→¬P&¬Q
¬(P&Q)→¬Pv¬Q
• Topic Stats
• Top Replies
• Link to this Topic
Type: Question • Score: 0 • Views: 477 • Replies: 2
No top replies

View best answer, chosen by nemo66
carpenters

2
Sat 2 Dec, 2017 12:47 pm
@nemo66,
nemo66 wrote:
(De Morgan's laws cannot be used).

It makes sense that DeMorgan cannot be used, as it is DeMorgan that is to be proved here!
I think for the first problem, there are missing parentheses and it should instead be (¬PvQ)→¬(P&¬Q), otherwise it would not follow.

We proceed here by using reductio ad absurdum.
Code:``` 1 (1) ¬PvQ assumption 2 (2) P&¬Q assumption (assume the negation of the conclusion) 3 (3) ¬P assumption 2 (4) P & elim 2, 3 (5) <contradiction> 3, 4 not-elimination 6 (6) Q assumption 2 (7) ¬Q 2, & elim 2,6(8) <contradiction> 6,7 not-elimination 1,2(9) <contradiction> 1,3,5,6, 8 v-elimination 1 (10) ¬(P&¬Q) 2, 9 not-introduction. (11) (¬PvQ)→¬(P&¬Q) 1, 10 conditional proof □```

In a reductio ad absurdum, making use of not-elim and not-intro rules is necessary. It cannot be done otherwise.

The second one ¬(P&Q)→¬Pv¬Q is as follows:
Code:``` 1 (1) ¬(P&Q) Assumption 2 (2) ¬(¬Pv¬Q) Assumption 3 (3) ¬P Assumption 3 (4) ¬Pv¬Q 3, v-intro 2, 3 (5) <contradiction> 2, 4 not-elim 2 (6) P 3, 5 not-intro (also double negation if allowed) 7 (7) ¬Q assumption 7 (8) ¬Pv¬Q 7, v-intro 2, 7 (9) <contradiction> 2, 8 not-elim 2 (10) Q 7, 9 not-intro (double negation if allowed) 2 (11) P&Q 6, 10 &-intro 1, 2 (12) <contradiction> 1, 11 not-elim 1 (13) ¬Pv¬Q 2, 11 not-intro ( and Double negation) (14) ¬(P&Q)→¬Pv¬Q 1, 13 conditional proof □```

If you allow me to advise you, then I advise you to try to work it out by yourself thoroughly before seeking help, otherwise you will not benefit fully from your studies. As very last resort seek help.
nemo66

1
Sat 2 Dec, 2017 05:11 pm
@carpenters,
I'm self-studying and am also a beginner, and using only the book's instructions I couldn't figure out the necessary assumptions.
Thanks anyway.
0 Replies

### Related Topics

A2K challenge! - Discussion by HexHammer
Logic Proof Help - Question by crimhaze
THE TEN COMMANDMENTS OF LOGIC - Discussion by Ragman
Derivations vs. symbolisation? - Question by collegestudent123
Logic word problem - Question by johnr
Cause of death..... - Discussion by gungasnake
Need help in defining - Question by ichishti
Predicate Logic Help - Question by splenax

1. Forums
2. » Proof help