Logic 101 (#39): Proof By Contradiction/Indirect Proof

This lecture introduces the logic proof technique called "proof by contradiction." When you are struggling to show that p is true, you can always try showing that ~p must be false instead.

[charity]

Wow my professor is absolute crap. I should be paying you instead.

[sickofcounting]

Thank you. I appreciate the effort put into this, and this greatly helped me.

[okxa]

I tried solving the example without proof by contradiction and it was a bit shorter:
1 P v Q
2 Q => ~Q
3 ~Q v ~Q 2 material implication
4 ~Q 3 idempotence
5 P 1, 4 disjunctive syllogism

[PunmasterSTP]

Proof by contradiction? More like "these videos are an addiction", because they are so awesome!

[mamo]

seriously exactly what i was looking for ❤️❤️❤️ u don’t understand how awesome u are.. or maybe u do who knows but thanks

[tronagar]

I think the proof can also be done without assumption:

PvQ 1
Q->~Q 2
~P->Q 3 1 IMP
~Q->P 4 3 CONTRA
~Qv~Q 5 2 IMP
~Q 6 5 TAUT
|-P 7 4, 6 MP

Have I missed anything here?

[thegreatsparsh]

How does Statement 2 work?

"If Q, then not Q"

Isn't it like saying if John wears a coat, then John doesn't wear a coat?

I'm so confused

[Smjh]

I asked my professor if we can prove a conditional statement (p->q) by contradiction like this: (p->-q)
(Usually its (-p->q) )
He literally said that he doesn't know .-.
So, can we?

[ardabaser]

You don't have to make modus ponens and than conjunction on lines 5 and 6 because by assuming p is wrong, you prove q is right, and if so, the second given appears to be a lie, which can't happen, meaning you have already proven p is right right there. (no pun intended)

[stevenfletcher]

When I was taught how to do assumption by contradiction, I was told that if I assume ~M I have to prove M to complete the proof by contradiction. I was specifically told that I can't prove some other random contradiction and then just say that M is true.

In my case, I believe I assumed some random thing was false, proved that 1 = 0, and than said that random thing was true after all. I was told that I can't do this.

In your case, you assumed for contradiction ~P, showed Q & ~Q, and then said that P is true. Is this allowed? I may be remembering what I was told incorrectly.

[Biyer]

Are we looking only for Q ^ ~Q as the contradiction? If not, what are the other examples?

[nicholasperkins]

This only works for Boolean systems. Don't try this for quantum mechanics.

[jagvirji]

sir u r just awesome but i need to know just one thing how did u bring 7th step of double negation from 3-6 step i mean which rule is used bcoz from q or either not q how that come

[lea]

Is this a tautology and could I use it to prove -Q and from that later proving P with disjunction introduction?


 {[-(Q and -Q) and (Q => -Q)] => -Q}

[strobelala]

Question: can't we just say that P is true without the proof by contradiction - by just adding a third premiss: P (disjunctive syllogism)?

[paulcarello]

Is this a valid direct proof?

1) P ∨ Q
⇔ Q ∨ P ... commutativity law (3)

2) Q ⇒ ~Q ... the conditional is true only if Q is false
∴ ~Q ... (4)

~Q ... (4)
Q ∨ P ... (3)
∴ P ... Disjunctive Syllogism

[fluck]

Q -> ~Q mindfucked me, looks false as hell and not logic

[fd]

I don't know if anyone is still monitoring this page. But how did he get line 2? What logic was used to give us line 2, so that we could then use it in line 5 and 7?

[truth]

There is a God, 3D protein printers cannot come about by chance.

[raynv]

How in the world am I suppose to prove that XANDER FORD IS HANDSOME?! And it's due tomorrow!!