Why truth table is not used in logic?

First, of course, mathematicians and logicians often do use truth tables, so it is incorrect to suggest that they are not used. (I won't comment on your reading of Principia Mathematica, beyond saying that that text is not meant to be taken as a piece of pedagogy.)

But second, the truth table method is not a feasible method for large propositions. This is because for a formula with $n$ free variables, the truth table is an object with $2^n$ rows, exponentially large in size. But many logical expressions nevertheless have comparatively short derivations showing them to be tautological.

For example, $$(p_0\vee \neg p_0)\wedge(p_1\vee \neg p_1)\wedge\cdots\wedge(p_{100}\vee\neg p_{100})$$ has a truth table with $2^{101}$ rows, but there is a simple, obvious derivation that allows us to see it as taugological without calculating this table.

Thus, although when there are just two propositional variables, I don't mind computing a truth table, or even for three, it is often easier with more to use more focused reasoning.


In Principia, the authors wanted to produce an explicit list of purely logical ideas, including an explicit finite list of axioms and rules of inference, from which all of mathematics could be derived. The method of truth tables is not such a finite list, and in any case would only deal with propositional logic.

The early derivations of Principia are quite tedious, and could have been eliminated by adopting a more generous list of initial axioms. But for reasons of tradition, the authors wanted their list to be as small as possible.

Remark: Principia is nowadays only of historical interest, since the subject has developed in quite different directions from those initiated by Russell and Whitehead. The idea of basing mathematics (including the development of the usual integers, reals, function spaces) purely on "logic" has largely been abandoned in favour of set-theory based formulations. And Principia does not have a clear separation between syntax and semantics. Such a separation is essential to the development of Model Theory in the past $80$ years.


Your teacher may be referring to the difference between semantics and syntax. A syntactic proof is a finite formal derivation of a sentence from the axioms of a theory using the logical axioms and the rules of inference of a logic. A proof by a truth table is a semantic proof; in allowing truth tables you are tacitly assuming the completeness theorem of propositional logic. Essentially, a priori, we don't know that everything we can prove by studying the models of a theory (i.e. truth tables, in the case of propositional logic) can be proven syntactically, or even for that matter vice versa. It's a non-trivial result in logic, which I will state below:

Definition. Let $T$ be a theory in some logic. We say the logic is sound if every sentence $P$ which can be formally derived from the axioms of $T$ is true in every model of $T$, i.e. $T \vdash P$ implies $T \vDash P$. We say the logic is complete if when a sentence $P$ is true for every model of $T$, $P$ can also be derived formally from the axioms of $T$, i.e. $T \vDash P$ implies $T \vdash P$.

Theorem. Classical propositional logic is sound and complete.

Theorem (Gödel). Classical first-order logic is sound and complete.

And yes, it is that Gödel. There are also incomplete logics; you don't have to go very far to find them, since even second-order logic (under the usual semantics) is incomplete.

Tags:

Logic