Natural deduction

In logic and proof theory, natural deduction is a kind of proof calculus in which logical reasoning is expressed by inference rules closely related to the "natural" way of reasoning, such as introducing temporary assumptions (to introduce…

Uses your system voice; voice and rate in settings.

≈ 21 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In logic and proof theory, natural deduction is a kind of proof calculus in which logical reasoning is expressed by inference rules closely related to the "natural" way of reasoning, such as introducing temporary assumptions (to introduce an "if") or reasoning by cases (to eliminate an "or"). This contrasts with Hilbert-style systems, which instead use axioms as much as possible to express the logical laws of deductive reasoning.

History of notation styles

Natural deduction has had a large variety of notation styles, which can make it difficult to recognize a proof for a reader not familiar with one of them. To help with this situation, this article has a section explaining how to read all the notation that it will actually use.

This section just explains the historical evolution of notation styles, most of which cannot be shown because there are no illustrations available under a public copyright license – the reader is pointed to the SEP and IEP for pictures. Gentzen invented natural deduction using tree-shaped proofs – see for details. Jaśkowski changed this to a notation that used various nested boxes.

Fitch changed Jaśkowski method of drawing the boxes, creating Fitch notation. 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, what is now known as Suppes–Lemmon notation. 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.

Notation

Here is a table with the most common notational variants for logical connectives.

Gentzen's tree notation

Gentzen, who invented natural deduction, had his own notation style for arguments. This will be exemplified by a simple argument below. Let's say we have a simple example argument in propositional logic, such as, "if it's raining then it's cloudly; it is raining; therefore it's cloudy".

(This is in modus ponens.) Representing this as a list of propositions, as is common, we would have: 1) ~ P \to Q 2) ~ P \therefore ~ Q In Gentzen's notation, this would be written like this: \frac{P \to Q, P}{Q} The premises are shown above a line, called the inference line, separated by a comma, which indicates combination of premises.

The conclusion is written below the inference line. The inference line represents syntactic consequence, sometimes called deductive consequence, which is also symbolized with ⊢.

So the above can also be written in one line as P \to Q, P \vdash Q . (The turnstile, for syntactic consequence, is of lower precedence than the comma, which represents premise combination, which in turn is of lower precedence than the arrow, used for material implication; so no parentheses are needed to interpret this formula.) Syntactic consequence is contrasted with semantic consequence, which is symbolized with ⊧.

In this case, the conclusion follows syntactically because natural deduction is a syntactic proof system, which assumes inference rules as primitives. Gentzen's style will be used in much of this article.

Gentzen's discharging annotations used to internalise hypothetical judgments can be avoided by representing proofs as a tree of sequents Γ ⊢ A instead of a tree of judgments that A (is true).

Propositional language syntax

This section defines the formal syntax for a propositional logic language, contrasting the common ways of doing so with a Gentzen-style way of doing so. \neg \phi \; \overset{\text{def}}{=} \; \phi \to \bot , where \bot (falsum) represents a contradiction or absolute falsehood. Older publications, and publications that do not focus on logical systems like minimal, intuitionistic or Hilbert systems, take negation as a primitive logical connective, meaning it is assumed as a basic operation and not defined in terms of other connectives.

Some authors, such as Bostock, use \bot and \top , and also define \neg as primitives.

Gentzen-style propositional logic

Let the propositional language \mathcal{L} be inductively defined as \Phi ::= p_1, p_2, \dots \mid \bot \mid (\Phi \to \Phi) \mid (\Phi \land \Phi) \mid (\Phi \lor \Phi) . Define negation as \neg \Phi \, \overset{\text{def}}{=} \, (\Phi \to \bot) .

The following is a list of primitive inference rules for natural deduction in propositional logic: In this table the Greek letters \varphi, \psi, \chi are schemata, which range over formulas rather than only over atomic propositions. The name of a rule is given to the right of its formula tree.

For instance, the first introduction rule is named \land_I , which is short for "conjunction introduction". Minimal logic: the natural deduction rules are ND_{MPC} = \{ \land_I, \land_E, \lor_I, \lor_E, \to_I, \to_E \} . Without the rules \bot_E and \neg\neg_E the system defines minimal logic (as discussed by Johansson).

Intuitionistic logic: the natural deduction rules are ND_{IPC} = ND_{MPC} \cup \{ \bot_E \} . When the rule \bot_E (principle of explosion) is added to the rules for minimal logic, the system defines intuitionistic logic. The statement P \to \neg \neg P is valid (already in minimal logic, see example 1 below), unlike the reverse implication which would entail the law of excluded middle.

