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.

What is this rule of inference called?

$(P\wedge Q)\vee(P\wedge\neg Q)\vdash P$

My (silly) motivation is this answer.

share|improve this question
2  
I think that the name you have used is correct; the rule Peter Smith applied in his proof is called conjunction elimination, but also simplification : see Simplification –  Mauro ALLEGRANZA Mar 17 at 17:54
    
@MauroALLEGRANZA: Yours is, technically, the only attempt to answer my question! Thanks. –  Charles Mar 17 at 18:40
    
You are welcome ! :) –  Mauro ALLEGRANZA Mar 17 at 20:08
    
Distributive conjunctive elimination. –  Doug Spoonwood Mar 17 at 20:29
    
Distributive conjunction simplification. –  Doug Spoonwood Mar 18 at 1:22
show 1 more comment

3 Answers 3

Someone down voted dtldarek's answer, but his principal claim is plainly correct:

In a natural deduction system, start with the premiss:

$(P \land A) \lor (P \land B)$

then argue by cases (an intuitionistically acceptable mode of reasoning):

$\quad|\quad (P \land A)$

$\quad|\quad P$

$\quad/$

$\quad|\quad (P \land B)$

$\quad|\quad P$

Since we get to the same conclusion either way, we can discharge the two temporary assumptions and conclude

$P$.

Hence we have $(P\wedge A)\vee(P\wedge B)\vdash P$ whatever the $A$ and $B$, and so have $(P\wedge Q)\vee(P\wedge\neg Q)\vdash P$ as a special case. The special case doesn't depend on the law of excluded middle.

share|improve this answer
add comment

You don't need to use the law of excluded middle (i.e. this is true in intuitionistic logic too). In fact even a stronger statement is true:

$$(P \land A) \lor (P \land B) \to P$$

and you can prove it by the distributive law and projection (i.e. $P \land Q \to P$):

\begin{align} (P \land A) \lor (P \land B) &\to P\\ P \land (A \lor B) &\to P \\ P &\to P \end{align}

I hope this helps $\ddot\smile$

share|improve this answer
    
Why downvote?$ $ –  dtldarek Mar 17 at 18:39
    
zso now enough upvotes again:) –  Willemien Mar 17 at 20:30
add comment

It can be justified by distribution and the law of the excluded middle: $Q\lor \lnot Q \equiv T$:

$$(P \land Q)\lor (P \land \lnot Q) \equiv P \land (Q\lor \lnot Q) \equiv P$$

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.