3
$\begingroup$

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

  • 0
    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.2011-05-31

2 Answers 2

2

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. 
  • 0
    Glad I could provide some help here! I'll definitely have to work on learning LaTex. Could you vote up my answer?2011-06-01
10

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

  • 0
    Part o$f$ learnin$g$ is lear$n$ing to be able to translate an inference, name, definition, etc, to terms one is used to. Conceptual understanding is the key. If one recognizes the inference at play, one should be able to identify the name for the rule that one has learned. At any rate, I appreciate your constructive criticism; I did not catch what system/approach the user was accustomed to/constrained to. I do think, though, that asking why others would want to vote up my answer was a little over the top.2011-06-01