Classical logic: the natural deduction rules are ND_{CPC} = ND_{IPC} \cup \{ \neg\neg_E \} .{{refn|name="RAA"|Instead of \neg\neg E one can add reductio ad absurdum as a rule to obtain classical logic: \frac{\begin{array}{c} [\varphi \to \bot] \\ \vdots \\ \bot \end{array}}{\varphi} (RAA)}} When all listed natural deduction rules are admitted, the system defines classical logic. In the table below, based on Lemmon (1978) and Allen & Hand (2022), Lemmon's derived rules are highlighted .

They can be derived from the (non-highlighted) Gentzen rules. There are nine primitive rules of proof, which are the rule assumption, plus three pairs of introduction and elimination rules for the binary connectives, and the rules of double negation and reductio ad absurdum, of which only one is needed.

Double negation, and reductio ad absurdum in the form that allows inferring \varphi as the denial of an assumption \neg \varphi , make the system classical; reductio ad absurdum restricted to inferring \neg \varphi from an assumption \varphi amounts to →I with negation read as \varphi \to \bot , and is valid in minimal logic. Disjunctive Syllogism can be used as an easier alternative to the proper ∨-elimination, and MTT is a commonly given rule, although it is not primitive.

Consistency, completeness, and normal forms

A theory is said to be consistent if falsehood is not provable (from no assumptions) and is complete if every theorem or its negation is provable using the inference rules of the logic. These are statements about the entire logic, and are usually tied to some notion of a model.

However, there are local notions of consistency and completeness that are purely syntactic checks on the inference rules, and require no appeals to models. The first of these is local consistency, also known as local reducibility, which says that any derivation containing an introduction of a connective followed immediately by its elimination can be turned into an equivalent derivation without this detour.

It is a check on the strength of elimination rules: they must not be so strong that they include knowledge not already contained in their premises. As an example, consider conjunctions. \begin{aligned}\cfrac{\cfrac{\cfrac{}{A\ }u\qquad\cfrac{}{B\ }w}{A \wedge B\ }\wedge_I}{A\ }\wedge_{E1}\end{aligned}\quad\Rightarrow\quad\cfrac{}{A\ }u Dually, local completeness says that the elimination rules are strong enough to decompose a connective into the forms suitable for its introduction rule.

Again for conjunctions: \cfrac{}{A \wedge B\ }u \quad \Rightarrow \quad \begin{aligned}\cfrac{\cfrac{\cfrac{}{A \wedge B\ }u}{A\ }\wedge_{E1} \qquad \cfrac{\cfrac{}{A \wedge B\ }u}{B\ }\wedge_{E2}}{A \wedge B\ }\wedge_I\end{aligned} These notions correspond exactly to β-reduction (beta reduction) and η-conversion (eta conversion) in the lambda calculus, using the Curry–Howard isomorphism. By local completeness, we see that every derivation can be converted to an equivalent derivation where the principal connective is introduced.

In fact, if the entire derivation obeys this ordering of eliminations followed by introductions, then it is said to be normal. In a normal derivation all eliminations happen above introductions. In most logics, every derivation has an equivalent normal derivation, called a normal form.

The existence of normal forms is generally hard to prove using natural deduction alone, though such accounts do exist in the literature, most notably by Dag Prawitz in 1961. It is much easier to show this indirectly by means of a cut-free sequent calculus presentation.

First and higher-order extensions

The logic of the earlier section is an example of a single-sorted logic, i.e., a logic with a single kind of object: propositions. Many extensions of this simple framework have been proposed; in this section we will extend it with a second sort of individuals or terms. More precisely, we will add a new category, "term", denoted \mathcal{T} .

We shall fix a countable set V of variables, another countable set F of function symbols, and construct terms with the following formation rules: \frac{v\in V}{v : \mathcal{T}} \hbox{ var}_F and \frac{f\in F\qquad t_1 : \mathcal{T}\qquad t_2 : \mathcal{T}\qquad \cdots \qquad t_n : \mathcal{T}}{f(t_1, t_2,\cdots,t_n) : \mathcal{T}} \hbox{ app}_F For propositions, we consider a third countable set P of predicates, and define atomic predicates over terms with the following formation rule: \frac{\phi\in P\qquad t_1 : \mathcal{T}\qquad t_2 : \mathcal{T}\qquad \cdots \qquad t_n : \mathcal{T}}{\phi(t_1, t_2,\cdots,t_n) : \mathcal{F}} \hbox{ pred}_F The first two rules of formation provide a definition of a term that is effectively the same as that defined in term algebra and model theory, although the focus of those fields of study is quite different from natural deduction. The third rule of formation effectively defines an atomic formula, as in first-order logic, and again in model theory.

