# Before starting the Reductio Ad Absurdum, how can you guess or divine that F causes the contradiction?

As with most proofs by Indirect Method or Reductio Ad Absurdum, the key step is to discover (at least, to divine or presage) the location of the contradiction. So for the following example, what suggests or reveals F as the cause of the contradiction, as in Step 15?

[Scroll down 70% hereof to see this example:] 1. R ⊃ B  2. R ⊃ (B ⊃ F)  3. B ⊃ (F ⊃ H)
Conclusion: R ⊃ H

Now, since this has a conditional for its conclusion, CP is the smarter choice, but we’re going to walk through it with IP to exhibit how it can apply.

| 4. ~ (R ⊃ H)    AIP
| 5. ~( ~R ∨ H)  Material Implication: 4
| 6. ~~R ∧ ~H   DeMorgan's Rule: 5
| 7. R ∧ ~H     Double Negation: 6
| 8. R       Simplification (SM): 7
| 9. B      Modus Ponens (MP): 1,8
| 10. F ⊃ H    MP 9,3
| 11. ~H     CM, SM 7
| 12. ~F      MT 11,10
| 13. B ⊃ F     MP 8,2
| 14. F      MP 9, 13
| 15. F ∧ ~F    CN 14,12
16. R ⊃ H     IP 4-15

The problem of evaluating the truth of a proposition (including whether it leads to a contradiction or not) from a computational point of view amounts to evaluating the boolean expression corresponding to that proposition.

Determining whether your proposition F would lead to a contradiction or not is the same as being able to determining whether the corresponding boolean expression is satisfiable or not. At the present time there is no known method for evaluating the truth of a general boolean expression without actually calculating the expression itself. This is known as the boolean satisfiability problem, and it is conjectured that there is no efficient algorithm for evaluating whether it has a truth value or not. The only guaranteed way of determining whether it is satisfiable or not, and determining the corresponding variable assignment, is to evaluate all possible combinations of the boolean expression.

This fact that there is no known general efficient solution, and the conjecture that the can't be one, is known as the P vs NP problem.

Here efficient means that it can be solved in (deterministic) polynomial time.
Inefficient means that the problem is solvable in Non-deterministic polynomial time (The "NP" in NP-complete). For practical purposes this means the only way of finding a solution is to evaluate every possible input combination, which can take up to an exponential amount of time.

The P vs NP problem first gained importance after Cook and Levin independently proved the NP-completness theorem in the 70s. In particular Cook was working on automated theorem proving procedures, and it was in this context that he ended up with his result regarding boolean satisfiability.

There is a remote possibility that P=NP and that there is such an efficient procedure, but it is considered highly unlikely, and if it were true, the consequence would be significant for our understanding of computation and science in general.

"If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found." — Scott Aaronson, MIT

To summarize, the answer to your overall question "Before starting the Reductio Ad Absurdum, how can you guess or divine that F causes the contradiction?": There is no known method for doing so beforehand. Being able to do so implies an efficient method for solving boolean satisfiability, and it is conjectured (but not yet proven conclusively) that an efficient method is impossible.

• This answer is perhaps akin to putting in a finish nail with a sledgehammer...
– user9166
Commented Jan 2, 2016 at 1:54
• @jobermark this is a philosophy forum, the answers have to be pompous or they're irrelevant :-) Commented Jan 2, 2016 at 2:02
• Thank you for your detailed answer, but which has confused me. Though the argument in the OP did not originate from A Concise Introduction to Logic (12 Ed, 2014) by Patrick Hurley, this textbook (that I am using now) discusses, in many examples, how to divine or presage the key steps in an argument before doing the proof. These presages: do they affect your answer? Do they contradict your answer? Please tell me if you wish me to quote such presages.
– user8572
Commented Jan 3, 2016 at 22:15