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

  • 7
    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$2011-05-31
  • 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
    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.2011-06-01
  • 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
    @amWhy, yes, but---how does that use excluded middle?2011-05-31
  • 0
    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.2011-06-01
  • 0
    @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.2011-06-01
  • 0
    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 >.>2011-06-01
  • 0
    @Gerry: no problem...you had me second guessing my understanding of the LEM, though! :) No -7 for you!!!2011-06-01
  • 0
    @Clintonio: I hate that "enter" = submit as well!! (in the comments)...I'm finally getting used to it, but it took awhile! Can you adapt the proof above to suit the requirements of your class? Each $\iff$ denotes an equivalent expression to the expression immediately above it. I'm assuming you're familiar with the equivalence of ($p\to q$) and ($\lnot p \lor q$). If not, have you used the equivalence $(p\to q$) and $\lnot(p \land \lnot q)$? From the latter you can obtain the former by DeMorgan's.2011-06-01
  • 0
    The reasoning here shows that |=(p→q)∨(q→r) (semantic validity). The author asked for ⊢(p→q)∨(q→r) (syntactically yielded formula). In other words, he asked it to get shown as a theorem, instead of a tautology. Though, a completeness theorem does hold for classical propositional logic, you'd need to state it here, and already have proved it for propositional logic, and then you'd have to use it in the proof. How did this get so many up votes?2011-06-01
  • 0
    @Doug: I'm not clear what you mean. The entire "theorem" can be constructed by starting from ($q \lor \lnot q$) alone (i.e., starting from the law of the excluded middle). A true statement remains true regardless of any extention to it through the use of additional disjuncts, whatever they may be.2011-06-01
  • 0
    A "theorem" in the context of formal logic usually means a well-formed formula which has gotten *derived* using rules of inference or axioms. Theorems do not necessarily have any reference to "truth" or any other semantic concept. In order to derive a theorem you can only use rules of inference or axioms of the system. To show a tautology you may make a reference to truth values as you did, but for theorems of formal logic this only holds if treat the semantic concept of truth as a syntactic entity.2011-06-01
  • 0
    Thank you all for your help. Doug Spoonwood answered the question within the confines of Propositional Logic with the restricted ruleset we have to play with!2011-06-01
  • 0
    @amWhy Though the second argument you gave didn't come as what the original post of this question wanted, (given certain strings as abbreviations of wffs) it does qualify as a proof instead of just a semantic argument. Do you see how your second proof doesn't make any appeal to truth or other semantic concepts necessarily? That's along the lines of what I meant to say.2011-06-01
  • 0
    The post wasn't really clear about what was wanted: emphasizing PROPOSITIONAL logic and NOT predicate (which was all anyone used here: propositional logic). The only clue that you pointed out was the turnstile/double turnstile distinction, which I hadn't paid close enough attention to. Additionally, we try, here, not to solve problems step by step, for students to "copy"...we try to lay out the reasoning, some justification, etc.. There are so many "names" for different rules of inference, we cannot hope to read a user's mind to guess which one s/he knows and stick with that.2011-06-01
  • 0
    Part of learning is learning 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