# 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
Subproof level
Formula
Justification
$m$
0
$\mathscr{A}$
$n$
0
$\mathscr{B}$

0
$\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
Subproof level
Formula
Justification
$m$
0
$\mathscr{A}\rightarrow\mathscr{B}$
$n$
0
$\mathscr{A}$

0
$\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
Subproof level
Formula
Justification
$m$
0
$\neg\mathscr{A}$
$n$
0
$\mathscr{A}$
0
$\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
Subproof level
Formula
Justification
$m$
0
$\mathscr{A}\leftrightarrow\mathscr{B}$
$n$
0
$\mathscr{A}$

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

0
$\mathscr{A}$
$\leftrightarrow$E $m$, $n$

# C.5 Derived rules for TFL

## Disjunctive syllogism

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

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

0
$\mathscr{A}$
DS $m$, $n$

## Modus Tollens

Line number
Subproof level
Formula
Justification
$m$
0
$\mathscr{A}\rightarrow\mathscr{B}$
$n$
0
$\neg\mathscr{B}$

0
$\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
Subproof level
Formula
Justification
$m$
0
$\mathscr{a}=\mathscr{b}$
$n$
0
$\mathscr{A}(\ldots\mathscr{a}\ldots\mathscr{a}\ldots)$

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

0
$\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})$