Proofing Implications Using Negation: P=>Q & ¬P=>Q

  • Context: MHB 
  • Thread starter Thread starter aconti
  • Start date Start date
Click For Summary
SUMMARY

This discussion focuses on proving implications using negation, specifically the proofs of ¬P=>Q leading to PvQ and P=>Q leading to ¬PvQ. The first proof employs negation introduction and elimination, demonstrating that assuming ¬(PvQ) leads to a contradiction, thereby establishing the validity of the statement. The second proof similarly seeks to apply contradiction to derive ¬PvQ from P=>Q. Participants are encouraged to explore these proofs further using formal logical techniques.

PREREQUISITES
  • Understanding of propositional logic
  • Familiarity with negation introduction and elimination
  • Knowledge of proof by contradiction
  • Experience with logical operators such as conjunction and disjunction
NEXT STEPS
  • Study formal proofs in propositional logic
  • Learn about the rules of negation introduction and elimination
  • Explore proof techniques involving contradiction
  • Practice constructing logical proofs using tools like Coq or Lean
USEFUL FOR

Students of mathematics, logicians, and anyone interested in formal proofs and logical reasoning will benefit from this discussion.

aconti
Messages
1
Reaction score
0
1st proof: ¬P=>Q |- PvQ

2nd proof: P=>Q |- ¬PvQ

I think negation introduction and negation elimination should be used, can you share any thoughts on how you would work out the above?

Thanks
 
Physics news on Phys.org
aconti said:
1st proof: ¬P=>Q |- PvQ

2nd proof: P=>Q |- ¬PvQ

I think negation introduction and negation elimination should be used, can you share any thoughts on how you would work out the above?

Thanks

For the 1st one:

Proof :

1) ~P=>Q.....................Given

2) ~(PVQ)..................Assumption to lead to a contradiction

3) ~P & ~Q...................2, D.Morgan

4) ~P....................3, Addition Elimination

5) ~Q ....................3,Addition Elimination

6) Q.....................1,4 M.Ponens

7) Q&~Q ...................5,6 Addition Introduction

8) PVQ....................2 to 7 and Contradiction

Can you do the 2nd exescise also by contradiction ??
 

Similar threads

Undergrad Modus Ponens deduction rule
  • · Replies 12 ·
Replies
12
Views
2K
Undergrad Equivalence Question between when-then statement and if then statement
  • · Replies 4 ·
Replies
4
Views
1K
Undergrad On the meaning of logical implication within specific context/models
  • · Replies 22 ·
Replies
22
Views
3K
Undergrad Translate compound proposition p → q (implication) to p↓q question
  • · Replies 4 ·
Replies
4
Views
2K
MHB Converting Numbers Between Different Bases: Is It Possible to Use Only n Digits?
  • · Replies 9 ·
Replies
9
Views
1K
MHB Getting Nowhere with a Proof Question: Help Needed
  • · Replies 3 ·
Replies
3
Views
2K
MHB Proving p<=>~p: Two Contradictory and Identical Proofs Explained
  • · Replies 5 ·
Replies
5
Views
2K
MHB Solving a High School Algebra Proof Using Constractive Dilemma
  • · Replies 1 ·
Replies
1
Views
1K
Is it possible to prove (P→Q)↔[(P ∨ Q)↔Q] without using truth tables?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Proving the Implication of p and (p -> q) to q without Truth Tables
  • · Replies 3 ·
Replies
3
Views
2K