0
   

Proof help

 
 
nemo66
 
Reply 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: 311 • Replies: 2
No top replies

 
View best answer, chosen by nemo66
carpenters
  Selected Answer
 
  2  
Reply 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! Smile
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  
Reply 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
Copyright © 2019 MadLab, LLC :: Terms of Service :: Privacy Policy :: Page generated in 0.03 seconds on 03/24/2019 at 10:25:11