# Foundations of Logic (validity of the argument)

I am currently preparing for my Foundations of Logic midterm and while going through different problems I ran into this question that I just can't solve

Premises:

(1) $p \to (q \lor r)$

(2) $r \to \lnot p$

(3) $q \to s$

∴ $p \to s$

I need to prove the validity of the following argument. It doesn't seem that I can use any of the inference rules here, I also tried using material implication but it didn't get me anywhere either. Any idea how this argument can be proved?

The conclusion can only be false if $p=T$, $s=F$. There are only $4$ rows in the truth table with this assignment; just check every row which has these assignments and make sure that at least one of the premises is false. If this is the case, the argument is valid; if you find a row where all the premises are true but the conclusion false, the argument is invalid.

• Thanks, that helped – Anar Kazimov Jan 31 '18 at 17:57
• @AnarKazimov No problem – Ovi Jan 31 '18 at 17:58
1. Suppose p, now q or r.

2. Suppose q first, by 3) we conclude s.

3. Suppose r which by 2) implies negation of p, but this is a contradiction since we are already assuming p, so anything goes, and thus s.

So s either way. Done.

Assume $p$ is true. Then from (1), we get $q \vee r$. We now argue by cases on $q \vee r$. In the first case, (3) gives $s$, and we are done. In the second case, (2) gives $\lnot p$; but since we were also assuming $p$, this gives a contradiction, so this case cannot actually happen.

More formally, using Fitch-style notation for an argument using natural deduction:

A1: $p \rightarrow q \vee r$ (context assumption)

A2: $r \rightarrow \lnot p$ (context assumption)

A3: $q \rightarrow s$ (context assumption)

1. $p$ (assumption)

2. | $q \vee r$ (modus ponens from A1, 2)

3. | $q$ (assumption)

4. | | $s$ (modus ponens from A3, 3)

5. | $r$ (assumption)

6. | | $\lnot p$ (modus ponens from A2, 5)

7. | | $\bot$ (modus ponens from 6, 1)

8. | | $s$ ($\bot$-elim from 7, a.k.a. ex falso quodlibet)

9. | $s$ ($\vee$-elim from 2, 3-4, 5-8)

10. $p \to s$ ($\rightarrow$-intro from 1-9)