Natural deduction

Natural deduction is a formal proof system whose rules introduce and eliminate logical connectives. Proofs proceed from assumptions to conclusions, with assumptions discharged when appropriate.

Introduction rule: A proof rule that licenses asserting a connective by establishing the conditions it requires. Natural deduction introduces each connective through a rule tailored to its meaning.
Propositional logic: The study of arguments formed from propositions and logical connectives. Natural deduction is commonly presented first as a proof system for propositional logic.
Gerhard Gentzen: A German logician who introduced natural deduction and sequent calculus in the 1930s. Gentzen formulated natural deduction as a system organized around rules for each connective.
Intuitionistic logic: A logic in which proofs, rather than truth in all classical interpretations, ground assertion. Natural deduction gives intuitionistic logic a direct interpretation of connectives through their proof rules.
Elimination rule: A proof rule that derives consequences from a statement containing a connective. Elimination rules specify how to use formulas already established in a derivation.
Conjunction: The logical connective that is true when both of its component propositions are true. Its introduction requires proofs of both conjuncts, while elimination extracts either one.
Dag Prawitz: A Swedish logician whose work established a rigorous proof-theoretic study of natural deduction. Prawitz developed normalization and a systematic theory of natural-deduction proofs.
Curry–Howard correspondence: The correspondence between propositions and types, and between proofs and programs. Natural-deduction derivations translate into typed lambda terms under this correspondence.
Assumption discharge: The cancellation of a temporary assumption when a proof establishes a conclusion conditional on that assumption. Conditional and negation introductions close subproofs by discharging assumptions.
Disjunction: The logical connective that is true when at least one of its component propositions is true. Its rules distinguish proving one alternative from reasoning by cases.

Linked from 33 pages