To these are added a pair of formation rules, defining the notation for quantified propositions; one for universal (∀) and existential (∃) quantification: \frac{x\in V \qquad A : \mathcal{F}}{\forall x.A : \mathcal{F}} \;\forall_F \qquad\qquad \frac{x\in V \qquad A : \mathcal{F}}{\exists x.A : \mathcal{F}} \;\exists_F The universal quantifier has the introduction and elimination rules: \cfrac{ \begin{array}{c} \cfrac{}{a : \mathcal{T}}\text{ u} \\ \vdots \\{}[a/x]A \end{array} }{\forall x.A }\;\forall_{I^{u,a}} \qquad \qquad \frac{\forall x.A \qquad t : \mathcal{T}}{[t/x]A}\;\forall_{E} The existential quantifier has the introduction and elimination rules: \frac{[t/x]A }{\exists x.A}\;\exists_{I} \qquad\qquad \cfrac{ \begin{array}{cc} & \underbrace{\,\cfrac{}{a : \mathcal{T}}\hbox{ u} \quad \cfrac{}{[a/x]A }\hbox{ v}\,}\\ & \vdots \\ \exists x.A \quad & C \\ \end{array} } {C }\exists_{E^{a,u,v}} In these rules, the notation [t/x] A stands for the substitution of t for every (visible) instance of x in A, avoiding capture. As before the superscripts on the name stand for the components that are discharged: the term a cannot occur in the conclusion of ∀I (such terms are known as eigenvariables or parameters), and the hypotheses named u and v in ∃E are localised to the second premise in a hypothetical derivation.

Although the propositional logic of earlier sections was decidable, adding the quantifiers makes the logic undecidable. So far, the quantified extensions are first-order: they distinguish propositions from the kinds of objects quantified over. Higher-order logic takes a different approach and has only a single sort of propositions.

The quantifiers have as the domain of quantification the very same sort of propositions, as reflected in the formation rules: \cfrac{ \begin{matrix} \cfrac{}{p : \mathcal{F}}\hbox{ u} \\ \vdots \\ A: \mathcal{F} \\ \end{matrix}} {\forall p.A : \mathcal{F}} \;\forall_{F^u} \qquad\qquad \cfrac{ \begin{matrix} \cfrac{}{p : \mathcal{F}}\hbox{ u} \\ \vdots \\ A: \mathcal{F} \\ \end{matrix}} {\exists p.A : \mathcal{F}} \;\exists_{F^u} A discussion of the introduction and elimination forms for higher-order logic is beyond the scope of this article. It is possible to be in-between first-order and higher-order logics.

For example, second-order logic has two kinds of propositions, one kind quantifying over terms, and the second kind quantifying over propositions of the first kind.

Proofs and type theory

The presentation of natural deduction so far has concentrated on the nature of propositions without giving a formal definition of a proof. To formalise the notion of proof, we alter the presentation of hypothetical derivations slightly. We label the antecedents with proof variables (from some countable set V of variables), and decorate the succedent with the actual proof.

The antecedents or hypotheses are separated from the succedent by means of a turnstile (⊢). This modification sometimes goes under the name of localised hypotheses. The following diagram summarises the change.

The collection of hypotheses will be written as Γ when their exact composition is not relevant. To make proofs explicit, we move from the proof-less judgment "A" to a judgment: "π is a proof of (A)", which is written symbolically as "π : A". Following the standard approach, proofs are specified with their own formation rules for the judgment "π proof".

The simplest possible proof is the use of a labelled hypothesis; in this case the evidence is the label itself. Let us re-examine some of the connectives with explicit proofs. For conjunction, we look at the introduction rule ∧I to discover the form of proofs of conjunction: they must be a pair of proofs of the two conjuncts.

Thus: The elimination rules ∧E 1 and ∧E 2 select either the left or the right conjunct; thus the proofs are a pair of projections—first (fst) and second (snd). For implication, the introduction form localises or binds the hypothesis, written using a λ; this corresponds to the discharged label.

