# How do I find the contradition in this indirect proof?

I'm utterly stuck with no where to go. The assignment is to complete the indirect proof. I'm stuck on the following step, and have no clue how to proceed. Where do I go? Also, pardon the poor formatting. I have no clue how properly format here. I can't space it like I'd like, or use the symbol I'd like.

$p \rightarrow t, s \rightarrow r \lor \neg t, q \land s \vdash \neg p \land q \lor r$

$\begin{array}{l|ll} 1.& p\to t &\text{Premise} \\2.& s\to r \lor\lnot t &\text{Premise} \\3.& q\land s &\text{Premise} \\4.& \quad \lnot(\lnot p\land q \lor r) &\text{Assumption} \\5.& \quad s &\text{Simplification (Premise 3)} \\6.& \quad q &\text{Simplification (Premise 3)} \\7.& \quad r \lor \lnot t &\text{Modus Ponens (Premise 2 & 5)} \\8.& \quad p \lor \lnot q ~\land~ \lnot r &\text{DeMorgans (Premise 4)} \\9.& \quad (p \lor\lnot q)\land (p \lor \lnot r) &\text{Distributive (Premise 8)} \\10.& \quad \lnot q \lor p &\text{Simplification (Premise 9)} \\11.& \quad q \to p &\text{Law of Implication (Premise 10)} \\12.& \quad p &\text{Modus Ponens (Premise 11 & 6)} \\13.& \quad t &\text{Modus Ponens (Premise 1 & 12)} \\14.& \quad r &\text{Disjunctive Syllogism (Premise 7 & 13)} \\15.&& \text{Cry because I'm stuck here}\end{array}$

• Please check the parentheses in your statements! – Bram28 Mar 23 '17 at 11:46
• I formatted your goal ... please take a look so you can figure out how it works (it's really fairly straightforward) and edit the rest of your post accordingly. Thanks! – Bram28 Mar 23 '17 at 13:33
• There also is documentation to help you format future questions. Here is one place you can start reading: math.stackexchange.com/help/notation – David K Mar 24 '17 at 0:36

Full proof, to avoid misunderstanding:

1) $p \to t$ --- 1st premise

2) $s \to (r \lor ¬t)$ --- 2nd premise

3) $q \land s$ --- 3rd premise

4) $¬[(¬p \land q) \lor r]$ --- assumed [b]

5) $s$ --- from 3) by Simplification

6) $q$ --- from 3) by Simplification

7) $r \lor ¬t$ --- from 5) and 2) by Modus Ponens.

Now we have to assume:

8) $p$ --- assumed [a]

9) $t$ --- from 1) and 8) by Modus Ponens.

10) $r$ --- from 9) and 7) by Disjunctive Syllogism

11) $(\lnot p \land q) \lor r$ --- from 10) by Addition.

This contradicts 4), and thus we have:

12) $\lnot p$ --- from 8) by Negation Introduction, discharging assumption [a].

13) $(\lnot p \land q)$ --- from 12) and 6) by by Conjunction introduction

14) $(\lnot p \land q) \lor r$ --- from 13) by Addition.

We have a contradicition again, from 4) and 14), and thus we can conclude by Double Negation, discharging assumption [b], with :

$(\lnot p \land q) \lor r$.

• How did you get a ¬p? – Xenorosth Mar 23 '17 at 11:23
• A second one? Because I'm still not seeing it. Do I have to do two assumptions and two discharges? – Xenorosth Mar 23 '17 at 11:29

You really need to add some parentheses to disambiguate! For example, is the goal $\neg p \land (q \lor r)$, or is it $(\neg p \land q) \lor r$? Those two statements are not the same! (use a truth table to verify that)

Likewise, is the second premise $s \rightarrow (r \lor \neg t)$, or is it $(s \rightarrow r) \lor \neg t$? Again, these are different statements.

Now, noticing how you go from line 4 to line 8, you must be seeing the goal as $\neg p \land (q \lor r)$.

And noticing how you go from 2 and 5 to 7, you must be seeing the second premise as $s \rightarrow (r \lor \neg t)$

So, it looks like the argument you are trying to prove is:

$p \rightarrow t$

$s \rightarrow (r \lor \neg t)$

$q \land s$

$\therefore \neg p \land (q \lor r)$

Unfortunately, this argument is not valid! Use $p=q=r=s=t=True$ as a counter-example.

So no wonder you got stuck and cry: there is no formal proof for that argument!

Which makes me wonder: do the parentheses for the second premise and/or the conclusion go elsewhere?

Indeed, if we change the parentheses of the second premise, we get a valid argument. And if we change the parentheses of the conclusion, we also get a valid argument. Though if we change then for both statements, it is invalid again (with the same counterexample: set them all to True).

OK, I am guessing you got the parentheses for the conclusion wrong, so the argument becomes:

$p \rightarrow t$

$s \rightarrow (r \lor \neg t)$

$q \land s$

$\therefore (\neg p \land q) \lor r$

And here is a proof:

• The quibble in your first sentence is unfair: taking conjunction to have stronger precedence than disjunction goes back to Boole: $x \land y \lor z$, means $(x \land y) \lor z$ unless there is very strong evidence for a (perverse) alternative reading. – Rob Arthan Mar 25 '17 at 21:23
• @RobArthan Ok, I didn't know, thanks! Still, had the OP used parentheses, the OP would never have made the invalid move from 4 to 8. – Bram28 Mar 26 '17 at 2:53