Proof verification for natural deduction in propositional logic

851 Views Asked by At

I wanted to know if the following natural deduction proof is correct.

    (p ⇒ r) ∨ (q ⇒ r) ├ (p ∧ q) ⇒ r
1       (p ⇒ r) ∨ (q ⇒ r)      Assump o
2       (p ∧ q) ├ r        
2.1     p ∧ q                   Assump 2
2.2     r                       V E 1,2
3       (p ∧ q) ⇒ r            ⇒I 2       
1

There are 1 best solutions below

3
On BEST ANSWER

No. You use of $\vee-$elimination is wrong. The proof rule works as is we know that $A\vee B$ hold, $A\vdash C$ and $B\vdash C$, then we may conclude $C$. In this specific case you you know that $(p\to r) \vee (q\to r) $ hold, thus is you prove a sentence $C$, you need to show that $p\to r\vdash C$ and $q\to r\vdash C$.

In this specific case you want to prove $(p\wedge q)\to r$, something you do (preferrable) by $\to$-introduction i.e. show that $p\wedge q\vdash r$.

So to give you an outline: Show that $p\wedge q\vdash r$ hold, by assuming $p\wedge q$ and then try to prove $r$. Now to prove $r$, do $\vee-$elimination as I described above.