In the rule, "Γ, u:A" stands for the collection of hypotheses Γ, together with the additional hypothesis u. With proofs available explicitly, one can manipulate and reason about proofs. The key operation on proofs is the substitution of one proof for an assumption used in another proof.

This is commonly known as a substitution theorem, and can be proved by induction on the depth (or structure) of the second judgment.

Example: Dependent Type Theory

Like logic, type theory has many extensions and variants, including first-order and higher-order versions. One branch, known as dependent type theory, is used in a number of computer-assisted proof systems. Dependent type theory allows quantifiers to range over programs themselves.

These quantified types are written as Π and Σ instead of ∀ and ∃, and have the following formation rules: These types are generalisations of the arrow and product types, respectively, as witnessed by their introduction and elimination rules. Dependent type theory in full generality is very powerful: it is able to express almost any conceivable property of programs directly in the types of the program.

This generality comes at a steep price — either typechecking is undecidable (extensional type theory), or extensional reasoning is more difficult (intensional type theory). For this reason, some dependent type theories do not allow quantification over arbitrary programs, but rather restrict to programs of a given decidable index domain, for example integers, strings, or linear programs.

Since dependent type theories allow types to depend on programs, a natural question to ask is whether it is possible for programs to depend on types, or any other combination. There are many kinds of answers to such questions.

A popular approach in type theory is to allow programs to be quantified over types, also known as parametric polymorphism; of this there are two main kinds: if types and programs are kept separate, then one obtains a somewhat more well-behaved system called predicative polymorphism; if the distinction between program and type is blurred, one obtains the type-theoretic analogue of higher-order logic, also known as impredicative polymorphism. Various combinations of dependency and polymorphism have been considered in the literature, the most famous being the lambda cube of Henk Barendregt.

The intersection of logic and type theory is a vast and active research area. New logics are usually formalised in a general type theoretic setting, known as a logical framework. Popular modern logical frameworks such as the calculus of constructions and LF are based on higher-order dependent type theory, with various trade-offs in terms of decidability and expressive power.

These logical frameworks are themselves always specified as natural deduction systems, which is a testament to the versatility of the natural deduction approach.

Classical and modal logics

For simplicity, the first-order and higher-order extensions and the proof terms presented above have been intuitionistic; for propositional logic, the minimal, intuitionistic and classical rule sets were given in . Classical logic extends intuitionistic logic with an additional axiom or principle of excluded middle: For any proposition p, the proposition p ∨ ¬p is true.

This statement is not obviously either an introduction or an elimination; indeed, it involves two distinct connectives. Gentzen's original treatment of excluded middle prescribed one of the following three (equivalent) formulations, which were already present in analogous forms in the systems of Hilbert and Heyting: (XM 3 is merely XM 2 expressed in terms of E.) This treatment of excluded middle, in addition to being objectionable from a purist's standpoint, introduces additional complications in the definition of normal forms.

A comparatively more satisfactory treatment of classical natural deduction in terms of introduction and elimination rules alone was first proposed by Parigot in 1992 in the form of a classical lambda calculus called λμ. The key insight of his approach was to replace a truth-centric judgment A with a more classical notion, reminiscent of the sequent calculus: in localised form, instead of Γ ⊢ A, he used Γ ⊢ Δ, with Δ a collection of propositions similar to Γ. Γ was treated as a conjunction, and Δ as a disjunction.

This structure is essentially lifted directly from classical sequent calculi, but the innovation in λμ was to give a computational meaning to classical natural deduction proofs in terms of a callcc or a throw/catch mechanism seen in LISP and its descendants. (See also: first class control.)

Another important extension was for modal and other logics that need more than just the basic judgment of truth. These were first described, for the alethic modal logics S4 and S5, in a natural deduction style by Prawitz in 1965, and have since accumulated a large body of related work.

To give a simple example, the modal logic S4 requires one new judgment, "A valid", that is categorical with respect to truth: If "A" (is true) under no assumption that "B" (is true), then "A valid". This categorical judgment is internalised as a unary connective ◻A (read "necessarily A") with the following introduction and elimination rules: Note that the premise "A valid" has no defining rules; instead, the categorical definition of validity is used in its place.

This mode becomes clearer in the localised form when the hypotheses are explicit. We write "Ω;Γ ⊢ A" where Γ contains the true hypotheses as before, and Ω contains valid hypotheses.

