# Truth tables in propositional calculus: semantic or syntactic in nature?

Modern treatments of (classical) propositional calculus first set up a language $\mathsf{L}$, which consists of formulas built up recursively from a set of propositional letters $\{p,q,r,\dots \}$, and a certain number of connectives $\{ \neg, \lor, \land \}$.

The semantics of $\mathsf{L}$ is a Boolean valuation of the propositional letters, whereby each letter is mapped to either $T$ or $F$, and the valuation is extended to all formulas of $\mathsf{L}$, such that the connectives are interpreted in the usual way, as truth-functional connectives. We say that the formula $\phi$ semantically entails formula $\Phi$, or $\phi \vDash \Phi$, if every valuation of $L$ which maps $\phi$ to $T$ must map $\Phi$ to $T$ also.

If we set up a proof system (say Gentzen's natural deduction) for $\mathsf{L}$, we say that $\phi$ syntactically entails $\Phi$ if there is a proof of $\Phi$ from $\phi$ ("proof" would of course depend on the proof system used).

Now it can be proved that, for $\mathsf{L}$ equipped with a proof system, $\phi \vDash \Phi$ if and only if $\phi \vdash \Phi$. The delineation between semantic and syntactic entailment is emphasised very much in most texts; in certain logic books I've consulted, the authors even make it a point that truth tables are a purely semantical concept. I do not have any problems with the distinction.

However, Chang and Keisler's book on Model Theory has cast a serious doubt on the syntax-semantics dichotomy. Their definition of the semantics of propositional calculus is as before, but look at how they define syntactic consequence (my paraphrase):

Let $\phi$ be a formula, and $p_0, p_2, \dots, p_n$ be all the propositional letters occuring in $\phi$. We say that $\vdash \phi$ if $\phi$ has the value $T$ for every valuation of $p_0, p_1, \dots, p_n$.

And now to my question proper:

With this definition, I no longer see much difference between semantic entailment and syntactic entailment. They claim that the method of truth tables is purely syntactic, which some books vehemently disagree with. This definition renders the completeness theorem of propositional logic pretty much useless in my opinion, because the original motivation of the theorem was to show that we can mechanically derive all propositional tautologies from a small number of axioms with some inference rules. I would appreciate answers which address this doubt.

Besides the completeness theorem, is there a reason why logicians came up with the theory of semantics of formal languages? The semantics of propositional logic only involves assigning each propositional letter to an element of $\{0,1\}$, and does not seem to be address the deeper issues of "truth".

• I don't know if it's semantic or syntactic, but you might have a look at my previous answer here: math.stackexchange.com/questions/2596766/… There I talk about deriving the truth table for material implication. In some sense, it seems to be a consequence of the Law of the Excluded Middle. – Dan Christensen Jan 28 '18 at 13:51
• I'd say truth-tables are largely semantic as the lines correspond to classes of truth-assignments. Also, when we point to the elementary tables for the operators we are clearly defining their semantics. But see Henning's nice answer below to regard them as syntactical objects as well. – Bram28 Jan 28 '18 at 19:54

The distinction between "syntax" and "semantics" in logic is not a technical one, but merely a concept that we use to mentally arrange our toolbox of definitions and proof techniques in some semblance of order. It is somewhat fuzzy at the edges.

So we can't go and look up a crisp formal definition of "syntactic" and check whether it applies to the definition you're reading.

I agree with you (and believe it is mainstream) that propositional entailment by truth tables feels like a distinctly semantic way of thinking, compared to proof systems a la Gentzen or Hilbert.

So your book calling truth tables syntactic is a bit out of the ordinary -- but it is not completely crazy. Its saving grace is that a truth table is a finite object that you can fill out while following simple local rules. If one considers "semantic" to mean "this is based on scary infinitary reasoning", then there is some case for viewing truth tables as safe and (therefore?) syntactic.

Another possibility is that the authors are maintaining a conceptual distinction between "for all valuations" and "all lines in the truth table". This sounds like pointless sophistry, since there is an obvious one-to-one correspondence between valuations and lines in the truth table. But perhaps there isn't? In particular, if we say that a "valuation" must give a truth value to each of the infinitely many possible propositional variables no matter whether they appear in the formula we're looking at right now, then quantifying over valuations is actually much more infinitary than the lines in a truth table.

Viewed in this way, it is coherent to say that the truth table is not the actual semantics of the formula, but a (syntactic?) shortcut to the semantics that allows us to express the semantic function from all (uncountably many) valuations to truth values in finite space!

In that way, it makes at least some sense to elevate the truth-table method to a possible proof system for the propositional calculus. Truth tables are finite like proof objects are supposed to be; they can be verified by checking local rules; and it is it easy to prove them sound and complete with respect to the (true?) infinite-valuation semantics of the calculus.

• What a beautiful and insightful answer! – Taroccoesbrocco Jan 28 '18 at 13:30
• @Taroccoesbrocco: Henning's answer is really on the dot. We know that the syntactic boolean algebra is satisfied by different boolean lattices, and truth tables only capture syntactically the semantics of one particular lattice that we have in mind. The fact that truth tables are a syntactic construct is clear when we realize that we still need to use our head to interpret what the columns and rows mean. We could use 0,1 or F,T or $\bot,\top$, and without our interpretation the truth table is simply meaningless. – user21820 Jan 29 '18 at 13:15
• @Taroccoesbrocco: However, when talking about classical propositional logic, the fact that the truth tables are intended to capture the boolean lattice we have in mind is also the reason we often consider it 'semantic' compared to a deductive system. It is not hard to see that at least for propositional logic both are very closely connected since we can easily transform any truth table verification of a tautology into a proof in any reasonable deductive system. – user21820 Jan 29 '18 at 13:20
• @Taroccoesbrocco: In fact, I did precisely that in this conversation for this Fitch-style deduction system. – user21820 Jan 29 '18 at 13:21
• @user21820 - Interesting, even if I don't agree when you say "The fact that truth tables are a syntactic construct is clear when we realize that we still need to use our head to interpret what the columns and rows mean. We could use 0,1 or F,T or ⊥,⊤, and without our interpretation the truth table is simply meaningless". Using this argument, we can conclude that everything is syntax and semantics does not exist, even in first-order classical logic. I totally agree with your second comment. – Taroccoesbrocco Jan 29 '18 at 17:29