Nat Deduction Proof - Distributive property

Question

I need to prove $(P \lor Q) \land (P \lor R) \vdash P \lor (Q \land R)$ using natural deduction and propositional logic. I should be able to do it using only AND and OR rules, but I am stuck on how to assume $Q$ and $R$. This is what I have:

$(P \lor Q) \land (P \lor R)$ ________premise

$P \lor Q$ ________________^e1___1

$P \lor R$ ________________^e2___1

...$P$__________________assumption

...$P \lor (Q \land R)$ ___________vi1___4

I know this is right so far. I just don't know how to introduce my assumptions for $Q$ and $R$. Do I assume $\neg P$? If so, which rule is applied, and what is the process, to conclude $Q \land R$? Thanks for any help you can give me

Answer 1

Assume $\rm \neg P$, then from 2 and 3 derive $\rm Q$ and $\rm R$. From that you have $\rm Q\wedge R$, and so on...

The rule, $\rm \neg P,\, P\vee Q \,\vdash\, Q$ , is called Deductive Syllogism. Sometimes also known as disjunctive elimination ($\rm\vee e$), or historically as modus tollendo ponens.

Answer 2

It depends on which rules you have for eliminating the disjunction.

If you indeed have the Disjunctive Syllogism, you can begin as Graham Kemp writes. But to complete, you will need Reductio ad Absurdum. From your question, however, I take it that you should not use that rule, and therefore not the Deductive Syllogism either.

The other standard option is that your disjunction elimination is a case analysis, which allows you to prove directly:

$P \vee Q, P \rightarrow R, Q \rightarrow R \vdash R$

To solve your problem, you need to apply this rule twice. Here is an outline. First, make two more assumptions, namely $Q$ and $R$. Second, introduce conjunction and disjunction to obtain $P \vee (Q \wedge R)$. Apply disjunction elimination for a first time (for example, on $P \vee R$, which will discharge $R$). Then apply it a second time, which will discharge the other assumption.

I can't write down the derivation since I don't know your variant of the calculus. That should be easy for you now, I hope.

Answer 3

It's easier to show $\wedge$ distributes over $\vee$ than vice-versa. And the latter follows straightforwardly from the former. So you might first try showing $(Q \vee R) \wedge P \vdash (Q \wedge P) \vee (R \wedge P)$, and use those arguments or the fact itself in the needed proof. To show $\wedge$ distributes over $\vee$, make use of $P \wedge Q \vdash R$ if and only if $P \vdash Q \rightarrow R$. (This shows that $ \_ \wedge Q$ is a left adjoint of $Q \rightarrow \_$, and left adjoints preserve joins. For "and" to distribute over "or" means the same thing as the "and" operator to preserve binary disjunction, a join.) In formal deduction of $(Q \vee R) \wedge P \vdash (Q \wedge P) \vee (R \wedge P)$, you can use the inference law I mentioned to isolate $Q \vee R$ to the left of $\vdash$ and deal with $Q$ and $R$ separately. Even if you want to show the needed result directly, the idea is that whenever you need to show an inference with a hypothesis that is a conjunction where one conjunct is a disjunction, use the inference law I mentioned to create an equivalent inference with hypothesis the disjunction, which inference can be broken up into simpler inferences each involving as hypothesis a disjunct, and each of these inferences can be dealt with by using the reverse direction of the inference law to remove the implication that was created.

Answer 4

Given $( P \lor Q ) \land ( P \lor R )$:

  $P \lor Q$. [$\land$ elimination]

  $P \lor R$. [$\land$ elimination]

  If $P$:

    $P \lor ( Q \land R )$. [$\lor$ introduction]

  If $Q$:

    If $P$:

      $P \lor ( Q \land R )$. [$\lor$ introduction]

    If $R$:

      $Q \land R$. [$\land$ introduction]

      $P \lor ( Q \land R )$. [$\lor$ introduction]

    $P \lor ( Q \land R )$ [$\lor$ elimination (by $P \lor R$)]

  $P \lor ( Q \land R )$ [$\lor$ elimination (by $P \lor Q$)]