Are truth tables for logic connectives deduced from axioms in propositional logic?

Question

Any sound and complete formal system in propositional logic consists of:

1.- A finite number of Variables (Symbols used as placeholders for proposition).

2.- At least one logic connective

3.- At least one Rule of inference (For example, Modus Ponens)

4.- A set of axioms

Any proposition stated using the variables and connectives should be provable from the axioms using the rule/s of inference.

Using these ingredients, one may construct many valid formal systems of propositional logic using different combinations of connectives, rules of inference and axioms.

For example, a famous axiomatization by Jan Łukasiewicz uses the connectives → and ¬ , Modus Ponens and the following three axioms:

ϕ→(ψ→ϕ)

(ϕ→(ψ→ξ))→((ϕ→ψ)→(ϕ→ξ))

(¬ϕ→¬ψ)→(ψ→ϕ)

Using this axiomatization as an example, my question is the following:

Are the truth tables for → and ¬ taken for granted when choosing said connectives as fundamental, or are they constructed from the axioms and modus ponens?

In other words, are truth tables part of the Definition of logic connectives, or is the definition of said connectives completely included in the axioms and rules of inference (with truth tables being merely a consequence of something more fundamental)?

Answer 1

The simple answer to the question in the header is yes.

When you read original sources, you come to realize that there had been no distinction between "$=$" and "$\leftrightarrow$" in the early writings of Frege and Russell. While Frege clearly had been struggling with a new logical calculus based upon the function concept, Russell and Whitehead had been working on axiomatic systems.

I have seen attributions to both Post and Wittgenstein concerning the identification of truth tables and propositional logic as a self-contained subsystem of what had been presented in "Principia Mathematica". So, truth tables had been deduced from the axiomatization of classical logic. But, I do not know to whom one ought attribute priority.

Your subsequent questions are more difficult. The answer depends upon your philosophy of mathematics.

Frege's innovation had been that of bringing the function concept into logic. Truth tables reflect an "extensional" view of a function having a domain. This is why one refers to connectives associated with the classical truth tables with the qualifier "material". Frege's "The True" and "The False" are intended to be viewed as extant objects.

But, because the innovation involves the function concept, one can axiomatize logical connectivity with an "intensional" view. Let me emphasize logical connectivity because I am not speaking of Boolean polynomials.

Let me denote the material biconditional by $LEQ$, and, consider an axiom given by

$$ XOR\;(\: OR, \; NAND \:) = LEQ $$

The truth tables for $OR$ and $NAND$ are

$$ \begin{array}{cccc} \begin{array}{cc|c} \text{$\:\:\:\:$} & \text{$\:\:\:\:$} & \text{$OR$} \\ \hline \text{$T$} & \text{$T$} & \text{$T$} \\ \text{$T$} & \text{$F$} & \text{$T$} \\ \text{$F$} & \text{$F$} & \text{$F$} \\ \text{$F$} & \text{$T$} & \text{$T$} \\ \end{array} &&& \begin{array}{cc|c} \text{$\:\:\:\:$} & \text{$\:\:\:\:$} & \text{$NAND$} \\ \hline \text{$T$} & \text{$T$} & \text{$F$} \\ \text{$T$} & \text{$F$} & \text{$T$} \\ \text{$F$} & \text{$F$} & \text{$T$} \\ \text{$F$} & \text{$T$} & \text{$T$} \\ \end{array} \end{array} $$

If one now performs a componentwise application of $XOR$,

$$ \begin{array}{cc|c} \text{$\:\:\:\:$} & \text{$\:\:\:\:$} & \text{$\:\:\:\:$} \\ \hline \text{$T$} & \text{$T$} & \text{$XOR \;( T,\: F )$} \\ \text{$T$} & \text{$F$} & \text{$XOR \;( T,\: T )$} \\ \text{$F$} & \text{$F$} & \text{$XOR \;( F,\: T )$} \\ \text{$F$} & \text{$T$} & \text{$XOR \;( T,\: T )$} \\ \end{array} $$

one obtains the truth table for $LEQ$,

$$ \begin{array}{cc|c} \text{$\:\:\:\:$} & \text{$\:\:\:\:$} & \text{$LEQ$} \\ \hline \text{$T$} & \text{$T$} & \text{$T$} \\ \text{$T$} & \text{$F$} & \text{$F$} \\ \text{$F$} & \text{$F$} & \text{$T$} \\ \text{$F$} & \text{$T$} & \text{$F$} \\ \end{array} $$

Of course, to implement this one must actually name all sixteen truth tables.

It is now possible to understand the system as an applicative structure. This requires that a set of parentheses be interpreted using either $NOR$ or $NAND$. That is, a string of names,

$$ ABCDEFG $$

evaluates according to

$$ ((((((AB)C)D)E)F)G) $$

Along similar lines one may formulate a magma by treating $NOR$ and $NAND$ as a left product and a right product if one sets a convention for expressions of the form $(A)$. My view is that it ought to be interpreted as a unary negation.

The reason that all of this depends upon one's philosophy of mathematics lies with the question of what might warrant the study of this system within foundations. Suppose you name all sixteen truth tables. Further, suppose you study negations and de Morgan conjugations as involutions on this system. This will partition the system with a specific pattern, and, that pattern corresponds with the finite affine geometry on sixteen points. Its associated projective plane has twenty-one points. It is well known in design theory that the 21-point projective plane is unique up to isomorphism. But, modern foundations arises almost exclusively from the arithmetization of mathematics. So, this geometric perspective is at odds with the received view.

At the end of his career, Frege retracted his logicism in a paper entitled "Numbers and Arithmetic". He expresses the belief that all mathematics arises from a geometrical basis. He concludes this paper with the remark,

