Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What is this rule of inference called?

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

My (silly) motivation is this answer.

share|cite|improve this question
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 '14 at 17:54
@MauroALLEGRANZA: Yours is, technically, the only attempt to answer my question! Thanks. – Charles Mar 17 '14 at 18:40
You are welcome ! :) – Mauro ALLEGRANZA Mar 17 '14 at 20:08
Distributive conjunctive elimination. – Doug Spoonwood Mar 17 '14 at 20:29
Distributive conjunction simplification. – Doug Spoonwood Mar 18 '14 at 1:22

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 (P \land B)$

$\quad|\quad P$

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


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|cite|improve this answer

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|cite|improve this answer
Why downvote?$ $ – dtldarek Mar 17 '14 at 18:39
zso now enough upvotes again:) – Willemien Mar 17 '14 at 20:30

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|cite|improve this answer

Your Answer


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.