Show that $(p \to q) \lor (q \to p)$ is a tautology

Question

I tried to prove that $(p \to q) \lor (q \to p)$ is a tautology.

I used $p$ and $¬q$ as conditions. (Premises 1 and 5)

I managed to get to a solution, but I'm not sure if it's right.

Can you please check it?

Thank you!!!:)

Answer 1

The answer is pretty simple to derive using truth tables:

Answer 2

There's a quicker way than your approach.

By the law of excluded middle, $p \lor \neg p$

If $p$, then ...

If $\neg p$, then ...

Remember, anything implies a true statement, and a false statement implies anything.

edit: I'm just suggesting that you start with $p \lor \neg p$, which is either an axiom or derivable from $p \dashv \vdash \neg \neg p$, depending on which book you use.

Answer 3

Regarding step 11 :

$\lnot q \rightarrow (q \rightarrow p)$

it is a tautology; so, it is provable.

You are trying to prove it from assumptions; you can simplify it as follows :

1) $p$ --- assumed

2) $\lnot q$ --- assumed

3) $\lnot q \lor p$ --- Add.2

4) $q \rightarrow p$ --- Impl.3

5) $\lnot q \rightarrow (q \rightarrow p)$ --- C.P.2-4

Then discharge assumption $p$ to get :

6) $p \rightarrow (\lnot q \rightarrow (q \rightarrow p))$ --- C.P.1-5

but from it, you cannot derive 13) : $\lnot (p \lor \lnot q) \rightarrow (q \rightarrow p)$ ...

You must have :

13') $(p \land \lnot q) \rightarrow (q \rightarrow p)$ --- by Exportation

Then we have :

14') $\lnot (p \rightarrow q) \rightarrow (q \rightarrow p)$ --- from 13') by the equivalence : $(p \rightarrow q) \leftrightarrow \lnot (p \land \lnot q)$ ... but we have to justify it !

and finally :

$(p \rightarrow q) \lor (q \rightarrow p)$ --- Impl.14'.

Answer 4

Here you go.

Given the logical fact that a disjunction is true as long as long as at least one statement is true:

• Work from all the variables first
• Implications
• Disjunction from implications

The final result is that it is true in all possible worlds, a tautology.