Solutions to Chapter 21 Derived rules ‣ Solutions to selected exercices ‣ forall x: Calgary

A. Provide proof schemes that justify the addition of the third and fourth De Morgan rules as derived rules.

Third rule:

Line number	Subproof level	Formula	Justification
$m$	0	$\neg\mathscr{A}\wedge\neg\mathscr{B}$
$k$	0	$\neg\mathscr{A}$	$\wedge$ E $m$
$k+1$	0	$\neg\mathscr{B}$	$\wedge$ E $m$
$k+2$	open subproof, 1	$\mathscr{A}\vee\mathscr{B}$
$k+3$	open subproof, 2	$\mathscr{A}$
$k+4$	2	$\bot$	$\neg$ E $k+3$ , $k$
$k+5$	close subproof, open subproof, 2	$\mathscr{B}$
$k+6$	2	$\bot$	$\neg$ E $k+5$ , $k+1$
$k+7$	close subproof, 1	$\bot$	$\vee$ E $k+2$ , $k+3$ – $k+4$ , $k+5$ – $k+6$
$k+8$	close subproof, 0	$\neg(\mathscr{A}\vee\mathscr{B})$	$\neg$ I $k+2$ – $k+7$

Fourth rule:

Line number	Subproof level	Formula	Justification
$m$	0	$\neg(\mathscr{A}\vee\mathscr{B})$
$k$	open subproof, 1	$\mathscr{A}$
$k+1$	1	$\mathscr{A}\vee\mathscr{B}$	$\vee$ I $k$
$k+2$	1	$\bot$	$\neg$ E $k+1$ , $m$
$k+3$	close subproof, 0	$\neg\mathscr{A}$	$\neg$ I $k$ – $k+2$
$k+4$	open subproof, 1	$\mathscr{B}$
$k+5$	1	$\mathscr{A}\vee\mathscr{B}$	$\vee$ I $k+4$
$k+6$	1	$\bot$	$\neg$ E $k+5$ , $m$
$k+7$	close subproof, 0	$\neg\mathscr{B}$	$\neg$ I $k+4$ – $k+6$
$k+8$	0	$\neg\mathscr{A}\wedge\neg\mathscr{B}$	$\wedge$ I $k+3$ , $k+7$

B. The proofs you offered in response to the practice exercises of appendices 19 to 20 used derived rules. Replace the use of derived rules, in such proofs, with only basic rules. You will find some ‘repetition’ in the resulting proofs; in such cases, offer a streamlined proof using only basic rules. (This will give you a sense, both of the power of derived rules, and of how all the rules interact.)