How to prove this using natural deduction

Question

$$⊢ P ∨ ¬P$$

I found this question on the net. I know the solution, but I find it complicated.

How should I approach this sort of question? Or can you provide me with another solution?

Answer 1

I don't know, whether you really find this helpful, but you could prove a bunch of other (generally useful) statements / rules first:

• $\neg(p \wedge q) \Rightarrow \neg p \vee \neg q$ (DM)
• $\neg(p \wedge \neg p)$ (PNC)
• $(p \vee q, p\vdash p', q \vdash q') \vdash p' \vee q'$ (CDL)

and then it should be easy:

1. $\neg(p\wedge \neg p)$ (by PNC)

2. $\neg p \vee \neg \neg p$ (by DM, 1.)

3. $\neg p \vdash \neg p$ (Assumption rule)

4. $\neg \neg p \vdash p$ (by $\neg\neg E$)

5. $p \vee \neg p$ (by CDL, 2.,3.,4.)

Here, for example, the proof for (PNC):

1. $p \wedge \neg p$ (H)
2. $\,\,\,\,$ $p$ $\,\,\,\,$ ($\wedge E1, 1.$)
3. $\,\,\,\,$ $\neg p$ $\,\,\,$ ($\wedge E2, 1.$)
4. $\,\,\,\,$ $\perp$ $\,\,\,\,$ ($\Rightarrow E$, 2., 3.)
5. $\neg(p \wedge \neg p)$ ($\Rightarrow I$, 1., 4.)