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$	$(\neg Q\rightarrow P)$ or $(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 the use of subproofs and citations

To cite an individual line when applying a rule:

1.

the line must come before the line where the rule is applied, but
2.

not occur within a subproof that has been closed before the line where the rule is applied.

To cite a subproof when applying a rule:

1.

the cited subproof must come entirely before the application of the rule where it is cited,
2.

the cited subproof must not lie within some other closed subproof which is closed at the line it is cited, and
3.

the last line of the cited subproof must not occur inside a nested subproof.

C.9 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})

Appendix C Quick reference