Solve this proof using tautologies (no truth tables)

Question

I am having trouble solving this problem using tautologies (no truth tables).

Hypotheses: $t \rightarrow s,\;\; d \rightarrow (u \vee t)$

Conclusion: $d \rightarrow ( u \vee s)$

Answer 1

Note: This is one way of using natural deduction to prove the conclusion, given the posted premises. It requires the use valid rules of inference to proceed, one step at a time.

This is not a proof using "tautologies"/logical identities, because the conclusion is not logically equivalent to the conjunction of the premises. The conclusion logically follows from the premises, however, which we demonstrate with the use of valid rules of inference.

Proof sketch:

$(1)\quad t\rightarrow s$ (Premise)

$(2)\quad d\rightarrow (u \lor t)$ (Premise)

$(3)\quad\quad$ Assume $d$.

$(4)\quad\quad\quad u \lor t$ (From $(2), (3),$ using modus ponents.)

$(5) \quad\quad\quad\quad$ Assume $u$.

$(6) \quad \quad\quad\quad\quad$ $u$ (From (5), reiteration)

$(7) \quad\quad\quad\quad\quad u \lor s$ (Or Introduction

$(8) \quad \quad\quad\quad$ Assume $t$.

$(9) \quad\quad\quad\quad\quad s$. (From (1), (8), modus ponens)

$(10) \quad \quad \quad\quad\quad u\lor s$. (Or-introduction.)

$(11) \quad\quad u \lor s$. (Or-Elimination: 4, 5-7, 8-10)

$(12) \quad d\rightarrow (u\lor s)$ (Implication introduction 3-11)

Answer 2

Assume that $t \Rightarrow s, d \Rightarrow u \vee t $ are true.

(1) Well $d \Rightarrow u \vee s$ is only false when $d$ is true and $u \vee s$ is false.

(2) To say that $u \vee s$ is false is the same as $u$ and $s$ being false.

(3) As $d \Rightarrow u\vee t$ is true by hypothesis and $u$ is false (2) then $t$ must be true, which gives a contradiction since we are assuming that $t \Rightarrow s$ is true.

Answer 3

The conclusion $d \implies (u \lor s)$ can be written as $\neg d \lor (u \lor s)$.

Assuming the conclusion to be false leads to $d \land \neg u \land \neg s$ to be true.

This can only be the case if $d$ is true and $u$ as well as $s$ are false.

Hypothesis $t \implies s$ with $s$ false implies $t$ false.

Hypothesis $d \implies (u \lor t)$ with $d$ true and $(u \lor t)$ false is a contradiction.

Answer 4

We can prove it in a different way with the rules of Patrick Hurley, A Concise Introduction to Logic (11th edition - 2012) see Ch.7 :

• Rules of inference

• Rules of replacement

• Conditional Proof and Indirect Proof

---

1) $t \rightarrow s$ --- premise

2) $d \rightarrow (u∨t)$ --- premise

3) $d$ --- assumed [a]

4) $\lnot u \land \lnot s$ --- assumed [b], for Indirect Proof

5) $u∨t$ --- from 2) and 3) by modus ponens

6) $\lnot u$ --- from 4) by Simplification

7) $\lnot s$ --- from 4) by Simplification

8) $t$ --- from 6) and 5) by Disjunctive syllogism

9) $s$ --- from 8) and 1) by modus ponens

10) $s \land \lnot s$ --- from 7) and 9) by Conjunction introduction

11) $\lnot (\lnot u \land \lnot s)$ --- from the contradiction 10) by Indirect Proof, discharging the assumption [b]

12) $u \lor s$ --- from 12) by De Morgan's laws

13) $d \rightarrow (u \lor s)$ --- from 3) and 12) by Conditional Proof.

---

We can shorten it ...

1) $t \rightarrow s$ --- premise

2) $d \rightarrow (u∨t)$ --- premise

3) $\lnot d \lor (u∨t)$ --- from 2) by Material implication

4) $(\lnot d \lor u) \lor t$ --- from 3) by Associativity

5) $\lnot(\lnot d \lor u) \rightarrow t$ --- from 4) by Material Implication

6) $\lnot(\lnot d \lor u) \rightarrow s$ --- from 1) and 5) by Hypothetical syllogism

7) $(\lnot d \lor u) \lor s$ --- from 5) by Material implication

8) $\lnot d \lor (u \lor s)$ --- from 7) by Associativity

9) $d \rightarrow (u \lor s)$ --- from 8) by Material implication.