Help with a logic problem (given this, prove this).

Question

Here is the problem:

Here is my progress.

We have:

i. $p \implies q$

ii. $r \vee s$

iii. $r \implies t$

iv. $\neg q$

v. $s \implies p$

Start with $r \vee s$. Suppose $r$. Since $r \implies t$, $t$ must be true.

Now suppose $s$. Since $s \implies p$, $p$ must be true. Then since $p \implies q$, $q$ must be true. But $q$ is false, since $\neg q$. So our original assumption $s$ is false.

Since $r$, then $t$.

Is this enough? Don't both $r$ and $s$ have to be true? I'm thinking this because I was taught that to prove $(a \vee b) \implies c$, you must prove that $a \implies c$ and $b \implies c$, since that is logically equivalent - that is,

$(a \vee b) \implies c \equiv (a \implies c) \wedge (b \implies c)$.

Answer 1

Is this enough?

Yes.   It is a good proof.

Don't both $r$ and $s$ have to be true?

No; just at least one needs to be true and that one needs to imply the required conclusion $(t)$.

When we don't know which from the two is true, we will need both to imply the same consequent, but when we do know which is true, we only need that one to do so.   See below.

I'm thinking this because I was taught that to prove $(a\vee b)\to c$, you must prove that $a\to c$ and $b\to c$, since that is logically equivalent - that is. $(a\vee b)\to c \equiv (a\to c)\wedge (b\to c)$

Yes, indeed, you may infer $c$ from $a\vee b, a\to c,$ and $b\to c$.  (This is the rule of "disjunction elimination" in natural deduction proof systems)

But have you not also been taught that $b\to c$ may be infered from $\neg b$, whatever $c$ may be?   (Conditionals are true whenever their antecedants are false. )

So you may also infer $c$ from $a\vee b, a\to c,$ and $\neg b$.

---

Given premises: i. $p\to q$, ii. $r\vee s$, iii. $r\to t$, iv. $¬q$, v. $s\to p$

Infer $\neg s$ from premises v., i., and iv. ($s\to p, p\to q, \neg q$), since assuming $s$ with those derives a contradiction.

Infer $s\to t$ from $\neg s$, since assuming $s$ derives a contradiction via which anything may be derived.   (Notice how we might combine this with the previous step.)

Infer $t$ from $s\to t$ and premises ii. and iii. ($r\vee s, r\to t$).

Thereby infering $t$ from the five premises.

$\blacksquare$

Answer 2

It's ok but it's kind of all upside down.

$p\Rightarrow q$ can be rewritten $\neg q\Rightarrow \neg p$,

$s\Rightarrow p$ can be rewritten $\neg p\Rightarrow \neg s$,

$s\vee t$ can be rewritten $\neg s\Rightarrow t$.

By transitivity you have $\neg q\Rightarrow t$.