Suppes–Lemmon Notation

Suppes–Lemmon notation is a natural deductive logic notation system developed by E.J. Lemmon.See for an introductory presentation of Lemmon's natural deduction system. Derived from Suppes' method,See , for an introductory presentation of Suppes' natural deduction system. it represents natural deduction proofs as sequences of justified steps. Both methods use inference rules derived from Gentzen's 1934/1935 natural deduction system, in which proofs were presented in tree-diagram form rather than in the tabular form of Suppes and Lemmon. Although the tree-diagram layout has advantages for philosophical and educational purposes, the tabular layout is much more convenient for practical applications.

A similar tabular layout is presented by Kleene. The main difference is that Kleene does not abbreviate the left-hand sides of assertions to line numbers, preferring instead to either give full lists of precedent propositions or alternatively indicate the left-hand sides by bars running down the left of the table to indicate dependencies. However, Kleene's version has the advantage that it is presented, although only very sketchily, within a rigorous framework of metamathematical theory, whereas the books by Suppes and Lemmon are applications of the tabular layout for teaching introductory logic.

Description of the deductive system

Suppes–Lemmon notation is a notation for predicate calculus with equality, so its description can be separated into two parts: the general proof syntax and the context specific rules.

General Proof Syntax

A proof is a table with 4 columns and unlimited ordered rows. From left to right the columns hold:

# A set of positive integers, possibly empty
# A positive integer
# A well-formed formula (or wff)
# A set of numbers, possibly empty; a rule; and possibly a reference to another proof
The following is an example:

The second column holds line numbers. The third holds a wff, which is justified by the rule held in the fourth along with auxiliary information about other wffs, possibly in other proofs. The first column represents the line numbers of the assumptions the wff rests on, determined by the application of the cited rule in context. Any line of any valid proof can be converted into a sequent by listing the wffs at the cited lines as the premises and the wff at the line as the conclusion. Analogously, they can be converted into conditionals where the antecedent is a conjunction. These sequents are often listed above the proof, as Modus Tollens is above.

Rules of Predicate Calculus with Equality

The above proof is a valid one, but proofs don't need to be to conform to the general syntax of the proof system. To guarantee a sequent's validity, however, we must conform to carefully specified rules. The rules can be divided into four groups: the propositional rules (1-11), the predicate rules (12-15), the rules of equality (15-16) and the rule of substitution (18). Adding these groups in order allows one to build a propositional calculus, then a predicate calculus, then a predicate calculus with equality, then a predicate calculus with equality allowing for the derivation of new rules. In the table below, the derived propositional rules (10-11) are highlighted. They follow from the primitive (non-highlighted) Gentzen rules. The rules 8 (''Double Negation Elimination'') and 9 (''Reductio Ad Absurdum'') are equivalent. One of them can be dropped (or be assimilated to the derived rules).

The assumptions are those of lines ''a'' and ''b''. A derived rule with no assumptions is a theorem, and can be introduced at any time with no assumptions. Some cite that as "TI(S)", for "theorem" instead of "sequent". Additionally, some cite only "SI" or "TI" in either case when a substitution instance isn't needed, as their propositions match the ones of the referenced proof exactly.

Examples

An example of the proof of a sequent (a theorem in this case):

A proof of the principle of explosion using monotonicity of entailment. Some have called the following technique, demonstrated in lines 3-6, the Rule of (Finite) Augmentation of Premises:

An example of substitution and ∨E:

History of tabular natural deduction systems

The historical development of tabular-layout natural deduction systems, which are rule-based, and which indicate antecedent propositions by line numbers (and related methods such as vertical bars or asterisks) includes the following publications.

* 1940: In a textbook, Quine indicated antecedent dependencies by line numbers in square brackets, anticipating Suppes' 1957 line-number notation.
* 1950: In a textbook, demonstrated a method of using one or more asterisks to the left of each line of proof to indicate dependencies. This is equivalent to Kleene's vertical bars. (It is not totally clear if Quine's asterisk notation appeared in the original 1950 edition or was added in a later edition.)
* 1957: An introduction to practical logic theorem proving in a textbook by . This indicated dependencies (i.e. antecedent propositions) by line numbers at the left of each line.
* 1963: uses sets of line numbers to indicate antecedent dependencies of the lines of sequential logical arguments based on natural deduction inference rules.
* 1965: The entire textbook by is an introduction to logic proofs using a method based on that of Suppes.
* 1967: In a textbook, briefly demonstrated two kinds of practical logic proofs, one system using explicit quotations of antecedent propositions on the left of each line, the other system using vertical bar-lines on the left to indicate dependencies.A particular advantage of Kleene's tabular natural deduction systems is that he proves the validity of the inference rules for both propositional calculus and predicate calculus. See .

See also

* Natural deduction
* Sequent calculus
* Deductive systems

Notes

References

*
* (English translation ''Investigations into Logical Deduction'' in Szabo.)
*
*
*
*
*
*
*
*
* {{cite book, last1=Szabo, first1=M.E., year=1969, title=The collected papers of Gerhard Gentzen, publisher=North-Holland, location=Amsterdam

External links

* Pelletier, Jeff,
A History of Natural Deduction and Elementary Logic Textbooks.

Propositional calculus