Help with Law of Excluded Middle I've got a problem with the law of excluded middle, and have a homework question surrounding it.
I normally would never ask, and this is my first time, but I can't for the life of me find an example on my university's website with LEM in it.
Here is the question:
Prove the validity of the sequents below (using LEM)
$$
\vdash (p \to q) \lor (q \to r)
$$
 A: What rules of inference and/or axioms do you have to work with?  If you have a natural deduction system, a possible proof [in Polish notation, Cxy means (x->y), Axy means (x V y), Nx means ~x, Kxy means (x ^ y)] might go)
1  ACpqNCpq form of the law of the excluded middle
2  | Cpq assumption
3  | ACpqCqr 2 alternation/disjunction-introduction
4  CCpqACpqCqr 2-3 Conditional Introduction
5  |    NCpq assumption
6  ||   q assumption
7  |||  Nr assumption
8  |||| p assumption
9  |||| q 6, repetition
10 |||  Cpq 8-9 conditional introduction
11 |||  KCpqNCpq 10, 5 conjunction introduction
12 ||   r 7-11 negation elimination
13 |    Cqr 6-12 conditional introduction
14 |    ACpqCqr 13 alternation introduction
15 CNCpqACpqCqr 5-14 conditional introduction
16 ACpqCqr 1, 4, 15 alternation elimination.

A: We can show that the sequents: $(p \to q) \lor (q \to r)$ is a tautology.
$((p \to q) \lor (q \to r))$ 
$\iff ((\lnot p \lor q) \lor (\lnot q \lor r))$
$\iff (\lnot p \lor \color{blue}{\bf (q \lor \lnot q)} \lor r)$
$\iff (\lnot p \lor \color{blue}{\bf\text{TRUE}} \lor r)\qquad$ by $\color{blue}{\bf LEM}$ (Either $q$ is true, or else $\lnot q$ is true.)
$\equiv \text{TRUE}$
$\therefore$ The sequent is valid as a tautology.
For a more detailed discussion of the Law of Excluded Middle (LEM), see this Wiki article

Note, one can "build up" (derive) the desired expression from only an application of the law of the excluded middle: 
Start with $q \lor \lnot q$.  
Introduce the disjunct $\lnot p$, to get $\lnot p \lor (q \lor \lnot q)$.
Through associativity of disjunction, we can express that as $(\lnot p \lor q) \lor \lnot q$.
Introduce another disjunct $r$, to get $(\lnot p \lor q) \lor \lnot q \lor r$, and 
Through associativity of disjunction, again, we can arrive at $(\lnot p \lor q) \lor (\lnot q \lor r)$.
Now we need only apply equivalences discussed above to arrive at the proposition: $$(p \to q) \lor (q \to r)$$  
