Afleidingen in Hilbert's systeem: pen-en-papier opdrachten (2 opdrachten)

Propositielogica: Hilbert's deductief systeem

Afleidingen in Hilbert's systeem: pen-en-papier opdrachten (2 opdrachten)

Maak eerst elke opdracht zelf en vergelijk daarna pas jouw antwoord met de uitwerking.

Toon aan dat $p\rightarrow q, q\rightarrow r \vdash p\rightarrow r$ .

Uitwerking

$\begin{array}{l|ll} 1 & p\rightarrow q & (\mathrm{P})\\ 2 & q\rightarrow r & (\mathrm{P})\\ 3& (q\rightarrow r) \rightarrow \bigl(p\rightarrow(q\rightarrow r)\bigr) & \mathrm{Ax\;a}\text{ met }\varphi=(q\rightarrow r), \psi=p\\ 4 & p\rightarrow (q\rightarrow r) & \mathrm{MP}, 2, 3\\ 5 & \bigl(p\rightarrow (q\rightarrow r)\bigr) \rightarrow \bigl((p\rightarrow q)\rightarrow (p\rightarrow r)\bigr)& \mathrm{Ax\;a}\text{ met }\varphi=p, \psi=q, \chi=r\\ 6 & (p\rightarrow q)\rightarrow (p\rightarrow r) & \mathrm{MP}, 4, 5\\ 7 & p\rightarrow r & \mathrm{MP}, 1, 6\end{array}$

Merk op dat deze bewering met de Deductiestelling volgt uit de eerder als voorbeeld gekozen afleiding van $p\rightarrow q, q\rightarrow r, p\vdash r$ .

Toon aan dat $p\rightarrow ( q\rightarrow r) \vdash q\rightarrow (p\rightarrow r)$ .

Uitwerking

Uit de deductiestelling volgt dat het volstaat om aan te tonen dat $p\rightarrow ( q\rightarrow r), q \vdash r$ . De afleiding hiervan gaat als volgt: $\begin{array}{l|ll} 1 & q & (\mathrm{P})\\ 2 & p\rightarrow (q\rightarrow r) & (\mathrm{P})\\ 3 & q\rightarrow (p\rightarrow q) & \mathrm{Ax\;a}\text{ met }\varphi=q, \psi=p\\ 4 & p\rightarrow q & \mathrm{MP}, 1, 3\\ 5 & \bigl(p\rightarrow (q\rightarrow r)\bigr) \rightarrow \bigl((p\rightarrow q)\rightarrow (p\rightarrow r)\bigr)& \mathrm{Ax\;a}\text{ met }\varphi=p, \psi=q, \chi=r\\ 6 & (p\rightarrow q)\rightarrow (p\rightarrow r) & \mathrm{MP}, 2, 4\\ 7 & p\rightarrow r & \mathrm{MP}, 4, 6\end{array}$