Conjunction reasoning rules

Propositional Logic: Natural deduction

Conjunction reasoning rules

Introduction rule for conjunction The introduction rule \(\land\,\mathrm{I}\) for the connective \(\land\) is as follows:

\[\begin{array}{l|ll} \vdots & \vdots &\\ k &\varphi & \\ \vdots & \vdots & \\ l &\psi & \\ \vdots & \vdots & \\ m & \varphi\land\psi & \land\,\mathrm{I}, k, l \end{array}\]

Examples

\(p, q\vdash p\land q\)	\(p\vdash p\land p\)	\(p, q, r\vdash (r\land p)\land q\)
\[\begin{array}{l\|ll} 1 & p & (\mathrm{P}) \\ 2 & q & (\mathrm{P}) \\ 3 & p\land q & \land\,\mathrm{I}, 1,2 \end{array}\]	\[\begin{array}{l\|ll} 1 & p & (\mathrm{P}) \\ 2 & p\land p & \land\,\mathrm{I}, 1,1 \end{array}\]	\[\begin{array}{l\|ll} 1 & p & (\mathrm{P}) \\ 2 & q & (\mathrm{P}) \\ 3 & r & (\mathrm{P}) \\ 4 & r\land p & \land\,\mathrm{I}, 3,1 \\ 5& (r\land p)\land q & \land\,\mathrm{I}, 4,2\end{array}\]

Elimination rule for conjunction The elimination rule \(\land\,\mathrm{E}\) for the connective \(\land\) can be applied in two ways:

\[\begin{array}{l|ll} \vdots & \vdots &\\ k &\varphi\land\psi & \\ \vdots & \vdots & \\ l & \varphi & \land\,\mathrm{E}, k \end{array}\]

\[\begin{array}{l|ll} \vdots & \vdots &\\ k &\varphi\land\psi& \\ \vdots & \vdots & \\ l & \psi & \land\,\mathrm{E}, k \end{array}\]

Examples

\(p\land q\vdash p\)	\(p\land q\vdash q\land p\)	\(p\land(q\land r)\vdash (p\land q)\land r\)
\[\begin{array}{l\|ll} 1 & p\land q & (\mathrm{P}) \\ 2 & p &\land\,\mathrm{E}, 1 \end{array}\]	\[\begin{array}{l\|ll} 1 & p\land q & (\mathrm{P}) \\ 2 & p &\land\,\mathrm{E}, 1 \\ 3 & q &\land\,\mathrm{E}, 1 \\ 4 & q\land p & \land\,\mathrm{I},3,2\end{array}\]	\[\begin{array}{l\|ll} 1 & p\land(q\land r) & (\mathrm{P}) \\ 2 & p & \land\,\mathrm{E}, 1\\ 3 & q\land r & \land\,\mathrm{E}, 1 \\ 4 & q & \land\,\mathrm{E}, 3 \\ 5 & r & \land\,\mathrm{E}, 3 \\ 6 & p\land q & \land\,\mathrm{I},2,4\\ 7 & (p\land q)\land r & \land\,\mathrm{I},6,5\end{array}\]