Do truth tables need proofs?

Question

Possibly a silly question but do truth tables themselves need proofs, or are they technically considered definitions and therefore require no proof?

Answer 1

It's not that silly of a question.

When you 'fill out' a truth table for some propositional formula, you are, in a sense, proving that the truth table has the values it has. It is a relatively trivial and informal proof, but a proof nonetheless. Then, when you observe that, say, the truth table always results in true, you have proved the sentence is a tautology. Similarly for a contradiction, or a sentence that is satisfiable but not a tautology.

The key here is that this is an ordinary mathematical proof about a sentence propositional logic, not a formal proof of some sentence in the deductive system of propositional logic. It is a proof in the so-called metatheory.

There is a completeness theorem (again, a meta-theorem about propositional logic, not a formal theorem of propositional logic) that says that there is a proof of a sentence in the deductive system for propositional logic if and only if it is a tautology according to truth tables. So when you prove that a sentence is a tautology, you can use this theorem to conclude that a formal proof of this sentence exists, even though you haven't actually done the work of finding the proof.

Edit Henning in the comments points out that rather than talking about truth tables for propositional sentences, you might be asking about the underlying truth tables for the primitive connectives $\lnot,\to,\land,\lor,$ etc., from which the truth tables of larger sentences are calculated. These are indeed definitions, so there is no notion of proving them from simpler notions. You can think of them as giving meanings to the connectives.

(However, we may choose to define certain connectives in terms of others, in which case we'd no longer call them "primitive". For instance if we define $A\lor B$ as $\lnot(\lnot A\land \lnot B)$, we can derive what the truth table for $\lor$ is in terms of the tables for $\lnot$ and $\land$.)

Answer 2

A proof table is just a specific representation of a logical formula. So you might use truth tables to define a logical formula. On the other hand, if your logical formula is defines by other means, a truth table for that formula needs a proof.

For example consider the formula $$ (A \Rightarrow B) \Rightarrow (C \wedge D).$$ This already is a well-defined logical expression. If you now provide a truth table you have to prove that it correctly represents the formula, i.e. you have to calculate the formula, given different inputs.

On the other hand, defining $$ A \wedge B$$ is normally done by providing a truth table, so here the truth table serves as a definition, because $A \wedge B$ does not have already have a meaning.

Answer 3

Truth tables are often used to define the various logical operators ($\neg,\land,\lor, \implies, \iff$), but they can also be derived from various rules of logical inference. See, for example, my blog posting where I use the principles of direct proof, proof by contradiction, detachment (modus ponens) and the removal of double negations to derive, among other things, the truth table for material implication.