How do I find the contradition in this indirect proof?

Question

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}$

Answer 1

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$.

Answer 2

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: