Appendix C Quick reference

C.1 Characteristic truth tables

$\mathscr{A}$	$\neg$ $\mathscr{A}$
T	F
F	T

$\mathscr{A}$	$\mathscr{B}$	$\mathscr{A}\wedge\mathscr{B}$	$\mathscr{A}\vee\mathscr{B}$	$\mathscr{A}\rightarrow\mathscr{B}$	$\mathscr{A}\leftrightarrow\mathscr{B}$
T	T	T	T	T	T
T	F	F	T	F	F
F	T	F	T	T	F
F	F	F	F	T	T

C.2 Symbolization

Sentential Connectives
It is not the case that $P$	$\neg P$
Either $P$ or $Q$	$(P\vee Q)$
Neither $P$ nor $Q$	$\neg(P\vee Q)$ or $(\neg P\wedge\neg Q)$
Both $P$ and $Q$	$(P\wedge Q)$
If $P$ then $Q$	$(P\rightarrow Q)$
$P$ only if $Q$	$(P\rightarrow Q)$
$P$ if and only if $Q$	$(P\leftrightarrow Q)$
$P$ unless $Q$	$(P\vee Q)$
Predicates
All $F$ s are $G$ s	$\forall x(F(x)\rightarrow G(x))$
Some $F$ s are $G$ s	$\exists x(F(x)\wedge G(x))$
Not all $F$ s are $G$ s	$\neg\forall x(F(x)\rightarrow G(x))$ or
	$\exists x(F(x)\wedge\neg G(x))$
No $F$ s are $G$ s	$\forall x(F(x)\rightarrow\neg G(x))$ or
	$\neg\exists x(F(x)\wedge G(x))$
Only $F$ s are $G$ s	$\forall x(G(x)\rightarrow F(x))$
	$\neg\exists x(\neg F(x)\wedge G(x))$
Identity
Only $c$ is $G$	$\forall x(G(x)\leftrightarrow x=c)$
Everything other
than $c$ is $G$	$\forall x(\neg x=c\rightarrow G(x))$
Everything
except $c$ is $G$	$\forall x(\neg x=c\leftrightarrow G(x))$
The $F$ is $G$	$\exists x(F(x)\wedge\forall y(F(y)\rightarrow x=y)\wedge G(x))$
It is not the case
that the $F$ is $G$	$\neg\exists x(F(x)\wedge\forall y(F(y)\rightarrow x=y)\wedge G(x))$
The $F$ is non- $G$	$\exists x(F(x)\wedge\forall y(F(y)\rightarrow x=y)\wedge\neg G(x))$

C.3 Using identity to symbolize quantities

There are at least blank $F$ s.

one	$\exists x\,F(x)$
two	$\exists x_{1}\exists x_{2}(F(x_{1})\wedge F(x_{2})\wedge\neg x_{1}=x_{2})$
three	$\exists x_{1}\exists x_{2}\exists x_{3}(F(x_{1})\wedge F(x_{2})\wedge F(x_{3})% \wedge\neg x_{1}=x_{2}\wedge\neg x_{1}=x_{3}\wedge\neg x_{2}=x_{3})$
four	$\exists x_{1}\exists x_{2}\exists x_{3}\exists x_{4}(F(x_{1})\wedge F(x_{2})% \wedge F(x_{3})\wedge F(x_{4})\wedge\neg x_{1}=x_{2}\wedge\neg x_{1}=x_{3}% \wedge\neg x_{1}=x_{4}\wedge\neg x_{2}=x_{3}\wedge\neg x_{2}=x_{4}\wedge\neg x% _{3}=x_{4})$
$n$	$\exists x_{1}\ldots\exists x_{n}(F(x_{1})\wedge\ldots\wedge F(x_{n})\wedge\neg x% _{1}=x_{2}\wedge\ldots\wedge\neg x_{n-1}=x_{n})$

There are at most blank $F$ s.

One way to say ‘there are at most $n$ $F$ s’ is to put a negation sign in front of the symbolization for ‘there are at least $n+1$ $F$ s’. Equivalently, we can offer:

one	$\forall x_{1}\forall x_{2}\bigl{[}(F(x_{1})\wedge F(x_{2}))\rightarrow x_{1}=x% _{2}\bigr{]}$
two	$\forall x_{1}\forall x_{2}\forall x_{3}\bigl{[}(F(x_{1})\wedge F(x_{2})\wedge F% (x_{3}))\rightarrow(x_{1}=x_{2}\vee x_{1}=x_{3}\vee x_{2}=x_{3})\bigr{]}$
three	$\forall x_{1}\forall x_{2}\forall x_{3}\forall x_{4}\bigl{[}(F(x_{1})\wedge F(% x_{2})\wedge F(x_{3})\wedge F(x_{4}))\rightarrow(x_{1}=x_{2}\vee x_{1}=x_{3}% \vee x_{1}=x_{4}\vee x_{2}=x_{3}\vee x_{2}=x_{4}\vee x_{3}=x_{4})\bigr{]}$
$n$	$\forall x_{1}\ldots\forall x_{n+1}\bigl{[}(F(x_{1})\wedge\ldots\wedge F(x_{n+1% }))\rightarrow(x_{1}=x_{2}\vee\ldots\vee x_{n}=x_{n+1})\bigr{]}$

There are exactly blank $F$ s.

One way to say ‘there are exactly $n$ $F$ s’ is to conjoin two of the symbolizations above and say ‘there are at least $n$ $F$ s and there are at most $n$ $F$ s.’ The following equivalent formulas are shorter:

zero	$\forall x\,\neg F(x)$
one	$\exists x\bigl{[}F(x)\wedge\forall y(F(y)\rightarrow x=y)\bigr{]}$
two	$\exists x_{1}\exists x_{2}\bigl{[}F(x_{1})\wedge F(x_{2})\wedge\neg x_{1}=x_{2% }\wedge\forall y\bigl{(}F(y)\rightarrow(y=x_{1}\vee y=x_{2})\bigr{)}\bigr{]}$
three	$\exists x_{1}\exists x_{2}\exists x_{3}\bigl{[}F(x_{1})\wedge F(x_{2})\wedge F% (x_{3})\wedge\neg x_{1}=x_{2}\wedge\neg x_{1}=x_{3}\wedge\neg x_{2}=x_{3}% \wedge\forall y\bigl{(}F(y)\rightarrow(y=x_{1}\vee y=x_{2}\vee y=x_{3})\bigr{)% }\bigr{]}$
$n$	$\exists x_{1}\ldots\exists x_{n}\bigl{[}F(x_{1})\wedge\ldots\wedge F(x_{n})% \wedge\neg x_{1}=x_{2}\wedge\ldots\wedge\neg x_{n-1}=x_{n}\wedge\forall y\bigl% {(}F(y)\rightarrow(y=x_{1}\vee\ldots\vee y=x_{n})\bigr{)}\bigr{]}$

C.4 Basic deduction rules for TFL

Reiteration

Line number	Subproof level	Formula	Justification
$m$	0	$\mathscr{A}$
	0	$\mathscr{A}$	R $m$

Conjunction

Line number	Formula	Justification
$m$	$\mathscr{A}$
$n$	$\mathscr{B}$
	$\mathscr{A}\wedge\mathscr{B}$	$\wedge$ I $m$ , $n$

Line number	Subproof level	Formula	Justification
$m$	0	$\mathscr{A}\wedge\mathscr{B}$
	0	$\mathscr{A}$	$\wedge$ E $m$

Line number	Subproof level	Formula	Justification
$m$	0	$\mathscr{A}\wedge\mathscr{B}$
	0	$\mathscr{B}$	$\wedge$ E $m$

Conditional

Line number	Subproof level	Formula	Justification
$m$	open subproof, 1	$\mathscr{A}$	AS
$n$	1	$\mathscr{B}$
	close subproof, 0	$\mathscr{A}\rightarrow\mathscr{B}$	$\rightarrow$ I $m$ – $n$

Line number	Formula	Justification
$m$	$\mathscr{A}\rightarrow\mathscr{B}$
$n$	$\mathscr{A}$
	$\mathscr{B}$	$\rightarrow$ E $m$ , $n$

Negation

Line number	Subproof level	Formula	Justification
$m$	open subproof, 1	$\mathscr{A}$	AS
$n$	1	$\bot$
	close subproof, 0	$\neg\mathscr{A}$	$\neg$ I $m$ – $n$

Line number	Formula	Justification
$m$	$\neg\mathscr{A}$
$n$	$\mathscr{A}$
	$\bot$	$\neg$ E $m$ , $n$

Indirect proof

Line number	Subproof level	Formula	Justification
$i$	open subproof, 1	$\neg\mathscr{A}$	AS
$j$	1	$\bot$
	close subproof, 0	$\mathscr{A}$	IP $i$ – $j$

Explosion

Line number	Subproof level	Formula	Justification
$m$	0	$\bot$
	0	$\mathscr{A}$	X $m$

Disjunction

Line number	Subproof level	Formula	Justification
$m$	0	$\mathscr{A}$
	0	$\mathscr{A}\vee\mathscr{B}$	$\vee$ I $m$

Line number	Subproof level	Formula	Justification
$m$	0	$\mathscr{A}$
	0	$\mathscr{B}\vee\mathscr{A}$	$\vee$ I $m$

Line number	Subproof level	Formula	Justification
$m$	0	$\mathscr{A}\vee\mathscr{B}$
$i$	open subproof, 1	$\mathscr{A}$	AS
$j$	1	$\mathscr{C}$
$k$	close subproof, open subproof, 1	$\mathscr{B}$	AS
$l$	1	$\mathscr{C}$
	close subproof, 0	$\mathscr{C}$	$\vee$ E $m$ , $i$ – $j$ , $k$ – $l$

Biconditional

Line number	Subproof level	Formula	Justification
$i$	open subproof, 1	$\mathscr{A}$	AS
$j$	1	$\mathscr{B}$
$k$	close subproof, open subproof, 1	$\mathscr{B}$	AS
$l$	1	$\mathscr{A}$
	close subproof, 0	$\mathscr{A}\leftrightarrow\mathscr{B}$	$\leftrightarrow$ I $i$ – $j$ , $k$ – $l$

Line number	Formula	Justification
$m$	$\mathscr{A}\leftrightarrow\mathscr{B}$
$n$	$\mathscr{A}$
	$\mathscr{B}$	$\leftrightarrow$ E $m$ , $n$

Line number	Formula	Justification
$m$	$\mathscr{A}\leftrightarrow\mathscr{B}$
$n$	$\mathscr{B}$
	$\mathscr{A}$	$\leftrightarrow$ E $m$ , $n$

C.5 Derived rules for TFL

Disjunctive syllogism

Line number	Formula	Justification
$m$	$\mathscr{A}\vee\mathscr{B}$
$n$	$\neg\mathscr{A}$
	$\mathscr{B}$	DS $m$ , $n$

Line number	Formula	Justification
$m$	$\mathscr{A}\vee\mathscr{B}$
$n$	$\neg\mathscr{B}$
	$\mathscr{A}$	DS $m$ , $n$

Modus Tollens

Line number	Formula	Justification
$m$	$\mathscr{A}\rightarrow\mathscr{B}$
$n$	$\neg\mathscr{B}$
	$\neg\mathscr{A}$	MT $m$ , $n$

Double-negation elimination

Line number	Subproof level	Formula	Justification
$m$	0	$\neg\neg\mathscr{A}$
	0	$\mathscr{A}$	DNE $m$

Excluded middle

Line number	Subproof level	Formula	Justification
$i$	open subproof, 1	$\mathscr{A}$	AS
$j$	1	$\mathscr{B}$
$k$	close subproof, open subproof, 1	$\neg\mathscr{A}$	AS
$l$	1	$\mathscr{B}$
	close subproof, 0	$\mathscr{B}$	LEM $i$ – $j$ , $k$ – $l$

De Morgan Rules

Line number	Subproof level	Formula	Justification
$m$	0	$\neg(\mathscr{A}\vee\mathscr{B})$
	0	$\neg\mathscr{A}\wedge\neg\mathscr{B}$	DeM $m$

Line number	Subproof level	Formula	Justification
$m$	0	$\neg\mathscr{A}\wedge\neg\mathscr{B}$
	0	$\neg(\mathscr{A}\vee\mathscr{B})$	DeM $m$

Line number	Subproof level	Formula	Justification
$m$	0	$\neg(\mathscr{A}\wedge\mathscr{B})$
	0	$\neg\mathscr{A}\vee\neg\mathscr{B}$	DeM $m$

Line number	Subproof level	Formula	Justification
$m$	0	$\neg\mathscr{A}\vee\neg\mathscr{B}$
	0	$\neg(\mathscr{A}\wedge\mathscr{B})$	DeM $m$

C.6 Basic deduction rules for FOL

Universal elimination

Line number	Subproof level	Formula	Justification
$m$	0	$\forall\mathscr{x}\,\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$
	0	$\mathscr{A}(\ldots\mathscr{c}\ldots\mathscr{c}\ldots)$	$\forall$ E $m$

Universal introduction

Line number	Subproof level	Formula	Justification
$m$	0	$\mathscr{A}(\ldots\mathscr{c}\ldots\mathscr{c}\ldots)$
	0	$\forall\mathscr{x}\,\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$	$\forall$ I $m$

$\mathscr{c}$ must not occur in any undischarged assumption

Existential introduction

Line number	Subproof level	Formula	Justification
$m$	0	$\mathscr{A}(\ldots\mathscr{c}\ldots\mathscr{c}\ldots)$
	0	$\exists\mathscr{x}\,\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{c}\ldots)$	$\exists$ I $m$

Existential elimination

Line number	Subproof level	Formula	Justification
$m$	0	$\exists\mathscr{x}\,\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$
$i$	open subproof, 1	$\mathscr{A}(\ldots\mathscr{c}\ldots\mathscr{c}\ldots)$	AS
$j$	1	$\mathscr{B}$
	close subproof, 0	$\mathscr{B}$	$\exists$ E $m$ , $i$ – $j$

$\mathscr{c}$ must not occur in any undischarged assumption, in $\exists\mathscr{x}\,\mathscr{A}(\ldots\mathscr{x}\ldots\mathscr{x}\ldots)$ , or in $\mathscr{B}$

Identity introduction

Line number	Subproof level	Formula	Justification
	0	$\mathscr{c}=\mathscr{c}$	=I

Identity elimination

Line number	Formula	Justification
$m$	$\mathscr{a}=\mathscr{b}$
$n$	$\mathscr{A}(\ldots\mathscr{a}\ldots\mathscr{a}\ldots)$
	$\mathscr{A}(\ldots\mathscr{b}\ldots\mathscr{a}\ldots)$	=E $m$ , $n$

Line number	Formula	Justification
$m$	$\mathscr{a}=\mathscr{b}$
$n$	$\mathscr{A}(\ldots\mathscr{b}\ldots\mathscr{b}\ldots)$
	$\mathscr{A}(\ldots\mathscr{a}\ldots\mathscr{b}\ldots)$	=E $m$ , $n$

C.7 Derived rules for FOL

Line number	Subproof level	Formula	Justification
$m$	0	$\forall\mathscr{x}\neg\mathscr{A}$
	0	$\neg\exists\mathscr{x}\mathscr{A}$	CQ $m$

Line number	Subproof level	Formula	Justification
$m$	0	$\neg\exists\mathscr{x}\mathscr{A}$
	0	$\forall\mathscr{x}\neg\mathscr{A}$	CQ $m$

Line number	Subproof level	Formula	Justification
$m$	0	$\exists\mathscr{x}\neg\mathscr{A}$
	0	$\neg\forall\mathscr{x}\mathscr{A}$	CQ $m$

Line number	Subproof level	Formula	Justification
$m$	0	$\neg\forall\mathscr{x}\mathscr{A}$
	0	$\exists\mathscr{x}\neg\mathscr{A}$	CQ $m$

C.8 Rules for chains of equivalences

$\displaystyle\lnot\lnot\mathscr{P}$	$\displaystyle\Leftrightarrow\mathscr{P}$	(DN)
$\displaystyle(\mathscr{P}\rightarrow\mathscr{Q})$	$\displaystyle\Leftrightarrow(\lnot\mathscr{P}\lor\mathscr{Q})$	(Cond)
$\displaystyle\lnot(\mathscr{P}\rightarrow\mathscr{Q})$	$\displaystyle\Leftrightarrow(\mathscr{P}\land\lnot\mathscr{Q})$
$\displaystyle(\mathscr{P}\leftrightarrow\mathscr{Q})$	$\displaystyle\Leftrightarrow((\mathscr{P}\rightarrow\mathscr{Q})\land(\mathscr% {Q}\rightarrow\mathscr{P}))$	(Bicond)
$\displaystyle\lnot(\mathscr{P}\land\mathscr{Q})$	$\displaystyle\Leftrightarrow(\lnot\mathscr{P}\lor\lnot\mathscr{Q})$	(DeM)
$\displaystyle\lnot(\mathscr{P}\lor\mathscr{Q})$	$\displaystyle\Leftrightarrow(\lnot\mathscr{P}\land\lnot\mathscr{Q})$
$\displaystyle(\mathscr{P}\lor\mathscr{Q})$	$\displaystyle\Leftrightarrow(\mathscr{Q}\lor\mathscr{P})$	(Comm)
$\displaystyle(\mathscr{P}\land\mathscr{Q})$	$\displaystyle\Leftrightarrow(\mathscr{Q}\land\mathscr{P})$
$\displaystyle(\mathscr{P}\land(\mathscr{Q}\lor\mathscr{R}))$	$\displaystyle\Leftrightarrow((\mathscr{P}\land\mathscr{Q})\lor(\mathscr{P}% \land\mathscr{R}))$	(Dist)
$\displaystyle(\mathscr{P}\lor(\mathscr{Q}\land\mathscr{R}))$	$\displaystyle\Leftrightarrow((\mathscr{P}\lor\mathscr{Q})\land(\mathscr{P}\lor% \mathscr{R}))$
$\displaystyle(\mathscr{P}\lor(\mathscr{Q}\lor\mathscr{R}))$	$\displaystyle\Leftrightarrow((\mathscr{P}\lor\mathscr{Q})\lor\mathscr{R})$	(Assoc)
$\displaystyle(\mathscr{P}\land(\mathscr{Q}\land\mathscr{R}))$	$\displaystyle\Leftrightarrow((\mathscr{P}\land\mathscr{Q})\land\mathscr{R})$
$\displaystyle(\mathscr{P}\lor\mathscr{P})$	$\displaystyle\Leftrightarrow\mathscr{P}$	(Id)
$\displaystyle(\mathscr{P}\land\mathscr{P})$	$\displaystyle\Leftrightarrow\mathscr{P}$
$\displaystyle(\mathscr{P}\land(\mathscr{P}\lor\mathscr{Q}))$	$\displaystyle\Leftrightarrow\mathscr{P}$	(Abs)
$\displaystyle(\mathscr{P}\lor(\mathscr{P}\land\mathscr{Q}))$	$\displaystyle\Leftrightarrow\mathscr{P}$
$\displaystyle(\mathscr{P}\land(\mathscr{Q}\lor\lnot\mathscr{Q}))$	$\displaystyle\Leftrightarrow\mathscr{P}$	(Simp)
$\displaystyle(\mathscr{P}\lor(\mathscr{Q}\land\lnot\mathscr{Q}))$	$\displaystyle\Leftrightarrow\mathscr{P}$
$\displaystyle(\mathscr{P}\lor(\mathscr{Q}\lor\lnot\mathscr{Q}))$	$\displaystyle\Leftrightarrow(\mathscr{Q}\lor\lnot\mathscr{Q})$
$\displaystyle(\mathscr{P}\land(\mathscr{Q}\land\lnot\mathscr{Q}))$	$\displaystyle\Leftrightarrow(\mathscr{Q}\land\lnot\mathscr{Q})$