What exactly is classical sentential logic? (1)

It’s taught to just about every undergraduate who gets close to a philosophy curriculum, so the answer should be obvious, isn’t it? And isn’t it the same as the propositional calculus that came into being with Boole and De Morgan just before 1850, more or less the same time as Charlotte Bronte published Jayne Eyre under a male pseudonym. So by now we should know what it is.

What Boole and De Morgan introduced was formalized by Frege, and the logic he presented stayed in essentially the same form till 1934, with just one significant change by von Neumann shortly before that time. In the period before 1934 the logic was presented in axiomatic form. Since then, starting with Gentzen and Jaskowski, and made student friendly by Irvin Copi, this logic has been presented mainly in natural deduction format.

The general impression is probably that it’s just the same thing. But it isn’t.

For sentential logic Frege presented six axioms, with explicitly the rule of Modus Ponens and implicitly the rule of Substitution. The latter was needed because the axioms are (in our modern notation) sentences like

(p ⊃ (q ⊃ p))

in which p, q are atomic sentences. Any uniform substitution of sentences A, B for atomic sentences in the axioms — such as (A ⊃ (B ⊃ A)) — is a theorem.

Russell and Whitehead preferred to use the disjunction v rather than the conditional ⊃ as primitive, but apart from that they did the same: axioms, and the two rules of Modus Ponens and Substitution. The presentation was made much more user-friendly, without altering the logic in any way, by von Neumann in 1927, when he replaced axioms by axiom schemata which made the rule of Substitution irrelevant. Corresponding to the above axiom, the axiom schema is

(A ⊃ (B ⊃ A))

where A, B are just ‘schematic letters’ or ‘placeholders’ and the schema is to be understood in this way:

any sentence formed by placing sentences in the places of A and B in (A ⊃ (B ⊃ A)) is an axiom

That means of course that now there are infinitely many axioms, not just six, but there are still only six axiom schemata, and then only the rule of Modus Ponens. That rule is also presented as a rule schema, of course.

Theorems are in both cases defined to be the results of applying rules sequentially, in a finite number of steps, starting with axioms.

We have to distinguish two things here, both of which can be regarded as being the classical sentential logic: the body T of theorems, and the body DI of deductive inferences, that is, of pairs A, B such that B is derivable from A, plus axioms, by the rules.

While in the literature we can find examples of the first identification, the second is surely the better one, for two reasons. First, the theorems can be defined as the sentences that can be deductively inferred from the axioms alone. Second, in practical applications, the importance derives from the provided extra information, the premises which are not axioms or theorems.

So, for this first, original historical period, it seems right to say that the classical sentential logic is the body of deductive inferences, defined with reference to the pertinent axiom schemata and the rule of Modus Ponens alone. I will call this system Original Classical Sentential Logic, or OCSL for short.

But today we don’t teach logic in that form. It is too clumsy, it wants too much and too complex symbol manipulation, we we like the intuitive, natural rules that seem to relate closely to the way we reason in ordinary contexts.

So, what is the Natural Deduction formulation of sentential logic? It has no axioms or axiom schemata, but only rule schemata. One rule schema that is taken over, not surprisingly, is Modus Ponens, or detachment as it is sometimes called. This one, and some of the others, like

from A infer (A v B)

Using the familiar symbol for deducibility: A ├ (A v B

are just specific deductive inferences, that were already there in the set DI. But then in addition there others, that have no counterpart in DI. They have a very different form: they say that if certain inferences are correct, then so is another one. They are not rules but meta-rules. So the other natural deduction rule for disjunction is the Disjunctive Syllogism:

If from A you can infer C, and from B you can infer C, then you can infer C from (A v B)

or in symbols: if A ├ C and B├ C then (A v B) ├ C

There are more meta-rules like this, the most important are Conditional Proof and Reductio ad Absurdum:

[Condit] if X, A ├ B then X ├ (A ⊃ B)

[Reductio] If X, A ├ B and X, A ├ ~B then X ├ ~A

These rules are admissible in or for the Original Classical Sentential Logic. That means, if they are applied in a derivation you still get as theorems and as deductive inferences only those that were already there.

Proof of admissibility are not always easy. For [Condit] the theorem that it is admissible was first proved by Herbrandin 1930, and it is still often presented in logic texts in one way or another, as the Deduction Theorem.

What the admissibility theorems show is that by switching to the Natural Deduction Formulation of Sentential Logic — or NDFSL for short — we do not add to the theorems and deductive inferences of the OCSL. And this fact is the reason why the two systems are generally taken to be just the same thing.

But they aren’t. NDFSL is a logically stronger system, in that there are contexts in which OCSL is sound and NDFSL is not.

I’ll take this up in the next post.

APPENDIX

For the history of logic that I sketched above see William and Mary Kneale, The Development of Logic, as well as the section “History of Logic — Boole and De Morgan” in the Encyclopedia Brittanica, and the many historical and bibliographical notes in Stephen C. Kleene, Introduction to Metamathematics.

The latter has a simple proof of the Deduction Theorem for sentential logic; note well that the most crucial step assumes that modus ponens is the only rule of inference that goes with the axioms.