自然演繹
話を単純化するため、ここまでの説明では直観論理を使ってきた。古典論理は、直観論理に次の公理あるいは排中律を追加して拡張したものと言える。
「任意の命題 p について、命題 p ∨ ¬p は真である」
この文自体は、導入も除去も明確でない。実は、これは2種類の連結子に関係している。ゲンツェンは、排中律を以下の3つの(等価な)定式化のうちの1つとして扱った。これらはヒルベルトと Arend Heyting の論理体系にも類似の形式で提示されていた。
この排中律の扱い方は、純粋主義的観点からは好ましくないのに加えて、正規形の定義においてさらなる複雑さを生む。
導入規則と除去規則だけからなる従来からの自然演繹にとって好ましい対処法は、1992年、Michel Parigot が λμ と呼ばれるラムダ計算の一種として提案した。彼の手法の鍵となった洞察は、真理値を中心とした判断 "A true" を、より古典的な記法に置換したことである。局所的形式では、Γ ⊢ A の代わりに Γ ⊢ Δ とした。この Δ は Γ と同様な命題の集合である。Γ は命題群の論理積であるが、Δ は命題群の論理和である。この構造はシークエント計算から直接持ってきたものだが、λμ での新規な点は、古典的な自然演繹的照明に計算的意味を与えた点であり、それには継続あるいはLISPやその後継で見られる throw/catch が用いられる。
正規化性は複雑な型理論では滅多にない特性であり、その点で論理の世界とは一線を画すことになる(多くの論理において、論理導出には等価な正規な導出があるという事実を思い出していただきたい)。再帰的定義が可能な型理論では、1つの値に還元できないプログラムを書くことが可能である。そのようなプログラムは一般にいかなる型も与えることが可能である。特に、再帰プログラムは型 ⊥ を持つこともあるが、"⊥ true" についての論理的証明は存在しない。以上から、「型としての命題、プログラムとしての証明」というパラダイムは一方向にしか働かない。もし型理論を論理に無理やり変換したとしても、一貫性のない論理しか得られない。
論理と同様、型理論には様々な拡張や変種があり、一階版も高階版もある。型理論の興味深い変種として依存型理論がある。これは、プログラム全体に量化を施せるものである。量化型は ∀ と ∃ の代わりに Π と Σ を使って記述する。構成規則は次のようになる。
これらの型は矢印と積の型の一般化であり、導入規則と除去規則は次のようになる。
普遍的な依存型理論は非常に強力であり、プログラムの想像可能ないかなる属性もプログラムの型で直接表すことができる。ただし、その普遍性と引き換えに、あるプログラムがある型であるかを決定不能となっている。
この形式では、第一の前提は構成規則 ∧ F {\displaystyle \wedge _{F}} に従って得られたものである。以下では判断 "prop" は自明として省略する。なお、真は前提が全くないところからも導かれる。
⊤ true ⊤ I {\displaystyle {\frac {\ }{\top {\hbox{ true}}}}\ \top _{I}}
命題の真理値が決まる過程が1つでない場合、その結合子には複数の推論規則が対応することになる。
A true A ∨ B true ∨ I 1 B true A ∨ B true ∨ I 2 {\displaystyle {\frac {A{\hbox{ true}}}{A\vee B{\hbox{ true}}}}\ \vee _{I1}\qquad {\frac {B{\hbox{ true}}}{A\vee B{\hbox{ true}}}}\ \vee _{I2}}
なお、何の前提もなく偽を導入する導入規則は存在しない。従って、単純な判断から偽であることを推論することはできない。
導入規則と対になる除去規則(elimination rules)がある(削除規則とも)。すなわち、複合型の命題を解体するものである。例えば、"A ∧ B true" から "A true" と "B true" を結論とすることができる。