proof by cases: if (P and Q) or (P and R), then P and (Q or R)

[chrislav]

Tried the following proof by cases:
Prove: [math](P\wedge Q)\vee (P\wedge R)\implies P\wedge(Q\vee R)[/math]Proof:
1)[math](P\wedge Q)\vee (P\wedge R)[/math] Assumption
2)[math](P\wedge Q)[/math]Hypothesis

3)[math] P[/math]2, Conjuncion elem.

4)[math]Q[/math]2, Conjunction elem.

5)[math]Q\vee R[/math]4,Disjunction introduction

6)[math] P\wedge(Q\vee R)[/math]3,5 Conjuction Introduction

7)[math](P\wedge Q)\implies P\wedge(Q\vee R)[/math]2 to 6 by conditional proof

8)[math]P\wedge R[/math]Hypothesis

9)[math] R[/math]8,Conjuction elem.

10)[math] R\vee Q[/math]9,Disjunction Introduction
11)[math] Q\vee R[/math]10, commutativity

12[math]P\wedge (Q\vee R)[/math]3,11 conjuction Introduction

13)[math]P\wedge R\implies P\wedge (Q\vee R)[/math] 8 to 12 by conditional proof
14)[math]P\wedge (Q\vee R)[/math]1,7,13 using proof by cases
But somebody insisted that i did a fatal mistake somewhere

where




12

 

[pka]

Tried the following proof by cases:
Prove: [math](P\wedge Q)\vee (P\wedge R)\implies P\wedge(Q\vee R)[/math]

Please tell us from where this question comes; what textbook gives this as an exercise?
This half of a well known basic property distributions: [imath]P\wedge(Q\vee R) \equiv (P\wedge Q)\vee(P\wedge R) [/imath].
That is: and is disturbed over an or Proved with truth tables.

Were I to try a proof of [imath]P\wedge(Q\vee R) \Rightarrow (P\wedge Q)\vee(P\wedge R) [/imath] with cases here would my approach.
Case I, [imath]P\wedge(Q\vee R)\equiv F[/imath] a false implies any statement. Thus we have the whole is true.

Case II. [imath]P\wedge(Q\vee R)\equiv T[/imath]
In order for for the conjunction to be true both conjuncts must be true.
So [imath]P\equiv T~\& (Q\vee R)\equiv T[/imath]
Using [imath](Q\vee R)\equiv T[/imath] Can you finish?
[imath][/imath][imath][/imath]

 

[chrislav]

In propositional calculus there are two kinds of proofs:
1) The semantical proof which is based on the use of truth tables and
2) the syntactical one where one can use basic rules of inference (tested to be valid,using truth tables) so the words true all false are not used
The above is a syntactical proof
The rule of proof by cases is the following:
[math]S\vee T[/math] and [math]S\implies R[/math] and [math]T\implies R[/math]All the above implies: [math] R[/math] This rule can be found in nearly any book of logic
For examle in Angelo Margaris book FIRST ORDER MATHEMATICAL LOGIC ,page 72

 

[Dr.Peterson]

Tried the following proof by cases:
Prove: [math](P\wedge Q)\vee (P\wedge R)\implies P\wedge(Q\vee R)[/math]Proof:
1)[math](P\wedge Q)\vee (P\wedge R)[/math] Assumption
2)[math](P\wedge Q)[/math]Hypothesis

3)[math] P[/math]2, Conjuncion elem.

4)[math]Q[/math]2, Conjunction elem.

5)[math]Q\vee R[/math]4,Disjunction introduction

6)[math] P\wedge(Q\vee R)[/math]3,5 Conjuction Introduction

7)[math](P\wedge Q)\implies P\wedge(Q\vee R)[/math]2 to 6 by conditional proof

8)[math]P\wedge R[/math]Hypothesis

9)[math] R[/math]8,Conjuction elem.

10)[math] R\vee Q[/math]9,Disjunction Introduction
11)[math] Q\vee R[/math]10, commutativity

12[math]P\wedge (Q\vee R)[/math]3,11 conjuction Introduction

13)[math]P\wedge R\implies P\wedge (Q\vee R)[/math] 8 to 12 by conditional proof
14)[math]P\wedge (Q\vee R)[/math]1,7,13 using proof by cases
But somebody insisted that i did a fatal mistake somewhere

where




12

One thing I see that is wrong is that in line 12 you use P without having isolated it in the second case, as you did in line 3 for the first case (to be used in line 6).

 

[chrislav]

And why this is wrong?

 

[Dr.Peterson]

And why this is wrong?

Isn't it obvious?
In your pattern here,

In propositional calculus there are two kinds of proofs:
1) The semantical proof which is based on the use of truth tables and
2) the syntactical one where one can use basic rules of inference (tested to be valid,using truth tables) so the words true all false are not used
The above is a syntactical proof
The rule of proof by cases is the following:
[imath]S\vee T[/imath] and [imath]S\implies R[/imath] and [imath]T\implies R[/imath]
All the above implies: [imath] R[/imath]
This rule can be found in nearly any book of logic
For examle in Angelo Margaris book FIRST ORDER MATHEMATICAL LOGIC ,page 72

you didn't show that [imath]T\implies R[/imath], because you didn't derive everything in the second case from facts assumed in that case.

 

[chrislav]

And why is not allowed to use facts derived (like P ,in our case) in the 1st case?
Which law of logic is violated here.
The only fact assumed in the 2nd case is "P&R"and we used that fact to derive the desired result

 

[Dr.Peterson]

