Back to the class
Quiz 3
Write a formal proof to show that if $\mathscr{F}=\{P \rightarrow Q, Q \rightarrow R, \neg R \vee S, P \}$, then $\mathscr{F} \vdash S$.
Solution:
$$\begin{array}{|l|l|}
\hline
1. \mathscr{F} \vdash P\rightarrow Q & \mathrm{Assumption} \\
2. \mathscr{F} \vdash P & \mathrm{Assumption} \\
3. \mathscr{F} \vdash Q & \rightarrow\text{-elimination on lines 1 and 2} \\
4. \mathscr{F} \vdash Q \rightarrow R & \mathrm{Assumption} \\
5. \mathscr{F} \vdash R & \rightarrow\text{-elimination on lines 3 and 4} \\
6. \mathscr{F} \vdash \neg R \vee S & \mathrm{Assumption} \\
7. \mathscr{F} \vdash R \rightarrow S & \rightarrow\text{-definition on line 6} \\
8. \mathscr{F} \vdash S & \rightarrow\text{-elimination on lines 5 and 7} \\
\hline
\end{array}$$