Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$$(P_0 \lor P_1 \lor P_2\lor\ldots\lor P_n) \rightarrow Q $$

is the same as

$$(P_0 \rightarrow Q) \land (P_1 \rightarrow Q) \land (P_2 \rightarrow Q) \land\ldots\land(P_n \rightarrow Q)$$

Do I use strong or weak induction, and how should I go about with it. e.g. I don't have concrete sets to test this on.


Table for n=1 and n=2

I'm not quite sure whether I'm on the right track. When showing n = 2.

Table for n=k+1, I'm not quite sure how to formalize this intuition, help?

share|improve this question
    
,in my text , the proffesor mentioned that this is a tautology !! this text is : mathematical logic by daneil lascar and rene cori .. it didn't provide the proof . but this formula is tautology . good luck , i'm in my first step in the subject , so i can't help so much . i will wait to read the answer like you :) –  Maths Lover Feb 4 '13 at 1:25
add comment

3 Answers

There is no doubt the induction will be over $n$ here. Start with the base of the induction, that is the case $n=0$. Write both expressions above for the case $n=0$ and show they are equivalent. This should be particularly easy since the two expressions you will get will be typographically identical.

Now, while unneeded for the formal proof, it is a good idea to go ahead and prove the case $n=1$. Now there will be a little bit to do in order to show that the expressions are equivalent. When you are done with that go ahead and do the case $n=2$. You will see that you can do it by using the case $n=1$. This is already a hint that induction should work. Now, try the case $n=3$. By now you should be getting a very strong sense of deja vu. If not do the case $n=4$. Stop when the deja vu is there.

Now attempt the induction step. Assume that when $n=k$ the two expressions are equivalent and proceed to analyse the expressions when $n=k+1$. Use the deja vu feeling from the informal previous step. Formalize this current step and voila - a proof.

share|improve this answer
    
I like the déjà vu feeling. –  Brian M. Scott Feb 4 '13 at 1:02
    
i used a truth table to show it works when n = 1, but i'm a bit stuck on how to show it for n = 2, the truth table just gets too big, and i'm not sure what a more elegant way is. –  user60862 Feb 4 '13 at 2:09
    
@user60862: Please edit your own post; not people's answers. –  Asaf Karagila Feb 4 '13 at 2:48
    
sorry i made that edit by accident. –  user60862 Feb 4 '13 at 2:48
    
@BrianM.Scott do you mind commenting on my progress thus far? and perhaps providing a hint on how to formalize the proof. –  user60862 Feb 4 '13 at 2:53
show 1 more comment

You could use truth tables, which is quite unpleasant to some degree, or you can do the following:

Recall, or prove, that $p\rightarrow q$ is equivalent to $\lnot p\lor q$. The first implication can be written as: $$\lnot(P_1\lor\ldots\lor P_n)\lor Q$$

And by DeMorgan laws (which you have to prove by induction based on the law for two propositions), this is equivalent to $$(\lnot P_1\land\ldots\land\lnot P_n)\lor Q$$

Lastly, you should prove that $(A\land B)\lor C$ is equivalent to $(A\lor C)\land(B\lor C)$, and proceed with the obvious generalization by induction. Now we have: $$(\lnot P_1\lor Q)\land(\lnot P_2\lor Q)\ldots\land(\lnot P_n\lor Q)$$ which translates by the first identity used, to: $$(P_1\rightarrow Q)\lor\ldots\lor(P_n\rightarrow Q)$$


Note that there are several inductive proofs here (DeMorgan's generalization, the distributivity of disjunction over conjunction); but those are often a preliminary exercise or a given theorem. If they are not, it is much easier to prove those by induction than working through a maze of implications and disjunctions.

share|improve this answer
add comment

You can solve it "embedding" the induction into the formula itself.

You have that the "general case" can be written as :

$$[(P_0 \lor P_1 \lor P_2\lor\ldots\lor P_n) \lor P_{n+1}] \rightarrow Q $$

i.e. $[\mathcal{A} \lor P_{n+1}] \rightarrow Q $

But $P \rightarrow Q$ is $\lnot P \lor Q$, so that the above formula is :

$\lnot [\mathcal{A} \lor P_{n+1}] \lor Q $

Using De Morgan :

$[\lnot \mathcal{A} \land \lnot P_{n+1}] \lor Q $

now distribute :

$(\lnot \mathcal{A} \lor Q)\land (\lnot P_{n+1} \lor Q)$

i.e.

$(\lnot \mathcal{A} \lor Q) \land (P_{n+1} \rightarrow Q)$.

Now, what about $(\lnot \mathcal{A} \lor Q)$ ?

It is :

$\lnot (P_0 \lor P_1 \lor P_2\lor\ldots\lor P_n) \lor Q$

and using "general" De Morgan we have :

$(\lnot P_0 \land \lnot P_1 \land \lnot P_2 \land \ldots \land \lnot P_n) \lor Q$

Distribute again :

$(\lnot P_0 \lor Q) \land \ldots \land (\lnot P_n \lor Q)$

that is :

$(P_0 \rightarrow Q) \land \ldots \land (P_n \rightarrow Q)$

But this was $(\lnot \mathcal{A} \lor Q)$, so that the complete formula will be :

$(P_0 \rightarrow Q) \land \ldots \land (P_n \rightarrow Q) \land (P_{n+1} \rightarrow Q)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.