Prove that $(p \to q) \lor (q \to p)$ is a tautology using natural deduction I have to prove that '  (p ⊃ q) ∨ ( q ⊃ p) ' is a tautology.I have to start by giving assumptions like     a1 ⇒ p ⊃ q and then proceed by eliminating my assumptions and at the end i should have something like ⇒(p ⊃ q) ∨ ( q ⊃ p) but could not figure out how to start.
 A: As a quick overview: You should be able to show $p\vdash q\supset p$ as well as $\neg p\vdash p\supset q$, and then by case distinction $p\lor\neg p\vdash (p\supset q)\lor (q\supset p)$.
A: (p ⊃ q) ∨ ( q ⊃ p) 
I assume that
"⊃" means "implies".
Actually,
since your statement
is symmetric in p and q,
it doesn't matter if
"a ⊃ b" means
"a implies b"
or
"b implies a".
Since
"a ⊃ b"
is equivalent to
"~a ∨ b",
your statement is
equivalent to
"(~p ∨ q) ∨ ( ~q ∨ p)".
Since
"∨" is commutative
and associative,
this is the same as
"(p ∨ ~p)∨(q ∨ ~q)"
which is always true.
Is this what you wanted?
A: If you are allowed to use the law of the exluded middle, then propositional logic proofs are straight forward.  You have 2 variables, that means you have 4 cases.  Then you combine the cases using LEE and Or-Elimination.  It looks like:
Dedution 1:
$$\begin{array} {r|l}
(11) & p \land q \\
(12) & p \\
(13) & q \\
     & \vdots \\
(1.) & p \implies q \\
(1.) & (p \implies q) \lor (q \implies p)
\end{array}$$
Deduction 2:
$$\begin{array} {r|l}
(21) & p \land \lnot q \\
(22) & p \\
(23) & \lnot q \\
     & \vdots \\
(2.) & q \implies p \\
(2.) & (p \implies q) \lor (q \implies p)
\end{array}$$
Deduction 3:
$$\begin{array} {r|l}
(31) & \lnot p \land q \\
     & \vdots \\
(3.) & p \implies q \\
(3.) & (p \implies q) \lor (q \implies p)
\end{array}$$
Deduction 4:
$$\begin{array} {r|l}
(41) & \lnot p \land \lnot q \\
     & \vdots \\
(4.) & p \implies q \quad \text{(You could also establish }q \implies p\text{ here.)} \\
(4.) & (p \implies q) \lor (q \implies p)
\end{array}$$
Also, you can assume $p \lor \lnot p$ and $q \lor \lnot q$.
What's left is to fill in the $\vdots$, organize the deductions, and use Or-Eliminations to suck the $(p \implies q) \lor (q \implies p)$ out of all the deductions.
A: $(p\rightarrow q)\lor (q\rightarrow p)\equiv (\lnot p\lor q)\lor (\lnot q\lor p)\equiv \lnot p\lor (q\lor\lnot q)\lor p\equiv \lnot p\lor T\lor p\equiv \lnot p\lor p\equiv T$
A: Start off by showing the law of the excluded middle (p V $\lnot$ p).
Put the proof of law of excluded middle here such that it ends as follows:
(p V $\lnot$ p)
Hypothesize p
    Hypothesize r
     .
     .
     .
     p
(r -> p)
((p -> q) V (r -> p))

(p -> ((p -> q) V (r -> p)))
 Hypothesize ~p
     hypothesize p
     .
     .
     .
     q
 (p -> q)
 ((p -> q) V (r -> p))

(~p -> ((p -> q) V (r -> p)))
By disjunction elimination, 
((p -> q) V (r -> p)).
Therefore,
((p -> q) V (q -> p)).
End of proof.
One might see that:
(q -> ((p -> q) V (r -> p)))
is a theorem also.
In Polish notation one can write:
CqACpqCrp.  This is a special case of a more general tautology:
CpACqrCsq.  If you did all of calculations involving CpACqrCsq and CpACpqCrp you would find that the calculations involving CpACqrCsq has all the instances of CqACpqCrp.  Additionally, say we start with 


*

*CpACqrCsq.  


Now, we'll put 'a' for every instance of 'p', 'b' for every instance of 'q', 'c' for every instance of 'r', and 'd' for every instance of 's' in CpACqrCsq.  Doing that, we obtain:


*CaACbcCdb.  


Now we put 'q' for 'a', 'p' for every instance of 'b', 'q' for every instance of 'c', and 'r' for 'd' obtaining:


*CqACpqCrp.


Thus, CqACpqCrp can get obtained from CpACqrCsq and using just a rule of substitution.  But, we cannot obtain CpACqrCsq from CqACpqCrp, since CpACqrCsq has more distinct letters in it and they have the same length and the same pattern of big letters.
CpACqrCsp is also a tautology.
CpACpqCrp is also a tautology.     
CNpACpqCrs is also a tautology.
CNpACqrCsq is also a tautology.  
