# 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)$$

-
if $q$ is true, then the left hand side of the disjunction is true. if $q$ is false, the right hand side of the disjunction is true. the "law of the excluded middle" assumes these are the only two truth values available to $q$ –  yoyo May 31 '11 at 23:19
yoyo's comment provides the answer in words. Note the particular case: $\vdash (p \to q) \lor (q \to p)$, which I find can easily confuse people about predicate logic or make them regard it as a meaningless manipulation of symbols. –  Henry May 31 '11 at 23:29

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.

-
Thank you, this is the solution I wanted. (edit: Stupid enter key) I also recommend learning LateX! Thank you again~ Edit 2: We only had the basic 10 axioms, plus LEM and Reductio Ad Absurdum (sp)? You did the trick only using the basics. Also taught me a few things that my course didn't. Such as line 2 to 3. I didn't realise I could introduce new variables in the introduction of a disjunction. If I did, I wouldn't have been so stuck ¬_¬ Then again, I refuse to spend £100 on a book. –  Clintonio Jun 1 '11 at 1:34
Glad I could provide some help here! I'll definitely have to work on learning LaTex. Could you vote up my answer? –  Doug Spoonwood Jun 1 '11 at 2:11

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)$$

-
@amWhy, yes, but---how does that use excluded middle? –  Gerry Myerson May 31 '11 at 23:41
The only possible truth values for q include true or false. If q is true, the entire statement is true, because (q(true) or notq(false)) evaluates true, and (q(false) or notq(true)) evaluates true. Hence, since a disjunctive proposition is true whenever one of the disjuncts is true, the entire proposition is true, regardless of the truth values of any of p q or r. –  amWhy Jun 1 '11 at 0:30
@amWhy, sorry, I didn't read your answer closely enough to see that "q or not q" in the middle of it. +1 for you, -7 for me. –  Gerry Myerson Jun 1 '11 at 0:46
Thank you, but it seems I'm using some strange simplified form of Propositional Logic where I have to write down each step, in a little neat list, with the line is affects. It's very annoying. Edit: I hate enter = submit. Anyway, I meant to finish with: I could do this logic alone, but the restrictions placed by my course make it more difficult than it has to be. It's a Formal Specification and Verification course. I did a year of pure mathematics, but switched to CS, where they make Maths a lot less fun >.> –  Clintonio Jun 1 '11 at 0:47
@Gerry: no problem...you had me second guessing my understanding of the LEM, though! :) No -7 for you!!! –  amWhy Jun 1 '11 at 0:48