I'm new to discrete logic and I had this question that I couldn't
figure out what to do.  If anyone can help me get the answer to it itd
would help me a lot.
I need to be able to prove contructive dilemma works for more than
just 2 premises by using induction.
Contructive dilemma states:
p v q
p->r
q->s
-------
r v q

I know how to prove that example, but I can't figure out how to prove
it if say you add another line like:
p v q v z
p->r
q->s
z->x
-------
r v q v x

Reminder, I don't need it just for that example I need it for a
generalization for 'n' additions to it.

---

Clarification of Question by kaska-ga on 06 Dec 2003 19:14 PST

Also this question is needed by Monday AM EST.

---

Request for Question Clarification by endo-ga on 06 Dec 2003 19:23 PST

Hi,

Have you tried breaking it down? Something like this:

p v (q v z)
p -> r
(q v z) -> s
-----------
r v (q v z)


Then you have your recursive step, you jsut express q v z in function
of what you had previously.

Thanks.
endo

---

Clarification of Question by kaska-ga on 06 Dec 2003 20:16 PST

No, I haven't I'm new at this and not really that good at it. Does
sound like it might work.  I'm not sure if I'm good enough to do it
though, although I'll try.

It seems to me that the difficulty of this question lies not so much
in seeing the truth of the argument as in correctly applying the
mechanics of proof by induction. In what follows, I shall number an
arbitrary set of propositions from 1 to n in the following manner:
p[1], p[2], ..., p[n-1], p[n]. I use brackets in lieu of subscript
notation, so you should pronounce p[n] as "p subscript n".


Introduction
-------------

We shall prove by induction that

    p[1] V p[2] V ... V p[n-1] V p[n]
    p[1] -> q[1]
    p[2] -> q[2]
         .
         .
         .
    p[n-1] -> q[n-1]
    p[n] -> q[n]
    ---------------------------------
    q[1] V q[2] V ... V q[n-1] V q[n]

is true for all n >= 1.


Base Case
---------

From the premises

    p[1]
    p[1] -> q[1]

we immediately conclude that

    q[1].


Inductive Hypothesis
--------------------

We shall assume that

    p[1] V p[2] V ... V p[k-2] V p[k-1]
    p[1] -> q[1]
    p[2] -> q[2]
         .
         .
         .
    p[k-2] -> q[k-2]
    p[k-1] -> q[k-1]
    -----------------------------------
    q[1] V q[2] V ... V q[k-2] V q[k-1]

is true for all k greater than 1.


Inductive Step
---------------

Consider the premises

    p[1] V p[2] V ... V p[k-2] V p[k-1] V p[k]
    p[1] -> q[1]
    p[2] -> q[2]
         .
         .
         .
    p[k-2] -> q[k-2]
    p[k-1] -> q[k-1]
    p[k] -> q[k].


We know from the first clause that at least one of

    p[1], p[2], ..., p[k-1], p[k]

must be true.

Suppose that p[k] is true. It follows from the clause

    p[k] -> q[k]

that

    q[k].

On the other hand, suppose that p[k] is false.

But then one of

    p[1], p[2], ..., p[k-1]

must be true, so we have

    p[1] V p[2] V ... V p[k-2] V p[k-1].

But this, together with the premises

    p[1] -> q[1]
    p[2] -> q[2]
         .
         .
         .
    p[k-2] -> q[k-2]
    p[k-1] -> q[k-1]

implies, by the inductive hypothesis, that

    q[1] V q[2] V ... V q[k-2] V q[k-1].

Thus, whether p[k] is true or false, we have

    q[k] V (q[1] V q[2] V ... V q[k-2] V q[k-1])

which, by the commutative and associative laws, is just

    q[1] V q[2] V ... V q[k-2] V q[k-1] V q[k].
    

Conclusion
----------

Since the base case is true (n = 1), and the inductive hypothesis (n =
k-1) implies the inductive step (n = k) for all k > 1 (n >= 1), we
conclude that

    p[1] V p[2] V ... V p[n-1] V p[n]
    p[1] -> q[1]
    p[2] -> q[2]
         .
         .
         .
    p[n-1] -> q[n-1]
    p[n] -> q[n]
    ---------------------------------
    q[1] V q[2] V ... V q[n-1] V q[n]

is true for all n >= 1.


If you find my answer incomplete or inaccurate in any way, please let
me know so that I have a chance to meet your needs before you assign a
rating.

Regards,

leapinglizard

Wow, you explained that really well and in depth, thanks so much!