2. Truth Tables
A recursion table does not merely list outcomes. It displays how a function is defined across all possible forms of its input.
To see this, it helps to contrast it with a truth table. In a truth table, the entries are fixed values. Each row corresponds to a complete situation, and the table records what the connective returns in that case. Nothing in the table refers beyond itself.
A recursion table is different. Its entries are not always final values. Some of them point back to the function itself, applied to smaller inputs. Instead of a closed grid of results, we obtain a finite description of a process.
A simple comparison makes the difference clear.
Truth tables
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
What we can see here is the definition of truth values of $p ∧ q$ based on all possible combinations of truth values of the propositions $p$ and $q$, from which it is built.
If $p$ is true and $q$ is true, so is $p ∧ q$. If one of them is false, however, then $p ∧ q$ is false.
Each entry is a final value. Nothing refers beyond the table.