On the right there is just a single judgment "A"; validity is not needed here since "Ω ⊢ A valid" is by definition the same as "Ω;⋅ ⊢ A". The introduction and elimination forms are then: The modal hypotheses have their own version of the hypothesis rule and substitution theorem.

Comparison with sequent calculus

The sequent calculus is the chief alternative to natural deduction as a foundation of mathematical logic. In natural deduction the flow of information is bi-directional: elimination rules flow information downwards by deconstruction, and introduction rules flow information upwards by assembly.

Thus, a natural deduction proof does not have a purely bottom-up or top-down reading, making it unsuitable for automation in proof search. To address this fact, Gentzen in 1935 proposed his sequent calculus, though he initially intended it as a technical device for clarifying the consistency of predicate logic.

Kleene, in his seminal 1952 book Introduction to Metamathematics, gave the first formulation of the sequent calculus in the modern style. In the sequent calculus all inference rules have a purely bottom-up reading. Inference rules can apply to elements on both sides of the turnstile.

(To differentiate from natural deduction, this article uses a double arrow ⇒ instead of the right tack ⊢ for sequents.) The introduction rules of natural deduction are viewed as right rules in the sequent calculus, and are structurally very similar. The elimination rules on the other hand turn into left rules in the sequent calculus.

To give an example, consider disjunction; the right rules are familiar: On the left: Recall the ∨E rule of natural deduction in localised form: The proposition A ∨ B, which is the succedent of a premise in ∨E, turns into a hypothesis of the conclusion in the left rule ∨L. Thus, left rules can be seen as a sort of inverted elimination rule. This observation can be illustrated as follows: In the sequent calculus, the left and right rules are performed in lock-step until one reaches the initial sequent, which corresponds to the meeting point of elimination and introduction rules in natural deduction.

These initial rules are superficially similar to the hypothesis rule of natural deduction, but in the sequent calculus they describe a transposition or a handshake of a left and a right proposition: The correspondence between the sequent calculus and natural deduction is a pair of soundness and completeness theorems, which are both provable by means of an inductive argument. Soundness of ⇒ wrt. ⊢ : If Γ ⇒ A, then Γ ⊢ A. Completeness of ⇒ wrt. ⊢ : If Γ ⊢ A, then Γ ⇒ A. It is clear by these theorems that the sequent calculus does not change the notion of truth, because the same collection of propositions remain true.

Thus, one can use the same proof objects as before in sequent calculus derivations. As an example, consider the conjunctions. The right rule is virtually identical to the introduction rule The left rule, however, performs some additional substitutions that are not performed in the corresponding elimination rules.

The kinds of proofs generated in the sequent calculus are therefore rather different from those of natural deduction. The sequent calculus produces proofs in what is known as the β-normal η-long form, which corresponds to a canonical representation of the normal form of the natural deduction proof.

If one attempts to describe these proofs using natural deduction itself, one obtains what is called the intercalation calculus (first described by John Byrnes), which can be used to formally define the notion of a normal form for natural deduction. The substitution theorem of natural deduction takes the form of a structural rule or structural theorem known as cut in the sequent calculus.

References

Translated and with appendices by Paul Taylor and Yves Lafont. Reprinted in Polish logic 1920–39, ed. Storrs McCall. Lecture notes to a short course at Università degli Studi di Siena, April 1983.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378912978 under CC BY-SA 4.0; modifications have been made.

Words in each sectionFirst and higher-order …First and higher-order extensionsFirst and higher-order extensions: 644 words644Comparison with sequent…Comparison with sequent calculusComparison with sequent calculus: 544 words544Classical and modal log…Classical and modal logicsClassical and modal logics: 482 words482Gentzen-style propositi…Gentzen-style propositional logicGentzen-style propositional logic: 423 words423Example: Dependent Type…Example: Dependent Type TheoryExample: Dependent Type Theory: 367 words367Consistency, completene…Consistency, completeness, and normal formsConsistency, completeness, and normal forms: 364 words364Proofs and type theoryProofs and type theoryProofs and type theory: 330 words330History of notation sty…History of notation stylesHistory of notation styles: 315 words315Gentzen's tree notationGentzen's tree notationGentzen's tree notation: 274 words274Propositional language …Propositional language syntaxPropositional language syntax: 97 words97NotationNotationNotation: 13 words13
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001378912978 · captured 2026-10-06 · ledger · version history

Cite this page as: encyclopegia.org, “Natural deduction”, snapshot enwiki-001378912978. https://encyclopegia.org/a/natural-deduction

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.