# 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! Commented Mar 23, 2017 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! Commented Mar 23, 2017 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 Commented Mar 24, 2017 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? Commented Mar 23, 2017 at 11:23
• A second one? Because I'm still not seeing it. Do I have to do two assumptions and two discharges? Commented Mar 23, 2017 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. Commented Mar 25, 2017 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. Commented Mar 26, 2017 at 2:53