And why is not allowed to use facts derived (like P ,in our case) in the 1st case?
Which law of logic is violated here.
The only fact assumed in the 2nd case is "P&R"and we used that fact to derive the desired result

You are working on two separate cases. You can't borrow a fact from one case to use in the other. That is what you did when you used line 3, in the first case, to support line 12, in the second case. Line 3 is supported by the hypothesis in line 2, which defines the first case. You need to repeat that same fact after line 8, which defines the second case.

Obviously everything is still correct, because P is in fact present in both cases; but your reasoning didn't explicitly state that P is present in the second case, so the reasoning is incomplete.

I'm not sure whether this is the "fatal mistake" someone told you about; perhaps there is something else I'm missing. But this is definitely a flaw in the logic. Mathematical proofs must be correct in detail.

 

[chrislav]

Ι did ask which law of logic i violated in my proof
Anyway the above is a formal proof in propositional calculus and the proof can only be two things either correct or incorrect and nothing else (for example incomplete as you have claimed)
For correctness all laws of logic must be correct and for incorrectness a law of logic nust be violated
Which is that law?
you write and i quote "You can't borrow a fact from one case to use in the other" Which meta theorem in psopositional calculus supports that?

 

[Dr.Peterson]

Ι did ask which law of logic i violated in my proof
Anyway the above is a formal proof in propositional calculus and the proof can only be two things either correct or incorrect and nothing else (for example incomplete as you have claimed)
For correctness all laws of logic must be correct and for incorrectness a law of logic nust be violated
Which is that law?
you write and i quote "You can't borrow a fact from one case to use in the other" Which meta theorem in psopositional calculus supports that?

A proof can be incorrect because it is incomplete! What I'm saying is that there is one line you can add to make it complete, and therefore correct.

Part of the problem here is that there are different presentations of things called "propositional calculus" (the Wikipedia article gives multiple examples of such things), so I don't know the exact terms to use in your version. But the basic concept should be clear: You can only use propositions that are known to be true at the point where you use them.

Here, for example (a randomly chosen site teaching logic, with a slightly different notation than yours), section 5.2.3, Assumptions & Subproofs, says

You can use derivation rules to reason within subproofs, but there are certain restrictions. The basic rule is the following:​

​

If P is in a section of the proof S1 that contains another subproof S2, then P can be used to reason in S2. If R is in a section of the proof S3 that does not contain a subproof S4, then R cannot be used in S4.​

This is followed by a couple examples of ways in which this can be violated. What I called a "case" is what they are calling here a "subproof". You are using in one subproof a proposition that was derived in another subproof, from an assumption made in that subproof.

Does that make sense?

 

[pka]

The rule of proof by cases is the following:
[imath]S\vee T[/imath] and [imath]S\implies R[/imath] and [imath]T\implies R[/imath]
All the above implies: [imath] R[/imath]
This rule can be found in nearly any book of logic.

First, thank you for providing the name of the textbook.
Angelo Margaris book FIRST ORDER MATHEMATICAL LOGIC
To my surprise, I did not know that textbook nor did collogues.
It appears that Marganis taught at Rhodes College but not now nor is the book in print.
But I digress; sorry, Reading through this thread again, it occurs to me that you may be referring to conditional proofs, (CP}.
That a well-known proof technique. Quoting Copi from Symbolic Logic: "this rule applies only to arguments whose conclusions are conditional statements. Having taught Mathematical (symbolic)logic for over forty years, both to undergraduates & graduates students and thus have dozens of logic textbooks none of which has a discussion of proofs by cases. Please read that LINK

 

[chrislav]

Use this truth generator to check the validity of that rule (proof by cases)

Step by step Truth Table Generator

Simple to use Truth Table Generator for any given logical formula. The step by step breakdown of every intermediate proposition sets this generator apart from others.

trutabgen.com

Further more i can give you
a syntactical proof using simple laws of inference

 

[Dr.Peterson]

Use this truth generator to check the validity of that rule (proof by cases)

Yes, "proof by cases" is valid. But are you entirely unable to see that you are applying it incorrectly (though a very small change will correct it)?

Here are a couple places I find the term used (in different contexts):

Proof by Cases/Proof Rule - ProofWiki

proofwiki.org

Proof by exhaustion - Wikipedia

en.wikipedia.org

Disjunction elimination - Wikipedia

en.wikipedia.org

https://www.math.cmu.edu/~mradclif/teaching/127S19/Notes/Logic and Proof.pdf (section 5)

 

[chrislav]

You wrote and i qoute "Yes, "proof by cases" is valid. But are you entirely unable to see that you are applying it incorrectly (though a very small change will correct it)?"

Show me then

And if you wish give a syntactical proof to clear things out

 

[farhan]

Case 1: P and Q are both true. In this case, we have P is true, and since (P and Q) is true, Q must also be true. Therefore, (Q or R) is true, and we have P and (Q or R).

Case 2: P and R are both true. Similarly, in this case, we have P is true, and since (P and R) is true, R must also be true. Therefore, (Q or R) is true, and we have P and (Q or R).

Case 3: P is true, and Q and R are both false. In this case, neither (P and Q) nor (P and R) is true. Therefore, the original statement is vacuously true, and we have P and (Q or R).

Since have shown that the original statement is true in all possible cases, we can conclude that the statement is true. Therefore, if (P and Q) or (P and R), then P and (Q or R).

 

[MaxMath]

The only improvement I can see is to add a line similar to 3) between lines 8) and 9), in terms of steps (not terminology).