"Counting, which arose psychologically out of the demands of practical life, has led the learned astray."

In other words, there are some questions in the foundations of mathematics that you can only answer for yourself.

@ Doug Spoonwood

The fact that the modern account of the syntax/semantics distinction creates a chicken and egg problem does not alter the fact of the historical reality that axiomatizations preceded the account of truth tables. Also, the expression "propositional logic" usually does not refer to non-classical interpretations when no other context is specified. For no good reason you are either reading too much in the question or too little in the meaning of "simple".

Answer 2

(I am going to collect many good points from comments.)

I guess that the confusion stems from the phrase “the definition of logic connectives”. It seems that you believe that we need to define logical connectives in order to do any mathematics at all. Think what kind of definition it could be. Mathematics is based on logic. If there ware the mathematical definition of logical connectives, that would be a vicious cycle.

Now I consider a practical definition of logical connectives. A practical definition should help in determining whether a given mathematical statement is true or false. We can calculate the truth value of any formula in propositional logic by truth tables. If the truth value is true, the formula is true. If the truth value is false, the formula is false. Hence truth tables are practical for propositional logic.

Unfortunately, propositional logic is too poor for describing any interesting mathematical statement. The best attempt of using truth tables for quantifiers is to interpret quantifiers as logical connectives spanning the whole domain of discourse. For example, $\forall x P(x)$ when the domain of discourse is natural numbers means $P(0)\land P(1)\land P(2)\dots$ and so on for all natural numbers. As the set of all natural numbers is infinite, we can’t calculate the truth value of $\forall x P(x)$. Truth tables are not practical for a logic with quantifiers, for example, any first-order logic.

A quote from the textbook “Introduction to Mathematical Logic” by Elliott Mendelson (2015, 6th ed., Chapter 2.3 “First-Order Theories”) that further elaborates on difficulties of the calculation approach to truth.

In the case of the propositional calculus, the method of truth tables provides an effective test as to whether any given statement form is a tautology. However, there does not seem to be any effective process for determining whether a given wf is logically valid, since, in general, one has to check the truth of a wf for interpretations with arbitrarily large finite or infinite domains. In fact, we shall see later that, according to a plausible definition of “effective,” it may actually be proved that there is no effective way to test for logical validity. The axiomatic method, which was a luxury in the study of the propositional calculus, thus appears to be a necessity in the study of wfs involving quantifiers, and we therefore turn now to the consideration of first-order theories.

We can salvage the calculation approach if we reason about logical connectives by truth tables and about quantifiers by other means. I guess this is possible in informal reasoning. However, in formal reasoning, inference systems are used. If a statement is proved using an inference system which is believed to be correct, then the statement is true. This is the answer to the question why axioms are needed: they are a practical way to determine whether a given mathematical statement is true or false. The inference system that you described belongs to the class called Hilbert systems. Actually, Hilbert systems are not very practical: proofs are unnecessarily long. Natural deduction is better.

As many inference systems were invented during formalization of mathematics, a natural question is which is better. In order to decide it, we need to know their properties and compare them. This is done in theoretical mathematical logic. In order to study inference systems, formal definitions of a well-formed logical formula and a proof were introduced. Logical connectives are just syntactic constructs, symbols. Then the notion of semantics (interpretation) of logical connectives and quantifiers was introduced. Truth tables are a part of semantics. Semantics helps to prove statements about provability. Semantics is a theoretical definition of logical connectives. This is the answer to the question why truth tables are needed.

Notice that the whole study of inference systems is going inside an inference system belonging to the metalevel. This inference system is usually left implicit, and reasoning in it is written in a natural language. Inference systems that are studied belong to an object level. These 2 levels are a characteristic property of theoretical mathematical logic.

A view on logical connectives that you want to adopt depends on your objective. If you care about practical proving, meaning of logical connectives is defined by inference systems. Semantics is useful for theoretical investigations, but is not practical.

Answer 3

First off, let us define an axiom.

Axiom - Any well-formed formula (or meaningful expression or statement form) using only the connectives and variables for the system in question.

You didn't actually reference any well-formed formula (check the definition carefully!), but that probably could get corrected and it doesn't change the question here.

Now let's suppose that we could deduce the truth tables from any axiom set for propositional logic. Thus, we would start with the axioms and the truth tables will end as theorems of the formal system. This doesn't make any sense, since axioms under rules of inference such as the one you referenced only yield more well-formed formulas. It works out this way, because every subformula (any formula within the well-formed formula which is shorter than the well-formed formula) of a well-formed formula is a well-formed formula and valid rules of inference, at least all that I've seen, yield either a sub-formula of a well-formed, or some combination of subformulas.

So, I suppose you might have intended to ask if there exists some sort of metalogical way to infer the truth tables from say the axiom set (once made into well-formed formulas) you referenced. This would entail the uniqueness of the truth tables as an interpretation of the axioms. However, there exists this following interpretation of the connectives attributed to Dmitri Bochvar, where 'T' indicates a truth value of true, 'N' a third truth value, and 'F' falsity.

$\lnot$T = F

$\lnot$N = T

$\lnot$F = T

(T -> T) = T

(T -> N) = F

(T -> F) = F

(N -> T) = T

(N -> N) = T

(N -> F) = T

(F -> T) = T

(F -> N) = T

(F -> F) = T

In other words, if you do the calculations with the above you will see that the axioms of the previously referenced Lukasiewicz axiom set all hold and so does the rule of detachment. And no other new tautologies follow.

So, no, the axioms of propositional logic (and the rules of inference) do not necessarily entail the truth tables. They work as consistent with the two-valued truth tables, but there exist other sets of truth tables which satisfy them similarly to how the two-valued truth tables satisfy the axioms and rules of inference.