1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Please check the parentheses in your statements! $\endgroup$
    – Bram28
    Commented Mar 23, 2017 at 11:46
  • $\begingroup$ 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! $\endgroup$
    – Bram28
    Commented Mar 23, 2017 at 13:33
  • $\begingroup$ There also is documentation to help you format future questions. Here is one place you can start reading: math.stackexchange.com/help/notation $\endgroup$
    – David K
    Commented Mar 24, 2017 at 0:36

2 Answers 2

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ How did you get a ¬p? $\endgroup$
    – Xenorosth
    Commented Mar 23, 2017 at 11:23
  • $\begingroup$ A second one? Because I'm still not seeing it. Do I have to do two assumptions and two discharges? $\endgroup$
    – Xenorosth
    Commented Mar 23, 2017 at 11:29
1
$\begingroup$

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:

enter image description here

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Rob Arthan
    Commented Mar 25, 2017 at 21:23
  • $\begingroup$ @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. $\endgroup$
    – Bram28
    Commented Mar 26, 2017 at 2:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .