Proof by contradiction for statement of the form P->(Q and R)

Click For Summary

Discussion Overview

The discussion revolves around the proof by contradiction for statements of the form P implies (Q and R). Participants explore the implications of assuming the negation of the conclusion and the necessary conditions for establishing a contradiction.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested

Main Points Raised

  • One participant proposes that to prove P implies (Q and R) by contradiction, one can assume P and the negation of (Q and R), which is (not Q or not R), and seek a contradiction.
  • Another participant questions whether finding a contradiction under the assumption of both (not Q1) and (not Q2) is sufficient, or if contradictions must be found for each individual negation (not Q1) and (not Q2) separately.
  • A later reply clarifies that the negation of "Q and R" is indeed "not Q or not R" and discusses the contrapositive of the original statement.
  • It is noted that the contrapositive maintains the same truth value as the original statement, while the negation is expressed as P and (not Q or not R).

Areas of Agreement / Disagreement

The discussion contains multiple viewpoints regarding the sufficiency of finding contradictions in the proof by contradiction method, indicating that there is no consensus on the exact requirements for the proof.

Contextual Notes

Participants express uncertainty about the implications of their assumptions and the necessary conditions for establishing contradictions in the context of logical proofs.

christoff
Messages
123
Reaction score
0
Say I have a statement like this:
P implies (Q1 and Q2).

If I wanted to prove this by contradiction, I would assume P and not(Q1 and Q2)=[(not Q1) or (not Q2)] both hold, and try to find a contradiction.

My question is... Am I done if I find a contradiction while assuming P and [(not Q1) and (not Q2)] ? Is this sufficient? Or do I need to find a contradiction in both the statements:
P and (not Q1),
P and (not Q2)

?
 
Physics news on Phys.org
Never mind. I figured it out.
 
No. The negation of "Q and R" is "not Q or not R".
The negation of "if P then (Q and R)" is "If (not Q or not R) then not P".

(For those who read this thread and wondered).
 
The contrapositive of "if P then (Q and R)" is "if (not Q or not R) then not P"

But the contrapositive has the same truth value as the original.

The negation of "if P then (Q and R)" is "P and (not Q or not R)"
 

Similar threads

Graduate Proof of fundamental theorem of arithmetic
  • · Replies 4 ·
Replies
4
Views
2K
MHB Understanding Ke Logic Rules & Finding Contradictions
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Translate compound proposition p → q (implication) to p↓q question
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Proving the Implication of p and (p -> q) to q without Truth Tables
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Proving Theorems Not in "If-Then" Form
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Can you make the induction step by contradiction?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Can you use proof by contradiction in the midst of induction
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Equivalence Question between when-then statement and if then statement
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Nuclear form factor, the graph F2(q) vs. q (fm-1)
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Circular reasoning and proof by Contradiction
  • · Replies 5 ·
Replies
5
Views
2K